Communication trade-offs for synchronized distributed SGD with large step size

2019/04/25 by Kumar Kshitij Patel, Aymeric Dieuleveut, Patel, Kumar Kshitij +1
Computer Science · Engineering · #FOS: Computer and information sciences #FOS: Mathematics #Ferroelectric and Negative Capacitance Devices #Machine Learning (cs.LG) #Machine Learning (stat.ML) #Optimization and Control (math.OC) #Privacy-Preserving Technologies in Data #Stochastic Gradient Optimization Techniques

paper · pdf · doi:10.48550/arxiv.1904.11325

openalex publication_date 2019/04/25 · openalex created_date 2019/05/03 · openalex updated_date 2026/07/28

Abstract

Synchronous mini-batch SGD is state-of-the-art for large-scale distributed machine learning. However, in practice, its convergence is bottlenecked by slow communication rounds between worker nodes. A natural solution to reduce communication is to use the `local-SGD' model in which the workers train their model independently and synchronize every once in a while. This algorithm improves the computation-communication trade-off but its convergence is not understood very well. We propose a non-asymptotic error analysis, which enables comparison to one-shot averaging i.e., a single communication round among independent workers, and mini-batch averaging i.e., communicating at every step. We also provide adaptive lower bounds on the communication frequency for large step-sizes ( t^-α , α∈ (1/2 , 1 ) ) and show that Local-SGD reduces communication by a factor of O(\frac√(T)P^3/2), with T the total number of gradients and P machines.

Citations

• Stochastic Gradient Descent for Non-smooth Optimization: Convergence\n Results and Optimal Averaging Schemes
• Deep learning with Elastic Averaging SGD
• Asynchronous stochastic convex optimization
• Non-strongly-convex smooth stochastic approximation with convergence rate O(1/n)
• Distributed Stochastic Variance Reduced Gradient Methods and A Lower Bound for Communication Complexity
• Parallel SGD: When does averaging help?
• AIDE: Fast and Communication Efficient Distributed Optimization
• Federated Learning: Strategies for Improving Communication Efficiency
• CoCoA: A General Framework for Communication-Efficient Distributed Optimization
• Optimal algorithms for smooth and strongly convex distributed optimization in networks
• TernGrad: Ternary Gradients to Reduce Communication in Distributed Deep Learning
• Accurate, Large Minibatch SGD: Training ImageNet in 1 Hour
• Bridging the Gap between Constant Step Size Stochastic Gradient Descent and Markov Chains
• Improved asynchronous parallel optimization analysis for stochastic incremental methods
• A Stochastic Large-scale Machine Learning Algorithm for Distributed Features and Observations
• Distributed learning with compressed gradients
• HOGWILD!: A Lock-Free Approach to Parallelizing Stochastic Gradient Descent

Related

• Communication-efficient SGD: From Local SGD to One-Shot Averaging
• Adaptive Communication Strategies to Achieve the Best Error-Runtime Trade-off in Local-Update SGD
• Local SGD Converges Fast and Communicates Little
• Asynchronous Decentralized SGD with Quantized and Local Updates
• Parallel Restarted SGD with Faster Convergence and Less Communication: Demystifying Why Model Averaging Works for Deep Learning