Sharper Convergence Guarantees for Asynchronous SGD for Distributed and Federated Learning

Anastasia Koloskova; Sebastian U. Stich; Martin Jaggi

Source-linked AI summary

Sharper Convergence Guarantees for Asynchronous SGD for Distributed and Federated Learning

Anastasia Koloskova, Sebastian U. Stich, Martin Jaggi

arXiv:2206.08307v1Jun 16, 2022cs.LGcs.DCmath.OC

TL;DR

Asynchronous SGD avoids making workers wait for one another, but existing convergence guarantees can depend on the largest gradient delay. This paper sharpens the analysis and proposes a delay-adaptive stepsize; it reports faster-than-mini-batch performance across delay patterns when server operations take negligible time.

Problem
Existing asynchronous-SGD guarantees can depend on the maximum gradient delay, a pessimistic measure when delays vary, while heterogeneous-objective guarantees also depend on maximum delay.
Source: §1 · p. 2
Method
The paper analyzes asynchronous SGD using concurrency and proposes a delay-adaptive stepsize for homogeneous objectives that needs no extra tuning or communication.
Source: §4.4 · p. 7, §6 · p. 10
Results
Asynchronous SGD is faster than mini-batch SGD for any delay pattern when server operations take negligible time.
Source: §4.4 · p. 6
Takeaways & Limitations
The proposed stepsize achieves an average-delay-dependent convergence rate without extra tuning or communication.
Source: §4.4 · p. 7, §6 · p. 10
In heterogeneous settings, delay-adaptive learning rates can bias updates toward faster clients and make Algorithm 2 converge to the wrong objective.
Source: §5.3 · p. 9

Abstract

from arXiv · show

We study the asynchronous stochastic gradient descent algorithm for distributed training over $n$ workers which have varying computation and communication frequency over time. In this algorithm, workers compute stochastic gradients in parallel at their own pace and return those to the server without any synchronization. Existing convergence rates of this algorithm for non-convex smooth objectives depend on the maximum gradient delay $\tau_{\max}$ and show that an $\epsilon$-stationary point is reached after $\mathcal{O}\!\left(\sigma^2\epsilon^{-2}+ \tau_{\max}\epsilon^{-1}\right)$ iterations, where $\sigma$ denotes the variance of stochastic gradients. In this work (i) we obtain a tighter convergence rate of $\mathcal{O}\!\left(\sigma^2\epsilon^{-2}+ \sqrt{\tau_{\max}\tau_{avg}}\epsilon^{-1}\right)$ without any change in the algorithm where $\tau_{avg}$ is the average delay, which can be significantly smaller than $\tau_{\max}$. We also provide (ii) a simple delay-adaptive learning rate scheme, under which asynchronous SGD achieves a convergence rate of $\mathcal{O}\!\left(\sigma^2\epsilon^{-2}+ \tau_{avg}\epsilon^{-1}\right)$, and does not require any extra hyperparameter tuning nor extra communications. Our result allows to show for the first time that asynchronous SGD is always faster than mini-batch SGD. In addition, (iii) we consider the case of heterogeneous functions motivated by federated learning applications and improve the convergence rate by proving a weaker dependence on the maximum delay compared to prior works. In particular, we show that the heterogeneity term in convergence rate is only affected by the average delay within each worker.

1 Introduction

Asynchronous SGD lets workers compute and return gradients without waiting for one another, addressing idle time from stragglers. The paper tightens convergence analysis and introduces a delay-adaptive stepsize, then extends its analysis to heterogeneous objectives.

1 Introduction

Asynchronous workers start their next computation immediately after returning a gradient, avoiding the waits for the slowest worker required by synchronous rounds.The paper studies this approach for distributed and federated learning settings.Source: §1 · pp. 1–2
Prior non-convex asynchronous-SGD bounds depend on the maximum gradient delay, which can be overly pessimistic when a worker struggles only once.Earlier average-delay approaches also had restrictions, including extra communication or tuning, convex-only analysis, or bounded-gradient assumptions.Source: §1 · p. 2
The paper proves a tighter convergence rate for standard asynchronous SGD with constant stepsize on non-convex L-smooth homogeneous objectives.A separate rate is given under a bounded-gradient assumption.Source: §1 · p. 2
For homogeneous objectives, a delay-adaptive stepsize requires no extra hyperparameter tuning and supports the claim that asynchronous SGD is faster than mini-batch SGD.The comparison is stated to hold regardless of the delay pattern, subject to the server performing operations in negligible time.Source: §1 · p. 2
For heterogeneous objectives, the paper improves the prior dependence on maximum delay; its heterogeneity term depends on each worker’s average delay.The setting is motivated by federated learning applications.Source: §1 · p. 2

2 Related Work

Prior work studies asynchronous SGD and delay-adaptive methods, while asynchronous federated learning is motivated by clients with differing computing speeds. The paper situates its analysis among these strands.

2 Related Work

Prior asynchronous-SGD analyses often depend on maximum delay; work on tighter rates includes, while Nguyen et al. [37] removed the bounded-gradient assumption.The cited literature also covers coordinate-wise asynchrony, variance-reduced methods, and atomic worker-server communication.Source: §2 · p. 3
Earlier delay-adaptive methods often still depend on maximum delay; Cohen et al. [14] and Aviv et al. [8] obtained average-delay rates for non-convex and convex settings, respectively.Mishchenko et al. studied a concurrency-dependent scheme but not constant-stepsize asynchronous SGD or the bounded-gradient case.Source: §2 · p. 3
Asynchronous federated learning is appealing when clients have different computing speeds, and many methods address unequal participation with server-side variance reduction.Nguyen et al. [36] introduced FedBuff and reported practical superiority over classical synchronous federated-learning algorithms.Source: §2 · p. 3

3 Setup

The setup distributes objective-function components across nodes and lets each node access its local loss through stochastic gradients. The analysis states regularity and boundedness assumptions and describes asynchronous server-worker updates.

3 Setup

The objective’s components are distributed across n nodes or clients, each with access to its local loss function.A local function is expressed as an expectation of a stochastic function; the setup also covers deterministic optimization and empirical risk minimization.Source: §3 · p. 3
The analysis uses bounded-variance, bounded-function-heterogeneity, and L-smoothness assumptions, with bounded gradients required only for some results.The heterogeneity assumption assigns a parameter ζ_i to each node.Source: §3 · pp. 3–4
Workers compute gradients in parallel at assigned points and send completed, potentially delayed gradients to the server, which updates the model using a stepsize that may depend on delay.The server then selects inactive workers to receive the updated point.Source: §3 · p. 4

4 Homogeneous Distributed Setting

The section analyzes asynchronous SGD for homogeneous objectives, first tightening constant-step convergence bounds and then introducing delay-adaptive stepsizes. It relates these guarantees to mini-batch SGD and practical delay patterns.

4 Homogeneous Distributed Setting

The homogeneous setting assumes identical worker objectives, as in identically distributed data, and simplifies the analysis by setting the heterogeneity parameter to zero.The authors also describe this setting as common in datacenter training where nodes share the dataset or data distribution.Source: §4 · p. 4

4.1 Algorithm

Workers compute gradients at their own pace from assigned iterates; the server applies possibly delayed gradients and assigns the latest iterate to newly active workers.The analysis tracks the active-worker set, whose size is the concurrency; mini-batch SGD is included as a special case.Source: §4.1 · pp. 4–5

4.2 Theoretical analysis: Constant stepsizes

With constant stepsizes, the delay term improves from τmax to √(τavgτmax) without changing the algorithm; bounded gradients remove its dependence on τmax entirely.The authors note that the improved dependence can matter when rare stragglers make maximum delay much larger than average delay.Source: §4.2 · p. 6, §4.4 · p. 7

4.3 Theoretical analysis: Delay-adaptive stepsizes

The delay-adaptive rule reduces stepsizes for gradients delayed beyond τC, removing dependence on τmax without requiring bounded gradients.For τt > τC, the stepsize may be any value between zero and min{η, 1/(4Lτt)}.Source: §4.3 · p. 6

4.4 Discussion

Asynchronous SGD with delay-adaptive stepsizes matches mini-batch SGD’s convergence rate while avoiding worker waits, and unlike PickySGD [14] requires no extra communication or tuning.The comparison assumes the server performs its operations in negligible time.Source: §4.4 · pp. 6–7

5 Heterogeneous Distributed Setting

The heterogeneous setting models clients with different local objectives, motivated by federated learning, and analyzes asynchronous client sampling under concurrency. Its discussion gives delay-dependent guarantees and compares asynchronous with synchronous mini-batch training.

5.1 Algorithm

Algorithm 2 keeps concurrency constant and samples a client uniformly from all clients after each update, allowing a client to be sampled again while earlier jobs remain unfinished.The active-worker set is therefore a multiset, and jobs may pile up on a client.Source: §5.1 · pp. 7–8

5.2 Theoretical analysis

With one client’s gradient applied per step, the leading 1/ε² term is affected by heterogeneity ζ², as is usual in federated learning with client subsampling.The analysis assumes the average delay for each client is independent of how often that client is sampled.Source: §5.2 · p. 8

5.3 Discussion

Under bounded gradients, Theorem 11 removes dependence on the maximum delay; without delay assumptions, the heterogeneity term depends on each client’s average delay.When client heterogeneity is equal, that term depends only on the overall average delay.Source: §5.3 · p. 9
For heterogeneous objectives, delay-adaptive stepsizes could bias updates toward faster clients and make Algorithm 2 converge to the wrong objective; practical investigation is left for future work.The text notes that waiting for a percentage of sampled clients and discarding the rest also favors fast workers.Source: §5.3 · p. 9
When clients’ delays are independent of client identity, Algorithm 2 can remove maximum-delay dependence without a bounded-gradient assumption, and delay-adaptive stepsizes are also possible.The passage gives this as a special case of the heterogeneous setting.Source: §5.3 · p. 9

5.4 Estimating Speedup over Synchronous SGD

For 1,000 clients—900 computing in 10 seconds and 100 in 60 seconds—10 asynchronous gradients take 15 seconds in expectation, versus 42.5 seconds for synchronous mini-batch SGD.The comparison uses concurrency τC = 10.Source: §5.4 · p. 10

6 Conclusion

The conclusion presents asynchronous SGD as improving delay dependence in both homogeneous and heterogeneous settings. It also reports a delay-adaptive stepsize result and a speed comparison with mini-batch SGD.

6 Conclusion

The paper reports that asynchronous SGD is faster than mini-batch SGD for any delay pattern.The authors state that this conclusion follows from their techniques.Source: §6 · p. 10
A simple delay-adaptive stepsize rule yields a rate depending only on average delay and requires neither additional tuning nor communication.The conclusion identifies this result across the paper’s asynchronous SGD analysis.Source: §6 · p. 10
The analysis improves dependence on maximum delay for asynchronous SGD with both homogeneous and heterogeneous objectives.The conclusion states that concurrency is leveraged in obtaining the improved rates.Source: §6 · p. 10

A.1 Proof of Remark 5

The proof tracks the delays of active workers and relates average concurrency to average delay. This relation is the key observation established in the section.

A.1 Proof of Remark 5

The proof defines an active worker’s delay by the difference between the current iteration and when that worker started its current gradient computation; initial workers have delay one.Newly selected workers begin with delay zero, while active workers’ delays increase with each iteration.Source: §A.1 · p. 14
When a gradient is applied, its delay moves out of the active-worker delay total, which the proof tracks alongside the sum of applied-gradient delays.The accounting uses the delay update at each iteration.Source: §A.1 · p. 14
The proof equates the left-hand side with (T + |C_T| − 1)τ_avg, then gives τ_avg = (T + 1)/(T + |C_T| − 1) times average concurrency and O(average concurrency) when T > |C_T|.Source: §A.1 · p. 14

A.3 Proof of Theorems 6, (8) and 8

The appendix proves the paper’s convergence results using descent and residual bounds. For delay-adaptive stepsizes, it also specifies a delay-dependent schedule, while another proof uses a virtual iterate sequence.

A.3 Proof of Theorems 6, (8) and 8

With bounded gradients, the proof invokes an additional convergence bound for the constant-stepsize result.The supplied passage states the bounded-gradient condition but does not expose the bound’s full expression.Source: §A.3 · p. 15

A.3.2 Proof of Theorem 8

Theorem 8 uses delay-adaptive stepsizes: η_t is capped by η when τ_t ≤ τ_C and by min{η, 1/(4Lτ_t)} when τ_t > τ_C.The proof sums the descent inequality and applies a residual bound for this schedule.Source: §A.3 · p. 15, §A.3.2 · pp. 17–18

A.3.1 Proof of Theorem 6, convergence rate (8)

For Theorem 6’s rate (8), the residual lemma uses constant stepsize η ≤ 1/(2L√(τ_maxτ_C)) before the proof selects η to obtain the stated rate.The proof first bounds the residual, then averages the descent inequality and tunes the stepsize.Source: §A.3.1 · pp. 16–17

A.4 Proof of Theorem 6, convergence rate (9)

For Theorem 6’s rate (9), the proof introduces a virtual sequence indexed by when each gradient computation began, then uses it in the descent analysis.The sequence is not accessible during Algorithm 1’s execution.Source: §A.4 · pp. 18–19

A.5 Proof of the Theorem 11

The proof establishes Theorem 11 guarantees for Algorithm 2 under stated assumptions and uses a perturbed-iterate sequence to analyze delayed updates.

Theorem 11 gives a constant-stepsize guarantee for Algorithm 2 under Assumptions 1, 2, 3, and 5.Source: §A.5 · p. 20
The cited passage states that a result holds under Assumptions 1, 2, and 3, together with the additional bounded-gradient Assumption 4.Source: §A.5 · p. 20
The proof introduces a virtual iterate and defines the future gradient delay so that j − τ_j = t.The corresponding gradient is computed with delay ˆτ_t, and j = t + ˆτ_t.Source: §A.5 · p. 20
A descent lemma applies under Assumptions 1, 2, and 3 when the stepsize is at most 1/(4L).Source: §A.5 · p. 20

A.5.1 Proof of Theorem 11, convergence rate (14)

This proof develops a distance estimate for the convergence-rate result and combines it with an averaged descent bound.

The distance estimate for Algorithm 2 is stated for stepsizes at most 1/(4L√(τ_Cτ_max)) under Assumptions 1, 2, and 3.Source: §A.5.1 · p. 21
Uniform sampling in Algorithm 2 makes the expected number of times each node is sampled equal.Source: §A.5.1 · p. 21
The proof averages the descent lemma and substitutes the distance estimate before tuning the stepsize.Source: §A.5.1 · p. 21

A.5.2 Proof of Theorem 11, convergence rate (15).

This section proves the bounded-gradient convergence-rate statement and compares expected execution times for asynchronous and mini-batch SGD at concurrency C.

A.5.2 Proof of Theorem 11, convergence rate (15).

Lemma 21 states a distance estimate for Algorithm 2 under Assumptions 1, 2, 3, and 4, with constant stepsize ηt ≡ η ≤ 1/(4LτC).Source: §A.5.2 · p. 22
The proof obtains the theorem statement by averaging the descent lemma, substituting the distance estimate, and tuning the stepsize.Source: §A.5.2 · p. 22

A.6 Proof of Lemma 12

The asynchronous execution-time analysis models concurrency C as C independent copies of the single-process algorithm running in parallel.Source: §A.6 · p. 22
For mini-batch SGD with batch size C, expected execution time is the expected maximum of C independently sampled workers’ computation times.Source: §A.6 · p. 22

B Experiments

The experiments test how iteration count varies with maximum delay on quadratic and logistic-regression functions. In both cases, T scales linearly with √τ_max.

With stochastic noise set to zero and concurrency τ_C = 2, the experiments vary the second worker’s relative speed to change τ_max.The relative speed is varied by making the second worker x times slower than the first, giving τ_max = x.Source: B Experiments · p. 23
The experiments use a random quadratic function and a logistic-regression function to test the predicted delay dependence.Source: B Experiments · p. 23
T has a linear dependence on √τ_max for both the quadratic and logistic-regression experiments.The figures report the quadratic and logistic-regression cases, respectively.Source: B Experiments · p. 23, Figure 1 · p. 24, Figure 2 · p. 24