SGD with shuffling: optimal rates without component convexity and large epoch requirements

By Kwangjun Ahn, Chulhee Yun, Suvrit Sra. 2020

77 citations recorded by the source corpus.

We study without-replacement SGD for solving finite-sum optimization problems. Specifically, depending on how the indices of the finite-sum are shuffled, we consider the RandomShuffle (shuffle at the beginning of each epoch) and SingleShuffle (shuffle only once) algorithms. First, we establish minimax optimal convergence rates of these algorithms up to poly-log factors. Notably, our analysis is general enough to cover gradient dominated nonconvex costs, and does not rely on the convexity of individual component functions unlike existing optimal convergence results. Secondly, assuming convexity of the individual components, we further sharpen the tight convergence results for RandomShuffle by removing the drawbacks common to all prior arts: large number of epochs required for the results to hold, and extra poly-log factor gaps to the lower bound.

Subfields: Artificial Intelligence, Computer Networks and Communications, Management Science and Operations Research

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 Computer Networks and Communications

In Management Science and Operations Research

Citations in the corpus

Breaking the Communication-Privacy-Accuracy Trilemma (2020, background): “To mitigate these worst-case scenarios, one can consider without-replacement SGD (SGDo) [55], [56], [57], [58], which ensures each client being sampled exactly T n times, and hence the total privacy loss is reduced to nTε N .”
Random Reshuffling: Simple Analysis with Vast Improvements (2020, background): “In concurrent work, Ahn et al. (2020) obtain in the same setting a complexity of (for a constant α > 2 ), which requires that each f i is Lipschitz and matches the lower bound only when the accuracy ε is large enough that 1 /ε 1 /α ≤ 1 .”
Permutation-Based SGD: Is Random Optimal? (2021, methodology): “1 Proof of Lemma 7 We begin by decomposing the product into product of independent terms, similar to proof of Lemma 8 in (Ahn et al., 2020).”
A Unified Convergence Analysis for Shuffling-Type Gradient Methods (2020, methodology): “(b) If either a general bounded variance condition is imposed on F (see Assumption 2) or each component f(·; i) is convex for all i ∈ [n], then by using a uniformly randomized reshuffling strategy, our convergence rate in the strongly convex case is improved to O(1/(nT 2)), which matches the best-kn”