Understand
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.
Built on
Monotone operators and the proximal point algorithm
R Tyrrell Rockafellar · 1976
Earlier work this paper cites.
Introductory Lectures On Convex Programming
Yu. Nesterov · 1998
Earlier work this paper cites.
Libsvm : a library for support vector machines
Chih-Chung Chang and Chih-Jen Lin · 2011
Earlier work this paper cites.
Pegasos: Primal estimated sub-gradient solver for svm
Shai Shalev-Shwartz, Yoram Singer, Nathan Srebro, and Andrew Cotter · 2011
Earlier work this paper cites.
Accelerating stochastic gradient descent using predictive variance reduction
Rie Johnson and Tong Zhang · 2013
Earlier work this paper cites.
Similar
Semi-Stochastic Gradient Descent Methods
Jakub Konečný and Peter Richtárik · 2013
Cited alongside, same era.
Minimizing finite sums with the stochastic average gradient
Mark Schmidt, Nicolas Le Roux, and Francis Bach · 2013
Cited alongside, same era.
Saga: A fast incremental gradient method with support for non-strongly convex composite objectives
Aaron Defazio, Francis Bach, and Simon Lacoste-Julien · 2014
Cited alongside, same era.
Incremental majorization-minimization optimization with application to large-scale machine learning
Julien Mairal · 2014
Cited alongside, same era.
Finito: A faster, permutable incremental gradient method for big data problems
Aaron Defazio, Tiberio Caetano, and Justin Domke
Cited in the paper.
Stochastic dual coordinate ascent methods for regularized loss minimization
Shai Shalev-Shwartz and Tong Zhang
Cited in the paper.
Accelerated mini-batch stochastic dual coordinate ascent
Shai Shalev-Shwartz and Tong Zhang
Cited in the paper.
Accelerated proximal stochastic dual coordinate ascent for regularized loss minimization
Shai Shalev-Shwartz and Tong Zhang
Cited in the paper.
Then
Stochastic proximal gradient descent with acceleration techniques
Atsushi Nitanda · 2014
Later among the works it cites.
Variance reduced stochastic gradient descent with neighbors
Thomas Hofmann, Aurelien Lucchi, Simon Lacoste-Julien, and Brian McWilliams · 2015
Later among the works it cites.
An optimal randomized incremental gradient method
G. Lan and Y. Zhou · 2015
Later among the works it cites.
A universal catalyst for first-order optimization
Hongzhou Lin, Julien Mairal, and Zaid Harchaoui · 2015
Later among the works it cites.
Beyond the bibliography
alphaXiv searches the wider corpus for related work and actual follow-ups.
alphaXiv is searching for related work…