Clipping Makes Distributed and Federated Asynchronous SGD Robust to Stragglers
Samuel Erickson 1 Mikael Johansson 1
arXiv:2606.13287v1 [cs.LG] 11 Jun 2026
Abstract
workers are present when there is heterogeneous hardware or network latency. In some settings, workers may even drop out entirely due to network issues.
In modern machine learning, parallelization of training is an important strategy for increasing scale. Asynchronous stochastic gradient descent (ASGD), which maximizes the utilization of available hardware by avoiding waiting for slow workers. However, with constant step sizes, the convergence of ASGD is nonetheless affected negatively by slow workers due to large delays in updates. At the same time, it has been empirically observed in asynchronous training of deep learning models that gradient clipping “stabilizes” training. In this work, we provide a theoretical justification for this behavior, as we show that clipping removes the dependence of the maximum delay in the oracle complexity. We employ a sub-Weibull model of gradient noise which generalizes sub-Gaussian and sub-exponential distributions to more heavytailed distributions, motivated by empirical observations in deep learning. We show convergence in expectation, and the first time in asynchronous optimization, convergence with high probability.
To increase worker utilization and decrease idling, it is natural to consider removing locking, resulting in asynchronous SGD (ASGD) (Nedić et al., 2001; Tsitsiklis et al., 2003; Feyzmahdavian et al., 2016; Nguyen et al., 2018). Introducing asynchrony can substantially increase gradient throughput compared to Minibatch SGD, but it does introduce a new challenge: stale gradients. That is, instead of slowing down per-iteration run-time, stragglers slow down convergence due to the noise in their updates that arise from large delays in gradient computations. Both empirically and theoretically, the convergence of “vanilla” ASGD with constant step size is slowed down by a large maximum delay (Koloskova et al., 2022; Wu et al., 2022). For this reason, several works have proposed variants of ASGD where the contributions from workers with large delays are de-emphasized, to obtain convergence rates that are independent of the maximum delay. However, it was proved by Mishchenko et al. (2022) and Koloskova et al. (2022) that vanilla ASGD is in fact independent of the maximum delay when the gradients are globally bounded. This naturally raises the following question: Does gradient clipping remove the effect of the maximum delay, making Clipped ASGD robust to stragglers?
1. Introduction In recent years, parallelism has become the primary strategy to accommodate the increasing scale of machine learning models and the datasets used to train them. The classical parallel distributed optimization algorithm for general machine learning is Minibatch SGD. However, synchronization in Minibatch SGD means model updates cannot proceed until all workers have finished, leading to faster workers idling. This means that iterations are only as fast as the slowest worker. If computation times are uniform across workers, this is not a problem, but in many real-world settings this is far from being the case. For instance, these straggler
If clipping can be shown to provide robustness against the effect of stragglers, it may explain some previously unexplained empirical behavior. Chen et al. (2016) found that in training large deep learning models, gradient clipping was necessary to “stabilize” asynchronous training, but was not necessary for synchronous training. For heterogeneous optimization (e.g., federated learning) this may also be particularly significant. Since delay-adaptive strategies are biased toward faster workers, they do not converge to a stationary point in the heterogeneous data case. Can we use clipping to make training robust to stragglers without introducing a bias?
1 School of EECS, KTH Royal Institute of Technology, Stockholm, Sweden. Correspondence to: Samuel Erickson <[email protected]>.
For these reasons, the focus of this work is to provide convergence guarantees for Clipped ASGD that are robust to stragglers. Moreover, in the asynchronous setting, high probability guarantees are especially interesting, as guaran-
Proceedings of the 43 𝑟 𝑑 International Conference on Machine Learning, Seoul, South Korea. PMLR 306, 2026. Copyright 2026 by the author(s).
1
Clipping Makes Asynchronous SGD Robust to Stragglers
√ 𝑂 (𝜎 2 /𝜀 4 + 𝜏max 𝜏𝐶 /𝜀 2 ) complexity in the smooth nonconvex case, where 𝜏𝐶 is the number of active workers, i.e., the concurrency.
tees in expectation do not capture the behavior of a single or few runs. Doing several runs is of course antithetical to the point of introducing asynchrony, which is to more effectively utilize available hardware. Despite this, there are to the best of our knowledge no prior results showing high probability convergence under asynchrony. Therefore, we focus on providing guarantees with high probability in addition to guarantees in expectation.
To mitigate the adverse effects of stragglers, several works have explored delay-adaptive optimization algorithms (McMahan & Streeter, 2014; Sra et al., 2016; Zhang et al., 2016; Zheng et al., 2017; Hannah & Yin, 2018; Cohen et al., 2021; Mishchenko et al., 2022; Koloskova et al., 2022; Wu et al., 2022). Picky SGD, proposed by Cohen et al. (2021), was the first ASGD variant to achieve the complexity 𝑂 (𝜎 2 /𝜀 4 + 𝜏𝐶 /𝜀 2 ), completely removing the dependence on the maximum delay. They achieved this by discarding gradients that are excessively stale. Mishchenko et al. (2022); Koloskova et al. (2022); Wu et al. (2022) later showed that it is also possible to achieve this by adapting the step size online using the realized delays. Extending the theory to incorporate time complexity, (Maranjyan et al., 2025) showed that by dropping gradients that exceed a certain delay, it is possible to achieve the optimal time complexity.
Contributions. The main contributions of this work are two-fold and are as follows: • We show that Clipped ASGD is robust to stragglers under a gradient noise model which allows us to model the heavy tails seen in deep learning. Specifically, we obtain rates that do not depend on the maximum delay in both the homogeneous and heterogeneous cases. For the heterogeneous case, this is to the best of our knowledge the first asynchronous optimization algorithm that is independent of the maximum delay, suggesting that clipping is beneficial in asynchronous federated learning where severe stragglers are often present.
Another recent development is asynchronous federated learning (FL). Due to the heterogeneity in hardware capabilities, network latencies, and size of local datasets among workers, severe stragglers are common in cross-device FL, making asynchrony very attractive. It has been shown in large production FL deployments that asynchronous training can lead to substantial speed-ups and reductions in communication overhead (Huba et al., 2022). An early asynchronous FL method is FedAsync (Xie et al., 2020), which was shown to outperform synchronous FL when the maximum staleness was small. Koloskova et al. (2022) also studied a federated variant of ASGD, showing a similar oracle complexity as vanilla ASGD in the homogeneous case. In order to make asynchronous training compatible with privacy mechanisms, Nguyen et al. (2022) propose FedBuff which uses buffered aggregation. Wang et al. (2023) take a control variate approach with their method CA2 FL to reduce the effect of data heterogeneity. Recently, (Maranjyan & Richtárik, 2026) proposed Ringleader ASGD, which achieves the optimal time complexity under data heterogeneity.
• We show that Clipped ASGD converges with high probability with a polylogarithmic dependence on the failure probability, where the degree depends on the tail parameter of the gradient noise. This is to the best of our knowledge the first result showing high probability convergence of an asynchronous optimization algorithm.
2. Related work Asynchronous optimization. Asynchronous optimization for machine learning has gained much interest since the works of Agarwal & Duchi (2011), Recht et al. (2011) and Dean et al. (2012) due to the increasing size of models and the datasets they are trained on. However, asynchrony in optimization is not a new idea (cf. Bertsekas & Tsitsiklis, 1989). Asynchronous gradient descent and SGD date back to at least the works of Nedić et al. (2001) and Tsitsiklis et al. (2003), respectively.
In Table 1, we summarize the oracle complexities of related works and ours. For current surveys on asynchronous and parallel optimization, see Ben-Nun & Hoefler (2019) and Feyzmahdavian & Johansson (2023).
Feyzmahdavian et al. (2016) proved an oracle complex2 ity of 𝑂 (𝜎 2 /𝜀 2 + 𝜏max /𝜀) for smooth convex objectives, where 𝜏max is the maximum delay. Mania et al. (2017) later introduced perturbed iterate analysis for studying the convergence of asynchronous stochastic optimization, which Stich & Karimireddy (2020) adopted in order to improve the complexity. They showed a 𝑂 (𝜎 2 /𝜀 2 + 𝜏max /𝜀) complexity for smooth convex objectives, and a 𝑂 (𝜎 2 /𝜀 4 + 𝜏max /𝜀 2 ) complexity for smooth non-convex objectives. Similarly, Koloskova et al. (2022) used perturbed iterate analysis but on another virtual sequence to further improve the complexity. They show that ASGD with constant step size achieves
Gradient clipping. Gradient clipping is a widely used heuristic for dealing with instability in optimization, with Alber et al. (1998) being an early work making use of this technique. Mai & Johansson (2021) showed that gradient clipping can significantly improve the stability of SGD for non-smooth convex functions with rapidly growing sub-gradients. For non-convex learning, Mikolov et al. 2
Clipping Makes Asynchronous SGD Robust to Stragglers Table 1. Oracle complexities (up to polylogarithmic factors) for homogeneous and heterogeneous smooth non-convex optimization. Here 𝜏𝐶 is the concurrency and 𝜏max is the maximum delay, which is always larger than 𝜏𝐶 .
Algorithm
Homogeneous
Vanilla ASGD (Koloskova et al., 2022)
√
𝜎2 𝜀4 +
𝜏max 𝜏𝐶 𝜀2
Heterogeneous 𝜎 2 +𝜁 2 + 𝜁𝜀𝜏3𝐶 + 𝜀4
√
𝜏max 𝜏𝐶 𝜀2
Delay-adaptive ASGD (Cohen et al. 2021; Koloskova et al. 2022; Mishchenko et al. 2022)
𝜏𝐶 𝜎2 𝜀4 + 𝜀2
N/A
FedBuff (Nguyen et al. 2022; Wang et al. 2023)
N/A
𝜎 2 +𝜁 2 𝜏𝐶 + 𝜏max 𝜀4 𝜀2
Clipped ASGD (This work)
𝜎 𝜏𝐶 𝜏𝐶 𝜎2 𝜀4 + 𝜀3 + 𝜀2
𝜎 2 +𝜁 2 ) 𝜏𝐶 + ( 𝜎+𝜁 + 𝜏𝜀𝐶2 𝜀4 𝜀3
(2012) and Pascanu et al. (2013) proposed gradient clipping for dealing with the so-called exploding gradient problem. Later, Zhang et al. (2020b) provided a theoretical justification for using clipping in this context. By generalizing the standard smoothness assumption to (𝐿 0 , 𝐿 1 )-smoothness, they showed that gradient clipping may enable the use of significantly larger step sizes. Zhang et al. (2020a) then improved upon the dependence on problem-specific parameters and allowed for momentum. However, Zhang et al. (2020a;b) both used the strong uniformly bounded gradient noise model. Relaxing to the standard bounded variance model, Koloskova et al. (2023) showed that Clipped SGD may still enjoy large step sizes, but has a relatively large irreducible error term.
bounds and high-probability convergence. Taking another approach to modeling heavy tails, Li & Liu (2022) and Madden et al. (2024) adopted a sub-Weibull (Vladimirova et al., 2020) noise assumption, and showed high probability convergence of Clipped SGD. In privacy-preserving machine learning, clipping also plays a structural role rather than a purely optimization-oriented one. Early work on differentially private empirical risk minimization and stochastic optimization explicitly relies on globally bounded gradients to calibrate additive noise mechanisms (Bassily et al., 2014; Dwork et al., 2014), and this requirement was operationalized in deep learning through gradient clipping in differentially private SGD (Abadi et al., 2016). Chen et al. (2020) later studied the bias that clipping introduces in differentially private SGD through a geometric lens. Extensions to federated learning further have emphasized clipping as a prerequisite for aggregating privatized updates across clients (McMahan et al., 2018).
Another important role that gradient clipping plays is in dealing with heavy-tailed gradient noise. Several works have showed that the gradient noise in the training of deep learning models have much heavier tails than sub-Gaussian distributions model (Simsekli et al., 2019; Panigrahi et al., 2019; Gurbuzbalaban et al., 2021). As a response, subsequent works have concerned SGD and its variants under different models of heavy-tailed noise.
3. Problem and computational setup We consider the unconstrained optimization problem
Zhang et al. (2020c) showed that Clipped SGD is convergent in expectation for noise with bounded 𝑞-moment for 𝑞 ∈ (1, 2], whereas vanilla SGD can diverge for 𝑞 < 2. Later, Cutkosky & Mehta (2021) and Nguyen et al. (2023) showed high probability convergence of Clipped SGD under the same noise model. In addition, Cutkosky & Mehta (2021) showed that SGD fails to attain a logarithmic dependence on the failure probability even in the bounded variance setting 𝑞 = 2. More recently, Hübler et al. (2025) connected gradient clipping to normalization and established improved, parameter-free convergence guarantees for non-convex optimization under heavy-tailed noise with only bounded 𝑝-th moments. They further proved tight sample complexity
minimize
𝑓 (𝑥) =
𝑖=1 E 𝜉 ∼D𝑖 [𝐹𝑖 (𝑥, 𝜉)]
Í𝑛
(1)
where 𝐹𝑖 : R𝑑 × S → R for a sample space S. We define 𝑓𝑖 (𝑥) = E 𝜉 ∼D𝑖 [𝐹𝑖 (𝑥, 𝜉)]. We denote the standard inner product ⟨·, ·⟩ and the Euclidean norm ∥ · ∥. We make the standard smoothness assumption on the objective 𝑓 : Assumption 3.1. The objective function 𝑓 is 𝐿-smooth, meaning ∥∇ 𝑓 (𝑥) − ∇ 𝑓 (𝑦) ∥ ≤ 𝐿 ∥𝑥 − 𝑦∥ for every 𝑥, 𝑦 ∈ R𝑑 . Furthermore, 𝑓 is bounded from below by 𝑓 ★ > −∞. The clipping operator clip𝑐 : R𝑑 → R𝑑 with clipping ra3
Clipping Makes Asynchronous SGD Robust to Stragglers
dius 𝑐 > 0 is defined by
clip𝑐 (𝑥) = min 1,
Bayesian neural networks. Note that sub-Weibull random variables generalize sub-Gaussian and sub-exponential random variables, which are recovered with 𝜃 = 1/2 and 𝜃 = 1, respectively.
𝑐 𝑥 ∥𝑥∥
Assumption 3.2. The stochastic gradients are unbiased and have sub-Weibull noise, meaning E 𝜉 ∼D𝑖 [∇𝐹𝑖 (𝑥, 𝜉)] = ∇ 𝑓𝑖 (𝑥) and
for 𝑥 ∈ R𝑑 \ {0} and clip𝑐 (0) = 0. Note that clipping 𝑥 is equivalent to projecting 𝑥 onto the ball {𝑦 : ∥𝑦∥ ≤ 𝑐}. In this setup, we assume 𝑛 workers are available for parallel computation, with each worker 𝑖 serving as a stochastic oracle that returns 𝑔𝑡𝑖 (𝑥 𝑡 ) = clip𝑐 (∇𝐹𝑖 (𝑥 𝑡 , 𝜉𝑡𝑖 )) when queried with 𝑥 𝑡 , where 𝜉𝑡𝑖 ∼ D𝑖 . In a real-world system, these workers may be GPUs in a cluster, cores in a CPU, mobile devices, etc.
∥∇𝐹𝑖 (𝑥, 𝜉) − ∇ 𝑓𝑖 (𝑥) ∥ ∼ subW (𝜃, 𝜎) for every 𝑥 ∈ R𝑑 . 50
80
Crucial to most analyses of gradient clipping is controlling the error of the clipped stochastic gradient when the full gradient is small (relative to the clipping threshold). This generally involves controlling the tail of the gradient noise, i.e., bounding the probability P(∥∇𝐹 (𝑥, 𝜉) − ∇ 𝑓 (𝑥) ∥ > 𝛼) with a function of 𝛼 ≥ 0. The works of Zhang et al. (2020a;b) consider the uniformly bounded noise model, when the tail probability is zero for 𝛼 ≥ 𝜎 for some parameter 𝜎 > 0. While this technically holds true in typical empirical risk minimization, it requires a very large value of 𝜎 in comparison to the ordinary bounded variance model. Zhang et al. (2020b) also note that the noise model can be relaxed to sub-Gaussian noise, however, this assumption is still strong. Recent works in deep learning have showed that the stochastic gradients typically exhibit more heavytailed noise than sub-Gaussian random variables models (Simsekli et al., 2019; Panigrahi et al., 2019; Gurbuzbalaban et al., 2021). Koloskova et al. (2023) consider the ordinary bounded variance model and use Markov’s inequality to bound the tail. However, Markov’s inequality gives a pessimistic bound, leading to a relatively large error term even for large choices of clipping radius. Koloskova et al. show that this error is irreducible in worst-case analysis. Additionally, the convergence results in these works are in expectation, which do not characterize the behavior of Clipped SGD in a single run. This motivates the need for a model of gradient noise that gives us better tools to bound the tails, but still allows us to model the heavy-tails seen in deep learning.
40
Count
60
30 40 20 20 0
10 100
200 300 Norm error
400
500
(a) Real distribution
0
100
200 300 Norm error
400
500
(b) Sub-Weibull 𝜃 = 2.71.
Figure 1. Histograms of (a) gradient errors in training of a ResNet18 model on CIFAR-10 and (b) simulated sub-Weibull distribution. The empirical estimate of the tail parameter is 𝜃 = 2.71.
This model of the gradient noise is used by Li & Liu (2022) and (Madden et al., 2024), who provide high probability guarantees for serial SGD. Note that if a random variable is sub-Weibull then it also has bounded second-moment. In particular, if 𝑋 ∼ subW(𝜃, 𝜎) then E|𝑋 | 2 ≤ 𝐶𝜎 2 , where 𝐶 only depends on 𝜃. Therefore, the quantity 𝜎 2 is directly comparable to the one in the ordinary bounded variance assumption. The quantity 𝜃 on the other hand determines how heavy the tails are. This makes the class of sub-Weibull distributions ideal for modeling gradient noise in the training of modern machine learning models. In Figure 1, we have plotted the empirical norm gradient errors in training of a ResNet-18 model on the CIFAR-10 dataset, as well as a simulated sub-Weibull distribution using the estimate of the tail parameter 𝜃 obtained from the ResNet-18 training. We used the tail parameter estimate suggested by Vladimirova et al. (2020).
Definition 3.1. A random variable 𝑋 : S → R is called sub-Weibull if there exists positive quantities 𝜎 and 𝜃 such that 1 E[exp((|𝑋 |/𝜎) 𝜃 )] ≤ 2.
4. Homogeneous setting We begin with the homogeneous special case of problem (1), where the objective functions 𝑓𝑖 are identical, i.e., we have 𝐹1 = ... = 𝐹𝑛 and D1 = ... = D𝑛 . This corresponds to the data centralized setup, where all workers have access to the full dataset. This setting gives us much freedom in how we utilize the workers, because we do not have to worry about introducing optimization bias from over-relying on the fast workers. Therefore, we consider Algorithm 1, where workers are at all times computing (or communicating) clipped
We denote 𝑋 ∼ subW (𝜃, 𝜎). The class of sub-Weibull random variables is proposed by Kuchibhotla & Chakrabortty (2022) and Vladimirova et al. (2020). Kuchibhotla & Chakrabortty analyze linear regression and covariance estimation under this model, while Vladimirova et al. analyze the induced prior distributions in 4
Clipping Makes Asynchronous SGD Robust to Stragglers
and the sequence {˜ 𝑥 𝑡 }𝑡 defined by (2) satisfy
Algorithm 1 Clipped ASGD (homogeneous setting) Input: Initialization 𝑥 0 , concurrency 𝜏𝐶 , step size 𝜂 > 0, clipping radius 𝑐 > 0. A subset C0 of 𝜏𝐶 workers receive 𝑥 0 and start computing gradients for 𝑡 = 0, ... , 𝑇 − 1 do Worker 𝑖 𝑡 finishes computing 𝑔𝑡𝑖𝑡− 𝜏𝑡 (𝑥 𝑡 − 𝜏𝑡 ) Server updates 𝑥 𝑡+1 = 𝑥 𝑡 − 𝜂𝑔𝑡𝑖𝑡− 𝜏𝑡 (𝑥 𝑡 − 𝜏𝑡 ) Server selects an inactive worker 𝑗 𝑡 ∈ [𝑛] \ C𝑡 and updates the active set C𝑡+1 = (C𝑡 \ {𝑖 𝑡 }) ∪ { 𝑗 𝑡 } Worker 𝑗 𝑡 receives 𝑥 𝑡+1 and starts computing 𝑗 𝑔𝑡+𝑡 1 (𝑥 𝑡+1 ) end for
∥˜ 𝑥 𝑡 − 𝑥 𝑡 ∥ ≤ 𝜂𝑐𝜏𝐶
for all 𝑡 = 0, ... , 𝑇 − 1.
Using this result, we may show that the convergence in expectation of Clipped ASGD does not depend on the maximum delay. Theorem 4.2. Suppose Assumptions 3.1 and 3.2 hold. Then there exists a constant step size 𝜂 and clipping radius 𝑐 such Í that for 𝜀 ∈ (0, 1), we have 𝑇1 𝑇𝑡=−01 E∥∇ 𝑓 (𝑥 𝑡 ) ∥ ≤ 𝜀 within 2 e 𝜎 + 𝜎𝜏𝐶 + 𝜏𝐶 𝑂 𝜀4 𝜀3 𝜀2 iterations of Algorithm 1.
gradients. This is the standard ASGD algorithm considered in e.g. (Agarwal & Duchi, 2011; Feyzmahdavian et al., 2016; Stich & Karimireddy, 2020; Mishchenko et al., 2022; Koloskova et al., 2022), differing only in the use of gradient clipping. Following Koloskova et al., we generalize to concurrency 𝜏𝐶 ≤ 𝑛, although in the homogeneous case it is common to run with full concurrency. For instance, the server may prioritize workers that have returned gradients quickly in the past. Here, the server may select the next worker 𝑗 𝑡 out of the inactive workers in any way, due to the homogeneity. Under maximum concurrency 𝜏𝐶 = 𝑛 and the fixed computation model used by e.g. (Mishchenko et al., 2022; Tyurin & Richtárik, 2023), where each worker 𝑖 takes ℎ𝑖 seconds a clipped gradient, Algorithm 1 takes at Í𝑛 to1return − 1 seconds per oracle call on average. Commost ( 𝑖= 1 ℎ𝑖 ) pare this to Minibatch SGD which takes 𝑛1 max𝑖 ℎ𝑖 seconds per oracle call.
Note that eventhough Clipped ASGD differs only in the middle term compared to the iteration complexity of Delayadaptive ASGD, despite the algorithm not compensating directly for delays. In fact, if either 𝜏𝐶 = 𝑂 (𝜎/𝜀) or 𝜎/𝜀 = 𝑂 (1), then Theorem 4.2 shows that Clipped ASGD achieves the same rate as up to polylogarithmic factors. Clipped ASGD is also favorable to Vanilla ASGD under globally bounded gradients ∥∇ 𝑓 (𝑥) ∥ ≤ 𝐺 or 𝐺-Lipschitz loss, which achieves the rate 𝑂 (𝜎 2 /𝜀 4 + 𝜏𝐶 𝐺/𝜀 3 + 𝜏𝐶 /𝜀 2 ), as 𝐺 will often be very large. Moreover, clipping also simplifies tuning. With Vanilla ASGD, the step size to achieve the rate √ 𝑂 (𝜎 2 /𝜀 4 + 𝜏max 𝜏𝐶 /𝜀 2 ) critically depends on 𝜏max , which is generally unknowable a priori. We can furthermore show convergence in high probability, which to the the best of our knowledge is the first time in asynchronous optimization. Theorem 4.3. Suppose Assumptions 3.1 and 3.2 hold. Then there exists a constant step size 𝜂 and clipping radius 𝑐 such that for𝜀 ∈ (0, 1) and failureprobability 𝛿 ∈ (0, 1), we Í have P 𝑇1 𝑇𝑡=−01 ∥∇ 𝑓 (𝑥 𝑡 ) ∥ ≤ 𝜀 ≥ 1 − 𝛿 within 2 𝜎 log2 𝜃 (1/𝛿) 𝜎𝜏𝐶 log 𝜃 (1/𝛿) 𝜏𝐶 e 𝑂 + + 2 𝜀4 𝜀3 𝜀
Central to recent analyses of ASGD is perturbed iterate analysis, where a virtual sequence is used to study the actual sequence {𝑥 𝑡 }𝑡 of iterates (Mania et al., 2017; Stich & Karimireddy, 2020; Mishchenko et al., 2022; Koloskova et al., 2022). In the state-of-the-art analyses of ASGD (Mishchenko et al., 2022; Koloskova et al., 2022), it is shown that with a virtual sequence 𝑥˜𝑡 which evolves almost like serial SGD, the differences 𝑥˜𝑡 − 𝑥 𝑡 can be expressed as a sum of at most 𝑛 gradient steps. It is precisely here that, in our theoretical analysis, clipping turns out to be very beneficial for ASGD. It is in fact for the same reason the strong assumption of globally bounded gradients is beneficial in (Mishchenko et al., 2022; Koloskova et al., 2022). In particular, with initialization 𝑥 0 = 𝑥˜0 and step size 𝜂, we define the virtual sequence by 𝑥˜1 = 𝑥0 − 𝜂
Í
𝑖 𝑖 ∈ C0 𝑔0 (𝑥 0 ),
𝑥˜𝑡+1 = 𝑥˜𝑡 − 𝜂𝑔𝑡𝑖𝑡 (𝑥 𝑡 )
iterations of Algorithm 1. In particular, in the high probability analysis, we get an additional martingale difference term 𝑍𝑡 = −𝜂⟨∇ 𝑓 (˜ 𝑥 𝑡 ), 𝑔𝑡𝑖𝑡 (𝑥 𝑡 ) − E[𝑔𝑡𝑖𝑡 (𝑥 𝑡 )]⟩. Gradient clipping lets us bound the norm of the arguments in the inner product, where Lemma 4.1 is necessary for the first argument. Subsequently applying Freedman’s inequality (Lemma A.5) we find that with probability atleast 1 − 𝛿,
(2)
𝑇 −1 ∑︁
and find that the differences 𝑥˜𝑡 − 𝑥 𝑡 can be controlled via the clipping radius 𝑐 and the step size 𝜂.
𝑡=0
𝑍𝑡 ≲
𝑇 −1 ∑︁ 𝑡=0
𝜂∥∇ 𝑓 (𝑥 𝑡 ) ∥ 2 + 𝜂3 𝑐2 𝜏𝐶2 𝐿 2
+ 𝜂𝑐2 log
Lemma 4.1. The sequence {𝑥 𝑡 }𝑡 generated by Algorithm 1 5
2 2𝑇 + 𝜎 2 log2 𝜃 . 𝛿 𝛿
Clipping Makes Asynchronous SGD Robust to Stragglers
Theorem 4.3 shows that the rate differs from Theorem 4.2 only in a polylogarithmic dependence on the failure probability, with the degree being determined by the tail parameter 𝜃 from Assumption 3.2. Remark 4.1. Since clipping does not affect the computation dynamics of ASGD, ignoring the small overhead of clipping the gradient, the same time complexity analysis applies. In the fixed computation model considered in (Tyurin & Richtárik, 2023; Maranjyan et al., 2025) we assume workers take at most 𝑠1 ≤ ... ≤ 𝑠 𝑛 seconds to compute gradients. Under this model, the time complexity of Clipped ASGD with full concurrency 𝜏𝐶 = 𝑛 is obtained by multiplying the oracle by the harmonic sum of computation Í𝑛complexity 1 −1 times ( 𝑖= ) . If the computation times are known 1 𝑠𝑖 beforehand, then the concurrency and set of workers can be chosen to yield a time complexity of 𝜏𝐶
∑︁ 1 e ©min 𝑂 𝜏𝐶 𝑠 𝑖=1 𝑖 «
! −1
call as compared to standard ASGD. Here, a worker can be sampled several times before finishing the first gradient computation, in which case a queue of gradients builds up on that worker. We make the bounded first-order heterogeneity assumption on the functions 𝑓𝑖 which is commonly found in the federated learning literature. Assumption 5.1. The functions 𝑓𝑖 have bounded heterogeneity, meaning ∥∇ 𝑓𝑖 (𝑥) −∇ 𝑓 (𝑥) ∥ 2 ≤ 𝜁 2 for every 𝑥 ∈ R𝑑 .
Theorem 5.1. Suppose Assumptions 3.1, 3.2 and 5.1 hold. Then there exists a constant step size 𝜂 and clipping radius Í 𝑐 such that 𝑇1 𝑇𝑡=−01 E∥∇ 𝑓 (𝑥 𝑡 ) ∥ ≤ 𝜀 within 2 𝜎 + 𝜁 2 (𝜎 + 𝜁)𝜏𝐶 𝜏𝐶 e + + 2 𝑂 𝜀4 𝜀3 𝜀 iterations of Algorithm 2.
𝜎 2 𝜎𝜏𝐶 𝜏𝐶 ª + + ®. 𝜀4 𝜀3 𝜀2 ¬
Surprisingly, Theorem 5.1 shows that gradient clipping can remove the dependence on the maximum delay even in the heterogeneous case, where delay-adaptive schemes which do not in general converge. Compared this rate with the rate √ 𝑂 ((𝜎 2 +𝜁 2 )/𝜀 4 +𝜁 𝜏𝐶 /𝜀 3 + 𝜏𝐶 𝜏max /𝜀 2 ) heterogeneous version of Vanilla ASGD, we have a significant improvement when delays are large. Moreover, for this result Koloskova et al. (2022) require an additional assumption that the average delay of a worker is independent from the number of times that worker is sampled, which may not be entirely realistic.
The same reasoning applies to the high probability analysis, since the worst-case computation dynamics in this model are deterministic.
5. Heterogeneous setting We now turn to the general heterogeneous case of problem (1), in which every worker has access to its own data distribution and function 𝐹𝑖 . In this setup, we have much less freedom in how we utilize workers, since over-relying on a few fast workers will bias towards their objectives. For this reason, standard ASGD does not in general converge in this setting (Mishchenko et al., 2022). Thus, we consider the same scheme for worker selection as for instance Koloskova et al. (2022) and Wang et al. (2023) in Algorithm 2.
Theorem 5.2. Suppose Assumptions 3.1, 3.2 and 5.1 hold. Then there exists a constant step size 𝜂 and clipping radius 𝑐 such that for 𝜀 ∈ (0, 1) and failure probability 𝛿 ∈ (0, 1), 1 Í𝑇 − 1 we have P 𝑇 𝑡=0 ∥∇ 𝑓 (𝑥 𝑡 ) ∥ ≤ 𝜀 ≥ 1 − 𝛿 within 2 (𝜎 + 𝜁 2 ) log2 𝜃 (1/𝛿) (𝜎 + 𝜁)𝜏𝐶 log 𝜃 (1/𝛿) 𝜏𝐶 e 𝑂 + + 2 𝜀4 𝜀3 𝜀
Algorithm 2 Clipped ASGD (heterogeneous setting) Input: Initialization 𝑥0 , concurrency 𝜏𝐶 step size 𝜂 > 0, clipping radius 𝑐 > 0. A subset C0 of 𝜏𝐶 workers receive 𝑥 0 and start computing clipped gradients for 𝑡 = 0, ... , 𝑇 − 1 do Worker 𝑖 𝑡 finishes computing 𝑔𝑡𝑖𝑡− 𝜏𝑡 (𝑥 𝑡 − 𝜏𝑡 ) Server updates 𝑥 𝑡+1 = 𝑥 𝑡 − 𝜂𝑔𝑡𝑖𝑡− 𝜏𝑡 (𝑥 𝑡 − 𝜏𝑡 ) Worker 𝑗 𝑡 ∼ Uniform{1, ... , 𝑛} receives 𝑥 𝑡+1 and 𝑗 schedules 𝑔𝑡+𝑡 1 (𝑥 𝑡+1 ) end for
iterations of Algorithm 2. This high-probability convergence guarantee may be particularly important in federated learning, as training runs in real-world deployments are typically done at most a few times because each run incurs substantial logistical, computational, and organizational cost. Coordinating participation across a large, dynamic population of client devices requires careful scheduling, incentives, and system overhead, and client availability cannot be reliably reproduced across runs. Moreover, federated training pipelines are tightly coupled to product release cycles, privacy reviews, and regulatory approvals, making repeated experimentation slow and expensive. As a result, retraining is not a cheap or repeatable process, making high-probability guarantees particularly relevant.
After a worker has finished computing a clipped gradient, a new worker is chosen uniformly at random among all workers, and is sent the updated model. This way, no bias is created toward faster workers. This does however potentially slow down the wall-clock time of the average oracle 6
Clipping Makes Asynchronous SGD Robust to Stragglers
Remark 5.2. Quantifying the time complexity is more delicate in the heterogeneous case due to the sampling scheme required to preserve the unbiasedness of the stochastic gradients. For this reason, we have included experiments on the homogeneous and heterogeneous setting to empirically measure this slowdown.
larger delays.
Wall clock time
4000
6. Numerical experiments We examine the effect of using gradient clipping in asynchronous optimization of neural network parameters. We conduct several experiments on the CIFAR-10 (Krizhevsky et al., 2009) and Shakespeare (Karpathy, 2015) datasets, in the homogeneous (shared memory) setting. To allow for different delay setups, we simulate asynchronous training with 𝑛 = 16 workers, where half of them take 1 time unit to compute a gradient, and the other half takes 𝐷 ∈ {4, 8} time units. We use full concurrency 𝜏𝐶 = 𝑛 in all runs. All experiments are averaged over three random seeds, and 2𝜎 error bars are shown in the figures. The code used to run these experiments is available at https: //github.com/samericks/clipped-asgd.
3000
2000
1000
Vanilla Delay-adaptive Ringmaster Clipped
2−8
2−6
Step size
2−4
2−2
2−4
2−2
(a) 𝐷 = 4
Wall clock time
4000
3000
2000
1000
6.1. Homogeneous setting
2−8
We compare Clipped ASGD with three baseline methods in the homogeneous setting: Vanilla ASGD with constant step size, Delay-adaptive ASGD with step size rule proposed by Koloskova et al. (2022), and Ringleader ASGD (Maranjyan et al., 2025). For Clipped ASGD, we choose the best clipping radius 𝑐 ∈ {2 𝑘 : 𝑘 = −1, ... , 2}, and for Ringleader ASGD we choose the best delay threshold 𝑅 ∈ {2 𝑘 : 𝑘 = 1, ... , 4}. In all cases, the optimal hyperparameter value lies strictly within the search range.
2−6
Step size
(b) 𝐷 = 8 Figure 2. Simulated wall-clock time to reach 80% test accuracy on CIFAR-10 dataset with ResNet-18 architecture, when half of the 16 workers are 𝐷 times slower than the other half. The average time per oracle call here is 0.108 and 0.123 time units for 𝐷 = 4 and 𝐷 = 8, respectively.
Shakespeare. We next consider next-word prediction on the Shakespeare dataset using an LSTM architecture (Hochreiter & Schmidhuber, 1997) with dropout rate 0.2. We sweep over step sizes 𝜂 ∈ {2−3 , ... , 23 } and measure the simulated wall-clock time required to reach test perplexity 5.0. Runs are terminated after 4,000 time units.
CIFAR-10. We train a ResNet-18 model (He et al., 2016) on CIFAR-10. We sweep over 𝜂 ∈ {2−9 , ... , 2−1 } and measure the simulated wall-clock time required to reach 80% test accuracy. We terminate runs that do not reach the target within 4,000 time units.
The results are shown in Figure 3. Clipped ASGD again outperforms both Vanilla and Delay-adaptive ASGD. For 𝐷 = 4, Clipped ASGD achieves the target perplexity 1.8× faster than Vanilla ASGD, 2.1× faster than Delay-adaptive ASGD, and 1.8× faster than Ringmaster ASGD. For 𝐷 = 8, Clipped ASGD is 2× faster than Vanilla ASGD, 2.2× faster than Delay-adaptive ASGD, and 1.4× faster than Ringmaster ASGD.
Figure 2 shows the results for delay factors 𝐷 ∈ {4, 8}. Clipped ASGD consistently improves over Vanilla ASGD and Delay-adaptive ASGD across all delay settings. Here, Clipped ASGD reduces the minimum wall-clock time by 1.8× relative to Vanilla ASGD, and by 1.5× relative to Delay-adaptive and Ringmaster ASGD. As predicted by the theory, increasing the delay primarily affects Vanilla ASGD, which requires substantially smaller step sizes to remain stable. While the best wall-clock time is not significantly worsened for Vanilla ASGD, it requires more fine-grained tuning to converge within the time budget. In contrast, the clipped and delay-adaptive methods remain robust to larger delays, with no significant shifts due to
6.2. Heterogeneous setting We now consider asynchronous optimization under data heterogeneity. We compare Clipped ASGD against Vanilla ASGD and Ringleader ASGD (Maranjyan & Richtárik, 2026). Clipped and Vanilla ASGD use the uniform sam7
Clipping Makes Asynchronous SGD Robust to Stragglers
𝐷 = 4, clipping reduces the minimum wall-clock time by 1.2× relative to Vanilla ASGD and Ringleader ASGD. With 𝐷 = 8, Clipped ASGD is 1.3× faster than Vanilla ASGD, and 1.2× faster than Ringleader ASGD. Note that due to the sampling schemes used to avoid oversampling the fast workers, the maximum delay is also effectively controlled at the expense of process time, which may explain why clipping yields a smaller improvement here than in the homogeneous experiments.
Wall clock time
4000 3000 2000 Vanilla Delay-adaptive Ringmaster Clipped
1000 2−3
2−2
2−1
20 Step size
21
22
23
8000 Wall clock time
(a) 𝐷 = 4
Wall clock time
4000 3000 2000
6000
4000
2000
Vanilla Ringleader Clipped
2−8
2−6
1000 2−3
2−2
2−1
20 Step size
21
22
Step size
2−4
2−2
2−4
2−2
(a) 𝐷 = 4
23
12000 Wall clock time
(b) 𝐷 = 8 Figure 3. Simulated wall-clock time to reach test perplexity 5.0 on Shakespeare dataset with LSTM architecture, when half of the 16 workers are 𝐷 times slower than the other half. The average time per oracle call here is 0.108 and 0.123 time units for 𝐷 = 4 and 𝐷 = 8, respectively.
10000 8000 6000 4000 2−8
pling scheme described in Section 5. As before, we tune the clipping radius over 𝑐 ∈ {2 𝑘 : 𝑘 = −1, ... , 2}.
2−6
Step size
(b) 𝐷 = 8
Note however that in practical FL deployments, exact unbiasedness is often sacrificed in favor of faster process times. For example, many synchronous FL deployments aggregate updates once only a fraction (e.g., 80%) of workers have responded, rather than waiting for the slowest participants. Thus, asynchrony can in fact decrease bias, since the slowest workers may participate at all (Huba et al., 2022).
Figure 4. Simulated wall-clock time to reach test metric target on label skew CIFAR-10 dataset with a CNN architecture, when half of the 16 workers are 𝐷 times slower than the other half. The average time per oracle call is 0.337 and 0.668 time units for 𝐷 = 4 and 𝐷 = 8 respectively.
7. Conclusions and future work Label-skew CIFAR-10. We revisit CIFAR-10, but now distribute the data heterogeneously across workers using a Dirichlet partitioning scheme. Following Nguyen et al. (2022); He et al. (2020); Diao et al. (2020), we sample client label distributions from a Dirichlet distribution with parameter 𝛼 = 0.5. We use a two-layer CNN architecture and sweep over step sizes 𝜂 ∈ {2−9 , ... , 2−1 }.
This paper shows that gradient clipping fundamentally alters the effect of asynchrony in stochastic optimization. In particular, clipping removes dependence on the maximum delay in the convergence behavior of ASGD, yielding methods that are provably robust to stragglers. We provide convergence guarantees in both expectation and high probability, and show that these guarantees hold under homogeneous and heterogeneous settings. Empirically, we demonstrate that clipping consistently improves asynchronous training and can substantially outperform both Vanilla and Delayadaptive ASGD across a range of architectures and delay regimes.
We measure the simulated wall-clock time required to reach 70% test accuracy, with a maximum runtime of 8,000 for 𝐷 = 4 and 12,000 for 𝐷 = 8. The results are shown in Figure 4. Clipped ASGD consistently improves over both baselines across heterogeneity levels. With delay factor 8
Clipping Makes Asynchronous SGD Robust to Stragglers
Future work. Our results suggest a broader connection between norm control and robustness to asynchrony, raising several directions for future investigation.
bounds. In 2014 IEEE 55th annual symposium on foundations of computer science, pp. 464–473. IEEE, 2014. Ben-Nun, T. and Hoefler, T. Demystifying parallel and distributed deep learning: An in-depth concurrency analysis. ACM Computing Surveys (CSUR), 52(4):1–43, 2019.
First, it is natural to ask how these effects extend beyond the standard smooth setting. In particular, under weaker assumptions such as (𝐿 0 , 𝐿 1 )-smoothness, the interaction between gradient norms and staleness may become more pronounced, potentially making clipping even more beneficial.
Bertsekas, D. P. and Tsitsiklis, J. N. Parallel and Distributed Computation: Numerical Methods. Prentice-Hall, 1989. Chen, J., Monga, R., Bengio, S., and Jozefowicz, R. Revisiting distributed synchronous SGD. In International Conference on Learning Representations Workshop Track, 2016. URL https://arxiv.org/abs/ 1604.00981.
Second, recent optimizers such as Muon (Jordan et al., 2024) and Scion (Pethick et al., 2025) achieve strong empirical performance by explicitly controlling update norms, through orthogonalization or constrained update steps. Since clipping provides a simple mechanism for norm control in asynchronous settings, it is natural to ask whether asynchronous variants of these methods inherit similar robustness to delays. We believe understanding this interaction between optimizer geometry and asynchrony is a promising direction for future work.
Chen, X., Wu, S. Z., and Hong, M. Understanding gradient clipping in private SGD: A geometric perspective. Advances in Neural Information Processing Systems, 33: 13773–13782, 2020. Cohen, A., Daniely, A., Drori, Y., Koren, T., and Schain, M. Asynchronous stochastic optimization robust to arbitrary delays. In Ranzato, M., Beygelzimer, A., Dauphin, Y., Liang, P., and Vaughan, J. W. (eds.), Advances in Neural Information Processing Systems, volume 34, pp. 9024–9035. Curran Associates, Inc., 2021. URL https://proceedings.neurips. cc/paper_files/paper/2021/file/ 4b85256c4881edb6c0776df5d81f6236-Paper. pdf.
Impact statement This paper presents work whose goal is to advance the field of Machine Learning. There are many potential societal consequences of our work, none which we feel must be specifically highlighted here.
Acknowledgement This work was supported in part by the Knut and Alice Wallenberg Foundation through project KAW 2022.0050 and by the Wallenberg AI, Autonomous Systems and Software Program (WASP).
Cutkosky, A. and Mehta, H. High-probability bounds for non-convex stochastic optimization with heavy tails. In Ranzato, M., Beygelzimer, A., Dauphin, Y., Liang, P., and Vaughan, J. W. (eds.), Advances in Neural Information Processing Systems, volume 34, pp. 4883–4895. Curran Associates, Inc., 2021. URL https://proceedings.neurips. cc/paper_files/paper/2021/file/ 26901debb30ea03f0aa833c9de6b81e9-Paper. pdf.
References Abadi, M., Chu, A., Goodfellow, I., McMahan, H. B., Mironov, I., Talwar, K., and Zhang, L. Deep learning with differential privacy. In Proceedings of the 2016 ACM SIGSAC conference on computer and communications security, pp. 308–318, 2016.
Dean, J., Corrado, G., Monga, R., Chen, K., Devin, M., Mao, M., Ranzato, M., Senior, A., Tucker, P., Yang, K., et al. Large scale distributed deep networks. Advances in neural information processing systems, 25, 2012.
Agarwal, A. and Duchi, J. C. Distributed delayed stochastic optimization. Advances in neural information processing systems, 24, 2011.
Diao, E., Ding, J., and Tarokh, V. Heterofl: Computation and communication efficient federated learning for heterogeneous clients. arXiv preprint arXiv:2010.01264, 2020.
Alber, Y. I., Iusem, A. N., and Solodov, M. V. On the projected subgradient method for nonsmooth convex optimization in a hilbert space. Mathematical Programming, 81(1):23–35, 1998.
Dwork, C., Roth, A., et al. The algorithmic foundations of differential privacy. Foundations and trends® in theoretical computer science, 9(3–4):211–407, 2014.
Bassily, R., Smith, A., and Thakurta, A. Private empirical risk minimization: Efficient algorithms and tight error 9
Clipping Makes Asynchronous SGD Robust to Stragglers
Feyzmahdavian, H. R. and Johansson, M. Asynchronous iterations in optimization: New sequence results and sharper algorithmic guarantees. Journal of Machine Learning Research, 24(158):1–75, 2023.
and federated learning. In Koyejo, S., Mohamed, S., Agarwal, A., Belgrave, D., Cho, K., and Oh, A. (eds.), Advances in Neural Information Processing Systems, volume 35, pp. 17202–17215. Curran Associates, Inc., 2022.
Feyzmahdavian, H. R., Aytekin, A., and Johansson, M. An asynchronous mini-batch algorithm for regularized stochastic optimization. IEEE Transactions on Automatic Control, 61(12):3740–3754, 2016.
Koloskova, A., Hendrikx, H., and Stich, S. U. Revisiting gradient clipping: Stochastic bias and tight convergence guarantees. In Krause, A., Brunskill, E., Cho, K., Engelhardt, B., Sabato, S., and Scarlett, J. (eds.), Proceedings of the 40th International Conference on Machine Learning, volume 202 of Proceedings of Machine Learning Research, pp. 17343–17363. PMLR, 23–29 Jul 2023. URL https://proceedings.mlr.press/ v202/koloskova23a.html.
Gurbuzbalaban, M., Simsekli, U., and Zhu, L. The heavytail phenomenon in SGD. In International Conference on Machine Learning, pp. 3964–3975. PMLR, 2021. Hannah, R. and Yin, W. On unbounded delays in asynchronous parallel fixed-point algorithms. Journal of Scientific Computing, 76(1):299–326, 2018. ISSN 15737691. doi: 10.1007/s10915-017-0628-z. URL https: //doi.org/10.1007/s10915-017-0628-z.
Krizhevsky, A., Hinton, G., et al. Learning multiple layers of features from tiny images.(2009), 2009. Kuchibhotla, A. K. and Chakrabortty, A. Moving beyond sub-gaussianity in high-dimensional statistics: Applications in covariance estimation and linear regression. Information and Inference: A Journal of the IMA, 11(4): 1389–1456, 2022.
He, C., Li, S., So, J., Zeng, X., Zhang, M., Wang, H., Wang, X., Vepakomma, P., Singh, A., Qiu, H., et al. Fedml: A research library and benchmark for federated machine learning. arXiv preprint arXiv:2007.13518, 2020.
Li, S. and Liu, Y. High probability guarantees for nonconvex stochastic gradient descent with heavy tails. In Chaudhuri, K., Jegelka, S., Song, L., Szepesvari, C., Niu, G., and Sabato, S. (eds.), Proceedings of the 39th International Conference on Machine Learning, volume 162 of Proceedings of Machine Learning Research, pp. 12931–12963. PMLR, 17–23 Jul 2022. URL https:// proceedings.mlr.press/v162/li22q.html.
He, K., Zhang, X., Ren, S., and Sun, J. Deep residual learning for image recognition. In Proceedings of the IEEE conference on computer vision and pattern recognition, pp. 770–778, 2016. Hochreiter, S. and Schmidhuber, J. Long short-term memory. Neural computation, 9(8):1735–1780, 1997. Huba, D., Nguyen, J., Malik, K., Zhu, R., Rabbat, M., Yousefpour, A., Wu, C.-J., Zhan, H., Ustinov, P., Srinivas, H., et al. Papaya: Practical, private, and scalable federated learning. Proceedings of Machine Learning and Systems, 4:814–832, 2022.
Madden, L., Dall’Anese, E., and Becker, S. High probability convergence bounds for non-convex stochastic gradient descent with sub-weibull noise. Journal of Machine Learning Research, 25(241):1–36, 2024. URL http: //jmlr.org/papers/v25/23-0466.html.
Hübler, F., Fatkhullin, I., and He, N. From gradient clipping to normalization for heavy tailed SGD. In Li, Y., Mandt, S., Agrawal, S., and Khan, E. (eds.), Proceedings of The 28th International Conference on Artificial Intelligence and Statistics, volume 258 of Proceedings of Machine Learning Research, pp. 2413–2421. PMLR, 03–05 May 2025. URL https://proceedings.mlr.press/ v258/hubler25a.html.
Mai, V. V. and Johansson, M. Stability and convergence of stochastic gradient clipping: Beyond lipschitz continuity and smoothness. In Meila, M. and Zhang, T. (eds.), Proceedings of the 38th International Conference on Machine Learning, volume 139 of Proceedings of Machine Learning Research, pp. 7325–7335. PMLR, 18–24 Jul 2021. URL https://proceedings.mlr.press/ v139/mai21a.html.
Jordan, K., Jin, Y., Boza, V., Yu, J., Cecista, F., Newhouse, L., and Bernstein, J. Muon: An optimizer for hidden layers in neural networks. https://kellerjordan. github.io/posts/muon/, 2024. Online article. Karpathy, A. char-rnn. https://github.com/ karpathy/char-rnn, 2015.
Mania, H., Pan, X., Papailiopoulos, D., Recht, B., Ramchandran, K., and Jordan, M. I. Perturbed iterate analysis for asynchronous stochastic optimization. SIAM Journal on Optimization, 27(4):2202–2229, 2017. doi: 10.1137/16M1057000. URL https://doi.org/10. 1137/16M1057000.
Koloskova, A., Stich, S. U., and Jaggi, M. Sharper convergence guarantees for asynchronous SGD for distributed
Maranjyan, A. and Richtárik, P. Ringleader ASGD: The first asynchronous SGD with optimal time complex10
Clipping Makes Asynchronous SGD Robust to Stragglers
ity under data heterogeneity. In The Fourteenth International Conference on Learning Representations, 2026. URL https://openreview.net/forum? id=5wqTal0EuC.
Nguyen, T. D., Nguyen, T. H., Ene, A., and Nguyen, H. Improved convergence in high probability of clipped gradient methods with heavy tailed noise. In Oh, A., Naumann, T., Globerson, A., Saenko, K., Hardt, M., and Levine, S. (eds.), Advances in Neural Information Processing Systems, volume 36, pp. 24191–24222. Curran Associates, Inc., 2023.
Maranjyan, A., Tyurin, A., and Richtárik, P. Ringmaster ASGD: The first asynchronous SGD with optimal time complexity. In Forty-second International Conference on Machine Learning, 2025. URL https: //openreview.net/forum?id=Rkgn9KLHhd.
Panigrahi, A., Somani, R., Goyal, N., and Netrapalli, P. Non-gaussianity of stochastic gradient noise. In Science Meets Engineering of Deep Learning (SEDL) Workshop at the 33rd Conference on Neural Information Processing Systems (NeurIPS), 2019.
McMahan, B. and Streeter, M. Delay-tolerant algorithms for asynchronous distributed online learning. Advances in Neural Information Processing Systems, 27, 2014.
Pascanu, R., Mikolov, T., and Bengio, Y. On the difficulty of training recurrent neural networks. In Dasgupta, S. and McAllester, D. (eds.), Proceedings of the 30th International Conference on Machine Learning, volume 28 of Proceedings of Machine Learning Research, pp. 1310– 1318, Atlanta, Georgia, USA, 17–19 Jun 2013. PMLR. URL https://proceedings.mlr.press/v28/ pascanu13.html.
McMahan, H. B., Ramage, D., Talwar, K., and Zhang, L. Learning differentially private recurrent language models. Proceedings of the 6th International Conference on Learning Representations (ICLR), 2018. Mikolov, T. et al. Statistical language models based on neural networks. Presentation at Google, Mountain View, 2nd April, 80(26), 2012.
Pethick, T., Xie, W., Antonakopoulos, K., Zhu, Z., SilvetiFalls, A., and Cevher, V. Training deep learning models with norm-constrained lmos. arXiv preprint arXiv:2502.07529, 2025.
Mishchenko, K., Bach, F., Even, M., and Woodworth, B. E. Asynchronous SGD beats minibatch SGD under arbitrary delays. In Koyejo, S., Mohamed, S., Agarwal, A., Belgrave, D., Cho, K., and Oh, A. (eds.), Advances in Neural Information Processing Systems, volume 35, pp. 420–433. Curran Associates, Inc., 2022.
Recht, B., Re, C., Wright, S., and Niu, F. Hogwild!: A lockfree approach to parallelizing stochastic gradient descent. Advances in neural information processing systems, 24, 2011.
Nedić, A., Bertsekas, D., and Borkar, V. Distributed asynchronous incremental subgradient methods. In Butnariu, D., Censor, Y., and Reich, S. (eds.), Inherently Parallel Algorithms in Feasibility and Optimization and their Applications, volume 8 of Studies in Computational Mathematics, pp. 381–407. Elsevier, 2001. doi: https://doi.org/10.1016/S1570-579X(01)80023-9. URL https://www.sciencedirect.com/ science/article/pii/S1570579X01800239.
Simsekli, U., Sagun, L., and Gurbuzbalaban, M. A tail-index analysis of stochastic gradient noise in deep neural networks. In International Conference on Machine Learning, pp. 5827–5837. PMLR, 2019. Sra, S., Yu, A. W., Li, M., and Smola, A. Adadelay: Delay adaptive distributed stochastic optimization. In Gretton, A. and Robert, C. C. (eds.), Proceedings of the 19th International Conference on Artificial Intelligence and Statistics, volume 51 of Proceedings of Machine Learning Research, pp. 957–965, Cadiz, Spain, 09–11 May 2016. PMLR. URL https://proceedings.mlr. press/v51/sra16.html.
Nguyen, J., Malik, K., Zhan, H., Yousefpour, A., Rabbat, M., Malek, M., and Huba, D. Federated learning with buffered asynchronous aggregation. In International conference on artificial intelligence and statistics, pp. 3581– 3607. PMLR, 2022.
Stich, S. U. and Karimireddy, S. P. The error-feedback framework: Sgd with delayed gradients. Journal of Machine Learning Research, 21(237):1–36, 2020. URL http://jmlr.org/papers/v21/19-748. html.
Nguyen, L., NGUYEN, P. H., van Dijk, M., Richtarik, P., Scheinberg, K., and Takac, M. SGD and hogwild! Convergence without the bounded gradients assumption. In Dy, J. and Krause, A. (eds.), Proceedings of the 35th International Conference on Machine Learning, volume 80 of Proceedings of Machine Learning Research, pp. 3750–3758. PMLR, 10–15 Jul 2018. URL https://proceedings.mlr.press/v80/ nguyen18c.html.
Tsitsiklis, J., Bertsekas, D., and Athans, M. Distributed asynchronous deterministic and stochastic gradient optimization algorithms. IEEE transactions on automatic control, 31(9):803–812, 2003. 11
Clipping Makes Asynchronous SGD Robust to Stragglers
Tyurin, A. and Richtárik, P. Optimal time complexities of parallel stochastic optimization methods under a fixed computation model. Advances in Neural Information Processing Systems, 36:16515–16577, 2023.
for attention models? Advances in Neural Information Processing Systems, 33:15383–15393, 2020c. Zhang, W., Gupta, S., Lian, X., and Liu, J. Staleness-aware Async-SGD for distributed deep learning. In Proceedings of the Twenty-Fifth International Joint Conference on Artificial Intelligence (IJCAI-16), 2016.
Vladimirova, M., Verbeek, J., Mesejo, P., and Arbel, J. Understanding priors in Bayesian neural networks at the unit level. In Chaudhuri, K. and Salakhutdinov, R. (eds.), Proceedings of the 36th International Conference on Machine Learning, volume 97 of Proceedings of Machine Learning Research, pp. 6458–6467. PMLR, 09–15 Jun 2019. URL https://proceedings.mlr.press/ v97/vladimirova19a.html.
Zheng, S., Meng, Q., Wang, T., Chen, W., Yu, N., Ma, Z.-M., and Liu, T.-Y. Asynchronous stochastic gradient descent with delay compensation. In Precup, D. and Teh, Y. W. (eds.), Proceedings of the 34th International Conference on Machine Learning, volume 70 of Proceedings of Machine Learning Research, pp. 4120–4129. PMLR, 06– 11 Aug 2017. URL https://proceedings.mlr. press/v70/zheng17b.html.
Vladimirova, M., Girard, S., Nguyen, H., and Arbel, J. Sub-weibull distributions: Generalizing sub-gaussian and sub-exponential properties to heavier tailed distributions. Stat, 9(1):e318, 2020. Wang, Y., Cao, Y., Wu, J., Chen, R., and Chen, J. Tackling the data heterogeneity in asynchronous federated learning with cached update calibration. In Federated learning and analytics in practice: algorithms, systems, applications, and opportunities, 2023. Wu, X., Magnusson, S., Feyzmahdavian, H. R., and Johansson, M. Delay-adaptive step-sizes for asynchronous learning. In Chaudhuri, K., Jegelka, S., Song, L., Szepesvari, C., Niu, G., and Sabato, S. (eds.), Proceedings of the 39th International Conference on Machine Learning, volume 162 of Proceedings of Machine Learning Research, pp. 24093–24113. PMLR, 17–23 Jul 2022. URL https:// proceedings.mlr.press/v162/wu22g.html. Xie, C., Koyejo, O., and Gupta, I. Asynchronous federated optimization. OPT2020: 12th Annual Workshop on Optimization for Machine Learning, 2020. Zhang, B., Jin, J., Fang, C., and Wang, L. Improved analysis of clipping algorithms for non-convex optimization. In Larochelle, H., Ranzato, M., Hadsell, R., Balcan, M., and Lin, H. (eds.), Advances in Neural Information Processing Systems, volume 33, pp. 15511–15521. Curran Associates, Inc., 2020a. URL https://proceedings.neurips. cc/paper_files/paper/2020/file/ b282d1735283e8eea45bce393cefe265-Paper. pdf. Zhang, J., He, T., Sra, S., and Jadbabaie, A. Why gradient clipping accelerates training: A theoretical justification for adaptivity. In International Conference on Learning Representations, 2020b. URL https: //openreview.net/forum?id=BJgnXpVYwS. Zhang, J., Karimireddy, S. P., Veit, A., Kim, S., Reddi, S., Kumar, S., and Sra, S. Why are adaptive methods good 12
Clipping Makes Asynchronous SGD Robust to Stragglers
A. Preliminaries A.1. Properties of Sub-Weibull random variables Theorem A.1 (Vladimirova et al. 2020). Let 𝑋 : S → R be a random variable. Then the following are equivalent: 1
(i) There exists a 𝐾1 > 0 such that P(|𝑋 | ≥ 𝑥) ≤ 2 exp(−(𝑥/𝐾1 ) 𝜃 ) for all 𝑥 ≥ 0. (ii) There exists a 𝐾2 > 0 such that E[|𝑋 | 𝑞 ] 1/𝑞 ≤ 𝐾21/𝑞 𝑞 𝜃 for all 𝑞 ∈ (1, ∞). 1
1
(iii) There exists a 𝐾3 > 0 such that E[exp((𝜆|𝑋 |) 𝜃 )] ≤ exp((𝜆𝐾3 )) 𝜃 ). 1
(iv) There exists a 𝐾4 > 0 such that E[exp((|𝑋 |/𝐾4 ) 𝜃 )] ≤ 2. Additionally, the constants 𝐾1 , ... , 𝐾4 differ at most by a factor that depends on 𝜃 (in particular, 𝐾1 = 𝐾4 ). Lemma A.2. If 𝑋 ∼ subW (𝜃, 𝜎), then (i) P |𝑋 | ≤ 𝜎 log 𝜃 (2/𝛿) ≥ 1 − 𝛿, (ii) E[𝑋 2 ] ≤ 2Γ(2𝜃 + 1)𝜎 2 . A.2. Inequalities and lemmas Lemma A.3 (Smoothness inequality). If Assumption 3.1 holds, then 𝑓 (𝑥) ≤ 𝑓 (𝑦) + ⟨𝑥 − 𝑦, ∇ 𝑓 (𝑦)⟩ +
𝐿 ∥𝑥 − 𝑦∥ 2 2
for all 𝑥, 𝑦 ∈ R𝑑 .
Lemma A.4 (Young’s inequality). For any pair of vectors 𝑥, 𝑦 ∈ R𝑑 , ⟨𝑥, 𝑦⟩ ≤
1 1 ∥𝑥∥ 2 + ∥𝑦∥ 2 . 2 2
Lemma A.5 (Freedman’s inequality). Consider a martingale difference sequence {𝑍𝑡 }𝑡 adapted to a filtration G𝑡 and suppose that |𝑍𝑡 | ≤ ℓ almost surely. Then with probability at least 1 − 𝛿 it holds for any 𝜌 ∈ (0, 1) that 𝑇 −1 ∑︁ 𝑡=0
𝑍𝑡 ≤
𝑇 −1
𝜌 ∑︁ ℓ E[𝑍𝑡2 | G𝑡 ] + log(1/𝛿). ℓ 𝑡=0 𝜌
B. Proof of Theoretical Results For notational brevity, we write 𝑔𝑡𝑖 = 𝑔𝑡𝑖 (𝑥 𝑡 ), and denote the expectation and probability conditioned upon the 𝜎-algebra F𝑡 −1 generated by {𝑔𝑠 }𝑡𝑠= 𝑥 𝑡 }𝑡 are adapted to {F𝑡 }𝑡 , and 0 by E𝑡 [·] and P𝑡 {·}, respectively. Note that the sequences {𝑥 𝑡 } 𝑡 and {˜ that 𝑓 and ∇ 𝑓 are measurable due to everywhere differentiability of 𝑓 , so E𝑡 [ 𝑓 (˜ 𝑥 𝑡 )] = 𝑓 (˜ 𝑥 𝑡 ) and E𝑡 [∇ 𝑓 (𝑥 𝑡 )] = ∇ 𝑓 (𝑥 𝑡 ) almost surely. Define the virtual sequence {˜ 𝑥 𝑡 }𝑇𝑡=0 by ∑︁ 𝑥˜0 = 𝑥0 , 𝑥˜1 = 𝑥0 − 𝜂 𝑔0𝑖 , 𝑥˜𝑡+1 = 𝑥˜𝑡 − 𝜂𝑔𝑡𝑖𝑡 , 𝑖∈ C0
We first present a key inequality for our analysis, which is essentially a corollary of (Lemma 1, Mishchenko et al., 2022). Lemma B.1 (Virtual iterate bound). The sequences {𝑥 𝑡 }𝑡 and {˜ 𝑥 𝑡 }𝑡 satisfy ∥˜ 𝑥 𝑡 − 𝑥 𝑡 ∥ ≤ 𝜂𝑐𝜏𝐶 for all 𝑡 = 0, ... , 𝑇 − 1. 13
Clipping Makes Asynchronous SGD Robust to Stragglers
Í𝑡 −1 𝑖 (𝑠) 𝑖 𝑖=1 𝑔0 and 𝑥 𝑡 = 𝑥 0 − 𝜂 𝑠=1 𝑔 𝑠− 𝜏 (𝑠) . But all clipped gradients apart from the Í 𝑖 (𝑠) 𝜏𝐶 clipped gradients being computed at iteration 𝑡 are included in the sum 𝑡𝑠=−11 𝑔𝑠− , hence 𝜏 (𝑠)
Proof. We have that 𝑥˜𝑡 = 𝑥0 − 𝜂
Í𝑡 − 1
𝑠=1 𝑔 𝑠 − 𝜂
Í𝑛
∥˜ 𝑥𝑡 − 𝑥𝑡 ∥ = 𝜂
𝑡 −1 ∑︁ 𝑠=1
𝑔𝑠𝑖 (𝑠) −
𝑡 −1 ∑︁ 𝑠=1
𝑖 (𝑠) 𝑔𝑠− + 𝜏 (𝑠)
∑︁ 𝑖 ∈ C0
𝑔0𝑖 ≤ 𝜂𝑐𝜏𝐶 ,
noting that ∥𝑔𝑠 ∥ ≤ 𝑐 for all 𝑠.
□
Central to our analysis is bounding the squared norm error between the clipped stochastic gradient and the full gradient, when the full gradient is small. Lemma B.2 (Bias and moment bounds). Suppose Assumptions 3.1, 3.2 and 5.1 hold. Then E𝑡 ∥∇𝐹𝑖𝑡 (𝑥 𝑡 , 𝜉𝑡𝑖𝑡 ) − ∇ 𝑓 (𝑥 𝑡 ) ∥ 2 ≤ 4𝜎 2 Γ(2𝜃 + 1) + 2𝜁 2 .
(3)
Additionally, if ∥∇ 𝑓 (𝑥 𝑡 ) ∥ < 𝑐/2 and 𝑐 > 2𝜁, then ∥E𝑡 𝑔𝑡𝑖𝑡 − clip𝑐 (∇ 𝑓 (𝑥 𝑡 )) ∥ 2 ≤
8𝜎 2 Γ(2𝜃 + 1) + 4𝜁
2
𝑐 − 2𝜁 exp − 4𝜎
1𝜃 ! ,
(4)
and E𝑡 ∥𝑔𝑡𝑖𝑡 ∥ 2 ≤ 24𝜎 2 Γ(2𝜃 + 1) + 8𝜁 2 + 2∥∇ 𝑓 (𝑥 𝑡 ) ∥ 2 .
(5)
Proof. For (3), we first apply Young’s inequality E𝑡 ∥∇𝐹𝑖𝑡 (𝑥 𝑡 , 𝜉𝑡𝑖𝑡 ) − ∇ 𝑓 (𝑥 𝑡 ) ∥ 2 ≤ 2E𝑡 ∥∇𝐹𝑖𝑡 (𝑥 𝑡 , 𝜉𝑡𝑖𝑡 ) − ∇ 𝑓𝑖𝑡 (𝑥 𝑡 ) ∥ 2 + 2E𝑡 ∥∇ 𝑓𝑖𝑡 (𝑥 𝑡 ) − ∇ 𝑓 (𝑥 𝑡 ) ∥ 2 . Then using (ii) from Lemma A.2 on the first term, and Assumption 5.1 on the second, we get the stated bound (3). Bounding P𝑡 {∥∇𝐹𝑖𝑡 (𝑥 𝑡 , 𝜉𝑡𝑖𝑡 ) ∥ ≥ 𝑐}.
Define the indicator function 𝜒𝑡 = 1{∥∇𝐹𝑖𝑡 (𝑥 𝑡 , 𝜉𝑡𝑖𝑡 ) ∥ ≥ 𝑐}. We have that
P𝑡 { 𝜒𝑡 = 1} ≤ P𝑡 ∥∇𝐹𝑖𝑡 (𝑥 𝑡 , 𝜉𝑡𝑖𝑡 ) − ∇ 𝑓𝑖𝑡 (𝑥 𝑡 ) ∥ + ∥∇ 𝑓𝑖𝑡 (𝑥 𝑡 ) ∥ > 𝑐 ≤ P𝑡 ∥∇𝐹𝑖𝑡 (𝑥 𝑡 , 𝜉𝑡𝑖𝑡 ) − ∇ 𝑓𝑖𝑡 (𝑥 𝑡 ) ∥ + ∥∇ 𝑓𝑖𝑡 (𝑥 𝑡 ) − ∇ 𝑓 (𝑥 𝑡 ) ∥ + ∥∇ 𝑓 (𝑥 𝑡 ) ∥ > 𝑐 o n 𝑐 ≤ P𝑡 ∥∇𝐹𝑖𝑡 (𝑥 𝑡 , 𝜉𝑡𝑖𝑡 ) − ∇ 𝑓𝑖𝑡 (𝑥 𝑡 ) ∥ > − 𝜁 . 2 Applying the sub-Weibull concentration inequality (i) in Theorem A.1, we get the bound 𝑐 − 2𝜁 P𝑡 { 𝜒𝑡 = 1} ≤ 2 exp − 4𝜎
1𝜃 ! .
(6)
This yields the exponential term in (4). For the polynomial bound, we bound the probability as P𝑡 { 𝜒𝑡 = 1} ≤ P𝑡 ∥∇𝐹𝑖𝑡 (𝑥 𝑡 , 𝜉𝑡𝑖𝑡 ) − ∇ 𝑓 (𝑥 𝑡 ) ∥ + ∥∇ 𝑓 (𝑥 𝑡 ) ∥ > 𝑐 n 𝑐o ≤ P𝑡 ∥∇𝐹𝑖𝑡 (𝑥 𝑡 , 𝜉𝑡𝑖𝑡 ) − ∇ 𝑓 (𝑥 𝑡 ) ∥ > . 2 and apply Markov’s inequality to get P𝑡 { 𝜒𝑡 = 1} ≤
4E𝑡 ∥∇𝐹𝑖𝑡 (𝑥 𝑡 , 𝜉𝑡𝑖𝑡 ) − ∇ 𝑓 (𝑥 𝑡 ) ∥ 2 16Γ(2𝜃 + 1)𝜎 2 + 4𝜁 2 ≤ . 𝑐2 𝑐2 14
(7)
Clipping Makes Asynchronous SGD Robust to Stragglers
Bias bound. Turning to the quantity ∥E𝑡 𝑔𝑡𝑖𝑡 − clip𝑐 (∇ 𝑓 (𝑥 𝑡 )) ∥ 2 , we first note that clip𝑐 (∇ 𝑓 (𝑥 𝑡 )) = ∇ 𝑓 (𝑥 𝑡 ) = E𝑡 [∇𝐹𝑖𝑡 (𝑥 𝑡 , 𝜉𝑡𝑖𝑡 )] since we have assumed ∥∇ 𝑓 (𝑥 𝑡 ) ∥ < 𝑐/2. Thus, we have that " ∥E𝑡 𝑔𝑡𝑖𝑡 − ∇ 𝑓 (𝑥 𝑡 ) ∥ 2 =
E𝑡
1−
" ≤ E𝑡
1−
# 2
!
𝑐 ∥∇𝐹𝑖𝑡 (𝑥 𝑡 , 𝜉𝑡𝑖𝑡 ) ∥ 𝑐 ∥∇𝐹𝑖𝑡 (𝑥 𝑡 , 𝜉𝑡𝑖𝑡 ) ∥
∇𝐹𝑖𝑡 (𝑥 𝑡 , 𝜉𝑡𝑖𝑡 )
𝜒𝑡 #2
! ∇𝐹𝑖𝑡 (𝑥 𝑡 , 𝜉𝑡𝑖𝑡 )
𝜒𝑡
i2 h = E𝑡 𝑐 − ∥∇𝐹𝑖𝑡 (𝑥 𝑡 , 𝜉𝑡𝑖𝑡 ) ∥ 𝜒𝑡 i2 h ≤ E𝑡 ∥∇ 𝑓 (𝑥 𝑡 ) ∥ − ∥∇𝐹𝑖𝑡 (𝑥 𝑡 , 𝜉𝑡𝑖𝑡 ) ∥ 𝜒𝑡 . Now, using the reverse triangle inequality followed by the Cauchy-Schwarz inequality, E𝑡
h
∥∇ 𝑓 (𝑥 𝑡 ) ∥ − ∥∇𝐹𝑖𝑡 (𝑥 𝑡 , 𝜉𝑡𝑖𝑡 ) ∥ 𝜒𝑡
i2
2 ≤ E𝑡 ∥∇ 𝑓 (𝑥 𝑡 ) − ∇𝐹𝑖𝑡 (𝑥 𝑡 , 𝜉𝑡𝑖𝑡 ) ∥ 𝜒𝑡 ≤ E𝑡 [∥∇ 𝑓 (𝑥 𝑡 ) − ∇𝐹𝑖𝑡 (𝑥 𝑡 , 𝜉𝑡𝑖 ) ∥ 2 ]E𝑡 [ 𝜒𝑡2 ]
≤ (4𝜎 2 Γ(2𝜃 + 1) + 2𝜁 2 )E𝑡 [ 𝜒𝑡2 ]
= (4𝜎 2 Γ(2𝜃 + 1) + 2𝜁 2 )P𝑡 { 𝜒𝑡 = 1},
where we applied (3) and in the last inequality we used (ii) in Lemma A.2. We arrive at the stated result (4) by applying (6). Second moment bound.
Turning to E𝑡 ∥𝑔𝑡𝑖𝑡 ∥ 2 , we have that E𝑡 ∥𝑔𝑡𝑖𝑡 ∥ 2 = E𝑡 [ 𝜒𝑡 ∥𝑔𝑡𝑖𝑡 ∥ 2 + (1 − 𝜒𝑡 ) ∥𝑔𝑡𝑖𝑡 ∥ 2 ]
= P𝑡 ( 𝜒𝑡 = 1)E𝑡 [∥𝑔𝑡𝑖𝑡 ∥ 2 | 𝜒𝑡 = 1] + E𝑡 [(1 − 𝜒𝑡 ) ∥𝑔𝑡𝑖𝑡 ∥ 2 ] = P𝑡 ( 𝜒𝑡 = 1)𝑐2 + E𝑡 (1 − 𝜒𝑡 ) ∥∇𝐹𝑖𝑡 (𝑥 𝑡 , 𝜉𝑡𝑖𝑡 ) ∥ 2 ≤ P𝑡 ( 𝜒𝑡 = 1)𝑐2 + E𝑡 ∥∇𝐹𝑖𝑡 (𝑥 𝑡 , 𝜉𝑡𝑖𝑡 ) ∥ 2 .
Subsequently, we bound the term E𝑡 ∥∇𝐹𝑖𝑡 (𝑥 𝑡 , 𝜉𝑡𝑖𝑡 ) ∥ 2 by applying Young’s inequality and (ii) in Lemma A.2: E𝑡 ∥∇𝐹𝑖𝑡 (𝑥 𝑡 , 𝜉𝑡𝑖𝑡 ) ∥ 2 = E𝑡 ∥ (∇𝐹𝑖𝑡 (𝑥 𝑡 , 𝜉𝑡𝑖𝑡 ) − ∇ 𝑓 (𝑥 𝑡 )) + ∇ 𝑓 (𝑥 𝑡 ) ∥ 2
≤ 2E𝑡 ∥∇𝐹𝑖𝑡 (𝑥 𝑡 , 𝜉𝑡𝑖𝑡 ) − ∇ 𝑓 (𝑥 𝑡 ) ∥ 2 + 2E𝑡 ∥∇ 𝑓 (𝑥 𝑡 ) ∥ 2 ≤ 8Γ(2𝜃 + 1)𝜎 2 + 4𝜁 2 + 2∥∇ 𝑓 (𝑥 𝑡 ) ∥ 2 .
Thus we arrive at (5) by applying (7).
□
B.1. Convergence in expectation We begin with the main descent lemma we will use in the analysis of convergence in expectation. n o Lemma B.3. If 𝑓 is 𝐿-smooth and 𝛼𝑡 = min 1, ∥ ∇ 𝑓 𝑐( 𝑥𝑡 ) ∥ , then E𝑡 𝑓 (˜ 𝑥 𝑡+1 ) − 𝑓 (˜ 𝑥𝑡 ) ≤ −
𝜂𝛼𝑡 𝜂 𝜂2 𝐿 ∥∇ 𝑓 (𝑥 𝑡 ) ∥ 2 + ∥E𝑡 𝑔𝑡𝑖𝑡 − clip𝑐 (∇ 𝑓 (𝑥 𝑡 )) ∥ 2 + (𝜂𝑐2 𝜏𝐶2 𝐿 + E𝑡 ∥𝑔𝑡𝑖𝑡 ∥ 2 ). 2 2𝛼𝑡 2
(8)
Proof. Since 𝑓 is 𝐿-smooth we have that 𝑓 (˜ 𝑥 𝑡+1 ) ≤ 𝑓 (˜ 𝑥 𝑡 ) + ⟨˜ 𝑥 𝑡+1 − 𝑥˜𝑡 , ∇ 𝑓 (˜ 𝑥 𝑡 )⟩ + 𝜂 = 𝑓 (˜ 𝑥 𝑡 ) − 𝜂⟨𝑔𝑡𝑖𝑡 , ∇ 𝑓 (˜ 𝑥 𝑡 )⟩ + 15
2
𝐿 ∥˜ 𝑥 𝑡+1 − 𝑥˜𝑡 ∥ 2 2
𝐿 𝑖𝑡 2 ∥𝑔𝑡 ∥ . 2
(9)
Clipping Makes Asynchronous SGD Robust to Stragglers
due to Lemma A.3. Taking the conditional expectation we have that E𝑡 𝑓 (˜ 𝑥 𝑡+1 ) − 𝑓 (˜ 𝑥 𝑡 ) ≤ −𝜂⟨E𝑡 𝑔𝑡𝑖𝑡 , ∇ 𝑓 (˜ 𝑥 𝑡 )⟩ +
𝜂2 𝐿 E𝑡 ∥𝑔𝑡𝑖𝑡 ∥ 2 . 2
Turning our attention to the inner product in the right-hand side, we apply Young’s inequality and 𝐿-smoothness, −𝜂⟨∇ 𝑓 (˜ 𝑥 𝑡 ), E𝑡 𝑔𝑡 ⟩ = −𝜂⟨∇ 𝑓 (𝑥 𝑡 ), E𝑡 𝑔𝑡𝑖𝑡 ⟩ + 𝜂⟨∇ 𝑓 (𝑥 𝑡 ) − ∇ 𝑓 (˜ 𝑥 𝑡 ), E𝑡 𝑔𝑡𝑖𝑡 ⟩ 𝜂 𝜂 ≤ −𝜂⟨∇ 𝑓 (𝑥 𝑡 ), E𝑡 𝑔𝑡𝑖𝑡 ⟩ + ∥∇ 𝑓 (𝑥 𝑡 ) − ∇ 𝑓 (˜ 𝑥 𝑡 ) ∥ 2 + ∥E𝑡 𝑔𝑡𝑖𝑡 ∥ 2 2 2 2 𝜂𝐿 𝜂 ≤ −𝜂⟨∇ 𝑓 (𝑥 𝑡 ), E𝑡 𝑔𝑡𝑖𝑡 ⟩ + ∥𝑥 𝑡 − 𝑥˜𝑡 ∥ 2 + ∥E𝑡 𝑔𝑡𝑖𝑡 ∥ 2 2 𝜂 𝜂𝐿 2 𝜂 𝑖𝑡 = − ⟨clip𝑐 (∇ 𝑓 (𝑥 𝑡 )), E𝑡 𝑔𝑡 ⟩ + ∥𝑥 𝑡 − 𝑥˜𝑡 ∥ 2 + ∥E𝑡 𝑔𝑡𝑖𝑡 ∥ 𝛼𝑡 2 2 𝜂 𝜂 𝜂 𝜂𝐿 2 𝜂𝛼𝑡 ∥∇ 𝑓 (𝑥 𝑡 ) ∥ 2 − ∥𝑥 𝑡 − 𝑥˜𝑡 ∥ 2 + ∥E𝑡 𝑔𝑡𝑖𝑡 ∥ 2 ∥E𝑡 𝑔𝑡𝑖𝑡 ∥ 2 + ∥E𝑡 𝑔𝑡𝑖𝑡 − clip𝑐 (∇ 𝑓 (𝑥 𝑡 )) ∥ 2 + =− 2 2𝛼𝑡 2𝛼𝑡 2 2 2 𝜂𝛼𝑡 𝜂 𝜂𝐿 ≤− ∥∇ 𝑓 (𝑥 𝑡 ) ∥ 2 + ∥E𝑡 𝑔𝑡𝑖𝑡 − clip𝑐 (∇ 𝑓 (𝑥 𝑡 )) ∥ 2 + ∥𝑥 𝑡 − 𝑥˜𝑡 ∥ 2 , 2 2𝛼𝑡 2 where the last inequality is due to 𝛼𝑡 ≤ 1, so the two terms involving ∥E𝑡 𝑔𝑡𝑖𝑡 ∥ 2 can be dropped. Applying Lemma B.1 we obtain the stated inequality. □ Theorem B.4. Suppose Assumptions 3.1 and 3.2 hold. Then there exists a constant step size 𝜂 and clipping radius 𝑐 such Í that for 𝜀 ∈ (0, 1), we have 𝑇1 𝑇𝑡=−01 E∥∇ 𝑓 (𝑥 𝑡 ) ∥ ≤ 𝜀 within 2 (𝜎 + 𝜁 2 )𝐿Δ (𝜎 + 𝜁)𝜏𝐶 𝐿Δ 𝜏𝐶 𝐿Δ e 𝑂 + + (10) 𝜀4 𝜀3 𝜀2 iterations of Algorithm 1. Proof. We analyze the convergence in two cases seperately. Case I. We first turn to case when ∥∇ 𝑓 (𝑥 𝑡 ) ∥ ≤ 𝑐/2. Applying (4) and (5) from Lemma B.2 to our main descent inequality, we have E𝑡 𝑓 (˜ 𝑥 𝑡+1 ) − 𝑓 (˜ 𝑥𝑡 )
1! 𝜂 𝑐 − 2𝜁 𝜃 𝜂2 𝐿 2 2 2 + ≤ − ∥∇ 𝑓 (𝑥 𝑡 ) ∥ + 𝜂(4𝜎 Γ(2𝜃 + 1) + 2𝜁 ) exp − 𝜂𝑐2 𝜏𝐶2 𝐿 + 24𝜎 2 Γ(2𝜃 + 1) + 8𝜁 2 + 2∥∇ 𝑓 (𝑥 𝑡 ) ∥ 2 2 4𝜎 2 1! 𝜂3 𝑐2 𝜏𝐶2 𝐿 2 𝜂 𝑐 − 2𝜁 𝜃 2 2 2 = − (1 − 2𝜂𝐿) ∥∇ 𝑓 (𝑥 𝑡 ) ∥ + 𝜂(4𝜎 Γ(2𝜃 + 1) + 2𝜁 ) exp − + 𝜂2 (12𝜎 2 Γ(2𝜃 + 1) + 4𝜁 2 )𝐿 + 2 4𝜎 2 ! 1 𝜂3 𝑐2 𝜏𝐶2 𝐿 2 𝜂 𝑐 − 2𝜁 𝜃 ≤ − ∥∇ 𝑓 (𝑥 𝑡 ) ∥ 2 + 𝜂(4𝜎 2 Γ(2𝜃 + 1) + 2𝜁 2 ) exp − + 𝜂2 (12𝜎 2 Γ(2𝜃 + 1) + 4𝜁 2 )𝐿 + . 4 4𝜎 2
where in the last inequality we used 𝜂 ≤ 1/(4𝐿). Taking the unconditional expectation, we have that 1𝜃 ! 𝜂2 𝑐2 𝜏𝐶2 𝐿 2 1 E[ 𝑓 (˜ 𝑥 ) − 𝑓 (˜ 𝑥 )] 𝑐 − 2𝜁 𝑡 𝑡+ 1 E∥∇ 𝑓 (𝑥 𝑡 ) ∥ 2 ≤ + (4𝜎 2 Γ(2𝜃 +1) +2𝜁 2 ) exp − +𝜂(12𝜎 2 Γ(2𝜃 +1) +4𝜁 2 )𝐿 + . 4 𝜂 4𝜎 2 Summing over 𝑡 ∈ T = {𝑡 : ∥∇ 𝑓 (𝑥 𝑡 ) ∥ ≤ 𝑐/2}, we obtain 1 ∑︁ E∥∇ 𝑓 (𝑥 𝑡 ) ∥ 2 ≤ 4𝑇 𝑡 ∈ T
! 1! 𝜂2 𝑐2 𝜏𝐶2 𝐿 2 𝑐 − 2𝜁 𝜃 1 ∑︁ E[ 𝑓 (˜ 𝑥 𝑡 ) − 𝑓 (˜ 𝑥 𝑡+1 )] 2 2 2 2 + (4𝜎 Γ(2𝜃 + 1) + 2𝜁 ) exp − + 𝜂(12𝜎 Γ(2𝜃 + 1) + 4𝜁 )𝐿 + . 𝑇 𝑡∈T 𝜂 4𝜎 2 16
Clipping Makes Asynchronous SGD Robust to Stragglers
Case II. We now turn to the case when ∥∇ 𝑓 (𝑥 𝑡 ) ∥ > 𝑐/2. Using Jensen’s inequality and nonexpansiveness of the clipping operator, we have ∥E𝑡 𝑔𝑡𝑖𝑡 − clip𝑐 (∇ 𝑓 (𝑥 𝑡 )) ∥ 2 ≤ E𝑡 ∥∇𝐹𝑖𝑡 (𝑥 𝑡 , 𝜉𝑡𝑖𝑡 ) − ∇ 𝑓 (𝑥 𝑡 ) ∥ 2 ≤ 4𝜎 2 Γ(2𝜃 + 1) + 2𝜁 2 . Thus, our main inequality (8) in this case implies that 𝜂𝛼𝑡 𝜂 𝜂2 𝐿 E∥∇ 𝑓 (𝑥 𝑡 ) ∥ 2 + (4𝜎 2 Γ(2𝜃 + 1) + 2𝜁 2 ) + (𝜂𝑐2 𝜏𝐶2 + E∥𝑔𝑡 ∥ 2 ) 2 2𝛼𝑡 2 𝜂 𝜂2 𝑐2 𝐿 𝜂𝛼𝑡 E∥∇ 𝑓 (𝑥 𝑡 ) ∥ 2 + (4𝜎 2 Γ(2𝜃 + 1) + 2𝜁 2 ) ∥∇ 𝑓 (𝑥 𝑡 ) ∥ + (1 + 𝜂𝜏𝐶2 𝐿) ≤− 2 𝑐 2 √︁ where we used that ∥𝑔𝑡 ∥ ≤ 𝑐 always. Whenever ∥∇ 𝑓 (𝑥 𝑡 ) ∥ > 𝑐, we have 𝛼𝑡 = 𝑐/∥∇ 𝑓 (𝑥 𝑡 ) ∥, so if 𝑐 ≥ 2 8Γ(2𝜃 + 1)𝜎 2 + 4𝜁 2 the inequality takes the form 8𝜎 2 Γ(2𝜃 + 1) + 4𝜁 2 𝜂2 𝑐2 𝐿 𝜂𝑐 1− E∥∇ 𝑓 (𝑥 ) ∥ + (1 + 𝜂𝜏𝐶2 𝐿) E[ 𝑓 (˜ 𝑥 𝑡+1 ) − 𝑓 (˜ 𝑥 𝑡 )] ≤ − 𝑡 2 𝑐2 2 3𝜂𝑐 𝜂2 𝑐2 𝐿 ≤− E∥∇ 𝑓 (𝑥 𝑡 ) ∥ + (1 + 𝜂𝜏𝐶2 𝐿) 8 2 E[ 𝑓 (˜ 𝑥 𝑡+1 ) − 𝑓 (˜ 𝑥 𝑡 )] ≤ −
Using 𝜂 ≤ 1/(4𝜏𝐶 𝐿), we arrive at 3𝑐 E[ 𝑓 (˜ 𝑥 𝑡+1 ) − 𝑓 (˜ 𝑥 𝑡 )] 𝜂𝑐2 𝐿 E∥∇ 𝑓 (𝑥 𝑡 ) ∥ ≤ + (1 + 𝜂𝜏𝐶2 𝐿). 8 𝜂 2 Now consider the case when 𝑐/2 < ∥∇ 𝑓 (𝑥 𝑡 ) ∥ < 𝑐, so 𝛼𝑡 = 1. In this case, we have that −∥∇ 𝑓 (𝑥 𝑡 ) ∥ ≤ −𝑐/2 and 1 ≤ ∥∇ 𝑓 (𝑥 𝑡 ) ∥/𝑐. Thus, similarly as in the previous case, our main inequality (8) implies that 𝜂𝑐 𝜂 𝜂2 𝑐2 𝐿 ∥∇ 𝑓 (𝑥 𝑡 ) ∥ + 2Γ(2𝜃 + 1)𝜎 2 ∥∇ 𝑓 (𝑥 𝑡 ) ∥ + (1 + 𝜂𝜏𝐶2 𝐿) 4 𝑐 2 8𝜎 2 Γ(2𝜃 + 1) 𝜂2 𝑐2 𝐿 𝜂𝑐 1− ∥∇ 𝑓 (𝑥 𝑡 ) ∥ + (1 + 𝜂𝜏𝐶2 𝐿) ≤− 2 4 𝑐 2 𝜂𝑐 𝜂2 𝑐2 𝐿 ≤ − ∥∇ 𝑓 (𝑥 𝑡 ) ∥ + (1 + 𝜂𝜏𝐶2 𝐿). 8 2
E𝑡 𝑓 (˜ 𝑥 𝑡+1 ) − 𝑓 (˜ 𝑥𝑡 ) ≤ −
Taking the unconditional expectation, we arrive at the inequality E[ 𝑓 (˜ 𝑥 𝑡 ) − 𝑓 (˜ 𝑥 𝑡+1 )] 𝜂𝑐2 𝐿 𝑐 E∥∇ 𝑓 (𝑥 𝑡 ) ∥ ≤ + (1 + 𝜂𝜏𝐶2 𝐿). 8 𝜂 2 Thus we have that
1 ∑︁ 1 ∑︁ E[ 𝑓 (˜ 𝑥 𝑡 ) − 𝑓 (˜ 𝑥 𝑡+1 )] 𝜂𝑐2 𝐿 𝑐E∥∇ 𝑓 (𝑥 𝑡 ) ∥ = + (1 + 𝜂𝜏𝐶2 𝐿) 8𝑇 𝑡 ∈ T 𝑐 𝑇 𝑡 ∈ T𝑐 𝜂 2
Choosing the parameters.
Putting together the two cases, we have that ! 1! 𝑇 −1 ∑︁ 1 ∑︁ 1 ∑︁ E[ 𝑓 (˜ 𝑥 𝑡 ) − 𝑓 (˜ 𝑥 𝑡+1 )] 𝑐 − 2𝜁 𝜃 2 2 2 + (4𝜎 Γ(2𝜃 + 1) + 2𝜁 ) exp − E∥∇ 𝑓 (𝑥 𝑡 ) ∥ + 𝑐E∥∇ 𝑓 (𝑥 𝑡 ) ∥ ≤ 8𝑇 𝑡 ∈ T 𝑇 𝑡=0 𝜂 4𝜎 𝑡 ∈ T𝑐 𝜂2 𝑐2 𝜏𝐶2 𝐿 2
𝜂𝑐2 𝐿 + 2 2 ! 1𝜃 ! ! Δ 𝑐 − 2𝜁 2 2 2 2 2 2 2 =𝑂 + (𝜎 + 𝜁 ) 𝜂𝐿 + exp − + 𝜂 𝑐 𝜏𝐶 𝐿 + 𝜂𝑐 𝐿 . 𝜂𝑇 4𝜎 + 𝜂(12𝜎 2 Γ(2𝜃 + 1) + 4𝜁 2 )𝐿 +
This means that both 1 ∑︁ E∥∇ 𝑓 (𝑥 𝑡 ) ∥ = 𝑂 𝑇 𝑡∈T
√︄
! 1𝜃 ! √︁ √︁ Δ √︁ 𝑐 − 2𝜁 + 𝜂(𝜎 2 + 𝜁 2 )𝐿 + 𝜎 2 + 𝜁 2 exp − + 𝜂𝑐𝜏𝐶 𝐿 + 𝜂𝑐2 𝐿 𝜂𝑇 4𝜎 17
Clipping Makes Asynchronous SGD Robust to Stragglers
and
! 1 !! 1 ∑︁ Δ 𝜎2 + 𝜁 2 𝑐 − 2𝜁 𝜃 2 2 2 𝜂𝐿 + exp − + 𝜂 𝑐𝜏𝐶 𝐿 + 𝜂𝑐𝐿 . E∥∇ 𝑓 (𝑥 𝑡 ) ∥ = 𝑂 + 𝑇 𝑡 ∈ T𝑐 𝜂𝑐𝑇 𝑐 4𝜎
√︁ We choose the clipping radius to be 𝑐 = 2 8Γ(2𝜃 + 1)𝜎 2 log 𝜃 𝑇 + 4𝜁. Assuming 𝑇 is large enough so that 𝑐 ≥ 1, we have that √︄ ! √︂ 𝑇 −1 2 + 𝜁2 √︁ Δ 𝜎 1 ∑︁ 𝜃 e + 𝜂(𝜎 2 + 𝜁 2 )𝐿 + 𝜂(𝜎 + 𝜁)𝜏𝐶 𝐿 log 𝑇 + . E∥∇ 𝑓 (𝑥 𝑡 ) ∥ = 𝑂 𝑇 𝑡=0 𝜂𝑇 𝑇 Then choosing the step size to be ! 1/3 1/2 1 Δ Δ 𝜂 = min , , , 2 2 2 + 𝜁 2 )𝐿𝑇 2 2 4𝜏 𝐿 (𝜎 (𝜎 + 𝜁 )𝜏𝐶 𝐿 𝑇 𝐶 we obtain 𝑇 −1
1 ∑︁ e E∥∇ 𝑓 (𝑥 𝑡 ) ∥ = 𝑂 𝑇 𝑡=0
√︂
! 2 1/4 1/3 √︂ 2 𝜏𝐶 𝐿Δ 𝜎 + 𝜁2 (𝜎 + 𝜁 2 )𝐿Δ (𝜎 + 𝜁)𝜏𝐶 𝐿Δ + + + . 𝑇 𝑇 𝑇 𝑇
Hence, we require 2 2 e (𝜎 + 𝜁 )𝐿Δ + (𝜎 + 𝜁)𝜏𝐶 𝐿Δ + 𝜏𝐶 𝐿Δ . 𝑂 𝜀4 𝜀3 𝜀2 iteration to reach 𝜀-stationarity.
□
B.2. Convergence with high probability Lemma B.5. If 𝑓 is 𝐿-smooth and 𝛼𝑡 = min{1, 𝑐/∥∇ 𝑓 (𝑥 𝑡 ) ∥}, then 𝜂3 𝑐2 𝜏𝐶2 𝐿 2 𝜂2 𝐿 𝑖𝑡 2 𝜂 𝜂 𝑓 (˜ 𝑥 𝑡+1 ) − 𝑓 (˜ 𝑥 𝑡 ) ≤ − ∥∇ 𝑓 (𝑥 𝑡 ) ∥ 2 + ∥E𝑡 𝑔𝑡𝑖𝑡 − ∇ 𝑓 (𝑥 𝑡 ) ∥ 2 + + ∥𝑔𝑡 ∥ 2 2 2 2 𝑥 𝑡 ) − ∇ 𝑓 (𝑥 𝑡 ), 𝑔𝑡𝑖𝑡 − E𝑡 𝑔𝑡𝑖𝑡 ⟩. − 𝜂⟨∇ 𝑓 (𝑥 𝑡 ), 𝑔𝑡𝑖𝑡 − E𝑡 𝑔𝑡𝑖𝑡 ⟩ − 𝜂⟨∇ 𝑓 (˜
(11)
Proof. Due to 𝐿-smoothness we have that 𝑓 (˜ 𝑥 𝑡+1 ) ≤ 𝑓 (˜ 𝑥 𝑡 ) + ⟨˜ 𝑥 𝑡+1 − 𝑥˜𝑡 , ∇ 𝑓 (˜ 𝑥 𝑡 )⟩ + = 𝑓 (˜ 𝑥 𝑡 ) − 𝜂⟨𝑔𝑡𝑖𝑡 , ∇ 𝑓 (˜ 𝑥 𝑡 )⟩ +
𝐿 ∥˜ 𝑥 𝑡+1 − 𝑥˜𝑡 ∥ 2 2
𝜂2 𝐿 𝑖𝑡 2 ∥𝑔𝑡 ∥ . 2
due to Lemma A.3. We first expand the inner product according to −𝜂⟨∇ 𝑓 (˜ 𝑥 𝑡 ), 𝑔𝑡𝑖𝑡 ⟩ = − 𝜂⟨∇ 𝑓 (𝑥 𝑡 ), E𝑡 𝑔𝑡𝑖𝑡 ⟩
(deterministic descent)
− 𝜂⟨∇ 𝑓 (˜ 𝑥 𝑡 ) − ∇ 𝑓 (𝑥 𝑡 ), E𝑡 𝑔𝑡𝑖𝑡 ⟩ −𝜂⟨∇ 𝑓 (𝑥 𝑡 ), 𝑔𝑡𝑖𝑡 − E𝑡 𝑔𝑡𝑖𝑡 ⟩ − 𝜂⟨∇ 𝑓 (˜ 𝑥 𝑡 ) − ∇ 𝑓 (𝑥 𝑡 ), 𝑔𝑡𝑖𝑡 − E𝑡 𝑔𝑡𝑖𝑡 ⟩ , |
{z
(delay error) (martingale difference)
}
𝑍𝑡
where we note that the last two terms form a martingale difference sequence 𝑍𝑡 adapted to G𝑡 = F𝑡+1 . The first inner product in the right-hand side can be written as 𝜂 𝜂 𝜂 −𝜂⟨∇ 𝑓 (𝑥 𝑡 ), E𝑡 𝑔𝑡𝑖𝑡 ⟩ = − ∥∇ 𝑓 (𝑥 𝑡 ) ∥ 2 − ∥E𝑡 𝑔𝑡𝑖𝑡 ∥ 2 + ∥E𝑡 𝑔𝑡𝑖𝑡 − ∇ 𝑓 (𝑥 𝑡 ) ∥ 2 . 2 2 2
(12)
Using Young’s inequality (Lemma A.4) on the second inner product gives the bound −𝜂⟨∇ 𝑓 (˜ 𝑥 𝑡 ) − ∇ 𝑓 (𝑥 𝑡 ), E𝑡 𝑔𝑡𝑖𝑡 ⟩ ≤
𝜂 𝜂 ∥∇ 𝑓 (˜ 𝑥 𝑡 ) − ∇ 𝑓 (𝑥 𝑡 ) ∥ 2 + ∥E𝑡 𝑔𝑡𝑖𝑡 ∥ 2 . 2 2 18
(13)
Clipping Makes Asynchronous SGD Robust to Stragglers
Moreover, due to 𝐿-smoothness of 𝑓 (Assumption 3.1) and Lemma B.1, we have 𝜂 𝜂𝐿 2 𝜂3 𝑐2 𝐿 2 ∥∇ 𝑓 (˜ 𝑥 𝑡 ) − ∇ 𝑓 (𝑥 𝑡 ) ∥ 2 ≤ ∥˜ 𝑥𝑡 − 𝑥𝑡 ∥ 2 ≤ 2 2 2 By subtracting 𝑓 (˜ 𝑥 𝑡 ) from both sides of (9), we arrive at the stated inequality by noting that the 𝜂2 E𝑡 ∥𝑔𝑡 ∥ 2 terms in (12) and (13) cancel. □ Theorem B.6. Suppose Assumptions 3.1 and 3.2 hold. Then there exists a constant step size 𝜂 and clipping radius 𝑐 such Í 1 that for 𝜀 ∈ (0, 1) and failure probability 𝛿 ∈ (0, 1), we have P 𝑇 𝑇𝑡=−01 ∥∇ 𝑓 (𝑥 𝑡 ) ∥ ≤ 𝜀 ≥ 1 − 𝛿 within 2 𝜃 2𝜃 e 𝜎 log (1/𝛿) + 𝜎𝜏𝐶 log (1/𝛿) + 𝜏𝐶 𝑂 𝜀4 𝜀3 𝜀2
(14)
iterations of Algorithm 1. Proof. Similarly as before, we analyze the convergence in two different cases seperately. Case I. We begin by treating the case when ∥∇ 𝑓 (𝑥 𝑡 ) ∥ ≤ 𝑐/2, in which we will show that the martingale difference sequence concentrates. First, we denote the martingale difference term 𝑍𝑡 = −𝜂⟨∇ 𝑓 (𝑥 𝑡 ), 𝑔𝑡𝑖𝑡 − E𝑡 𝑔𝑡𝑖𝑡 ⟩ − 𝜂⟨∇ 𝑓 (˜ 𝑥 𝑡 ) − ∇ 𝑓 (𝑥 𝑡 ), 𝑔𝑡𝑖𝑡 − E𝑡 𝑔𝑡𝑖𝑡 ⟩ and the indicator function 𝜓𝑡 = {∥∇ 𝑓 (𝑥 𝑡 ) ∥ ≤ 𝑐/2} Since clipping ensures ∥𝑔𝑡𝑖𝑡 ∥ ≤ 𝑐 almost surely, we can bound |𝑍𝑡 | uniformly for 𝑡 ∈ T : |𝜓𝑡 𝑍𝑡 | ≤ 𝜂(∥∇ 𝑓 (𝑥 𝑡 ) ∥ + ∥∇ 𝑓 (˜ 𝑥 𝑡 ) − ∇ 𝑓 (𝑥 𝑡 ) ∥) ∥𝑔𝑡𝑖𝑡 ∥ + ∥E𝑡 𝑔𝑡𝑖𝑡 ∥ 𝑐 ≤ 2𝜂 + 𝜂𝑐𝜏𝐶 𝐿 𝑐 2 3𝜂𝑐2 ≤ 4 where in the second inequality we use that 𝜂 ≤ 1/(4𝜏𝐶 𝐿). By applying the Cauchy-Schwarz inequality and Young’s inequality we can also bound the conditional second moment of 𝑍𝑡 : E[𝑍𝑡2 | F𝑡 ] ≤ 𝜂2 ∥∇ 𝑓 (𝑥 𝑡 ) + ∇ 𝑓 (˜ 𝑥 𝑡 ) − ∇ 𝑓 (𝑥 𝑡 ) ∥ 2 ∥𝑔𝑡𝑖𝑡 − E𝑡 𝑔𝑡𝑖𝑡 ∥ 2 ≤ 𝜂2 2∥∇ 𝑓 (𝑥 𝑡 ) ∥ 2 + 2∥∇ 𝑓 (˜ 𝑥 𝑡 ) − ∇ 𝑓 (𝑥 𝑡 ) ∥ 2 2∥𝑔𝑡𝑖𝑡 ∥ 2 + 2∥E𝑡 𝑔𝑡𝑖𝑡 ∥ 2 ≤ 4𝜂2 𝑐2 ∥∇ 𝑓 (𝑥 𝑡 ) ∥ 2 + 𝜂2 𝑐2 𝜏𝐶2 𝐿 2 . So applying Freedman’s inequality (Lemma A.5) with 𝜌 = 3/16, we have with probability at least 1 − 𝛿/2 that ∑︁ 𝑡∈T
3𝜂𝑐2 4𝜌𝜂2 𝑐2 ∑︁ 2 ∥∇ 𝑓 (𝑥 𝑡 ) ∥ 2 + 𝜂2 𝑐2 𝜏𝐶2 𝐿 2 + log 2 3𝜂𝑐 𝑡 ∈ T 4𝜌 𝛿 ∑︁ 2 1 ≤ 𝜂∥∇ 𝑓 (𝑥 𝑡 ) ∥ 2 + 𝜂3 𝑐2 𝜏𝐶2 𝐿 2 + 4𝜂𝑐2 log . 4 𝑡∈T 𝛿
𝑍𝑡 ≤
Thus, summing (11) over 𝑡 ∈ T , we have ! 3 2 2 2 2 𝜂 𝑐 𝜏 𝐿 𝜂 𝜂 𝜂 𝐿 𝐶 ( 𝑓 (˜ 𝑥 𝑡+1 ) − 𝑓 (˜ 𝑥 𝑡 )) ≤ − ∥∇ 𝑓 (𝑥 𝑡 ) ∥ 2 + ∥E𝑡 𝑔𝑡𝑖𝑡 − ∇ 𝑓 (𝑥 𝑡 ) ∥ 2 + + ∥𝑔𝑡𝑖𝑡 ∥ 2 + 𝑍𝑡 2 2 2 2 𝑡∈T 𝑡∈T ! ∑︁ 𝜂 3𝜂3 𝑐2 𝜏𝐶2 𝐿 2 𝜂2 𝑐2 𝐿 𝜂 2 𝑖𝑡 2 2 ≤ − ∥∇ 𝑓 (𝑥 𝑡 ) ∥ + ∥E𝑡 𝑔𝑡 − ∇ 𝑓 (𝑥 𝑡 ) ∥ + + + 4𝜂𝑐2 log 4 2 4 2 𝛿 𝑡∈T ∑︁
∑︁
19
Clipping Makes Asynchronous SGD Robust to Stragglers
under the same probability. Applying (4) from Lemma (B.2) to the clipping error term ∥E𝑡 𝑔𝑡𝑖𝑡 − ∇ 𝑓 (𝑥 𝑡 ) ∥ 2 and dividing by 𝜂, we have 1 ∑︁ ∥∇ 𝑓 (𝑥 𝑡 ) ∥ 2 4 𝑡∈T ! 1! ∑︁ 𝑓 (˜ 3𝜂2 𝑐2 𝜏𝐶2 𝐿 2 𝜂𝑐2 𝐿 2 𝑥 𝑡 ) − 𝑓 (˜ 𝑥 𝑡+1 ) 𝑐 − 2𝜁 𝜃 2 2 + (4𝜎 Γ(2𝜃 + 1) + 2𝜁 ) exp − + + 4𝑐2 log ≤ + 𝜂 4𝜎 4 2 𝛿 𝑡∈T with probability at least 1 − 𝛿/2. Case II.
We consider the case ∥∇ 𝑓 (𝑥 𝑡 ) ∥ > 𝑐/2. By smoothness, we have
3 2 2
2
𝜂 𝑐 𝜏𝐶 𝐿 𝜂 𝜂2 𝑐2 𝐿 𝜂𝛼𝑡 ∥∇ 𝑓 (𝑥 𝑡 ) ∥ 2 + + ∥𝑔𝑡𝑖𝑡 − clip𝑐 (∇ 𝑓 (𝑥 𝑡 )) ∥ 2 + 2 2𝛼𝑡 2 2 3 2 2 2 𝜂 𝑐 𝜏𝐶 𝐿 𝜂𝛼𝑡 𝜂 𝜂2 𝑐2 𝐿 ≤− ∥∇ 𝑓 (𝑥 𝑡 ) ∥ 2 + + . ∥∇𝐹𝑖𝑡 (𝑥 𝑡 , 𝜉𝑡𝑖𝑡 ) − ∇ 𝑓 (𝑥 𝑡 ) ∥ 2 + 2 2𝛼𝑡 2 2
𝑓 (˜ 𝑥 𝑡+1 ) − 𝑓 (˜ 𝑥𝑡 ) ≤ −
where the second inequality holds due to nonexpansiveness of the clipping operator. Then, under sub-Weibull noise (Assumption 3.2), ∑︁ ∑︁ ∥∇𝐹𝑖𝑡 (𝑥 𝑡 , 𝜉𝑡𝑖𝑡 ) − ∇ 𝑓 (𝑥 𝑡 ) ∥ 2 ≤ (2∥∇𝐹𝑖𝑡 (𝑥 𝑡 , 𝜉𝑡𝑖𝑡 ) − ∇ 𝑓𝑖𝑡 (𝑥 𝑡 ) ∥ 2 + 2∥∇ 𝑓𝑖𝑡 (𝑥 𝑡 ) − ∇ 𝑓 (𝑥 𝑡 ) ∥ 2 ) 𝑡 ∈ T𝑐
𝑡 ∈ T𝑐 2
≤ 2𝜎 log2 𝜃 (2𝑇/𝛿) + 2𝜁 2
with probability at least 1 − 𝛿/2. Thus for all 𝑡 ∈ T 𝑐 , we have under the same probability that if ∥∇ 𝑓 (𝑥 𝑡 ) ∥ ≤ 𝑐 3 2 2
2
3 2 2
2
𝜂 𝑐 𝜏𝐶 𝐿 𝜂 𝜂2 𝑐2 𝐿 𝜂𝛼𝑡 ∥∇ 𝑓 (𝑥 𝑡 ) ∥ 2 + (𝜎 2 log2 𝜃 (4𝑇/𝛿) + 𝜁 2 ) + + 2 𝛼𝑡 2 2 3 2 2 2 𝜂 𝑐 𝜏𝐶 𝐿 𝜂𝑐 𝜂 𝜂2 𝑐2 𝐿 ≤ − ∥∇ 𝑓 (𝑥 𝑡 ) ∥ + 2 (𝜎 2 log2 𝜃 (4𝑇/𝛿) + 𝜁 2 ) ∥∇ 𝑓 (𝑥 𝑡 ) ∥ + + 4 𝑐 2 2 𝜂3 𝑐2 𝜏𝐶2 𝐿 2 𝜂2 𝑐2 𝐿 𝜂𝑐 8(𝜎 2 log2 𝜃 (4𝑇/𝛿) + 𝜁 2 ) ≤− 1− ∥∇ 𝑓 (𝑥 𝑡 ) ∥ + + , 4 𝑐2 2 2
𝑓 (˜ 𝑥 𝑡+1 ) − 𝑓 (˜ 𝑥𝑡 ) ≤ −
whereas if ∥∇ 𝑓 (𝑥 𝑡 ) ∥ ≥ 𝑐,
𝜂 𝑐 𝜏𝐶 𝐿 𝜂𝛼𝑡 𝜂 𝜂2 𝑐2 𝐿 ∥∇ 𝑓 (𝑥 𝑡 ) ∥ 2 + (𝜎 2 log2 𝜃 (2/𝛿) + 𝜁 2 ) + + 2 𝛼𝑡 2 2 3 2 2 2 𝜂 𝑐 𝜏 𝐿 𝜂𝑐 𝜂 𝜂2 𝑐2 𝐿 𝐶 ≤ − ∥∇ 𝑓 (𝑥 𝑡 ) ∥ + (𝜎 2 log2 𝜃 (2/𝛿) + 𝜁 2 ) ∥∇ 𝑓 (𝑥 𝑡 ) ∥ + + 2 𝑐 2 2 3 2 2 2 2𝜃 2 2 2 2 𝜂 𝑐 𝜏 𝐿 2(𝜎 log (2/𝛿) + 𝜁 ) 𝜂 𝑐 𝐿 𝜂𝑐 𝐶 1− ∥∇ 𝑓 (𝑥 𝑡 ) ∥ + + . ≤− 2 𝑐2 2 2
𝑓 (˜ 𝑥 𝑡+1 ) − 𝑓 (˜ 𝑥𝑡 ) ≤ −
√︁ Hence, choosing 𝑐 ≥ 4 𝜎 2 log2 𝜃 (2/𝛿) + 𝜁 2 , we have ∑︁ 1 ∑︁ 𝑐∥∇ 𝑓 (𝑥 𝑡 ) ∥ ≤ 8𝑇 𝑡 ∈ T 𝑐 𝑡 ∈ T𝑐
2 2 2
2
𝑓 (˜ 𝑥 𝑡+1 ) − 𝑓 (˜ 𝑥 𝑡 ) 𝜂 𝑐 𝜏𝐶 𝐿 𝜂𝑐2 𝐿 + + 𝜂 2 2
!
with probability at least 1 − 𝛿/2. Choosing the parameters.
Putting the two cases together, we have that ! 𝑇 −1 2 2 2 2 ∑︁ 1 ∑︁ 1 ∑︁ 𝑓 (˜ 𝑥 𝑡 ) − 𝑓 (˜ 𝑥 𝑡+1 ) 3𝜂 𝑐 𝜏𝐶 𝐿 𝜂𝑐2 𝐿 ∥∇ 𝑓 (𝑥 𝑡 ) ∥ 2 + 𝑐∥∇ 𝑓 (𝑥 𝑡 ) ∥ ≤ + + 8𝑇 𝑡 ∈ T 𝑇 𝑡=0 𝜂 4 2 𝑡 ∈ T𝑐 1! 𝑐 − 2𝜁 𝜃 2 2 2 + (4𝜎 Γ(2𝜃 + 1) + 2𝜁 ) exp − + 4𝑐2 log 4𝜎 𝛿 20
Clipping Makes Asynchronous SGD Robust to Stragglers
with probability atleast 1 − 𝛿. Using the same technique as in the proof of Theorem B.4, we have that √︄ ! 1 ! √︂ 2 𝑇 −1 √︁ Δ √︁ 2 𝑐 log(1/𝛿) 1 ∑︁ Δ 1 𝑐 − 2𝜁 𝜃 2 2 ∥∇ 𝑓 (𝑥 𝑡 ) ∥ = 𝑂 + + 𝜂𝑐 𝐿 + 𝜂𝑐𝜏𝐶 𝐿 + 𝜎 + 𝜁 exp − + 𝑇 𝑡=0 𝜂𝑐𝑇 𝜂𝑇 2 4𝜎 𝑇 with probability at least 1 − 𝛿. Then if √︃ 𝑐 = max 4 𝜎 2 log2 𝜃 (2/𝛿) + 𝜁 2 , 4𝜎 log 𝜃 𝑇 + 2𝜁 and assuming 𝑇 is large enough that 𝑐 ≥ 1, we have √︄ √︄ 𝑇 −1 √︁ 1 ∑︁ Δ 𝜎 2 log2 𝜃+1 (1/𝛿) + 𝜁 2 ª © e ∥∇ 𝑓 (𝑥 𝑡 ) ∥ = 𝑂 + 𝜂(𝜎 2 + 𝜁 2 )𝐿 + 𝜂(𝜎 + 𝜁)𝜏𝐶 𝐿 log 𝜃 (𝑇/𝛿) + ® 𝑇 𝑡=0 𝜂𝑇 𝑇 ¬ « with probability at least 1 − 𝛿. Then choosing ! 1/3 1/2 1 Δ Δ 𝜂 = min , , , 2 2 𝜃 2 2 2 2 2 4𝜏𝐶 𝐿 (𝜎 + 𝜁 ) log (𝑇/𝛿)𝐿𝑇 (𝜎 + 𝜁 )𝜏𝐶 𝐿 𝑇 we have 𝑇 −1
1 ∑︁ ∥∇ 𝑓 (𝑥 𝑡 ) ∥ 𝑇 𝑡=0 1/4 1/3 1/2 2 ! 2 𝜃 2 𝜃+1 2𝜃 2 1/2 2 (𝜎 + 𝜁)𝜏 log (𝑇/𝛿)𝐿Δ 𝜏 𝐿Δ 𝜎 log (1/𝛿) + 𝜁 (𝜎 + 𝜁 ) log (𝑇/𝛿)𝐿Δ 𝐶 𝐶 e + + + =𝑂 𝑇 𝑇 𝑇 𝑇 with the same probability. Then, for 𝜀 ∈ (0, 1), it holds that P( 𝑇1
Í𝑇 −1 𝑡=0
∥∇ 𝑓 (𝑥 𝑡 ) ∥ ≤ 𝜀) ≥ 1 − 𝛿 after
2 (𝜎 + 𝜁 2 ) log2 𝜃 (1/𝛿)𝐿Δ (𝜎 + 𝜁)𝜏𝐶 log 𝜃 (1/𝛿)𝐿Δ 𝜏𝐶 𝐿Δ 𝜎 2 log2 𝜃+1 (1/𝛿) + 𝜁 2 e 𝑂 + + + 𝜀4 𝜀3 𝜀2 𝜀2 iterations. □
21