A Unified Convergence Analysis for Shuffling-Type Gradient Methods

By Lam M. Nguyen, Quoc Tran-Dinh, Dzung T. Phan, Phuong Ha Nguyen, Marten van Dijk. 2020

100 citations recorded by the source corpus.

In this paper, we provide a unified convergence analysis for a class of shuffling-type gradient methods for solving a well-known finite-sum minimization problem commonly used in machine learning. This algorithm covers various variants such as randomized reshuffling, single shuffling, and cyclic/incremental gradient schemes. We consider two different settings: strongly convex and non-convex problems. Our main contribution consists of new non-asymptotic and asymptotic convergence rates for a general class of shuffling-type gradient methods to solve both non-convex and strongly convex problems. While our rate in the non-convex problem is new (i.e. not known yet under standard assumptions), the rate on the strongly convex case matches (up to a constant) the best-known results. However, unlike existing works in this direction, we only use standard assumptions such as smoothness and strong convexity. Finally, we empirically illustrate the effect of learning rates via a non-convex logistic regression and neural network examples.

Subfields: Artificial Intelligence, Computational Mechanics, Optimization & Training

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computational Mechanics

In Optimization & Training

Citations in the corpus

On The Impact of Machine Learning Randomness on Group Fairness (2023, background): “[41] Lam M Nguyen, Quoc Tran-Dinh, Dzung T Phan, Phuong Ha Nguyen, and Marten Van Dijk.”
SGD with shuffling: optimal rates without component convexity and large epoch requirements (2020, methodology): “[13] provide a unified analysis for both RANDOMSHUFFLE and SINGLESHUFFLE, and prove O (1/K(2)) convergence rates for F satisfying the PŁ condition or strong convexity.”
Permutation-Based SGD: Is Random Optimal? (2021, background): “However, a recent line of breakthrough results provides the first tight convergence guarantees for several classes of convex functions F (Nagaraj et al., 2019; Safran & Shamir, 2019; Rajput et al., 2020; Mishchenko et al., 2020; Ahn et al., 2020; Nguyen et al., 2020).”
Random Reshuffling: Simple Analysis with Vast Improvements (2020, methodology): “Our approach for establishing this lemma is similar to that of (Nguyen et al., 2020, Theorem 1), which we became aware of in the course of preparing this manuscript.”
Characterizing & Finding Good Data Orderings for Fast Convergence of Sequential Gradient Methods (2022, background): “Recent theoretical works confirmed this observation, showing that using a random permutation instead of random sampling can lead to faster convergence [17, 20, 22, 24, 33].”