Contribution
Proposes DC-ASGD, which corrects delayed gradients in asynchronous SGD using a first-order Taylor expansion of the gradient function approximated with a cheap diagonal Hessian estimator (scaled outer product of past gradients). This closes much of the accuracy gap between ASGD and sequential SGD while preserving ASGD’s speed advantages.
Key insight
The stale gradient g(w_t) used in ASGD is merely the zero-order approximation of the correct gradient g(w_{t+tau}); adding a first-order Taylor correction term—approximating the Hessian via a scaled diagonal of the gradient outer product—substantially reduces the bias introduced by delay without extra communication cost.
Assumptions
- Objective function Q(w) is L-smooth (Lipschitz continuous gradient).
- Stochastic gradients are unbiased with bounded variance: E[g] = ∇Q(w), Var[g] ≤ V.
- Delay tau is bounded: there exists a maximum delay tau_max such that all worker delays are ≤ tau_max.
- Diagonal Hessian approximation introduces bounded diagonalization error epsilon_D.
- Non-convexity error epsilon_nc is bounded (hard to quantify in practice).
- Lambda is chosen such that the variance introduced by the correction term remains controlled.
Key results
- Theorem 1 (DC-ASGD convergence). DC-ASGD converges at the same asymptotic rate O(V/sqrt(T)) as standard ASGD for non-convex smooth objectives, while tolerating delays by a factor of T/C_0 larger than ASGD can. Holds when: Requires L-smooth objective, bounded gradient variance V, bounded delay tau_max, and T ≥ C_0 where C_0 is a constant depending on problem parameters.
- Empirical result (CIFAR-10, 4 workers). DC-ASGD-a achieves 8.19% test error vs. 9.27% for ASGD and 8.65% for sequential SGD on ResNet-20. Holds when: 4 asynchronous workers, parameter-server architecture, ResNet-20 on CIFAR-10.
Claims
| id | claim | strength | support |
|---|---|---|---|
| C1 | DC-ASGD converges at the same asymptotic rate O(V/sqrt(T)) as ASGD for non-convex objectives but tolerates larger delays by a factor of T/C_0. | moderate | Formal convergence theorem (Section 5) with proof in appendix; delay tolerance improvement derived analytically under smoothness and bounded-delay assumptions. |
| C2 | On CIFAR-10 with 4 workers, DC-ASGD-a achieves 8.19% test error, matching or beating sequential SGD (8.65%) while ASGD reaches only 9.27%. | strong | Controlled experiment on ResNet-20, same initialization and schedule; results in Table 1. |
| C3 | DC-ASGD incurs negligible extra computational and communication overhead compared to ASGD. | strong | No additional communication needed; only a lightweight elementwise operation at the parameter server per update (Eq. 10); empirically similar wall-clock curves in Figures 3-4. |
Method
DC-ASGD (Delay Compensated ASGD).
Workers operate identically to standard ASGD: pull current model w_t, compute gradient g_m, push gradient to server. The parameter server stores a backup snapshot w_bak(m) of the model sent to each worker m. When the delayed gradient g_m arrives, the server applies a compensated update: w_{t+1} = w_t - eta * (g_m + lambda * g_m elementwise_square * (w_t - w_bak(m))). The correction term approximates H(w_t)(w_{t+tau} - w_t) using a diagonal Hessian estimate lambda * g elementwise_square. The hyperparameter lambda trades off bias and variance of the Hessian approximation; it can be constant or adapt via a running mean-square of gradients.
- Taylor expansion of gradient function to first order in the weight change
- Diagonal Hessian approximation via scaled outer product of gradient (lambda * g odot g)
- Parameter server backup model w_bak(m) per worker to compute weight delta
- Variance-control hyperparameter lambda (tuned or annealed via RMSProp- style running average)
Concepts
- Delayed gradient — The gradient g(w_t) computed at model snapshot w_t but applied to a later model w_{t+tau} because tau other updates occurred during communication; the central pathology of ASGD.
- Delay factor tau — Number of global model updates that occur between when a worker reads the model and when its gradient is applied; grows with the number of workers.
- Diagonal Hessian approximation — Approximation of the full Hessian matrix by lambda * Diag(g(w) outer_product g(w)), storing only n scalars; unbiased when the model is near optimum and the network output is confident.
Connections
Builds on.
- Hogwild!: A Lock-Free Approach to Parallelizing Stochastic Gradient Descent (LIT-279) — Adopts the asynchronous parameter-server framework from Hogwild! and addresses the delayed-gradient degradation that Hogwild! analysis assumes is small under sparsity.
- Large Scale Distributed Deep Networks (Dean et al., 2012) — Identifies the delayed gradient problem in the DistBelief ASGD system that DC-ASGD directly solves.
Related.
- Asynchronous stochastic gradient descent with decoupled backpropagation and layer-wise updates (LIT-374) — Cites DC-ASGD as a prior delay- compensation approach and claims layer-wise updates eliminate the need for gradient compensation entirely.
Recommendations
- R1 — Use DC-ASGD in place of standard ASGD when training deep networks across many workers to recover accuracy lost to gradient delay; set lambda via a running mean-square of gradients (DC-ASGD-a variant). Topic: asynchronous distributed training · Strength: strong · When: Parameter-server architecture; works best when number of workers is moderate (4-16 GPUs); requires storing one additional model copy per worker on the server.
- R2 — Tune lambda in [1-(L2-L3*pi)/L1^2, 1] for non-convex problems; too large lambda inflates gradient variance and can diverge, while lambda=0 reduces to plain ASGD. Topic: hyperparameter tuning · Strength: moderate · When: Applies when using the constant-lambda variant (DC-ASGD-c); the adaptive variant (DC- ASGD-a) is more robust to lambda choice.
Bearing on the record
A correction for stale gradients rather than a scheme for avoiding them. No practice here recommends asynchronous SGD, so this bears on the record as the thing that would have to be true for one to be recommendable.
Limitations
- Requires the parameter server to store one backup model per worker, increasing server memory by a factor proportional to the number of workers.
- Diagonal Hessian approximation introduces diagonalization error epsilon_D that can degrade compensation quality for non-diagonal-dominant Hessians.
- Convergence tolerance bound includes a non-convexity error epsilon_nc that is hard to quantify in practice.
- Analysis assumes bounded delay tau; accuracy gains over ASGD are guaranteed only when T >= C_0, a potentially large constant.
Open questions
- Can higher-order Taylor terms (cubic correction) yield further accuracy improvement over DC-ASGD, and at what computational cost?
- How does DC-ASGD perform with very large numbers of workers (e.g., hundreds) where delay grows proportionally?
- Can the diagonal Hessian approximation be replaced by a low-rank or structured estimate to improve compensation accuracy?