Robustifying Asynchronous SGD via Soft Throttling

Kaoru Otsuka; Maxime Meyer; Yuki Takezawa; Makoto Yamada; Anastasia Koloskova

cs.LGSep 30, 2026

Robustifying Asynchronous SGD via Soft Throttling

Authors: Kaoru Otsuka, Maxime Meyer, Yuki Takezawa, Makoto Yamada, Anastasia Koloskova

Organizations: Okinawa Institute of Science and Technology · National University of Singapore · Toyota Motor Corporation · University of Zurich

Abstract

Asynchronous SGD is a popular algorithm for distributed learning where each client's gradient update is applied on arrival. This leads to a speed-up, but also an increased vulnerability to attacks, as fast clients can dominate the total update. We introduce Throttle, a Byzantine-robust generalization of asynchronous SGD where the key idea is to exponentially down-weight updates from faster clients by a factor $q$ . Both asynchronous SGD ( $q=1$ ) and synchronous Byzantine-robust SGD ( $q\to\infty$ ) correspond to specific settings of Throttle. We provide a theoretical analysis of the convergence rate and validate the robustness to attacks both theoretically and empirically. Remarkably, our experiments show that this down-weighting mechanism can also improve performance over standard asynchronous SGD even in the non-Byzantine setting.

Figures & tables

Panel of Figure 1 — Figure 1: Illustration of Throttle with three clients. A block $\bm{g}_{i}^{(t)}$ is a gradient computation started at $\bm{x}^{(t)}$ (its left end), and its coefficient is the weight it receives on arrival, $1/n$ for a first arrival and $1/q^{c}$ for a repeated one. Dashed lines mark the synchronous clock $S_{r}$ , at which in-flight computations are discarded (hatched blocks) and all clients restart from $\bm{x}^{(S_{r})}$ (green blocks).

Figure 2: Test accuracy on MNIST with

n=25

clients,

|{\mathcal{B}}|=5

Byzantine clients. Standard attacks (RD,NG,Empire,ALIE) under the scheduler based on the codebase 0 0 footnotemark: 0 , in which Byzantine updates are at most

1/3

of all gradients at any time. Flooding attacks under using a fixed vector/random vectors. The higher

\rho

, the more frequently the Byzantine clients send their updates. Throttle keeps a higher accuracy overall. Figure 6 also shows the results with other choices of

\rho=1,3,10

Figure 3: We ran experiments without Byzantine clients on a simple least-squares problem with random data and tuned all stepsizes for each methods under pure asynchrony using Ray 0 0 footnotemark: 0 framework. We averaged over three seeds. Left: all clients compute gradients at similar speeds. Right: one worker sleeps for

100\times

its compute time after every gradient computation. Throttle (green) achieves faster convergence because the soft throttling mechanism allows us to take slightly larger stepsize

\eta

than asynchronous SGD.

Appendix figures & tables8 assets

Supplementary material from the paper’s appendix.

Appendix

Panel of Figure 4 — Figure 4: Actual and virtual iterates with a hard restart.

Panel of Figure 5 — Figure 5: Virtual iterates with clipping and a hard restart.

Figure 6: Additional MNIST flooding-attack results complementing Figure 0 , with

n=25

clients, including

|{\mathcal{B}}|=5

Byzantine clients. The top and bottom rows show fixed-vector and random-vector flooding, respectively. Columns correspond to

\rho\in\{1,3,10\}

, extending the

\rho=30

results in Figure 0 . Here,

\rho

multiplies the Byzantine clients’ update rates, yielding an expected Byzantine update fraction of

\rho/(2+\rho)

. All other experimental settings are the same as in Figure 0 . Throttle maintains high test accuracy across the three flooding rates.

Objective	$F(x)=\frac{1}{2n}\\|Ax-b\\|^{2}$ , $n=10{,}000$ , $d=400$ , condition number $\approx 1.9\times 10^{3}$
Stochastic gradient	minibatch of 256 samples without replacement. all clients have shared i.i.d. data
Clients	$M=40$ Ray actors on 20 CPU cores.
Straggler (right panel)	worker 39 sleeps $100\times$ its compute time after each gradient ( $1.7\%$ of arrivals instead of $2.5\%$ )
Budget	$32{,}000$ computed gradients for every method.
Methods	Minibatch SGD and asynchronous SGD are based on ( Mishchenko et al., 2022 ) ,
	Throttle $q\in\{1.1,1.5\}$ , $\mu^{2}$ -SGD ( $\beta=0.25,\gamma=0.1$ ),

Appendix

Table 1: Least-squares configuration used in Figure 0 .

Figure 7: Empirical distribution of gradient delays in the least-squares experiment with

M=40

asynchronous workers on 20 CPU cores based on ( Mishchenko et al., 2022 ) . Delay is the number of server updates between a worker’s dispatch and the arrival of its gradient. frequencies are shown on a logarithmic scale. The green and red vertical lines average delay

M

and the maximum observed delay

\tau_{\max}

, respectively, illustrating that delays can greatly exceed the number of workers.

Dataset	MNIST (60,000 train / 10,000 test), i.i.d. clients
	each drawing minibatches from its own reshuffling of the full training set
Model	Conv-Conv-FC-BatchNorm-FC (66,230 parameters), cross-entropy loss
Clients	$n=20$ (15 honest, 5 Byzantine. $\delta=0.25$ )
Arrivals (standard attacks)	periodic sequence as in the Dahan & Levy (2024) ’s code
	every third arrival is Byzantine ( $1/3$ of updates).
	The arriving client is drawn within its group with probability $\propto$ its index

Appendix

Table 3: MNIST configuration used in Figure 0 .

Method	$\eta=0.01$	$\eta=0.1$	$\eta=1$
Kardam	41.5 $\pm$ 14.7	70.3 $\pm$ 10.5	68.5 $\pm$ 26.4
BASGD	94.4 $\pm$ 0.4	98.3 $\pm$ 0.2	98.7 $\pm$ 0.1
BASGDm	94.7 $\pm$ 0.5	98.6 $\pm$ 0.1	99.1 $\pm$ 0.1
$\mu^{2}$ -SGD (CWMed)	99.1 $\pm$ 0.1	99.2 $\pm$ 0.2	10.6 $\pm$ 0.9
$\mu^{2}$ -SGD (RFA)	99.1 $\pm$ 0.1	99.2 $\pm$ 0.1	11.0 $\pm$ 0.6
Throttle $q=1.1$ , $\lambda=1$	98.8 $\pm$ 0.1	99.2 $\pm$ 0.1	99.2 $\pm$ 0.1

Appendix

Table 4: Learning-rate selection on MNIST without attack: final test accuracy (%, mean

\pm

std over seeds

\{1,2,3\}

) for

\eta\in\{0.01,0.1,1\}

. Throttle results are shown for

\lambda=1

. Bold entries indicate the selected values for the baseline methods; ties are broken towards the smaller

\eta

CPU	20 logical cores (aarch64)
GPU	NVIDIA GB10, CUDA 13.0 (MNIST, $\mu^{2}$ -SGD only)
Python / NumPy	3.12.3 / 2.4.4
PyTorch	2.12.0+cu130 (MNIST)
Ray	2.58.0 (least squares)

Appendix

Table 5: Runtime hardware and software.

Explore similar work

Bringing Order to Asynchronous SGD: Towards Optimality under Data-Dependent Delays with Momentum
May 3, 2026Tehila Dahan, Roie Reshef, Sharon Goldstein +1Stochastic Gradient Descent Asynchronous Execution
Technion – Israel Institute of Technology, Haifa, Israel
Clipping Makes Distributed and Federated Asynchronous SGD Robust to Stragglers
Jun 11, 2026Samuel Erickson, Mikael JohanssonStochastic Gradient Descent Gradient Clipping
School of EECS, KTH Royal Institute of Technology, Stockholm, Sweden.
Rescaled Asynchronous SGD: Optimal Distributed Optimization under Data and System Heterogeneity
May 13, 2026Ammar Mahran, Artavazd Maranjyan, Peter RichtárikDecentralized Optimization Stochastic Gradient Descent
KAUST

May 3, 2026, cs.LGJ/K move · Enter open · S save

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

Tehila Dahan, Roie Reshef, Sharon Goldstein, Kfir Y. Levy

Technion – Israel Institute of Technology, Haifa, Israel

Stochastic Gradient Descent Asynchronous Execution Batch Momentum Gradient Staleness Optimality

Open paper AskPDF arXiv

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.

Abstract

Explore similar work

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

Clipping Makes Distributed and Federated Asynchronous SGD Robust to Stragglers

Rescaled Asynchronous SGD: Optimal Distributed Optimization under Data and System Heterogeneity