Asynchronous Distributed Optimization with Stochastic Delays

Margalit R. Glasgow, Mary WoottersAISTATS 2022 · OpenReview

Abstract

We study asynchronous finite sum minimization in a distributed-data setting with a central parameter server. While asynchrony is well understood in parallel settings where the data is accessible by all machines—e.g., modifications of variance-reduced gradient algorithms like SAGA work well—little is known for the distributed-data setting. We develop an algorithm ADSAGA based on SAGA for the distributed-data setting, in which the data is partitioned between many machines. We show that with $m$ machines, under a natural stochastic delay model with an mean delay of $m$, ADSAGA converges in $\tilde{O}((n + \sqrt{m}\kappa)\log(1/\epsilon))$ iterations, where $n$ is the number of component functions, and $\kappa$ is a condition number. This complexity sits squarely between the complexity of SAGA without delays and the complexity of parallel asynchronous algorithms where the data is accessible by all. We empirically demonstrate the wallclock advantage of variance-reduced asynchronous approaches over SGD or synchronous approaches.

The Challenge of Distributed Data

In large-scale machine learning, training is often distributed across multiple machines coordinated by a Parameter Server (PS). There are two primary architectural paradigms for this:

  1. Shared-data: Every machine can access the entire dataset (e.g., from a cloud bucket).
  2. Distributed-data: Data is partitioned; each machine only sees its local subset. This is the standard model for Federated Learning.
Comparison of data distribution architectures: (a) Shared Data, (b) Distributed Data with Central PS, and (c) Decentralized Distributed Data.

While asynchronous optimization—where machines update the PS without waiting for others—is well-understood for shared data, it is notoriously difficult to analyze for distributed data. Without the "i.i.d." assumption inherent in shared data, stale gradients from one machine can point in a significantly different direction than the global gradient, potentially leading to divergence. Previous provable rates for this setting were either very slow or required unrealistic assumptions.

ADSAGA: Variance Reduction for Asynchrony

To bridge this gap, we propose ADSAGA (Asynchronous Distributed SAGA). It builds on the SAGA algorithm, which maintains a table of past gradients to reduce the variance of stochastic updates, allowing for a constant learning rate and linear convergence.

Key Innovations

  • Stochastic Delay Model: Instead of assuming "arbitrary bounded delays" (which forces a pessimistic worst-case analysis), we use a stochastic model where machines communicate at random intervals. This captures the reality of heterogeneous hardware where some machines are occasionally much faster than others.
  • Novel Potential Function: To prove convergence, we developed a sophisticated mathematical "potential function." Beyond tracking the distance to the optimum, it includes a quadratic term that accounts for the dot product between the current error and the expected next stale gradient update.
  • Square Root Scaling: ADSAGA’s iteration complexity scales with $\sqrt{m}$ (the number of machines). This means as you add more machines, the "penalty" for asynchrony grows much slower than previously thought.

Empirical Performance and Scaling

We evaluated ADSAGA against several baselines, including asynchronous SGD, IAG, and synchronous minibatch SAGA. Our results focus on iteration complexity and wall-clock performance across various machine counts.

Iteration complexity until convergence (MSE < 0.1) versus the number of machines. ADSAGA (red crosses) shows superior scaling compared to distributed SGD and IAG.

Key Results

  • Theoretical Speedup: ADSAGA is the first result for distributed data that scales logarithmically with precision ($1/\epsilon$) and linearly with the dataset size ($n$).
  • Wall-clock Advantage: In cluster experiments with 30 machines, ADSAGA and IAG were over 60% faster than synchronous alternatives like minibatch SAGA or SGD.
  • Robustness: ADSAGA outperformed the state-of-the-art IAG algorithm in iteration complexity across various simulated delay distributions, including "heavy-tailed" scenarios common in real-world data centers.

Conclusion

ADSAGA demonstrates that fast, provable convergence is possible for variance-reduced methods in truly distributed-data settings. By leveraging a stochastic delay model, we achieve a $\sqrt{m}$ scaling that significantly improves upon previous theoretical bounds. Future work will explore if these rates hold in fully decentralized (peer-to-peer) networks and how variance reduction interacts with multiple local steps (Local-SGD) under stochastic delays.

Summary updated

Abstract

We study asynchronous finite sum minimization in a distributed-data setting with a central parameter server. While asynchrony is well understood in parallel settings where the data is accessible by all machines—e.g., modifications of variance-reduced gradient algorithms like SAGA work well—little is known for the distributed-data setting. We develop an algorithm ADSAGA based on SAGA for the distributed-data setting, in which the data is partitioned between many machines. We show that with $m$ machines, under a natural stochastic delay model with an mean delay of $m$, ADSAGA converges in $\tilde{O}\left(\left(n + \sqrt{m}\kappa\right)\log(1/\epsilon)\right)$ iterations, where $n$ is the number of component functions, and $\kappa$ is a condition number. This complexity sits squarely between the complexity $\tilde{O}\left(\left(n + \kappa\right)\log(1/\epsilon)\right)$ of SAGA without delays and the complexity $\tilde{O}\left(\left(n + m\kappa\right)\log(1/\epsilon)\right)$ of parallel asynchronous algorithms where the delays are arbitrary (but bounded by $O(m)$), and the data is accessible by all. Existing asynchronous algorithms with distributed-data setting and arbitrary delays have only been shown to converge in $\tilde{O}(n^2\kappa\log(1/\epsilon))$ iterations. We empirically compare on least-squares problems the iteration complexity and wallclock performance of ADSAGA to existing parallel and distributed algorithms, including synchronous minibatch algorithms. Our results demonstrate the wallclock advantage of variance-reduced asynchronous approaches over SGD or synchronous approaches.
BibTeX
@inproceedings{glasgow2022asynchronous,
  author = {Margalit R. Glasgow and Mary Wootters},
  title = {{Asynchronous Distributed Optimization with Stochastic Delays}},
  booktitle = {International Conference on Artificial Intelligence and Statistics},
  year = {2022},
  url = {https://openreview.net/forum?id=lyWB7f_tiXb},
}
Figure