On the convergence properties of a K-step averaging stochastic gradient descent algorithm for nonconvex optimization

By Fan Zhou, Guojing Cong. 2017

249 citations recorded by the source corpus.

We adopt and analyze a synchronous K-step averaging stochastic gradient descent algorithm which we call K-AVG for solving large scale machine learning problems. We establish the convergence results of K-AVG for nonconvex objectives. Our analysis of K-AVG applies to many existing variants of synchronous SGD. We explain why the K-step delay is necessary and leads to better performance than traditional parallel stochastic gradient descent which is equivalent to K-AVG with $K=1$. We also show that K-AVG scales better with the number of learners than asynchronous stochastic gradient descent (ASGD). Another advantage of K-AVG over ASGD is that it allows larger stepsizes and facilitates faster convergence. On a cluster of $128$ GPUs, K-AVG is faster than ASGD implementations and achieves better accuracies and faster convergence for training with the CIFAR-10 dataset.

Subfields: Optimization & Training

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Optimization & Training

Citations in the corpus

Federated Optimization in Heterogeneous Networks (2018, background): “with data being non-identically distributed between devices. Several works have made steps towards analyzing FedAvg in simpler, non-federated settings. For instance, parallel SGD and related variants [39, 27, 24, 42, 30, 33, 35, 21], which make local updates similar to FedAvg, have been studied in t”
Tackling the Objective Inconsistency Problem in Heterogeneous Federated Optimization (2020, background): “[8–10] ﬁrst analyze FedAvg by assuming the local objectives are identical and show that FedAvg is guaranteed to converge to a stationary point of F ( x ) .”
A Unified Theory of Decentralized SGD with Changing Topology and Local Updates (2020, methodology): “A special algorithm of this type is • local SGD (Coppola, 2015; Zhou & Cong, 2018; Stich, 2019b) where averaging on the complete graph is performed every τ iterations and only local steps are performed otherwise (mixing matrix I n for τ − 1 steps).”
Personalized Federated Learning: A Meta-Learning Approach (2020, background): “Several work develop algorithms for the homogeneous setting, where the data points of all users are sampled from the same probability distribution [14, 15, 16, 17].”
Local SGD with Periodic Averaging: Tighter Analysis and Adaptive Synchronization (2019, methodology): “This motivates us to study the following key question: Can we reduce the number of communication rounds even more, and yet achieve linear speedup? In this paper, we give an affirmative answer to this question by providing a tighter analysis of local SGD via model averaging [43, 38, 51, 23, 45, 49].”
Communication Efficient Decentralized Training with Multiple Local Updates (2019, background): “When data are not identically distributed (i.e., κ is strictly positive), both Yu et al. [49] and Zhou and Cong [56] show that the residual error grows quadratically in I .”
SlowMo: Improving Communication-Efficient Distributed SGD with Slow Momentum (2019, background): “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).”
On the Linear Speedup Analysis of Communication Efficient Momentum SGD for Distributed Non-Convex Optimization (2019, background): “We run both Algorithm 1 and the model averaging with Polyak’s momentum SGD suggested in (Seide & Agarwal, 2016; Wang & Joshi, 2018b), referred as “model averaging with cleared momentum” to train ResNet56 over CIFAR10.”
Don't Use Large Mini-Batches, Use Local SGD (2018, background): “[13] show a rate O ( (KTBloc) −1/2) which only coincides in the extreme case H = 1 with the rate of mini-batch SGD.”
Cooperative SGD: A unified Framework for the Design and Analysis of Communication-Efficient SGD Algorithms (2018, background): “Although extensive empirical results have validated the effectiveness of periodic averaging, rigorous theoretical understanding of how its convergence depends on the number of local updates τ is quite limited (Zhou & Cong, 2017; Yu et al., 2018; Stich, 2018).”
Parallel Restarted SGD with Faster Convergence and Less Communication: Demystifying Why Model Averaging Works for Deep Learning (2018, methodology): “The method in (Zinkevich et al. 2010) (McDonald, Hall, and Mann 2010), referred to as one-shot averaging, uses only one single communication step at the end and is numerically shown to have good solution quality in many applications.”
Local SGD Converges Fast and Communicates Little (2018, background): “Indeed, very recent work [44, 51] analyzes local SGD for non-convex optimization problems and shows convergence of SGD to a stationary point, though the restrictions on H are stronger than here.”
FedDANE: A Federated Newton-Type Method (2019, methodology): “Several primal methods [e.g., 9, 10, 13, 14, 17, 18], including DANE [10] and inexact DANE [9], have also been proposed, and have the added beneﬁt of being applicable to non-convex objectives.”
Federated Learning: Challenges, Methods, and Future Directions (2019, methodology): “work, methods such as FedAvg have been shown to diverge in practice [65, 75]. Parallel SGD and related variants, which make local updates similar to FedAvg, have been 9 analyzed in the I.I.D. setting [68, 93, 104, 108, 120, 121, 122, 125, 136, 140]. However, the results rely on the premise that each”
Adaptive Communication Strategies to Achieve the Best Error-Runtime Trade-off in Local-Update SGD (2018, methodology): “The convergence analysis is conducted under the following assumptions, which are similar to the assumptions made in previous work on the analysis of PASGD (Zhou & Cong, 2017; Yu et al., 2018; Wang & Joshi, 2018; Stich, 2018).”