Source-linked AI summary
On the convergence properties of a $K$-step averaging stochastic gradient descent algorithm for nonconvex optimization
Fan Zhou, Guojing Cong
TL;DR
ASGD can be impractical because its convergence guarantees typically require small stepsizes and its staleness and parameter-server communication are difficult to control at scale. The paper analyzes synchronous K-AVG for nonconvex objectives, showing that it can scale better than ASGD, use larger stepsizes while retaining convergence, and outperform ASGD implementations in accuracy and speed.
Problem
ASGD’s practical performance is limited by small theoretically justified stepsizes, difficult-to-control staleness, and parameter-server bottlenecks on many-GPU platforms.
Method
The paper analyzes a synchronous K-step averaging SGD algorithm, K-AVG, establishing its convergence behavior for nonconvex objectives under fixed and diminishing stepsizes.
Results
K-AVG scales better than ASGD, supports larger stepsizes while still guaranteeing convergence, and achieves better accuracy and faster convergence than ASGD implementations.
Takeaways & Limitations
K-AVG’s averaging delay need not be one; choosing K appropriately can support large-scale distributed training while balancing communication time and iteration increases.
Takeaways & Limitations
The optimal delay Kopt remains unknown, so selecting the best averaging interval is not fully resolved.
Abstract
from arXiv · showhide
Despite their popularity, the practical performance of asynchronous stochastic gradient descent methods (ASGD) for solving large scale machine learning problems are not as good as theoretical results indicate. We adopt and analyze a synchronous K-step averaging stochastic gradient descent algorithm which we call K-AVG. We establish the convergence results of K-AVG for nonconvex objectives and explain why the K-step delay is necessary and leads to better performance than traditional parallel stochastic gradient descent which is a special case of K-AVG with $K=1$. We also show that K-AVG scales better than ASGD. Another advantage of K-AVG over ASGD is that it allows larger stepsizes. On a cluster of $128$ GPUs, K-AVG is faster than ASGD implementations and achieves better accuracies and faster convergence for \cifar dataset.
1 Introduction
The paper addresses practical limitations of ASGD by analyzing synchronous K-AVG for nonconvex optimization. It shows that K-AVG can scale better, use larger stepsizes, and achieve stronger empirical performance than ASGD implementations.
- Motivation: ASGD convergence analyses often require stepsizes that are too small for practical use, while stale updates are difficult to control and parameter-server communication can bottleneck many-GPU platforms.These issues include dependence on learner speeds and network positions, aggregation limits, shard inconsistencies, and CPU–GPU communication costs.
- Method: K-AVG is a distributed bulk-synchronous SGD method in which learners periodically average parameter copies through global reduction after K local steps.The communication interval K amortizes communication over samples processed within each interval and avoids reliance on a parameter server.
- Analysis: For nonconvex objectives, the paper studies K-AVG’s convergence, processor-count dependence, stepsize choices, and the effect of the averaging delay K.The analysis applies across synchronous SGD variants, with K = 1 corresponding to hard-sync SGD.
- Analysis: The paper argues that the optimal delay Kopt is often not 1 and can be large, allowing practitioners to balance communication time against additional iterations.The authors note that the proper choice of Kopt remains unknown, so the analysis provides guidance rather than a universally fixed value.
2 Preliminaries and notations
The paper formulates smooth, generally nonconvex stochastic optimization under standard assumptions and establishes notation for processors, delay, mini-batches, and random samples.
- Notation: P denotes the number of processors, K the delay length, B the mini-batch size, and ξ denotes independent random-variable realizations across processors and iterations.The notation indexes update, local-step, and processor-related realizations.
- Optimization setting: The objective F is continuously differentiable with a Lipschitz-continuous gradient and need not be convex.The optimization domain is a nonempty open subset, and the analysis covers expected or empirical risk formulations.
- Assumptions: The iterates remain in a region where the objective is bounded below by F*, ensuring the optimization problem is well defined.This is stated as the second assumption used by the analysis.
- Assumptions: The stochastic gradient is assumed to be an unbiased estimator of the true gradient for each fixed parameter.The paper notes that a weaker First Limit Assumption could replace unbiasedness, but adopts unbiasedness for simplicity.
- Assumptions: The analysis also uses an assumption characterizing the variance, or second-order moments, of stochastic gradients.All convergence results rely on the four assumptions introduced in the preliminaries.
3 Main results
K-AVG is a synchronous stochastic-gradient method that performs K local updates before synchronization, generalizing parallel SGD and supporting nonconvex convergence analysis. The results show that less frequent averaging can improve convergence-related bounds, scalability, and allowable stepsizes under stated conditions.
- Algorithm and relation to parallel SGD: K-AVG performs K individual updates before synchronization, with traditional parallel SGD corresponding to K = 1.This makes K-AVG a more general synchronous algorithm containing parallel SGD.
- Algorithm and relation to parallel SGD: More frequent synchronization does not always result in faster convergence for nonconvex optimization.The analysis and experiments report that the optimal averaging frequency is not always K = 1.
- Convergence guarantees: Under fixed stepsize and batch-size conditions, K-AVG’s expected average squared gradient norms are bounded and converge to a nonzero constant.The theorem assumes a fixed stepsize, fixed batch size, and stated conditions involving L, γ̄, K, and δ.
- Convergence guarantees: K-AVG eventually achieves a convergence rate similar to classical SGD, with the bound ordered as O((N * B * P)^-1/2) after N updates.K-AVG processes N * K * B * P samples after N updates, while the classical SGD rate is N^-1/2 after N samples.
- Convergence guarantees: With diminishing stepsizes and growing batch sizes, K-AVG’s expected average squared gradient norms converge to zero for nonconvex optimization.Theorem 3.2 establishes this result for a diminishing stepsize sequence and growing batch sizes satisfying the stated condition.
- Scalability and stepsizes: K-AVG scales better with P than ASGD and can allow larger stepsizes, while larger stepsizes can cause divergence in popular ASGD implementations.The analysis attributes scaling to a 1/P factor and reports experimentally that larger stepsizes work well in K-AVG but may diverge in ASGD.
4 Experiments
Experiments compare K-AVG with ASGD implementations and sequential SGD on CIFAR-10 using vgg and nin across up to 128 learners. K-AVG generally maintains better accuracy, scales faster, and shows that the best averaging delay depends on learner count and model.
- Comparison with ASGD: K-AVG’s convergence bound is not substantially affected by scaling, whereas ASGD’s bound increases linearly with P.The experiments therefore examine convergence and scalability as the learner count grows.
- Comparison with ASGD: At P = 128, Downpour and EAMSGD degrade to around 10% test accuracy, while ASGD implementations do not converge with γ0 = 1.With γ0 = 0.1, Downpour reaches around 80% for vgg and 87% for nin, whereas EAMSGD still does not converge.
- Comparison with ASGD: At P = 128, K-AVG’s speedups are around 2.5× over Downpour and 2.6× over EAMSGD for vgg, with similar behavior for nin.ASGD implementations are slightly faster at P = 8, but K-AVG’s speedup increases as P grows.
- The optimal delay in averaging for K-AVG: The optimal K is not always 1: for vgg, Kopt ranges from 32 at P = 8 to 2 at P = 64, generally decreasing as P increases.Small P is more forgiving, whereas overly large K can severely reduce accuracy at larger P; for P = 128, Kopt = 4.
- The optimal delay in averaging for K-AVG: For nin, almost all experiments have Kopt = 1, except P = 8, where K = 8 is 0.27% more accurate than K = 1.The differing Kopt behavior may reflect differences in the Lipschitz constant L because the same hyperparameters were used.
- Convergence comparison with SGD: Compared with sequential SGD, K-AVG is slightly worse for vgg but better for nin at 8 and 16 learners, comparable at 32, and less accurate at 64 and 128.Accuracy degradation reaches up to 8.8% for vgg but remains within 1.3% for nin at 128 learners.
- Convergence comparison with SGD: At 128 learners, K-AVG achieves approximately half of the reported 56.3× and 58.3× computational speedups because it runs twice as many epochs as SGD.The paper states that linear speedup is achieved; epoch-time speedups are also reported for 8–128 learners.
5 Conclusion
The paper analyzes synchronous K-AVG for nonconvex large-scale machine learning and establishes convergence under fixed and diminishing stepsizes. It reports better scaling than ASGD, larger allowable stepsizes, and a delay length that need not be one, while noting that the optimal K remains unknown.
- K-AVG is analyzed for large-scale machine learning with nonconvex objectives.
- K-AVG achieves a convergence rate similar to its sequential counterpart with a properly chosen stepsize sequence.
- With properly chosen K when P is large, K-AVG scales better than ASGD.
- K-AVG allows larger stepsizes that still guarantee convergence, whereas ASGD may fail to converge.
- The delay length for averaging parallel learners need not be 1, although the proper choice of Kopt remains unknown.
- The analysis explains how Kopt depends on other parameters to guide practical implementations.
6 Proofs
The proofs analyze one global K-AVG update by taking expectations over independent learner and stochastic-gradient variables under stated assumptions. They derive bounds for variable and constant stepsizes or batch sizes, then use stepsize restrictions to establish convergence.
- The proof represents the next global average from the learners’ local updates on each processor.
- Iterative conditional expectations remove summations over stochastic samples and processors from the convergence bound.
- For fixed inner steps, learner iterates are treated as identically and independently distributed across processors.
- The proof bounds the objective change using Cauchy-Schwarz together with Assumptions 3 and 4.
- Restrictions involving K, P, L, and the stepsize control the terms in the derived bounds.
- With changing batch sizes and diminishing stepsizes, the proof derives convergence of expected average squared gradient norms.
- For constant stepsize and batch size, the analysis obtains a bound on expected average squared gradient norms.