Asynchronous Heavy-Tailed Optimization

Junfei Sun; Dixi Yao; Xuchen Gong; Tahseen Rabbani; Manzil Zaheer; Tian Li

cs.LGFeb 20, 2026

Asynchronous Heavy-Tailed Optimization

Authors: Junfei Sun, Dixi Yao, Xuchen Gong, Tahseen Rabbani, Manzil Zaheer, Tian Li

Organizations: University of Chicago · Work done at Meta.

Abstract

Heavy-tailed stochastic gradient noise, commonly observed in transformer models, can destabilize the optimization process. Recent works mainly focus on developing and understanding approaches to address heavy-tailed noise in the centralized or distributed, synchronous setting, leaving the interactions between such noise and asynchronous optimization underexplored. In this work, we investigate two communication schemes that handle stragglers with asynchronous updates in the presence of heavy-tailed gradient noise. We propose and theoretically analyze algorithmic modifications based on delay-aware learning rate scheduling and delay compensation to enhance the performance of asynchronous algorithms. Our convergence guarantees under heavy-tailed noise match the rate of the synchronous counterparts and improve delay tolerance compared with existing asynchronous approaches. Empirically, our approaches outperform prior synchronous and asynchronous methods in terms of accuracy/runtime trade-offs and are more robust to hyperparameters in both image and language tasks.

Figures & tables

Panel of Figure 1 — Figure 1: Illustrations of server- and client-centric asynchronous models where the total number of workers $N=3$ , number of local steps $K=3$ , and asynchronous buffer size $M=2$ .

Panel of Figure 2 — Algorithm 2 Proposed: $SGDClip$ / $Clip^{2}$ with staleness-aware downplaying (SD) and $Clip^{2}$ with delay compensation (DC)

	Async Mode	MNLI	QNLI	QQP	RTE	SST-2	MRPC	CoLA	STS-B	Avg
Mild Straggler	Sync	83.67	87.33	79.86	64.30	92.88	86.03	82.08	86.54	82.84
	Server	83.54	84.72	86.33	60.29	92.66	86.03	81.11	88.14	82.85
	Client	81.87	86.86	85.37	70.04	91.63	87.01	81.02	87.14	81.70
Large Straggler	Sync	83.30	87.22	83.03	64.30	92.78	85.05	79.77	86.43	81.45
	Server	82.58	85.78	86.09	59.95	91.97	83.58	80.44	85.63	82.00
	Client	82.19	86.89	85.39	67.87	92.29	85.05	80.15	86.92	81.33

Table 1: Comparison of synchronous training with vanilla server- and client-centric asynchronous training (Algorithm 1 ) on the GLUE benchmark. We see that under both mild and large delays, neither server-centric or client-centric variant degrades accuracies compared with the synchronous case, while greatly reducing the runtime (see Table 14 in the appendix). The optimizer is

Clip^{2}

Figure 2: Test loss versus #epochs (left) and runtime (right) of synchronous SGDClip/

Clip^{2}

and asynchronous SGDClip/

Clip^{2}

with large stragglers. We observe that asynchronous methods provide similar loss as synchronous versions with significantly less runtime, across different optimizers including

Clip^{2}

which is designed to handle heavy-tailed noise. Moreover, comparing ‘CC Async SGDClip’ with ‘CC Async Clip 2 ’ (or ‘SC Async SGDClip’ with ‘SC Async Clip 2 ’), we see that

Clip^{2}

has inherent benefits to control the bias caused by asynchrony. We observe similar trends for the mild straggler setting (Figure 5 in the appendix).

Figure 3: Test loss versus #epochs and runtime of Sync SGDClip, Async SGDClip and

Clip^{2}

under a specific hyperparameter choice on CIFAR-10. ‘cr, sr, cu, su’ denotes client learning rate, server learning rate, client upper clipping bound, and server upper clipping bound, respectively. We see that vanilla asynchronous could cause divergence, whereas

Clip^{2}

, which is originally designed to handle heavy-tailed noise, can help convergence.

Figure 4: Test loss versus #epochs of vanilla asynchronous method and that with staleness-aware downplaying (SD) under SGDClip optimizer for three hyperparameter choices. SD largely improves the robustness of hyperparameter choosing.

	Async Mode	Methods	MNLI	QNLI	QQP	RTE	SST-2	MRPC	CoLA	STS-B	Avg
Mild Straggler	Server	vanilla	83.54	84.72	86.33	60.29	92.66	86.03	81.11	88.14	82.85
		SD	82.18	87.24	84.48	64.32	93.11	82.11	80.47	87.33	82.66
		DC	83.30	86.66	86.52	56.32	92.09	82.35	79.87	86.36	82.93
	Client	vanilla	81.87	86.86	85.37	70.04	91.63	87.01	81.02	87.14	81.70
		SD	83.42	86.91	86.10	70.76	92.20	85.78	80.35	86.19	84.00
		DC	81.56	86.53	86.57	70.40	92.09	86.76	81.88	88.37	84.27

Table 2: Comparison of results on GLUE for server- and client-centric training scenarios with and without staleness-aware downplaying (SD) and delay compensation (DC). The base optimizer is

Clip^{2}

. We see that SD or DC (Algorithm 2 ) improves over the vanilla asynchronous algorithm (Algorithm 1 ) in most cases.

Appendix figures & tables16 assets

Supplementary material from the paper’s appendix.

Appendix

Assumptions	Sync w/ local updates	Async w/ local updates	Dependence on the delay
Bounded variance Non-convex & smooth	$T^{-1/2}$	$O(T^{-1/2}+T^{-1}\tau\tau_{avg})$ ( Wang et al., 2024a ) $O(T^{-1/2})$ ( Nguyen et al., 2022 )	$O(\tau\tau_{avg})$ ( Wang et al., 2024a ) $\tau\leq O(T^{1/4})$ or $O(\tau^{2})$ ( Nguyen et al., 2022 )
Heavy-tailed noise (unbounded variance) Non-convex & smooth	$T^{\frac{1-\alpha}{4\alpha-2}}$ ( Lee et al., 2025 )	This paper Vanilla async: SGDClip (Theorem 4 ): $T^{\frac{1-\alpha}{2\alpha}}$ Clip 2 (Theorem 5 ): $T^{\frac{1-\alpha}{4\alpha-2}}$ Staleness-aware downplaying: SGDClip (Theorem 1 ): $T^{\frac{1-\alpha}{2\alpha}}$ Clip 2 (Theorem 2 ): $T^{-r}$ , where $r=\min\{\frac{3(\alpha-1)}{8},\frac{\alpha-1}{4\alpha}\}$	This paper Vanilla async: SGDClip (Theorem 4 ): $\tau\leq O(T^{\frac{1}{2\alpha}})$ or $O(\tau)$ Clip 2 (Theorem 5 ): $\tau\leq O(T^{\frac{\alpha}{4\alpha-2}})$ or $O(\tau)$ Staleness-aware downplaying: SGDClip (Theorem 1 ): $\tau\leq\frac{1}{2\alpha}$ ; explicit dependence (Proposition 1 ): unrestricted by the largest delay Clip 2 (Theorem 2 ): $\tau\leq\frac{1}{4}+\frac{1}{4\alpha}$ ; explicit dependence (Proposition 2 ): unrestricted by the largest delay
Heavy-tailed noise (unbounded variance) Strongly-convex	$T^{\frac{1-\alpha}{4\alpha-2}}$ ( Lee et al., 2025 )	This paper Non-convex results naturally carry over Additionally: Delay Compensation (Theorem 3 ): $T^{\frac{1-\alpha}{4\alpha-2}}$	This paper Non-convex results naturally carry over Additionally: Delay Compensation (Theorem 3 ): $\tau\leq O(T^{\frac{1}{2\alpha}})$ ; explicit dependence: $O(\tau)$ , with a constant improvement of $\\|1-\eta_{\ell}\\|$ relative to vanilla

Appendix

Table 3: Comparison of convergence rates and delay dependence for various optimization settings. This paper is the first to give explicit theoretical guarantees for asynchronous training under heavy-tailed noise. We see that all our methods achieve comparable convergence rates to the synchronous baseline ( Lee et al., 2025 ) under certain delay tolerance. Moreover, staleness-aware downplaying possesses the benefit of converging even with unbounded delay, which is different from prior works ( Wang et al., 2024a ; Liu et al., 2024 ) . Delay compensation achieves a constant improvement of

1-\eta_{\ell}

relative to vanilla asynchronous methods.

Algorithm	Server-side LR	Client-side LR	Server-side U	Client-side U
SGDClip	(0.1, 0.01, 0.001, 0.0001)	(0.1, 0.01, 0.001, 0.0001)	-	np.linspace( $10^{-4}$ , 1.5, 4)
$Clip^{2}$	(0.1, 0.01, 0.001, 0.0001)	(0.1, 0.01, 0.001, 0.0001)	np.linspace( $10^{-4}$ , 1.5, 4)	np.linspace( $10^{-4}$ , 1.5, 4)
SD-SGDClip	(0.1, 0.01, 0.001, 0.0001)	(0.1, 0.01, 0.001, 0.0001)	-	np.linspace( $10^{-4}$ , 1.5, 4)
SD- $Clip^{2}$	(0.1, 0.01, 0.001, 0.0001)	(0.1, 0.01, 0.001, 0.0001)	np.linspace( $10^{-4}$ , 1.5, 4)	np.linspace( $10^{-4}$ , 1.5, 4)
DC-SGDClip	(0.1, 0.01, 0.001, 0.0001)	(0.1, 0.01, 0.001, 0.0001)	-	np.linspace( $10^{-4}$ , 1.5, 4)
DC- $Clip^{2}$	(0.1, 0.01, 0.001, 0.0001)	(0.1, 0.01, 0.001, 0.0001)	np.linspace( $10^{-4}$ , 1.5, 4)	np.linspace( $10^{-4}$ , 1.5, 4)

Appendix

Table 4: Hyperparameter sweep grids.

Algorithm	Straggler mode	Server-side LR	Client-side LR	Server-side U	Client-side U
Sync SGDClip	large	0.0001	0.01	-	0.0001
Sync SGDClip	mild	0.0001	0.01	-	1.0
SC Async SGDClip	large	0.0001	0.0001	-	0.5
SC Async SGDClip	mild	0.0001	0.01	-	1.0
CC Async SGDClip	large	0.0001	0.0001	-	0.5
CC Async SGDClip	mild	0.0001	0.001	-	0.5

Appendix

Table 5: Optimal Hyperparameters for experiments on CIFAR-10.

Dataset	Algorithm	Straggler mode	Server-side LR	Client-side LR	Server-side U	Client-side U
MNLI	SGDClip	mild&large	1	0.56	-	0.0001
	Sync $Clip^{2}$	mild&large	1	0.5	0.75	0.0001
	Async $Clip^{2}$	mild&large	1	0.5	1	0.0001
QQP	SGDClip	mild&large	1	0.56	-	0.0001
	$Clip^{2}$	mild&large	1	0.5	1.5	0.0001
	SGDClip	mild&large	1	0.5	-	0.0001

Appendix

Table 6: Optimal Hyper-parameters for task: MNLI, QQP, RTE, SST-2 and SST-B in the GLUE benchmark.

Dataset	Algorithm	Straggler mode	Server-side LR	Client-side LR	Server-side U	Client-side U
QNLI	Sync SGDClip	mild&large	1	0.44	-	0.0001
	Async SGDClip	mild&large	1	0.5	-	0.0001
	Sync $Clip^{2}$	large	0.5	0.5	0.001	0.0001
	Sync $Clip^{2}$	mild	1	0.5	0.01	0.0001
	SC Async $Clip^{2}$	large	0.5	0.5	0.001	0.0001
	SC Async $Clip^{2}$	mild	0.5	0.5	0.01	0.0001

Appendix

Table 7: Optimal Hyperparameters for task QNLI, MRPC, and CoLA on GLUE benchmark.

Methods	CIFAR-10		GLUE
	Acc.	runtime	Acc.	runtime
Sync SGDClip (mild straggler)	98.6	818	82.5	93
Server-centric Async SGDClip (mild straggler)	97.7	40	83.4	21
Client-centric Async SGDClip (mild straggler)	98.4	36	83.0	20
Sync SGDClip (large straggler)	98.6	3170	82.5	445
Server-centric Async SGDClip (large straggler)	97.7	44	82.2	36

Appendix

Table 8: Best accuracy and runtime comparisons of Sync SGDClip and Async SGDClip. Asynchronous training achieves similar test performance compared with the synchronous case but requires much less runtime.

Methods	CIFAR-10		GLUE
	Acc.	runtime	Acc.	runtime
Sync $Clip^{2}$ (mild straggler)	98.4	860	82.7	95
Server-centric Async $Clip^{2}$ (mild straggler)	98.3	40	82.9	23
Client-centric Async $Clip^{2}$ (mild straggler)	98.1	37	83.9	26
Sync $Clip^{2}$ (large straggler)	98.4	3139	82.6	380
Server-centric Async $Clip^{2}$ (large straggler)	98.2	42	82.0	21

Appendix

Table 9: Best accuracy and runtime comparisons of synchronous

Clip^{2}

and asynchronous

Clip^{2}

. Asynchronous training achieves similar test performance compared with the synchronous case but requires much less runtime.

Async Mode	Methods	CIFAR-10		GLUE
		Acc.	runtime	Acc.	runtime
Server-centric	SGDClip (mild straggler)	97.7	40	83.4	21
	SD-SGDClip (mild straggler)	98.2	41	82.0	24
	SGDClip (large straggler)	97.7	44	82.2	36
	SD-SGDClip (large straggler)	98.2	44	81.9	22
Client-centric	SGDClip (mild straggler)	98.4	36	83.0	20

Appendix

Table 10: Best accuracy and runtime comparisons of Async SGDClip and Async SD-SGDClip (i.e., SGDClip with staleness-aware downplaying).

Async Mode	Methods	CIFAR-10		GLUE
		Acc.	runtime	Acc.	runtime
Server-centric	Clip 2 (mild straggler)	98.3	40	82.9	23
	SD- Clip 2 (mild straggler)	98.2	39	82.7	22
	DC- Clip 2 (mild straggler)	98.4	42	81.8	24
	Clip 2 (large straggler)	98.2	42	82.0	21
	SD- Clip 2 (large straggler)	98.2	43	81.6	18

Appendix

Table 11: Best Accuracy and Runtime comparisons of Async

Clip^{2}

, Async SD-

Clip^{2}

, and Async DC-

Clip^{2}

Async Mode	Methods	Acc.
Server-centric	Clip 2 (mild straggler)	98.3
	SD- Clip 2 (mild straggler)	98.2
	DC- Clip 2 (mild straggler)	98.4
	Clip 2 (large straggler)	98.2
	SD- Clip 2 (large straggler)	98.2
	DC- Clip 2 (large straggler)	98.5

Appendix

Table 12: Accuracies (in %) Comparison for

(SD/DC-)Clip^{2}

with FADAS and DN+DyLU on CIFAR-10.

Algorithm	Straggler	M=1 Acc.	M=1 Runtime	M=10 Acc.	M=10 Runtime	M=20 Acc.	M=20 Runtime	M=30 Acc.	M=30 Runtime
Sync SGDClip	large	97.4	1328	97.0	4715	97.0	5163	96.9	5393
Async SGDClip	large	10.3	10	97.3	115	97.5	289	97.7	832
SD SGDClip	large	10.3	12	97.4	122	97.7	291	97.8	869
Sync SGDClip	mild	96.8	559	98.5	1036	98.3	1081	98.4	1090
Async SGDClip	mild	9.8	11	98.3	104	98.5	248	98.4	541
SD SGDClip	mild	9.8	12	97.1	98	97.6	248	97.9	541

Appendix

Table 13: Accuracies (in %) and runtimes for different

M

values on CIFAR-10.

Figure 5: Best Test Loss v.s. Epochs and Runtime of Sync SGDClip/

Clip^{2}

and Async SGDClip/

Clip^{2}

under the mild straggler setting on CIFAR-10.

		Mode	MNLI		QNLI		QQP		RTE		SST-2		MPRC		CoLA		STS-B
Algorithm	Straggler		Acc.	Runtime	Acc.	Runtime	Acc.	Runtime	Acc.	Runtime	Acc.	Runtime	Acc.	Runtime	Acc.	Runtime	Pearson	Runtime
SGDClip	Mild	Sync.	83.15	96	86.58	102	86.98	96	57.76	105	91.86	88	84.80	94	81.11	63	87.32	103
		Server	82.50	19	84.72	18	86.33	23	69.26	26	92.09	16	82.11	24	81.59	19	88.92	22
		Client	82.18	19	86.91	18	81.91	15	70.04	16	91.51	18	82.35	32	80.15	23	89.33	19
	Large	Sync.	82.88	451	86.53	510	86.92	509	63.18	443	92.20	516	83.58	303	81.21	369	83.65	457
		Server	82.58	21	85.78	22	86.09	16	60.29	16	91.97	17	80.39	19	81.69	31	88.42	26

Appendix

Table 14: Accuracy and runtime comparison of synchronous, server-centric asynchronous, and client-centric asynchronous methods under SGDClip and

Clip^{2}

optimizers, in settings with mild and large stragglers.

		Mode	MNLI		QNLI		QQP		RTE		SST-2		MPRC		CoLA		STS-B
Algorithm	Straggler		Acc.	Runtime	Acc.	Runtime	Acc.	Runtime	Acc.	Runtime	Acc.	Runtime	Acc.	Runtime	Acc.	Runtime	Pearson	Runtime
SGDClip	Mild	Server	81.57	23	84.40	26	85.35	23	61.39	20	91.17	25	83.82	24	82.07	22	86.36	25
	Mild	Client	80.14	23	86.53	13	82.78	11	64.26	9	90.94	22	83.33	26	81.40	13	88.65	20
	Large	Server	81.50	26	81.99	23	85.26	20	60.3	21	92.10	23	85.29	22	81.40	20	87.36	22
	Large	Client	82.20	14	87.42	43	84.43	13	63.90	13	91.17	25	83.58	33	81.02	28	88.46	68
$Clip^{2}$	Mild	Server	82.18	21	87.24	26	84.48	17	64.32	21	93.11	20	82.11	20	80.47	22	87.33	25

Appendix

Table 15: Accuracy and runtime comparison of synchronous, server-centric asynchronous, and client-centric asynchronous methods under SGDClip and

Clip^{2}

optimizers, in settings with mild and large stragglers. We additionally leverage staleness-aware downplaying.

		Mode	MNLI		QNLI		QQP		RTE		SST-2		MPRC		CoLA		STS-B
Algorithm	Straggler		Acc.	Runtime	Acc.	Runtime	Acc.	Runtime	Acc.	Runtime	Acc.	Runtime	Acc.	Runtime	Acc.	Runtime	Pearson	Runtime
$Clip^{2}$	Mild	Server	83.30	30	86.66	31	86.52	31	56.32	19	93.23	22	82.35	21	79.87	17	86.36	20
	Mild	Client	81.56	29	86.53	23	86.57	36	70.40	33	92.09	21	86.76	31	81.88	53	88.37	38
	Large	Server	83.50	30	86.47	27	86.92	34	58.14	19	92.78	19	77.45	26	80.57	21	85.60	22
	Large	Client	82.29	23	86.36	36	84.44	59	66.43	48	91.63	25	86.03	42	81.78	370	87.91	113

Appendix

Table 16: Accuracy and runtime comparison of synchronous, server-centric asynchronous, and client-centric asynchronous methods under SGDClip and

Clip^{2}

optimizers, in settings with mild and large stragglers. We additionally leverage delay compensation.

Algorithm	Straggler	Async Mode	MNLI	QNLI	QQP	RTE	SST-2	MPRC	CoLA	STS-B	Avg
$Clip^{2}$	Large	Server	82.58	85.78	86.09	59.95	91.97	83.58	80.44	85.63	82.00
$Clip^{2}$	Large	Client	82.19	86.89	85.39	67.87	92.29	85.05	80.15	86.92	81.33
SD- $Clip^{2}$	Large	Server	82.50	87.59	84.47	54.51	92.78	84.31	81.40	85.60	81.65
SD- $Clip^{2}$	Large	Client	83.35	86.55	86.96	72.56	91.51	86.52	80.73	86.60	84.35
DC- $Clip^{2}$	Large	Server	83.50	86.47	86.92	58.14	92.78	77.45	80.57	85.60	81.43
DC- $Clip^{2}$	Large	Client	82.29	86.36	84.44	66.43	91.63	86.03	81.78	87.91	83.36

Appendix

Table 17: Accuracy comparison between (SD/DC-)

Clip^{2}

and FADAS.

Stochastic Optimization

Stochastic optimization studies how to find good decisions or model parameters when objectives, data, or feedback are random or noisy.

See all 210 papers

May 3, 2026

Bringing Order to Asynchronous SGD: Towards Optimality under Data-Dependent Delays with Momentum

Asynchronous SGD enables scalable distributed training but suffers from stale gradients. When delays depend on the data, slower samples may be underrepresented, biasing training toward faster samples. We introduce ordered momentum, a unified framework that attains the best-known rates for smooth convex and non-convex objectives under both data-independent and data-dependent delays. Notably, we establish (i) the first convergence guarantee for smooth convex objectives with data-dependent delays and, among analyses of data-dependent delays, the first to (ii) benefit from parallelization and (iii) match the tight data-independent rate, with a leading stochastic term independent of the number of workers. Finally, we derive robust learning rates that simplify hyperparameter tuning across convex and non-convex settings.

Tehila Dahan, Roie Reshef, Sharon Goldstein +1

Technion – Israel Institute of Technology, Haifa, Israel

Momentum Methods Distributed Optimization Nonconvex Stochastic Optimization Stochastic Optimization Convergence Stochastic Gradient Descent

Ask PDF

Mar 27, 2026

Optimization Trade-offs in Asynchronous Federated Learning: A Stochastic Networks Approach

Synchronous federated learning scales poorly due to the straggler effect. Asynchronous algorithms increase the update throughput by processing updates upon arrival, but they introduce two fundamental challenges: gradient staleness, which degrades convergence, and bias toward faster clients under heterogeneous data distributions. Although algorithms such as AsyncSGD and Generalized AsyncSGD mitigate this bias via client-side task queues, most existing analyses neglect the underlying queueing dynamics and lack closed-form characterizations of the update throughput and gradient staleness. To close this gap, we develop a stochastic queueing-network framework for Generalized AsyncSGD that jointly models random computation times at the clients and the central server, as well as random uplink and downlink communication delays. Leveraging product-form network theory, we derive a closed-form expression for the update throughput, alongside closed-form upper bounds for both the communication round complexity and the expected wall-clock time required to reach an

ε

-stationary point. These results formally characterize the trade-off between gradient staleness and wall-clock convergence speed. We further extend the framework to quantify energy consumption under stochastic timing, revealing an additional trade-off between convergence speed and energy efficiency. Building on these analytical results, we propose gradient-based optimization strategies to jointly optimize routing and concurrency. Experiments on EMNIST demonstrate reductions of 29%--46% in convergence time and 36%--49% in energy consumption compared to AsyncSGD.

Abdelkrim Alahyane, Céline Comte, Matthieu Jonckheere

LAAS-SARA · EMINES, Mohammed VI Polytechnic University, Ben Guerir, Morocco · LAAS-CNRS, Université de Toulouse, CNRS, Toulouse, France +1

Asynchronous Federated Learning Federated Learning Stochastic Optimization Convergence

Ask PDF

Jun 11, 2026

Clipping Makes Distributed and Federated Asynchronous SGD Robust to Stragglers

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 heavy-tailed distributions, motivated by empirical observations in deep learning. We show convergence in expectation, and the first time in asynchronous optimization, convergence with high probability.

Samuel Erickson, Mikael Johansson

School of EECS, KTH Royal Institute of Technology, Stockholm, Sweden.

Gradient Clipping Stochastic Optimization Convergence Distributed Training Federated Learning Stochastic Gradient Descent

Ask PDF

Abstract

Stochastic Optimization

Explore similar work

Bringing Order to Asynchronous SGD: Towards Optimality under Data-Dependent Delays with Momentum

Optimization Trade-offs in Asynchronous Federated Learning: A Stochastic Networks Approach

Clipping Makes Distributed and Federated Asynchronous SGD Robust to Stragglers