A Simple Practical Accelerated Method for Finite Sums

2016/02/08 by Aaron Defazio, Defazio, Aaron · 2 citations
Computer Science · Mathematics · #Advanced Optimization Algorithms Research #FOS: Computer and information sciences #Machine Learning (cs.LG) #Machine Learning (stat.ML) #Matrix Theory and Algorithms #Stochastic Gradient Optimization Techniques

paper · pdf · doi:10.48550/arxiv.1602.02442

openalex publication_date 2016/02/08 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

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.

Citations

• Incremental Majorization-Minimization Optimization with Application to Large-Scale Machine Learning
• SAGA: A Fast Incremental Gradient Method With Support for Non-Strongly\n Convex Composite Objectives

Cited by

• Bregman Stochastic Proximal Point Algorithm with Variance Reduction
• The Stochastic Multi-Proximal Method for Nonsmooth Optimization

Related

• Accelerated Stochastic Gradient Descent for Minimizing Finite Sums
• SAGA: A Fast Incremental Gradient Method With Support for Non-Strongly\n Convex Composite Objectives
• SAGA with Arbitrary Sampling
• Limitations on Variance-Reduction and Acceleration Schemes for Finite Sum Optimization
• A Lower Bound for the Optimization of Finite Sums