Source-linked AI summary
Adaptive Communication Strategies to Achieve the Best Error-Runtime Trade-off in Local-Update SGD
Jianyu Wang, Gauri Joshi
TL;DR
Distributed SGD must remain efficient despite stragglers and communication delays, while existing analysis largely emphasizes iteration-based convergence. This paper jointly analyzes wall-clock error-runtime trade-offs for periodic local updates and develops ADACOMM, which adapts communication frequency; experiments report a 3× runtime speed-up while reaching the same low training loss as fully synchronous SGD.
Problem
Distributed SGD needs convergence analysis that accounts for variable computation and communication time, but the joint error-runtime problem is described as theoretically unexplored.
Method
The paper analyzes PASGD under runtime delays and variable communication periods, then derives ADACOMM to adapt communication frequency over training.
Results
3× runtime speed-up was reported for ADACOMM while reaching the same low training loss as fully synchronous SGD.
Takeaways & Limitations
Decaying the communication period can provide convergence benefits similar to decaying the learning rate while improving wall-clock convergence, and can be combined with learning-rate schedules.
Takeaways & Limitations
The practical adaptive rule approximates unknown quantities such as the limiting objective value, Lipschitz constant, and gradient variance bound; applying the theoretical rule with a sharply decayed learning rate can make τ = 1000 and cause divergence.
Abstract
from arXiv · showhide
Large-scale machine learning training, in particular distributed stochastic gradient descent, needs to be robust to inherent system variability such as node straggling and random communication delays. This work considers a distributed training framework where each worker node is allowed to perform local model updates and the resulting models are averaged periodically. We analyze the true speed of error convergence with respect to wall-clock time (instead of the number of iterations), and analyze how it is affected by the frequency of averaging. The main contribution is the design of AdaComm, an adaptive communication strategy that starts with infrequent averaging to save communication delay and improve convergence speed, and then increases the communication frequency in order to achieve a low error floor. Rigorous experiments on training deep neural networks show that AdaComm can take $3 \times$ less time than fully synchronous SGD, and still reach the same final training loss.
1 INTRODUCTION
Distributed SGD must optimize error reduction and iteration throughput together because shared infrastructure introduces variable computation, straggling, and communication delays. The paper analyzes this error-runtime trade-off for periodic averaging and proposes adaptive communication that begins infrequently and becomes more frequent near convergence.
- Motivation: Distributed SGD faces unpredictable node slowdowns and communication delays, creating a need for training that is both fast and robust.Parallelism increases data processed per iteration but exposes training to infrastructure variability.
- Problem: Wall-clock convergence depends on both error reduction per iteration and the number of iterations completed per second.The paper argues these optimization and scheduling factors should be studied jointly.
- Error-Runtime Trade-off: Periodic averaging trades slower iteration-based convergence at larger τ for reduced communication delay and faster runtime per iteration.The optimal choice depends on the error-runtime trade-off rather than iteration count alone.
- Adaptive Strategy: Adaptive communication starts with larger τ for rapid initial loss reduction and gradually decreases τ to approach a lower error floor.The paper presents this as the first adaptive communication-frequency strategy to achieve both goals.
- Contributions: The paper combines runtime and convergence analyses to derive a practical guideline for selecting the communication period.It also analyzes runtime speed-up over fully synchronous SGD and identifies mitigation of synchronization delays from straggling nodes.
- Empirical Results: 3× runtime speed-up was observed for ADACOMM while reaching the same low training loss as fully synchronous SGD.Experiments covered VGG16 and ResNet-50 with and without momentum and with fixed or decaying learning rates.
2 PROBLEM FRAMEWORK
The framework models periodic-averaging SGD with local updates, random computation and communication delays, and convergence measured through expected gradient norm. Workers periodically average their local models, with τ = 1 recovering fully synchronous SGD.
- PASGD Framework: PASGD uses m workers that each perform τ local mini-batch SGD updates before their models are averaged.After averaging, workers continue from the shared model.
- PASGD Framework: The iteration index counts local iterations rather than averaging steps, and τ is the communication period.This distinction is important when comparing local-update schedules.
- Synchronous Special Case: When τ = 1, PASGD is equivalent to fully synchronous SGD because models synchronize after every iteration.This provides the synchronous baseline within the framework.
- Illustrations: With m = 2 workers and τ = 3, the discrepancy between local models increases with the number of local updates.The time-space illustration separately depicts local-update durations and the communication block.
- Delay Model: Worker mini-batch computation times are modeled as i.i.d. random variables, while each all-node broadcast incurs a communication delay D.The communication delay may depend on the number of workers and system implementation.
- Convergence Criterion: The model measures convergence for a non-convex objective using the expected gradient norm and defines ε-suboptimality through that criterion.For arbitrarily small ε, the condition can guarantee convergence to a stationary point.
3 JOINTLY ANALYZING RUNTIME AND ERROR-CONVERGENCE
Periodic averaging improves wall-clock efficiency by amortizing communication and reducing straggler effects, but larger communication periods introduce an error-runtime trade-off. Theoretical analysis identifies how runtime gains can coexist with a higher eventual error floor.
- Runtime Analysis: PASGD performs τ local updates before communication, amortizing communication delay across local iterations.Fully synchronous SGD corresponds to τ = 1 and waits for all workers before each broadcast.
- Runtime Analysis: E[Tsync] / E[TP-Avg] = (1 + α) / (1 + α/τ), showing how communication/computation ratio α and period τ determine speed-up.Here α = D/Y, with D the communication delay and Y the local computation time.
- Runtime Analysis: Almost 2× speed-up occurs when communication delay is comparable to computation time, with α = 0.9.Figure 4 reports this comparison between PASGD and fully synchronous SGD.
- Straggler Mitigation: PASGD mitigates straggling because averaging local computation times reduces variance, producing a much lighter runtime tail than synchronous SGD.For exponentially distributed worker times, synchronous runtime grows approximately as y log m, while local averaging reduces computation-time variance by a factor of τ.
- Error-Runtime Trade-off: Larger τ lowers runtime per iteration but adds local-update noise, creating an error-runtime trade-off with a higher eventual error floor.Theorem 1 bounds the minimal expected squared gradient norm over a wall-clock interval; τ = 10 initially drops rapidly but converges to a higher floor.
4 ADACOMM: PROPOSED ADAPTIVE COMMUNICATION STRATEGY
AdaComm adapts the communication period over wall-clock intervals to balance early runtime gains against later error reduction. It estimates period choices from error-runtime analysis, applies practical safeguards, and is supported by convergence guarantees.
- Adaptive Strategy: AdaComm selects the communication period that gives the fastest expected decay during each fixed wall-clock interval.Training is divided into intervals of length T0, with τ chosen at each interval boundary.
- Adaptive Strategy: With a fixed learning rate, the theoretically selected communication periods decrease as the objective value decreases.The benefit of large τ diminishes near convergence, where a lower error floor becomes preferable to faster runtime.
- Practical Considerations: The practical update rule avoids estimating unknown Lipschitz and gradient-variance constants by approximating F_inf as zero and using observed training losses.The initial τ0 is estimated by a grid search over periods run for one or two epochs.
- Practical Considerations: When the period update stalls, AdaComm multiplies the period by γ < 1 to prevent prolonged saturation.The experiments use γ = 1/2 as a good choice.
- Adaptive Learning Rate: For variable learning rates, the communication period increases as the learning rate decreases because smaller steps reduce local-model discrepancies.The paper notes that directly scaling τ with (η0/ηl)^3/2 can produce τ = 1000 and diverging training loss after a dramatic learning-rate change.
- Convergence Guarantee: Under stated conditions, the adaptive communication and learning-rate scheme guarantees convergence of the averaged model to a stationary point.The guarantee is formulated for an arbitrary communication-period sequence satisfying the theorem’s conditions.
5 EXPERIMENTAL RESULTS
Experiments on CIFAR10 and CIFAR100 train VGG-16 and ResNet-50 under varied communication, learning-rate, and momentum settings. AdaComm consistently targets a better wall-clock error trade-off than fixed-period or synchronous baselines, including faster convergence and comparable or better accuracy.
- Experimental Setting: VGG-16 requires a larger communication period than ResNet-50 because its communication time is about four times its computation time.The experiments use a four-worker cluster and compare models with different architectures and parameter sizes.
- Adaptive Communication in PASGD: 1.3× faster: with learning-rate decay, AdaComm reaches 3 × 10−2 training loss in 15.0 minutes versus 21.5 minutes for fully synchronous SGD on ResNet-50.For ResNet-50, communication is not the bottleneck, so local-update effects reduce the benefit of fixed communication periods.
- Adaptive Communication in PASGD: Adaptive communication provides better test accuracy than fully synchronous SGD and can outperform PASGD with the best fixed communication period under variable learning rates.The comparison reports the best accuracy within a time budget for each setting.
- Block Momentum in periodic-averaging: Block momentum treats each local-update period as one accumulated step with global momentum, while local momentum buffers are cleared after averaging.The global momentum factor is 0.3 and the local momentum factor is 0.9 in the experiments.
- ADACOMM plus Block Momentum: 3.5× faster: with block momentum, AdaComm reaches 3 × 10−3 training loss on VGG-16 faster than fully synchronous SGD.On ResNet-50, AdaComm reaches 2 × 10−2 loss in 15.8 minutes versus 32.6 minutes for fully synchronous SGD, a 2× speedup.
6 CONCLUDING REMARKS
The paper analyzes PASGD by wall-clock error convergence and uses that analysis to design AdaComm. The strategy can improve runtime while reaching the same error floor as fully synchronous SGD and is proposed as extensible beyond PASGD.
- 6 CONCLUDING REMARKS: The paper analyzes PASGD convergence with respect to wall-clock time while accounting for computation and communication delays.PASGD averages locally updated models after every τ iterations.
- 6 CONCLUDING REMARKS: AdaComm adapts the frequency of distributed-SGD averaging and achieves up to a 3× runtime improvement while reaching the same error floor as fully synchronous SGD.The conclusion reports results using VGGNet and ResNet.
- 6 CONCLUDING REMARKS: AdaComm achieves a 3.3× speedup over fully synchronous SGD on VGG-16, reducing time to 4.5 × 10−2 training loss from 38.0 to 11.5 minutes.Additional reported results include 1.4× on ResNet-50 and 3.5× with block momentum.
- 6 CONCLUDING REMARKS: The averaging-frequency adaptation idea is proposed as extendable to elastic-averaging, decentralized SGD, and parameter-server training.Examples include adapting network sparsity in decentralized SGD and asynchrony in parameter-server training.
A ADDITIONAL EXPERIMENTAL RESULTS
Additional experiments with eight workers evaluate AdaComm on VGG-16 and ResNet-50. The results report substantial runtime speedups and test accuracies across communication periods under variable learning rates.
- Additional Experimental Results: 2.9× speedup: AdaComm reaches 1 × 10−2 training loss on VGG-16 in 6.0 minutes versus 17.5 minutes for fully synchronous SGD.These experiments use eight workers with NCCL communication.
- Additional Experimental Results: On VGG-16, convergence test accuracy is 92.72% for AdaComm versus 92.52% for τ = 1 under a variable learning rate.The same comparison reports 91.85% for τ = 20 and 91.15% for τ = 100.
- Additional Experimental Results: On ResNet-50 with eight workers, AdaComm achieves a reported 1.6× speedup over fully synchronous SGD.The figure reports 11.15 versus 18.25 minutes to reach the target loss, although the supplied passage does not include that target value.
- Additional Experimental Results: On another eight-worker comparison, convergence test accuracy is 91.77% for AdaComm versus 91.93% for τ = 1 under a variable learning rate.The same comparison reports 91.51% for τ = 10 and 90.46% for τ = 100.
B INEFFICIENT LOCAL UPDATES
PASGD can improve test accuracy over synchronous SGD and AdaComm under a fixed learning rate, but local models may remain substantially worse than synchronized models. The observed behavior suggests local updates can reduce accuracy without making progress after convergence.
- Observed accuracy behavior: When the learning rate is fixed, fine-tuned PASGD achieves better test accuracy than fully synchronous SGD and the adaptive method, despite higher training loss.On CIFAR100, PASGD with τ = 5 shows about 5% improved test accuracy.
- Evaluation condition: When evaluation occurs at iterations not divisible by the communication period, the reported accuracy may come from either synchronized or local models.For PASGD with τ = 15, iteration 100 is not an averaging point, unlike iteration 135.
- Observed accuracy behavior: Local-model accuracy remains much lower than synchronized-model accuracy even after the algorithm has converged.The authors conjecture that accuracy rises after averaging and falls during subsequent local steps because of stochastic-gradient noise.
- Observed accuracy behavior: A 10% accuracy gap separates local models from the synchronized model for PASGD with τ = 15 on CIFAR10.The comparison uses ResNet-50 with a fixed learning rate and no momentum.
C ASSUMPTIONS FOR CONVERGENCE ANALYSIS
The convergence analysis does not assume convexity or uniformly bounded stochastic-gradient norms, but relies on Lipschitz smoothness, a lower-bounded objective, and batch-size-dependent constants.
- Assumptions: The analysis assumes a differentiable objective that is Lipschitz smooth and lower bounded.These conditions are stated as Assumption 1.
- Assumptions: The convergence analysis makes no convexity assumption on the objective function.This broadens the stated setting beyond analyses requiring convexity.
- Assumptions: The analysis removes the assumption that stochastic gradients have uniformly bounded norms.The assumptions are described as similar to those used in previous PASGD analyses.
- Assumptions: The non-negative constants β and σ2 are inversely proportional to the mini-batch size.
D PROOF OF THEOREM 2: ERROR-RUNTIME CONVERGENCE OF PASGD
Theorem 2 derives PASGD’s error convergence with respect to wall-clock time by combining an iteration-based error bound with the expected runtime per iteration.
- Proof strategy: PASGD’s error bound is established under the stated assumptions, a learning-rate condition, and common initialization across workers.The condition is ηL + η2L2τ(τ −1) ≤ 1, and all workers start at x1.
- Proof strategy: The bound identifies L as the objective’s Lipschitz constant, σ2 as the mini-batch gradient variance bound, and xk as the averaged model.
- Runtime conversion: The proof converts iteration-based convergence into wall-clock convergence using PASGD’s expected runtime per iteration.
- Runtime conversion: The total training time for K iterations is substituted into the error bound to complete the error-runtime result.
E PROOF OF THEOREM 3: THE BEST COMMUNICATION PERIOD
The proof of the best communication period differentiates the error-runtime upper bound, verifies curvature, and develops the local-period analysis used to establish convergence conditions.
- Best communication period: The candidate communication period is obtained by setting the derivative of the error-runtime upper bound to zero.
- Best communication period: The second derivative establishes that the candidate communication period is a global minimum.
- Proof setup: The proof represents local models and gradients with matrices Xk and Gk, while J averages across the m workers.J is defined as 11⊤/(1⊤1), with J and I of size m × m.
- Period-wise error analysis: Within each local-update period, the proof bounds the objective value at each local step and then sums the bounds across periods.
- Period-wise error analysis: The disagreement term is bounded using common period initialization, the operator norm of I−J, unbiased gradients, and Jensen’s inequality.
- Convergence condition: A sufficient condition is derived to make the upper bound converge to zero as R →∞.
F.3 Asymptotic Result (Theorem 3)
The section states a sufficient condition for the upper bound to vanish asymptotically and then gives a simplified fixed-learning-rate result.
- A sufficient condition is introduced to ensure that upper bound (62) converges to zero as R →∞.
- The proof of Theorem 3 is completed in this section.
- A simplified asymptotic result is obtained when the learning rate is fixed.