PaperlayerView exact revision on arXiv

Source-linked AI summary

Slow and Stale Gradients Can Win the Race: Error-Runtime Trade-offs in Distributed SGD

Sanghamitra Dutta, Gauri Joshi, Soumyadip Ghosh, Parijat Dube, Priya Nagpurkar

arXiv:1803.01113v3stat.MLcs.LG

TL;DR

Distributed SGD faces a trade-off between synchronous delays from stragglers and asynchronous staleness that can harm stability. The paper models error and wallclock runtime under random learner delays, develops relaxed convergence analyses, and proposes a staleness-compensating learning-rate schedule. Its supported conclusion is that these analyses compare synchronous and asynchronous variants while the schedule improves asynchronous stability and convergence while preserving fast runtime.

  • Problem

    Synchronous SGD waits for stragglers, whereas asynchronous SGD can use stale gradients that make training unstable.

  • Method

    The paper characterizes error-runtime trade-offs using general random learner runtimes, relaxed asynchronous convergence assumptions, and a learning-rate schedule for stale gradients.

  • Results

    The proposed learning-rate schedule improves asynchronous SGD stability and convergence while preserving its fast runtime.

  • Takeaways & Limitations

    Comparing error reduction with wallclock runtime provides a basis for evaluating synchronous and asynchronous distributed SGD variants under straggler randomness.

  • Takeaways & Limitations

    The authors identify gradually increasing synchrony to achieve fast convergence and a low error floor as future work.

Abstract

from arXiv · show

Distributed Stochastic Gradient Descent (SGD) when run in a synchronous manner, suffers from delays in waiting for the slowest learners (stragglers). Asynchronous methods can alleviate stragglers, but cause gradient staleness that can adversely affect convergence. In this work we present a novel theoretical characterization of the speed-up offered by asynchronous methods by analyzing the trade-off between the error in the trained model and the actual training runtime (wallclock time). The novelty in our work is that our runtime analysis considers random straggler delays, which helps us design and compare distributed SGD algorithms that strike a balance between stragglers and staleness. We also present a new convergence analysis of asynchronous SGD variants without bounded or exponential delay assumptions, and a novel learning rate schedule to compensate for gradient staleness.

1 INTRODUCTION

Distributed SGD must balance synchronous waiting for stragglers against asynchronous gradient staleness. This paper analyzes that error-runtime trade-off under random runtimes, develops less restrictive convergence theory, and proposes a staleness-compensating learning-rate schedule.

  • 1 INTRODUCTION: Synchronous SGD can lose parallel speed-up because the parameter server waits for randomly straggling learners.Distributed learners process mini-batches in parallel, but each synchronous update waits for all learners.
  • 1 INTRODUCTION: Asynchronous SGD avoids waiting for all learners, but stale gradients evaluated on older model versions can destabilize training.The trade-off is faster updates versus potentially adverse effects from gradient staleness.
  • 1.2 OUR CONTRIBUTIONS: The paper analyzes error against actual wallclock runtime, modeling each learner’s runtime as a random variable with a general distribution.This framework compares K-sync SGD, K-batch-sync SGD, K-async SGD, and K-batch-async SGD.
  • 1.2 OUR CONTRIBUTIONS: Its asynchronous convergence analysis relaxes assumptions including bounded delays and gradients, exponential service times, and independent staleness.The analysis covers asynchronous SGD variants and applies to strongly convex objectives, with extension to non-convex formulations.
  • 1.2 OUR CONTRIBUTIONS: A new learning-rate schedule compensates for gradient staleness to improve asynchronous SGD stability and convergence while preserving fast runtime.The paper positions this schedule as distinct from momentum tuning.
  • 1.2 OUR CONTRIBUTIONS: The analysis identifies regimes where asynchronous methods can converge faster or slower than synchronous SGD.The comparison depends on the error reduction per iteration and the runtime per iteration.

2 PROBLEM FORMULATION

The paper formulates distributed SGD around a parameter server with parallel learners, random computation times, and an error–runtime objective. It then distinguishes synchronous and asynchronous variants by how gradients are fetched, aggregated, cancelled, or allowed to become stale.

  • 2.1 SYSTEM MODEL: The system uses a central parameter server with P parallel learners that fetch parameters, compute mini-batch gradients, and push them back for aggregation.Each iteration updates the parameter vector at the parameter server.
  • 2.1 SYSTEM MODEL: Learner mini-batch computation times are modeled as i.i.d. random variables across learners and mini-batches.This models variability from straggling computations.
  • 2.2 PERFORMANCE METRICS: Performance is evaluated using expected runtime per parameter update and expected error, the expected risk gap E[F(w_j) − F*] after j iterations.The objective is to compare accuracy with wallclock cost after a total of J iterations.
  • 2.3 VARIANTS OF SGD: K-sync waits for the first K of P learners, updates the parameter, and cancels the remaining learners; K = P recovers fully synchronous SGD.The first K completed gradients are averaged from mini-batches of size m.
  • 2.3 VARIANTS OF SGD: K-batch-sync waits for the first K completed mini-batches rather than learners, so learners immediately start new work and no learner is idle.It retains the same theoretical update form while improving runtime per iteration over K-sync.
  • 2.3 VARIANTS OF SGD: K-async accepts the first K learners without cancelling the rest, allowing gradients computed from stale parameter versions to enter updates.Staleness is indexed by the iteration when each learner last read from the parameter server.
  • 2.3 VARIANTS OF SGD: K-batch-async waits for the first K mini-batches regardless of learner identity, reducing runtime because learners continue computing instead of remaining idle.Its error convergence is described as similar to K-async.
  • 2.3 VARIANTS OF SGD: The variants exploit data redundancy by ignoring straggling gradients; with well-shuffled i.i.d. data, equal effective batch sizes yield equivalent error scaling to coded approaches.The paper introduces these variants within its stated system and convergence assumptions.

2. F(w) is strongly convex with parameter c. Thus,

The analysis assumes strongly convex objectives and an unbiased stochastic gradient under conditioning on the parameter available before data access, with bounded update variance.

  • The paper’s results extend from strongly convex objectives to non-convex objectives.
  • The stochastic gradient is assumed to be an unbiased estimate of the true gradient.The assumption is stated in conditional form for the parameter value available before the data is accessed.
  • Unbiasedness is conditioned on w_k for k ≤ j because later parameters can depend on the accessed data.
  • The stochastic update variance conditioned on the pre-access parameter w_k is assumed to be bounded.

3 MAIN RESULTS

The paper characterizes asynchronous SGD through runtime and convergence analyses, relaxing common assumptions and proposing staleness compensation. Its results identify when asynchronous methods can converge faster or slower than synchronous SGD and how runtime changes that comparison.

  • Runtime analysis: Theorem 1 analytically characterizes asynchronous-over-synchronous expected runtime speed-up for any general learner wall-clock-time distribution.The proof uses renewal theory.
  • Runtime analysis: For exponential service times, asynchronous SGD is approximately P log P times faster per iteration than synchronous SGD.The speed-up scales with P and can diverge for large P.
  • Runtime analysis: As K increases, K-batch-async speed-up increases and can reach up to log P times higher.The comparison is derived for exponential computation times and simulated for Pareto and shifted-exponential distributions.
  • Convergence analysis: The convergence analysis relaxes bounded-delay, bounded-gradient, exponential-service-time, and staleness-independence assumptions.The framework allows large but rare delays and removes independence between staleness and parameter values.
  • Convergence analysis: With fixed learning rate, asynchronous decay can be faster or slower than synchronous decay depending on staleness γ and conditional freshness lower bound p0.The asynchronous decay is faster when p0^2 > γ; it can still win in wall-clock time when iteration decay is slower.
  • Staleness compensation: The proposed learning-rate schedule uses learner-specific staleness information to stabilize asynchronous SGD while preserving fast runtime.The parameter server stores the last-read model parameters for every learner.

4 RUNTIME ANALYSIS

The runtime analysis models learner computation times as random variables and derives expected runtimes for synchronous and asynchronous variants. Renewal theory yields general-distribution results for batch-asynchronous SGD and distribution-specific comparisons for asynchronous methods.

  • Synchronous runtime: For K-sync SGD, the expected runtime per iteration is the expected Kth order statistic of P i.i.d. learner computation times.For J iterations, the expected runtime is J E[X_K:P].
  • Distribution-specific results: For exponential computation times, K-batch-sync runtime follows an Erlang(K, Pµ) distribution.The derivation uses the memoryless property of exponential service times.
  • Asynchronous runtime: K-batch-async SGD has expected runtime per iteration K E[X]/P in the large-iteration limit.This follows by treating learner gradient pushes as superposed renewal processes.
  • Distribution-specific results: For non-exponential computation times, K-async runtime is not analytically tractable, but an upper bound is obtained for new-longer-than-used distributions.The exponential case attains equality in the corresponding bound.
  • Error-runtime comparison: Figure 10 compares K-async with K-batch-async on MNIST under exponential computation times; K-batch-async falls more sharply while reaching a similar error floor.The figure presents the error-runtime trade-off.

5 CONCLUSIONS

The paper frames distributed SGD speed through both error reduction and runtime, combining runtime and convergence analyses to compare synchronous and asynchronous variants. It also proposes staleness compensation, while identifying gradual increases in synchrony as future work toward fast convergence and low error floors.

  • Conclusions: The paper compares distributed SGD algorithms using expected error together with actual wall-clock runtime.The analysis covers synchronous and asynchronous variants under general learner-time distributions.
  • Future work: Future work will explore gradually increasing synchrony to combine fast convergence with a low error floor.The paper also mentions local updates to reduce parameter-server communication frequency.

B RUNTIME ANALYSIS PROOFS

The runtime proofs use order statistics for synchronous variants and renewal-process arguments for asynchronous variants. Exponential service times provide tractable closed forms, while general distributions require bounds or asymptotic results.

  • Order statistics: The Kth order statistic of P exponential learner times is represented as a sum of independent exponential variables with rates Pµ, (P−1)µ, through (P−K+1)µ.This representation yields a harmonic-number expression for its expectation.
  • Order statistics: For exponential learner times, the Kth order statistic scales as log(P/(P−K))/µ.The expression is written using harmonic numbers H_P and H_{P−K}.
  • Batch-synchronous runtime: K-batch-sync has an Erlang(K, Pµ) runtime because each completed mini-batch restarts P exponential computations through memorylessness.This makes the expected runtime tractable in the exponential case.
  • Renewal-process proof: Asynchronous gradient pushes form renewal processes because inter-arrival times are independent learner computation times.Superposing the P renewal processes gives the average push rate used in the K-batch-async runtime proof.

B.4 Runtime of K-async SGD

The runtime analysis represents stale learner computations through residual times and compares their K-th order statistic with fresh computation times. For new-longer-than-used distributions, stochastic domination yields an upper bound, while exponential delays give an exact expression.

  • Each learner’s residual computation time is Xi−(t0−ti) conditioned on Xi>(t0−ti), and these residuals are independent and stochastically dominated by Xi.The K-th order statistic of the residuals equals the expected runtime of one K-async iteration.
  • The K-th order statistic is monotone in each learner time, so stochastic domination transfers to an upper bound on expected K-async runtime.The proof applies the increasing-function property to gK,s and iteratively to hK.
  • For exponential delays, memorylessness makes the stochastic-domination inequality an equality and permits direct derivation of the expected runtime.The supplied expression is μ log P divided by P−K.

C ASYNC-SGD ANALYSIS PROOFS

The asynchronous SGD proof establishes an error recursion under strong convexity, a learning-rate constraint, and a lower bound on the probability that an update is current. The resulting corollary characterizes error after J iterations.

  • The proof first treats K=1 for simplicity, with the general K-learner theorem supplied separately in Appendix C.2.This organizes the convergence argument from the simplified case to the general result.
  • Corollary 2 assumes strong convexity with parameter c and learning rate η ≤ 1/[2L(MG/m+1)] for Async SGD.It also invokes an expectation condition and a non-negative lower bound p0 on current-update probability.
  • The resulting error after J Async SGD iterations is given by the theorem’s stated bound.The supplied passage introduces the bound but does not include its complete displayed expression.
  • The proof derives the recursion by decomposing the update expression, applying the stated assumptions and lemmas, and choosing η below the prescribed bound.Strong convexity then converts gradient-norm control into objective-error control.

C.1.1 Discussion on range of p0

The current-update probability p0 depends on the learner-delay distribution. Exponential delays give p0=1/P, while new-longer-than-used and new-shorter-than-used distributions place p0 on opposite sides of that value.

  • For exponential delays, memorylessness makes all residual learner times i.i.d., so the probability of a specified learner finishing first is p0=1/P.The symmetry argument applies when one learner has pushed the gradient in the iteration.
  • For new-longer-than-used distributions, other learners’ residual times are stochastically dominated by the specified learner’s fresh time, yielding p0≤1/P.The passage states that these bounds also apply to K-async and K-batch-async SGD.
  • For new-shorter-than-used distributions, the specified learner’s residual time is stochastically dominated by the others, so its probability of finishing first is higher.Thus its current-update probability exceeds the exponential benchmark, although the supplied passage does not state a numeric lower bound.
  • The lower bound p0 is distribution-dependent because the conditional current-update probability varies with the delay distribution.The discussion explicitly notes that p0 differs across distributions.

C.2 K-async SGD under fixed learning rate

The convergence analysis extends from single stochastic updates to K-async sums, establishes convex and non-convex guarantees, and motivates a more stable learning-rate heuristic. The analysis also informs hyperparameter choices for synchronous variants.

  • K-async SGD under fixed learning rate: For K-async, the variance of the sum of stochastic updates is bounded after cross terms are shown to have zero expectation.This extends the single-update variance assumption to updates evaluated at potentially stale parameters.
  • K-async SGD under fixed learning rate: Theorem 5 provides an ergodic convergence result for non-convex objectives, using γ′=1−γ+p0/2.The proof uses the previously derived recursion and the lower bound F* on the objective.
  • K-async SGD under fixed learning rate: The paper proposes a learning-rate schedule heuristic described as more stable than a fixed learning rate.The heuristic is tied to a suitably large ηmax beyond which convergence diverges and to an assumption bounding ηjE[…].
  • K-async SGD under fixed learning rate: Theorem 4’s accuracy trade-off is derived under an assumption that bounds ηjE[…], with the recursion expressed through contraction factors and accumulated Δj terms.The supplied passages show the recursive form but not the complete definitions of every symbol.
  • K-async SGD under fixed learning rate: The analysis techniques can inform hyperparameter choices for synchronous and K-sync SGD.

E.1 Varying K in K-sync

The simulations show that increasing K or mini-batch size improves error per iteration, but the best error-runtime trade-off occurs at an intermediate setting because larger synchronization loads increase waiting time.

  • Runtime modeling: K-sync runtime is modeled with learner runtimes generated from a shifted exponential distribution.The shifted distribution combines a minimum work-related component with an exponential delay tail.
  • K-sync SGD on MNIST: Increasing K improves accuracy per iteration by increasing the effective mini-batch and reducing gradient variability.This pattern is shown for K-sync SGD on MNIST with eight learners, mini-batch m = 1, and learning rate 0.05.
  • K-sync SGD on MNIST: K = 4 gives the best MNIST error-runtime trade-off, although increasing K improves iteration-based error.Larger K makes the parameter server wait for more learners at each iteration, increasing the straggler effect.
  • Error-runtime analysis: The runtime-based analysis compares synchronization choices using actual wallclock time rather than iterations, whose per-iteration duration is random.This analysis is used to identify settings that balance improved gradient quality against delays from stragglers.
  • Mini-batch size on ImageNet: On ImageNet with fully synchronous SGD and K = P = 4, increasing mini-batch size improves error per iteration but does not necessarily improve error against expected runtime.Mini-batch size changes the runtime distribution, so iteration-based and runtime-based comparisons can favor different settings.
Loading 1803.01113v3…