2020

A Unified Convergence Analysis for Shuffling-Type Gradient Methods

Nguyen, Lam M., Tran-Dinh, Quoc, Phan, Dzung T. et al.

Understand

In this paper, we propose a unified convergence analysis for a class of generic shuffling-type gradient methods for solving finite-sum optimization problems.

Our analysis works with any sampling without replacement strategy and covers many known variants such as randomized reshuffling, deterministic or randomized single permutation, and cyclic and incremental gradient schemes.
We focus on two different settings: strongly convex and nonconvex problems, but also discuss the non-strongly convex case.
Our main contribution consists of new non-asymptotic and asymptotic convergence rates for a wide class of shuffling-type gradient methods in both nonconvex and convex settings.

Built on

A Stochastic Approximation Method
H. Robbins and S. Monro · 1951
Earlier work this paper cites.
Some Methods of Speeding Up the Convergence of Iteration Methods
Boris T. Polyak · 1964
Earlier work this paper cites.
Acceleration of Stochastic Approximation by Averaging
B. Polyak and A. Juditsky · 1992
Earlier work this paper cites.
Gradient-Based Learning Applied to Document Recognition
Y. LeCun, L. Bottou, Y. Bengio, and P. Haffner · 1998
Earlier work this paper cites.
Convergence Rate of Incremental Subgradient Algorithms
A. Nedić and D. Bertsekas · 2001
Earlier work this paper cites.
Incremental Subgradient Methods for Nondifferentiable Optimization
A. Nedic and D. P. Bertsekas · 2001
Earlier work this paper cites.
Introductory Lectures on Convex Optimization: A Basic Course , volume 87 of Applied Optimization
Y. Nesterov · 2004
Earlier work this paper cites.
Cubic Regularization of Newton Method and Its Global Performance
Y. Nesterov and B. T. Polyak · 2006
Earlier work this paper cites.
Curiously Fast Convergence of Some Stochastic Gradient Descent Algorithms
L. Bottou · 2009
Earlier work this paper cites.
Learning Multiple Layers of Features from Tiny Images
A. Krizhevsky and G. Hinton · 2009
Earlier work this paper cites.
Robust Stochastic Approximation Approach to Stochastic Programming
A. Nemirovski, A. Juditsky, G. Lan, and A. Shapiro · 2009
Earlier work this paper cites.
LIBSVM: A Library for Support Vector Machines
C.-C. Chang and C.-J. Lin · 2011
Earlier work this paper cites.
Adaptive Subgradient Methods for Online Learning and Stochastic Optimization
J. Duchi, E. Hazan, and Y. Singer · 2011
Earlier work this paper cites.
Stochastic Gradient Descent Tricks
L. Bottou · 2012
Earlier work this paper cites.

Similar

A Stochastic Gradient Method with an Exponential Convergence Rate for Finite Training Sets
N. Le Roux, M. Schmidt, and F. Bach · 2012
Cited alongside, same era.
Optimization for Machine Learning
S. Sra, S. Nowozin, and S. J. Wright · 2012
Cited alongside, same era.
Stochastic First-and Zeroth-Order Methods for Nonconvex Stochastic Programming
S. Ghadimi and G. Lan · 2013
Cited alongside, same era.
Accelerating Stochastic Gradient Descent Using Predictive Variance Reduction
R. Johnson and T. Zhang · 2013
Cited alongside, same era.
Incremental Gradient, Subgradient, and Proximal Methods for Convex Optimization: A Survey, 2015
D. P. Bertsekas · 2015
Cited alongside, same era.
ADAM: A Method for Stochastic Optimization
D. P. Kingma and J. Ba · 2015
Cited alongside, same era.
Linear Convergence of Gradient and Proximal-Gradient Methods under the Polyak-Łojasiewicz Condition
H. Karimi, J. Nutini, and M. Schmidt · 2016
Cited alongside, same era.
Stochastic Variance Reduction for Nonconvex Optimization
S. J. Reddi, A. Hefny, S. Sra, B. Póczos, and A. J. Smola · 2016
Cited alongside, same era.
Without-Replacement Sampling for Stochastic Gradient Methods
O. Shamir · 2016
Cited alongside, same era.
SARAH: A Novel Method for Machine Learning Problems Using Stochastic Recursive Gradient
L. M. Nguyen, J. Liu, K. Scheinberg, and M. Takáč · 2017
Cited alongside, same era.
Optimization Methods for Large-Scale Machine Learning
L. Bottou, F. E. Curtis, and J. Nocedal · 2018
Cited alongside, same era.
SGDLibrary: A MATLAB Library for Stochastic Optimization Algorithms
K. Hiroyuki · 2018
Cited alongside, same era.

Then

Convergence Rate of Incremental Gradient and Newton Methods
M. Gürbüzbalaban, A. Ozdaglar, and P. Parrilo · 2019
Later among the works it cites.
Random Shuffling Beats SGD After Finite Epochs
J. Z. HaoChen and S. Sra · 2019
Later among the works it cites.
Convergence Analysis of Distributed Stochastic Gradient Descent with Shuffling
Q. Meng, W. Chen, Y. Wang, Z.-M. Ma, and T.-Y. Liu · 2019
Later among the works it cites.
SGD without Replacement: Sharper Rates for General Smooth Convex Functions
D. Nagaraj, P. Jain, and P. Netrapalli · 2019
Later among the works it cites.
SGD with Shuffling: Optimal Rates without Component Convexity and Large Epoch Requirements
K. Ahn, C. Yun, and S. Sra · 2020
Closest in time.
Incremental Methods for Weakly Convex Optimization
X. Li, Z. Zhu, A. So, and J. D. Lee · 2020
Closest in time.
Random Reshuffling: Simple Analysis with Vast Improvements
K. Mishchenko, A. Khaled Ragab Bayoumi, and P. Richtárik · 2020
Closest in time.
ProxSARAH: An Efficient Algorithmic Framework for Stochastic Composite Nonconvex Optimization
N. H. Pham, L. M. Nguyen, D. T. Phan, and Q. Tran-Dinh · 2020
Closest in time.
Closing the Convergence Gap of SGD Without Replacement
S. Rajput, A. Gupta, and D. Papailiopoulos · 2020
Closest in time.
How Good is SGD with Random Shuffling?
I. Safran and O. Shamir · 2020
Closest in time.
Variance-Reduced Stochastic Learning Under Random Reshuffling
B. Ying, K. Yuan, and A. H. Sayed · 2020
Closest in time.
Why Random Reshuffling Beats Stochastic Gradient Descent?
M. Gürbüzbalaban, A. Ozdaglar, and P. Parrilo · 2021
Closest in time.
A Hybrid Stochastic Optimization Framework for Stochastic Composite Nonconvex Optimization
Q. Tran-Dinh, N. H. Pham, D. T. Phan, and L. M. Nguyen · 2021
Closest in time.

Beyond the bibliography

alphaXiv searches the wider corpus for related work and actual follow-ups.

Open on alphaXiv

alphaXiv is searching for related work…

Reading the bibliography…