Zheng et al. (2016) — ARXIV-1609.08326
Key takeaways
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.
- 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.
What the evidence does not cover
- 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.
Standing in the anthology
Read — the reading is NOTE-097. Arrived in the imported batch, which brought in the asynchronous and bounded-delay branch of distributed training.