PaperlayerView exact revision on arXiv

Source-linked AI summary

Asynchrony begets Momentum, with an Application to Deep Learning

Ioannis Mitliagkas, Ce Zhang, Stefan Hadjis, Christopher Ré

arXiv:1605.09774v2stat.MLcs.DCcs.LGmath.OC

TL;DR

Asynchronous SGD lacks a complete theoretical explanation for its behavior in non-convex deep learning, especially as training systems scale. The paper models asynchrony as implicit momentum, validates this relationship experimentally, and shows that tuning—including negative momentum under high asynchrony—can improve training efficiency.

  • Problem

    Asynchronous methods are widely used in deep learning, but their effectiveness and interaction with momentum remain insufficiently understood, particularly beyond sparse convex settings.

  • Method

    The paper analyzes asynchronous SGD under staleness and queuing models, treating asynchrony-induced momentum alongside explicit algorithmic momentum.

  • Results

    Experiments on CNNs show that optimal explicit momentum decreases as asynchrony increases, while tuning and negative momentum can reduce the statistical penalty under high asynchrony.

  • Takeaways & Limitations

    Momentum must be tuned for each level of asynchrony, and negative algorithmic momentum is a potential way to counteract adverse effects at high asynchrony.

Abstract

from arXiv · show

Asynchronous methods are widely used in deep learning, but have limited theoretical justification when applied to non-convex problems. We show that running stochastic gradient descent (SGD) in an asynchronous manner can be viewed as adding a momentum-like term to the SGD iteration. Our result does not assume convexity of the objective function, so it is applicable to deep learning systems. We observe that a standard queuing model of asynchrony results in a form of momentum that is commonly used by deep learning practitioners. This forges a link between queuing theory and asynchrony in deep learning systems, which could be useful for systems builders. For convolutional neural networks, we experimentally validate that the degree of asynchrony directly correlates with the momentum, confirming our main result. An important implication is that tuning the momentum parameter is important when considering different levels of asynchrony. We assert that properly tuned momentum reduces the number of steps required for convergence. Finally, our theory suggests new ways of counteracting the adverse effects of asynchrony: a simple mechanism like using negative algorithmic momentum can improve performance under high asynchrony. Since asynchronous methods have better hardware efficiency, this result may shed light on when asynchronous execution is more efficient for deep learning systems.

I. INTRODUCTION

Asynchronous training is widely used, but its effectiveness and interaction with momentum remain insufficiently understood. The paper argues that asynchrony introduces implicit momentum, making momentum tuning important across different levels of asynchrony.

  • Asynchronous-parallel SGD removes locks and synchronization barriers and is used in large-scale deep-learning systems.
  • Asynchrony remains theoretically puzzling because existing explanations for sparse convex problems do not cover reported gains on dense data.
  • Momentum settings interact with optimization and system dynamics, so the appropriate value depends on the objective, data, and hardware.
  • The paper shows that asynchrony introduces momentum into the SGD update and calls this effect implicit momentum.
  • The authors argue that explicit momentum should be tuned for different asynchrony levels and may be negative under heavy asynchrony.

1) Momentum:

The paper models asynchronous SGD through stale worker reads and shows that staleness creates memory in the expected update. Under suitable assumptions, this memory takes a momentum-like form.

  • Asynchronous workers update a shared parameter store using potentially stale values, with staleness represented by a random delay.
  • The expected value read by an asynchronous worker is a convex combination of past parameter values, creating memory in the system.
  • Under independent staleness and example selection with a constant step size, the expected update has a momentum-like expression.
  • Positive staleness variance makes the previous step contribute positively to the current step.
  • Geometrically distributed staleness yields the familiar momentum form used in the paper’s analysis.

A. Queuing Model

Under independent exponential work, asynchronous workers induce momentum whose magnitude grows with worker count, creating a total momentum that can become excessive. Explicit momentum can compensate for insufficient implicit momentum, but high asynchrony eventually hurts statistical efficiency.

  • A. Queuing Model: Under independent exponential work, the asynchrony-induced momentum is µS = 1 − 1/M.The queuing model uses mutually independent work times distributed exponentially with parameter λ.
  • A. Queuing Model: Asynchronous SGD has two momentum sources: explicit algorithmic momentum and implicit momentum contributed by asynchrony.Their total effective momentum is treated as the sum of the explicit and implicit terms as a first-order approximation.
  • A. Queuing Model: As worker count increases, implicit momentum rises, so explicit momentum can be tuned to supply the remaining amount needed for the optimal total momentum.The queuing-model analysis considers tuning explicit momentum separately at each worker count.
  • A. Queuing Model: Beyond a threshold M0, asynchrony-induced momentum exceeds the sequential optimum µ*, causing excessive momentum that hurts performance.Figure 2 characterizes this regime as statistically inefficient.

IV. EXPERIMENTAL VALIDATION

Experiments on ImageNet and CIFAR support the theory that increasing asynchrony changes the momentum needed for efficient training. The optimal explicit momentum decreases as the number of workers increases.

  • IV. EXPERIMENTAL VALIDATION: Experiments measure how momentum affects the iterations needed to reach a target loss across varying levels of asynchrony.The study uses 9 GPU machines, with cross-group updates performed asynchronously.
  • IV. EXPERIMENTAL VALIDATION: The optimal explicit momentum decreases as asynchrony increases on both ImageNet and CIFAR.Figure 3 reports the momentum value minimizing the number of steps to reach a target loss, with ImageNet shown above CIFAR.
  • IV. EXPERIMENTAL VALIDATION: The measurements support the theoretical prediction that system asynchrony and momentum interact.The authors report that the same interactions predicted by the theory appear in their system when momentum is tuned.

A. Measuring Performance

The paper separates parallel-training performance into hardware efficiency and statistical efficiency, then measures how asynchrony and momentum tuning affect these quantities. Experiments show that tuning momentum can substantially reduce asynchronous training’s statistical penalty, while ImageNet can show no penalty under specific conditions.

  • A. Measuring Performance: Parallel-training performance combines hardware efficiency, reflecting per-step time, and statistical efficiency, reflecting the number of steps to reach a target loss.The paper studies hybrid configurations with synchronous updates within groups and asynchronous updates across groups.
  • A. Measuring Performance: Asynchronous methods avoid synchronization stalls and improve hardware efficiency, but stale gradients can reduce statistical efficiency relative to synchronous training.Synchronous methods have zero staleness but wait at barriers; asynchronous methods have no stalls but may require more steps.
  • A. Measuring Performance: 2.5× improvement over fixed µL = 0.9 was achieved by grid-searching momentum and learning rate on CIFAR across asynchronous configurations.The experiment used 33 CPU machines and evaluated normalized iterations to a target loss.
  • A. Measuring Performance: ImageNet incurred no statistical-efficiency penalty for up to 8 asynchronous groups in an intermediate execution stage, despite dense model updates.The authors caution that smaller models or larger worker counts can still incur a penalty.

VI. COUNTERACTING THE EFFECTS OF ASYNCHRONY

The paper analyzes how explicit momentum can counteract momentum induced by asynchronous staleness. Theory and simulations indicate that negative explicit momentum is especially useful under high implicit momentum, and experiments confirm further gains from allowing it.

  • VI. COUNTERACTING THE EFFECTS OF ASYNCHRONY: Under geometric staleness, the expected asynchronous update takes the momentum form after rescaling the step size by α′ = (1 − µS)α.The result is stated for nonzero algorithmic momentum µL and links staleness-induced dynamics to explicit momentum analysis.
  • VI. COUNTERACTING THE EFFECTS OF ASYNCHRONY: The paper’s convergence analysis computes rates from characteristic polynomial roots, enabling numerical identification of explicit momentum values with fastest convergence.The rate analysis is formulated for quadratic objectives and uses the root of smallest magnitude.
  • VI. COUNTERACTING THE EFFECTS OF ASYNCHRONY: Negative explicit momentum is optimal when staleness produces high implicit momentum, according to the paper’s numerical convergence analysis.The analysis searches explicit momentum and step size for quadratic objectives with condition numbers Q = 5 and Q = 20.
  • VI. COUNTERACTING THE EFFECTS OF ASYNCHRONY: For implicit momentum µS > 0.3, negative explicit momentum yields about a 1.5× speedup over fixing µL = 0.0 in the simulated quadratic experiment.The comparison uses rates from Theorem 7 and contrasts joint momentum-and-step-size tuning with step-size-only tuning.
  • VI. COUNTERACTING THE EFFECTS OF ASYNCHRONY: Allowing negative momentum improved the 16-group CIFAR penalty by another 2× beyond the approximately 2.5× speedup from nonnegative tuning.The experiment supports the numerical finding that negative momentum can further reduce asynchronous statistical penalties.

VII. DISCUSSION AND FUTURE WORK

The discussion emphasizes that asynchrony-induced momentum interacts with explicit momentum, motivating momentum tuning and possible compensation strategies. It also identifies topology, data access patterns, and arbitrary staleness as directions for extending the work.

  • Asynchronous configurations require momentum tuning because implicit momentum complements algorithmic momentum, and a single globally optimized value can mis-evaluate systems with different asynchrony.The authors report that lower explicit momentum is more efficient under asynchrony and that negative momentum may help under heavy asynchrony.
  • The model could support an optimizer that tunes explicit momentum from system statistics such as measured staleness distributions.
  • The analysis is based on a simple model that the authors propose extending with control-theoretic tools for momentum compensation.
  • Future work should examine interactions among neural-network topology, physical mapping, and queueing theory.
  • Different data sparsity and access patterns, including heavy-tailed NLP data and irregular LSTM accesses, may produce different staleness distributions.
  • Arbitrary sparsity and staleness distributions may induce momentum different from the paper’s modeled form, leaving their convergence properties for future study.

APPENDIX

The appendix proof derives the claimed update relation by repeatedly applying the preceding update equation, rearranging terms, and integrating over the relevant randomness.

  • The proof obtains the statement by applying equation (6) twice and subtracting w_t from w_t+1.
  • After rearranging terms, the proof first takes expectation over random example selections and then integrates over the staleness variables.The intermediate conditioning uses the sigma-algebra under which staleness is measurable.
  • The proof uses independence in Assumption 1 when handling the conditional expectations.

C. Proof of Theorem 5

The proof models staleness through the number of writes by other workers during a worker’s iteration, yielding a geometric distribution with mean M − 1.

  • Staleness is the number of writes by other workers during the reference worker’s iteration time.The proof denotes the iteration duration by W_t and the intervening-write count by B_t.
  • The resulting staleness variable τ_t is geometrically distributed on {0, 1, . . .}.
  • Eτ_t = M −1, where M is the number of workers.This expectation is used with Theorem 3 to obtain the stated result.
  • The derivation starts from the asynchronous update rule and its expected step under independent geometric staleness.
  • The resulting expected recurrence contains current, previous, and two-step previous iterates, with coefficients determined by μS and μL.
  • The recurrence is stated for k ≥2.

E. Proof of Theorem 7

The proof analyzes the expected iterates through polynomial recurrences and a generating function. Convergence is governed by the growth-polynomial roots across eigendirections.

  • The proof represents the expected error sequence with a polynomial family q_k(z) and derives its generating-function recurrence.
  • The generating-function derivation expands the recurrence algebraically until the expression for G(z) is obtained.
  • After eigendecomposing A^T A, the expected dynamics reduce to scalar recurrences for each eigendirection.
  • The expected update recurrence combines μS and μL in the coefficients of the current and lagged iterates.
  • The growth polynomial is g_i(t) = μSμLt^3 −(μS + μL + μSμL)t^2 + z_i t −1.
  • The convergence rate is determined by the largest γ_i, where each γ_i is the inverse magnitude of the smallest-magnitude root of g_i(t).
Loading 1605.09774v2…