On the Linear Speedup Analysis of Communication Efficient Momentum SGD for Distributed Non-Convex Optimization

By Hao Yu, Rong Jin, Sen Yang. 2019

440 citations recorded by the source corpus.

Recent developments on large-scale distributed machine learning applications, e.g., deep neural networks, benefit enormously from the advances in distributed non-convex optimization techniques, e.g., distributed Stochastic Gradient Descent (SGD). A series of recent works study the linear speedup property of distributed SGD variants with reduced communication. The linear speedup property enable us to scale out the computing capability by adding more computing nodes into our system. The reduced communication complexity is desirable since communication overhead is often the performance bottleneck in distributed systems. Recently, momentum methods are more and more widely adopted in training machine learning models and can often converge faster and generalize better. For example, many practitioners use distributed SGD with momentum to train deep neural networks with big data. However, it remains unclear whether any distributed momentum SGD possesses the same linear speedup property as distributed SGD and has reduced communication complexity. This paper fills the gap by considering a distributed communication efficient momentum SGD method and proving its linear speedup property.

Subfields: Artificial Intelligence, Computer Vision and Pattern Recognition, Optimization & Training, Federated & Distributed Learning

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 Vision and Pattern Recognition

In Optimization & Training

In Federated & Distributed Learning

Citations in the corpus

Advances and Open Problems in Federated Learning (2019, background): “[429] proposed to let each client maintain a local momentum buffer and average these local buffers as well as local model parameters at each communication round.”
Federated Optimization in Heterogeneous Networks (2018, background): “Although some recent works (Yu et al., 2018; Wang et al., 2019; Hao et al., 2019; Jiang & Agrawal, 2018) have explored convergence guarantees in statistically heterogeneous settings, they make the limiting assumption that all devices participate in each round of communication, which is often infeasi”
Tackling the Objective Inconsistency Problem in Heterogeneous Federated Optimization (2020, methodology): “This analysis was further expanded to the non-IID data partition and client sampling cases by [11–18, 23, 24].”
Personalized Federated Learning with Moreau Envelopes (2020, background): “While Assumption 1 is standard for convergence analysis, Assumptions 2 and 3 are widely used in FL context in which γ(2) f and σ 2 f quantify the sampling noise and the diversity of client’s data distribution, respectively [3, 8, 42, 43].”
Local AdaAlter: Communication-Efficient Stochastic Gradient Descent with Adaptive Learning Rates (2019, methodology): “, less frequent synchronization, and periodically averaging the models across the workers (Stich, 2018; Lin et al., 2018; Yu et al., 2018; Wang and Joshi, 2018; Yu et al., 2019).”
Secure Federated Submodel Learning (2019, positive): “Their followup work [33] further presented a momentum extension of parallel restarted SGD, which is compatible with federated learning.”
Communication Efficient Decentralized Training with Multiple Local Updates (2019, methodology): “3 The similar dependence also established for centralized momentum SGD in [48].”
SlowMo: Improving Communication-Efficient Distributed SGD with Slow Momentum (2019, methodology): “Approaches such as Local SGD reduce the frequency of communication by having workers perform multiple updates between each round of communication (McDonald et al., 2010; McMahan et al., 2017; Zhou & Cong, 2018; Stich, 2019; Yu et al., 2019b).”
First Analysis of Local GD on Heterogeneous Data (2019, background): “For this reason, almost all prior work assumed bounded dissimilarity [8, 16, 17, 18] and addressed other less challenging aspects of federated learning such as decentralized communication, nonconvexity of the objective or unbalanced data partitioning.”
Qsparse-Local-SGD: Distributed SGD With Quantization, Sparsification, and Local Computations (2019, methodology): “Our numerics also incorporate momentum acceleration, whose analysis is a topic for future research, for example incorporating ideas from [42].”
Federated Learning: Challenges, Methods, and Future Directions (2019, background): “Theoretically, while several recent works have investigated convergence guarantees of variants of federated learning methods [56, 123, 131, 132], few analyses allow for low participation [e.”
Tighter Theory for Local SGD on Identical and Heterogeneous Data (2019, methodology): “We note that in recent work more sophisticated local stochastic gradient methods have been considered, for example with momentum (Yu et al., 2019a; Wang et al., 2019), with quantization (Reisizadeh et al., 2019; Basu et al., 2019), with adaptive stepsizes (Xie et al., 2019) and with various…”
On the Convergence of Local Descent Methods in Federated Learning (2019, methodology): “Also, [35] provides the convergence of local SGD with momentum for non-i.”
Variance Reduced Local SGD with Lower Communication Complexity (2019, methodology): “Beneﬁting from an additional variance reduction component, VRL-SGD eliminates the extra assumption about bounded gradient variance among workers in previous studies based on Local SGD [Yu et al., 2019a,b, Shen et al., 2019].”
Byzantine-Resilient High-Dimensional SGD with Local Iterations on Heterogeneous Data (2020, neutral): “In Assumption 2, κ quantiﬁes the bounded deviation between the local loss functions F r , r ∈ [ R ] and the global loss function F ; see also [YJY19,LYWZ19], where this assumption has been used in heterogeneous data settings in decentralized SGD without Byzantine clients.”
Q-GADMM: Quantized Group ADMM for Communication Efficient Decentralized Machine Learning (2019, positive): “Lastly, to reduce the number of communication rounds, convergence speed can be accelerated via collaboratively adjusting the training momentum [21], [22].”
Hierarchical Federated Learning ACROSS Heterogeneous Cellular Networks (2019, methodology): “We believe that using an additional global momentum term [14] or utilizing momentum averaging strategy [29] accuracy of the HFL can be improved further.”
An Improved Analysis of Stochastic Gradient Descent with Momentum (2020, methodology): “Very recently, [26] presents a convergence bound of O( 1 kα + α 1−β ) for general smooth nonconvex objectives 3.”