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:
- Shared-data: Every machine can access the entire dataset (e.g., from a cloud bucket).
- Distributed-data: Data is partitioned; each machine only sees its local subset. This is the standard model for Federated Learning.
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.
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