PaperlayerView exact revision on arXiv

Source-linked AI summary

Asynchronous Stochastic Gradient Descent with Delay Compensation

Shuxin Zheng, Qi Meng, Taifeng Wang, Wei Chen, Nenghai Yu, Zhi-Ming Ma, Tie-Yan Liu

arXiv:1609.08326v6cs.LGcs.DC

TL;DR

ASGD is efficient but applies gradients computed on stale model snapshots, motivating a method that restores behavior closer to sequential SGD. DC-ASGD uses Taylor expansion with a cheap Hessian approximation to compensate delay, and experiments on CIFAR-10 and ImageNet report better accuracy than synchronous and asynchronous SGD while nearly approaching sequential SGD.

  • Problem

    ASGD improves speed by eliminating worker waiting but suffers when gradients computed on earlier model snapshots are applied to an already updated global model.

  • Method

    DC-ASGD compensates delayed gradients using a Taylor expansion and a cheap Hessian approximation based on previously available gradients.

  • Results

    DC-ASGD achieves better accuracy than synchronous and asynchronous SGD and nearly approaches sequential SGD on CIFAR-10 and ImageNet.

  • Takeaways & Limitations

    Delay compensation can retain asynchronous training without waiting while bringing optimization performance closer to sequential SGD.

  • Takeaways & Limitations

    The Hessian approximation relies on conditions involving model convergence and class probabilities, while exact Hessian computation is costly for large models.

Abstract

from arXiv · show

With the fast development of deep learning, it has become common to learn big neural networks using massive training data. Asynchronous Stochastic Gradient Descent (ASGD) is widely adopted to fulfill this task for its efficiency, which is, however, known to suffer from the problem of delayed gradients. That is, when a local worker adds its gradient to the global model, the global model may have been updated by other workers and this gradient becomes "delayed". We propose a novel technology to compensate this delay, so as to make the optimization behavior of ASGD closer to that of sequential SGD. This is achieved by leveraging Taylor expansion of the gradient function and efficient approximation to the Hessian matrix of the loss function. We call the new algorithm Delay Compensated ASGD (DC-ASGD). We evaluated the proposed algorithm on CIFAR-10 and ImageNet datasets, and the experimental results demonstrate that DC-ASGD outperforms both synchronous SGD and asynchronous SGD, and nearly approaches the performance of sequential SGD.

1. Introduction

ASGD improves training speed by removing synchronization waits but introduces delayed gradients. DC-ASGD compensates for this delay using Taylor expansion and an efficient Hessian approximation, improving convergence and accuracy relative to ASGD and SSGD.

  • Optimization setting: ASGD avoids barrier synchronization, allowing workers to continue immediately after adding gradients, but its gradients can become delayed.SSGD waits for all M workers, so training speed is constrained by the slowest worker.
  • Delay compensation: DC-ASGD approximates the current gradient through Taylor expansion, treating the delayed gradient as its zero-order approximation.The method seeks a more accurate approximation to the gradient at the current model state.
  • Optimization setting: Backup workers address delayed gradients but require redundant computation and assume most workers train at similar speeds.
  • Delay compensation: The proposed Hessian approximator uses previously available gradients, avoiding direct Hessian computation while balancing approximation bias and variance.This addresses the computational and spatial cost of higher-order delay compensation.
  • Results: DC-ASGD accelerates convergence relative to SSGD and ASGD, while matching sequential SGD accuracy closely within the same time period.The paper reports both theoretical convergence guarantees and empirical results on CIFAR-10 and ImageNet.

2. Problem Setting

The section formalizes parallel neural-network training and identifies ASGD’s delayed-gradient problem: workers apply gradients computed on stale model snapshots to a newer global model.

  • Problem formulation: The training objective is empirical-risk minimization for a neural network parameterized by w, using i.i.d. examples from an unknown distribution P.The model maps inputs and labels to real-valued outputs used for classification.
  • ASGD process: ASGD trains neural networks asynchronously by letting each worker continue after its gradient reaches the global model.Unlike synchronous SGD, ASGD imposes no barrier between workers.
  • ASGD process: A worker may compute g(w_t) at snapshot w_t while other workers update the global model to w_t+τ.The gradient is therefore delayed by τ intervening updates before being applied.
  • Delayed-gradient problem: ASGD applies the stale gradient g(w_t) directly to w_t+τ instead of using the gradient evaluated at the current model.The paper identifies this mismatch as problematic and inequivalent to sequential SGD.
  • Delayed-gradient problem: Delayed gradients can require ASGD to use more iterations than sequential SGD and can prevent accuracy parity, especially with many workers.

3. Delay Compensation using Taylor Expansion and Hessian Approximation

The paper bridges ASGD’s delayed gradient and the correct current gradient using Taylor expansion, then makes the Hessian term practical through gradient-based approximation and diagonalization.

  • Taylor Expansion: ASGD’s delayed gradient is the zero-order Taylor approximation to the correct gradient at the current global model.Higher-order terms capture the difference between the worker’s stale snapshot and the updated model.
  • Taylor Expansion: Full Taylor expansion is intractable, while first-order delay compensation requires the Hessian matrix of the loss function.The Hessian introduces substantial computation and storage costs for large neural networks.
  • Hessian Approximation: The outer product of gradients is an asymptotically unbiased Hessian estimator under the paper’s model-distribution and convergence assumptions.For cross-entropy loss with Softmax outputs, this follows from equivalent Fisher-information calculations.
  • Hessian Approximation: A weighted gradient outer product is introduced to trade off approximation bias and variance, with mean square error used to assess quality.The paper proves that an appropriately chosen weight can reduce MSE relative to the unweighted estimator.
  • Hessian Approximation: Diagonalizing the weighted estimator reduces storage by retaining only diagonal elements, while the paper provides a bound on diagonalization error.The resulting approximation is intended to remain cheap to compute and store.

4. Delay Compensated ASGD: Algorithm Description

DC-ASGD uses a diagonal gradient-based Hessian approximation to compensate stale gradients without adding worker communication or substantial worker computation.

  • Update Rule: DC-ASGD forms a delay-compensated gradient by adding a diagonal Hessian approximation term to the stale gradient.The approximation is expressed as λg(wt)⊙g(wt)⊙(wt+τ−wt).
  • Worker Workflow: Workers asynchronously pull the latest global model, compute local gradients, and push them to the parameter server.The workflow preserves the no-wait behavior of asynchronous training.
  • Parameter Server: The parameter server stores a backup model for each worker to track the model associated with delayed gradients.This backup supports computation of the model difference used for delay compensation.
  • Efficiency: Compared with ASGD, DC-ASGD adds no communication cost or extra local-worker computation, with only lightweight overhead at the parameter server.The additional storage is one backup model per worker, and the server is typically distributed.
  • Scope: The delay-compensation approach is also applicable to synchronous SGD for improving approximations that treat nearby gradients as equal.The paper notes this extension in connection with small- and large-mini-batch SGD updates.

5. Convergence Analysis

The analysis establishes convergence guarantees for DC-ASGD under smoothness, non-convexity, and bounded-delay assumptions, then compares its delay tolerance and convergence behavior with ASGD.

  • Assumptions: The convergence analysis focuses on the non-convex case and assumes smooth loss functions with bounded first-, second-, and third-order derivatives.
  • Assumptions: The analysis additionally assumes local strong convexity around each local optimum and twice differentiability of the loss.
  • Convergence guarantee: Under the stated assumptions, the theorem sets a learning rate based on mini-batch size, iteration count, smoothness, and the variance bound of the compensated gradient, with an upper-bounded delay.
  • Proof strategy: DC-ASGD uses a delay-compensated gradient based on an approximate Taylor expansion involving the Hessian and the model displacement during the delay.
  • Convergence guarantee: DC-ASGD has a convergence rate of order O(V/√T), and its convergence rate matches ASGD when λ lies within the specified variance-dependent range.
  • Comparison with ASGD: DC-ASGD tolerates delay better than ASGD under sufficiently large T and suitable Cλ, while λ trades extra compensation variance against Hessian-approximation bias.

6. Experiments

Experiments on CIFAR-10 and ImageNet compare DC-ASGD with sequential, synchronous, and asynchronous SGD using ResNet models. DC-ASGD combines accuracy comparable to or better than the baselines with convergence speed close to ASGD.

  • Experimental setup: Experiments evaluate DC-ASGD, ASGD, and SSGD on CIFAR-10 and ImageNet using GPU-cluster implementations and ResNet models.CIFAR-10 uses a 20-layer ResNet; ImageNet uses a 50-layer ResNet with 16 GPU nodes.
  • CIFAR-10 results: 8.65% was sequential SGD’s final CIFAR-10 test error, while DC-ASGD achieved 8.67% with DC-ASGD-c and 8.19% with DC-ASGD-a when M = 4.With M = 8, DC-ASGD-c reached 9.27% and DC-ASGD-a reached 8.57%.
  • CIFAR-10 results: 9.27% and 9.17% were the M = 4 CIFAR-10 test errors for ASGD and SSGD, increasing to 10.26% and 10.10% when M = 8.The passage attributes ASGD’s degradation to more serious delayed gradients and SSGD’s to enlarged effective mini-batches.
  • CIFAR-10 convergence: DC-ASGD provides a balance between accuracy and speed, converging at a rate similar to ASGD while reaching a convergent point as good as or better than sequential SGD.Delay compensation adds some computational and memory cost, but the convergence speed remains very similar to ASGD.
  • ImageNet results: 25.18% was DC-ASGD’s ImageNet eventual test error, below ASGD’s 25.64% and SSGD’s 25.30% after equal amounts of training data.With respect to wallclock time, ASGD and DC-ASGD had similar efficiency, while SSGD was slowed by synchronization.
  • ImageNet results: DC-ASGD’s ImageNet results show similar efficiency to ASGD because its additional delay-compensation overhead can almost be neglected in practice.The experiment trained a 50-layer ResNet on 1.28 million training images and 50,000 validation images.

7. Conclusion

The paper analyzes delayed gradients and proposes DC-ASGD to compensate for them. Evaluations on CIFAR-10 and ImageNet report better accuracy than synchronous and asynchronous SGD, approaching sequential SGD performance.

  • Contribution: The paper analyzes delayed gradients in asynchronous SGD and proposes Delay Compensated Asynchronous SGD to address them.The conclusion identifies DC-ASGD as the paper’s novel algorithmic contribution.
  • Findings: Experiments on CIFAR-10 and ImageNet show better accuracy than synchronous and asynchronous SGD, with performance nearly approaching sequential SGD.Future work includes testing larger clusters and approximating higher-order Taylor-expansion terms.

Supplementary Material: Asynchronous Stochastic Gradient Descent with

The supplementary analysis studies mean-squared error when gradient-derived quantities approximate the Hessian. It establishes algebraic conditions under which scaling the gradient approximation improves Hessian approximation.

  • MSE analysis: Under the stated condition, the MSE of λG(w_t) is smaller than the MSE of G(w_t) for approximating H(w_t).The result is presented after assuming the loss function is L1-Lipschitz and imposing the relevant inequality on λ.
  • MSE analysis: The analysis compares the mean-squared error of G(w_t) and λG(w_t) as approximations to the Hessian H(w_t).The notation abbreviates G_t as G(w_t) and H_t as H(w_t), examining each matrix element.
  • MSE analysis: The derivation substitutes inequalities involving class-conditional quantities to obtain a sufficient condition for the MSE comparison.The passage describes this as a sufficient condition rather than a necessary one.

B. Corollary 3.2 and Its Proof

The corollary gives a sufficient condition for the scaled gradient approximation to improve Hessian approximation. Its proof uses bounds on class probabilities and Hessian diagonalization error.

  • Corollary 3.2: A sufficient condition for the stated inequality is λ ∈ [0, 1] together with the existence of a class k0 satisfying the specified condition on σk0.The condition is given as Corollary 3.2.
  • Proof: The proof introduces Δ and a function F to bound the relevant expression over the class-specific σk values.The proof distinguishes one σ value near one from the remaining values bounded by Δ.
  • Proof: The supporting lemma assumes an L1-Lipschitz loss and bounds Hessian diagonalization error by ϵD, while V1 bounds the variance of G(w_t).These assumptions provide the error and variance quantities used in the convergence analysis.

D. Convergence Rate for DC-ASGD: Convex Case

For convex objectives, DC-ASGD is analyzed under smoothness and strong-convexity assumptions, with a convergence rate comparable in order to sequential SGD and improved over ASGD under a stated condition.

  • Convex-case setup: DC-ASGD is analyzed for convex losses by adding a regularization term under smoothness and strong-convexity assumptions.The analysis assumes f(w) is convex, L2-smooth, and μ-strongly convex, with a smooth gradient and bounded expected delay-compensated gradient.
  • Convergence comparison: DC-ASGD’s convergence rate has the same order as sequential SGD under the stated bounded-delay conditions.The theorem sets the learning rate as ηt = 1/(μt).
  • Convex-case setup: The delay-compensated gradient uses an approximation involving the local gradient, its elementwise square, and the parameter difference wt+τ − wt.This is the diagonal Hessian-style approximation used to compensate delayed updates.
  • Convergence comparison: Compared with ASGD, DC-ASGD’s additional error term decreases faster in t and can be neglected for sufficiently large t.The comparison leads to the condition L2 > Cλ for DC-ASGD to outperform ASGD.

E. Convergence Rate for DC-ASGD: Nonconvex Case

For nonconvex objectives, DC-ASGD is proved to achieve an ergodic convergence rate under bounded-delay and variance conditions, while tolerating delay better than ASGD in a stated regime.

  • Nonconvex assumptions: The nonconvex analysis assumes a bounded delay, bounded gradient variance, and a sufficiently large training horizon T.The stated condition is T ≥ max{O(1/r4), 2D0bL2/V2}.
  • Nonconvex convergence: DC-ASGD has an ergodic convergence rate for nonconvex objectives under the theorem’s assumptions.The result is expressed through the minimum expected gradient norm over t = 1,…,T.
  • Approximation behavior: After entering a strongly convex neighborhood of a local optimum, the approximation error decreases as 1/(t − T0).Before T0, the error is bounded by the maximum earlier error.

F. Decreasing rate of the approximation error ϵt

The approximation error is controlled through local strong-convexity and smoothness assumptions, while λ balances compensation accuracy against variance; the same delay-compensated gradient is also applied to large-batch synchronous SGD.

  • Error analysis: The approximation-error analysis assumes locally strong-convex neighborhoods around local optima and regularity conditions on the loss and predictive probabilities.These assumptions support bounding the discrepancy between the true and approximated Hessian-related terms.
  • Error analysis: For strongly convex objectives, the nonconvexity error vanishes and the local optimum equals the global optimum.This removes the corresponding error component from the convergence analysis.
  • Parameter behavior: The delay-compensation parameter λ must balance approximation strength against variance: λ0 > 2 caused large variance in the CIFAR-10 setting, while small λ made compensation nearly disappear.As λ decreases, DC-ASGD gradually degrades toward ASGD.
  • Large-batch synchronous SGD: In synchronous SGD, delay-compensated gradients are proposed to address the assumption that linearly scaling the learning rate with mini-batch size is valid.The method updates the large-batch procedure using the delay-compensated gradient.
  • Large-batch synchronous SGD: The Taylor approximation becomes more accurate when the updated parameter remains closer to wt.The relevant design criterion is minimizing ||wt+1 − wt||2.
Loading 1609.08326v6…