A Simple Practical Accelerated Method for Finite Sums

Abstract

We describe a novel optimization method for finite sums (such as empirical risk minimization problems) building on the recently introduced SAGA method. Our method achieves an accelerated convergence rate on strongly convex smooth problems. Our method has only one parameter (a step size), and is radically simpler than other accelerated methods for finite sums. Additionally it can be applied when the terms are non-smooth, yielding a method applicable in many areas where operator splitting methods would traditionally be applied.

References in corpus (3)

• SAGA: A Fast Incremental Gradient Method With Support for Non-Strongly Convex Composite Objectives
• Finito: A Faster, Permutable Incremental Gradient Method for Big Data Problems
• Variance Reduced Stochastic Gradient Descent with Neighbors

Cited by in corpus (19)

• Federated Optimization: Distributed Machine Learning for On-Device Intelligence
• Variance-Reduced Decentralized Stochastic Optimization with Accelerated Convergence
• Anderson Accelerated Douglas-Rachford Splitting
• Stochastic Recursive Gradient Descent Ascent for Stochastic Nonconvex-Strongly-Concave Minimax Problems
• The Practicality of Stochastic Optimization in Imaging Inverse Problems
• Stochastic, Distributed and Federated Optimization for Machine Learning
• On the Ineffectiveness of Variance Reduced Optimization for Deep Learning
• Lower Complexity Bounds of Finite-Sum Optimization Problems: The Results and Construction
• An introduction to decentralized stochastic optimization with gradient tracking
• GENO -- GENeric Optimization for Classical Machine Learning
• A Stochastic Proximal Point Algorithm for Saddle-Point Problems
• Variance-Reduced Decentralized Stochastic Optimization with Gradient Tracking--Part I: GT-SAGA
• On the fast convergence of minibatch heavy ball momentum
• On Biased Stochastic Gradient Estimation
• A Stochastic Decoupling Method for Minimizing the Sum of Smooth and Non-Smooth Functions
• Globally Convergent Newton Methods for Ill-conditioned Generalized Self-concordant Losses
• Katyusha Acceleration for Convex Finite-Sum Compositional Optimization
• AI-SARAH: Adaptive and Implicit Stochastic Recursive Gradient Methods
• Boosting First-Order Methods by Shifting Objective: New Schemes with Faster Worst-Case Rates