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.
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.
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