Semi-Cyclic Stochastic Gradient Descent

2019/04/23 by Eichner, Hubert, Koren, Tomer, McMahan, H. Brendan +2 · 1 citation
#FOS: Computer and information sciences #Machine Learning (cs.LG) #Machine Learning (stat.ML)

paper · doi:10.48550/arxiv.1904.10120

Abstract

We consider convex SGD updates with a block-cyclic structure, i.e. where each cycle consists of a small number of blocks, each with many samples from a possibly different, block-specific, distribution. This situation arises, e.g., in Federated Learning where the mobile devices available for updates at different times during the day have different characteristics. We show that such block-cyclic structure can significantly deteriorate the performance of SGD, but propose a simple approach that allows prediction with the same performance guarantees as for i.i.d., non-cyclic, sampling.

Cited by

• Understanding Outer Optimizers in Local SGD: Learning Rates, Momentum, and Acceleration

Related

• SGD with a Constant Large Learning Rate Can Converge to Local Maxima
• Minibatch vs Local SGD with Shuffling: Tight Convergence Bounds and Beyond
• Empirical Risk Minimization with Shuffled SGD: A Primal-Dual Perspective and Improved Bounds
• Block stochastic gradient iteration for convex and nonconvex optimization
• On the Convergence to a Global Solution of Shuffling-Type Gradient Algorithms