Minibatch vs Local SGD with Shuffling: Tight Convergence Bounds and Beyond

Abstract

In distributed learning, local SGD (also known as federated averaging) and its simple baseline minibatch SGD are widely studied optimization methods. Most existing analyses of these methods assume independent and unbiased gradient estimates obtained via with-replacement sampling. In contrast, we study shuffling-based variants: minibatch and local Random Reshuffling, which draw stochastic gradients without replacement and are thus closer to practice. For smooth functions satisfying the Polyak-Łojasiewicz condition, we obtain convergence bounds (in the large epoch regime) which show that these shuffling-based variants converge faster than their with-replacement counterparts. Moreover, we prove matching lower bounds showing that our convergence analysis is tight. Finally, we propose an algorithmic modification called synchronized shuffling that leads to convergence rates faster than our lower bounds in near-homogeneous settings.

arXiv commentICLR 2022 camera-ready (selected for an oral presentation); 76 pages, 3 figures

References in corpus (16)

• Communication-Efficient Learning of Deep Networks from Decentralized Data
• Federated Learning: Strategies for Improving Communication Efficiency
• Speeding Up Distributed Machine Learning Using Codes
• Making Gradient Descent Optimal for Strongly Convex Stochastic Optimization
• On the Convergence of Local Descent Methods in Federated Learning
• A Unified Theory of Decentralized SGD with Changing Topology and Local Updates
• Local SGD with Periodic Averaging: Tighter Analysis and Adaptive Synchronization
• Why Random Reshuffling Beats Stochastic Gradient Descent
• Random Reshuffling: Simple Analysis with Vast Improvements
• A Unified Convergence Analysis for Shuffling-Type Gradient Methods
• Local SGD With a Communication Overhead Depending Only on the Number of Workers
• The Min-Max Complexity of Distributed Stochastic Convex Optimization with Intermittent Communication
• Closing the convergence gap of SGD without replacement
• Proximal and Federated Random Reshuffling
• Random Shuffling Beats SGD Only After Many Epochs on Ill-Conditioned Problems
• Permutation-Based SGD: Is Random Optimal?