Delay-Adaptive Distributed Stochastic Optimization

Zhaolin Ren, Zhengyuan Zhou, Linhai Qiu, Ajay Deshpande, Jayant KalagnanamAAAI 2020 · OpenReview

Abstract: In large-scale optimization problems, distributed asynchronous stochastic gradient descent (DASGD) is a commonly used algorithm. In most applications, there are often a large number of computing nodes asynchronously computing gradient information. As such, the gradient information received at a given iteration is often stale. In the presence of such delays, which can be unbounded, the convergence of DASGD is uncertain. The contribution of this paper is twofold. First, we propose a delay-adaptive variant of DASGD where we adjust each iteration's step-size based on the size of the delay, and prove asymptotic convergence of the algorithm on variationally coherent stochastic problems, a class of functions which properly includes convex, quasi-convex and star-convex functions. Second, we extend the convergence results of standard DASGD, used usually for problems with bounded domains, to problems with unbounded domains. In this way, we extend the frontier of theoretical guarantees for distributed asynchronous optimization, and provide new insights for practitioners working on large-scale optimization problems.

1. Introduction

Distributed asynchronous stochastic gradient descent (DASGD) is a cornerstone of modern large-scale machine learning, enabling parallel computation across numerous worker nodes. However, these systems frequently encounter "stale" gradients—updates calculated based on outdated model parameters due to network latency or hardware variability. While most theoretical frameworks assume these delays are strictly bounded, real-world "volunteer" computing grids often face arbitrary or growing delays that can cause standard algorithms to diverge. This paper introduces a delay-adaptive framework that ensures convergence even under massive, unbounded delays and extends these guarantees to unbounded search spaces.

2. Methodology

The authors propose two primary innovations to enhance the robustness of DASGD: a dynamic step-size adjustment and a truncation strategy for unbounded domains.

2.1 Delay-Adaptive Step-size

Instead of a fixed or purely time-decaying learning rate, the authors introduce a step-size $\alpha_{n+1}$ that incorporates the actual delay $s(n)$ of the received gradient. By scaling the step-size by a factor related to $n^c(\log(n)/\log s(n))$, the algorithm automatically reduces the influence of extremely stale gradients. This ensures that "bad" information from long-delayed updates does not push the model away from the optimal solution, while allowing the algorithm to behave normally when delays are small.

2.2 DASGD-T: Truncation for Unbounded Domains

To handle optimization problems where the domain is not restricted to a compact set, the authors introduce DASGD-T. This variant utilizes a "random truncation" technique, maintaining an expanding series of "safe zones." If a noisy or delayed update moves the model parameters outside the current safe zone, the algorithm resets the model to a known starting point and expands the zone for the next phase. This prevents the model from diverging to infinity due to the combination of noise and delay.

Convergence of DASGD-T on an unbounded domain, illustrating the truncation and reset mechanism at approximately $10^5$ steps.

3. Experimental Results

The effectiveness of the delay-adaptive approach was validated using both mathematical test functions (Rosenbrock) and real-world benchmarks (MNIST).

3.1 Stability Under Extreme Delay

In experiments simulating exponential delays—where gradients become progressively more stale at an accelerating rate—standard DASGD implementations typically diverge. The delay-adaptive version, however, demonstrates consistent stability and convergence. On the MNIST dataset, this robustness translated to a significant performance gap: the delay-adaptive method achieved 89.2% accuracy, whereas the standard non-adaptive version dropped to 57.5% under the same extreme delay conditions.

Smooth convergence of the delay-adaptive algorithm under simulated network delays, showing both sample values and their average.

3.2 Theoretical Generalization

A key theoretical insight of the paper is the proof of convergence for Variationally Coherent (VC) problems. This class of functions is broader than standard convexity, encompassing quasi-convex and star-convex functions. This generalization is crucial for applying these theoretical results to the complex, non-convex landscapes often encountered in deep learning.

4. Conclusion

This work provides a robust theoretical and practical foundation for distributed optimization in unpredictable network environments. By adapting the learning rate to observed delays and employing a truncation strategy for unbounded domains, the proposed DASGD variants offer guaranteed convergence for a wide class of objective functions, bridging the gap between theoretical optimization and large-scale distributed systems.

Summary updated

Abstract

In large-scale optimization problems, distributed asynchronous stochastic gradient descent (DASGD) is a commonly used algorithm. In most applications, there are often a large number of computing nodes asynchronously computing gradient information. As such, the gradient information received at a given iteration is often stale. In the presence of such delays, which can be unbounded, the convergence of DASGD is uncertain. The contribution of this paper is twofold. First, we propose a delay-adaptive variant of DASGD where we adjust each iteration's step-size based on the size of the delay, and prove asymptotic convergence of the algorithm on variationally coherent stochastic problems, a class of functions which properly includes convex, quasi-convex and star-convex functions. Second, we extend the convergence results of standard DASGD, used usually for problems with bounded domains, to problems with unbounded domains. In this way, we extend the frontier of theoretical guarantees for distributed asynchronous optimization, and provide new insights for practitioners working on large-scale optimization problems.
BibTeX
@inproceedings{ren2020delay,
  author = {Zhaolin Ren and Zhengyuan Zhou and Linhai Qiu and Ajay Deshpande and Jayant Kalagnanam},
  title = {{Delay-Adaptive Distributed Stochastic Optimization}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2020},
  url = {https://openreview.net/forum?id=dQ8cnqjc_t},
}
Figure