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→∞) 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
Figure 1: Illustration of Throttle with three clients. A block gi(t) is a gradient computation started at x(t) (its left end), and its coefficient is the weight it receives on arrival, 1/n for a first arrival and 1/qc for a repeated one. Dashed lines mark the synchronous clock Sr , at which in-flight computations are discarded (hatched blocks) and all clients restart from x(Sr) (green blocks).
Figure 2: Test accuracy on MNIST with n=25 clients, ∣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 ρ , 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 ρ=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× its compute time after every gradient computation. Throttle (green) achieves faster convergence because the soft throttling mechanism allows us to take slightly larger stepsize η than asynchronous SGD.
Appendix figures & tables8 assets
Supplementary material from the paper’s appendix.
Appendix
Figure 4: Actual and virtual iterates with a hard restart.
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 ∣B∣=5 Byzantine clients. The top and bottom rows show fixed-vector and random-vector flooding, respectively. Columns correspond to ρ∈{1,3,10} , extending the ρ=30 results in Figure 0 . Here, ρ multiplies the Byzantine clients’ update rates, yielding an expected Byzantine update fraction of ρ/(2+ρ) . All other experimental settings are the same as in Figure 0 . Throttle maintains high test accuracy across the three flooding rates.
Objective
F(x)=2n1∥Ax−b∥2 , n=10,000 , d=400 , condition number ≈1.9×103
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× 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∈{1.1,1.5} , μ2 -SGD ( β=0.25,γ=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 τmax , respectively, illustrating that delays can greatly exceed the number of workers.
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. δ=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 ∝ its index
Appendix
Table 3: MNIST configuration used in Figure 0 .
Method
η=0.01
η=0.1
η=1
Kardam
41.5 ± 14.7
70.3 ± 10.5
68.5 ± 26.4
BASGD
94.4 ± 0.4
98.3 ± 0.2
98.7 ± 0.1
BASGDm
94.7 ± 0.5
98.6 ± 0.1
99.1 ± 0.1
μ2 -SGD (CWMed)
99.1 ± 0.1
99.2 ± 0.2
10.6 ± 0.9
μ2 -SGD (RFA)
99.1 ± 0.1
99.2 ± 0.1
11.0 ± 0.6
Throttle q=1.1 , λ=1
98.8 ± 0.1
99.2 ± 0.1
99.2 ± 0.1
Appendix
Table 4: Learning-rate selection on MNIST without attack: final test accuracy (%, mean ± std over seeds {1,2,3} ) for η∈{0.01,0.1,1} . Throttle results are shown for λ=1 . Bold entries indicate the selected values for the baseline methods; ties are broken towards the smaller η .
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
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.
Asynchronous stochastic gradient descent (ASGD) is a standard way to exploit heterogeneous compute resources in distributed learning: instead of forcing fast workers to wait for slow ones, the server updates the model whenever a gradient arrives. Vanilla ASGD applies each arriving gradient with the same weight. When local data distributions are heterogeneous, this becomes problematic: faster workers contribute more updates, and we show theoretically that the method is biased toward a frequency-weighted average of the local objectives rather than the desired global objective. Existing remedies typically move away from the simple ASGD template by introducing gathering phases, buffering, or extra memory. We show that this is unnecessary. Keeping the standard ASGD mechanism, we recover the correct objective by rescaling worker-specific stepsizes in proportion to their computation times, so that each worker contributes the same aggregate learning rate over a cycle. In the non-convex setting, under smoothness and bounded heterogeneity assumptions, we prove that the resulting method, Rescaled ASGD, converges to stationary points of the correct global objective in the fixed-computation model. Its time complexity matches the known lower bound in the leading term, while the effects of staleness and data heterogeneity appear only in lower-order terms. Experiments confirm that the method converges to the correct objective and is competitive with state-of-the-art baselines.