Robustifying Asynchronous SGD via Soft Throttling

1 INTRODUCTION

• Distributed learning can be bottlenecked by its slowest client, while asynchronous SGD updates the model whenever a client’s gradient arrives.Asynchronous clients can immediately begin computing their next gradients after sending feedback.Source: §1 · p. 1
• Fast or malicious clients can flood asynchronous SGD with updates, while prior approaches either rely on assumptions vulnerable to attacks or may sacrifice speedups.The cited discussion contrasts methods that constrain flooding with nearly synchronous methods that may offer smaller speedups.Source: §1 · pp. 1–2
• THROTTLE exponentially decreases stepsizes for repeated updates from the same client to limit its influence and prevent malicious clients from dominating the global model.The paper reports robustness to a range of Byzantine attacks and better performance than evaluated methods, including standard asynchronous SGD without Byzantine clients.Source: §1 · p. 2

2 PRELIMINARIES

• The optimization setup uses sample loss F and a data distribution D, with clients partitioned into good and omniscient Byzantine clients.The Byzantine ratio is δ = |B|/n.Source: §2 · p. 2

2.1 ASYNCHRONOUS SGD

• Asynchronous SGD applies each stochastic gradient upon arrival, using a potentially stale model whose delay is τ_t = t − prev(t, j_t).This lets the server continue updating without waiting for the slowest client.Source: §2.1 · p. 2

2.2 BYZANTINE-ROBUST SYNCHRONOUS ALGORITHM

• Byzantine-robust synchronous methods replace gradient averaging with an aggregator that estimates the honest-client mean with error of order O(δ).The cited examples include centered clipping, coordinate-wise median, Krum, and robust federated averaging with pre-aggregation.Source: §2.2 · p. 3

2.3 BYZANTINE-ROBUST ASYNCHRONOUS ALGORITHM

• Existing Byzantine-robust asynchronous analyses assume bounded delays or bounded Byzantine feedback, but flooding can make delay arbitrarily large.THROTTLE is proposed to remove these assumptions.Source: §2.3 · p. 3

3 THROTTLE: ASYNCHRONOUS SGD WITH SOFT THROTTLING

• THROTTLE combines soft throttling and hard restart as its two core components for asynchronous SGD.The algorithm applies received updates through a local robust aggregator or gradient clipping.Source: §3 · p. 3, §3.3 · p. 5

3.1 SOFT THROTTLING

• Within each round, repeated updates from one client are exponentially down-weighted by q: the first has factor 1, then 1/q, 1/q^2, and so on; factors reset to 1 after every client responds.A larger q caps fast clients’ influence more tightly; as q approaches infinity, the method reduces to synchronous SGD.Source: §3.1 · p. 3

3.2 HARD RESTART

• At each round’s end, the server broadcasts the current model, discards computations in progress, and restarts all clients from the same model.This aligns round starts so client updates can be robustly aggregated; the decomposition requires side information.Source: §3.2 · p. 4

3.3 THROTTLE

• THROTTLE counts each client’s arrivals within a round and sets its stepsize to 1/n on first arrival or a q-dependent smaller value on repeats.After all clients have appeared, the server resets counters and side information and signals a hard restart.Source: §3.3 · p. 5

4 THEORETICAL ANALYSIS

• Theorem 1 analyzes non-convex convergence for q > 1 under Assumptions 1–4, a local (c, δ)-robust aggregator, and λt = G.The bound is expressed using effective time steps and restart quantities.Source: §4 · p. 6
• As q → ∞, the convergence rate recovers standard synchronous Byzantine-robust SGD, including the unavoidable O(cδσ2) term for aggregators applied only to current stochastic gradients.The passage notes that momentum or variance reduction can remove this term.Source: §4 · p. 6
• For finite q, the dominant error G2|B|2/(q −1)2 persists even with full gradients, and momentum or variance reduction alone cannot remove this asynchrony-induced term.Combining momentum with stale gradients is nontrivial; reducing both error terms is left for future work.Source: §4 · p. 6
• The experiments use λt = 1, where clipping is typically active, but the analysis uses λt = G and leaves the active-clipping regime for future work.Under Assumption 3, λt = G makes clipping the identity on honest gradients.Source: §4 · p. 6
• With no Byzantine clients and q → 1, the convergence rate is similar to asynchronous SGD without Byzantine clients, up to a T −1 term.The comparison is to Mishchenko et al. (2022, Theorem 2).Source: §4 · p. 7

Asynchronous SGD

• Asynchronous SGD research progressed from delay-dependent analyses to convergence rates independent of maximum delay, alongside work on momentum, unified frameworks, heterogeneity, and finite-sum settings.The passage cites Koloskova et al. (2022) and Mishchenko et al. (2022) for delay-independent rates.Source: §5 · p. 7

Byzantine-robust Learning

• Synchronous Byzantine-robust learning uses robust aggregators, while momentum and variance-reduction approaches address stochastic-gradient attacks; these results assume synchronous updates.The passage also notes that momentum under asynchrony is nontrivial because it accumulates stale gradients (Shi et al., 2024).Source: §5 · p. 7

Asynchronous Byzantine-robust Learning

• Combined asynchronous Byzantine-robust methods use partial synchronization or filter incoming gradients, with some filters requiring a trusted server dataset or risking rejection of honest gradients.Examples include BASGD/BASGDm, Zeno++, AFLGuard, and Kardam.Source: §5 · p. 7

6.1 THROTTLE IS BYZANTINE-ROBUST

• THROTTLE maintained high accuracy under flooding attacks and remained competitive under most standard attacks in the MNIST experiments.The experiment used 25 clients, including 5 Byzantine clients.Source: §6 · p. 7, Figure 2 · p. 8
• For Empire, THROTTLE achieved 59.6% and 61.5%, versus 96.0% for BASGDm and 94.0% for µ2-SGD with RFA.The authors expect adding momentum and tuning the clipping radius to narrow this gap.Source: §6.1 · p. 8

6.2 THROTTLE OUTPERFORMS STANDARD ASYNCHRONOUS SGD

• With tuned stepsizes, THROTTLE achieved lower optimization error than minibatch SGD, asynchronous SGD, and other evaluated baselines under the same gradient budget.Among tested values, q = 1.1 achieved the lowest final optimality gap in both worker configurations.Source: §6.2 · p. 9
• A worker sleeping for 100× its computation time had little effect on THROTTLE’s convergence per computed gradient, though q = 1.5 became less stable.The experiment used a least-squares problem without Byzantine clients and averaged over three seeds.Source: §6.2 · p. 9, Figure 3 · p. 9

• THROTTLE exponentially down-weights updates by client speed, generalizing synchronous Byzantine-robust SGD as q→∞ and (almost) asynchronous SGD as q→1.Source: §7 · p. 9
• Its convergence rate matches the known rate at each limit, and it holds against flooding attacks without a bound on the Byzantine update ratio.Source: §7 · p. 9
• Experiments show robustness to attacks and faster convergence from soft throttling even without Byzantine clients.Source: §7 · p. 9

AI USE STATEMENT

• LLMs assisted with proof checking, experiment implementation and refinement, manuscript drafting and editing, and TikZ figures; authors reviewed the work and take responsibility.The authors state that LLMs did not generate or clean datasets, refine hypotheses, develop the theoretical model, or propose research ideas.Source: AI USE STATEMENT · p. 10

A NOTATIONS

• The notation defines q as the scaling factor and c_i(t) as client i’s delivered-gradient count in the current round.Source: A NOTATIONS · p. 15

B ANALYZING ASYNCHRONOUS SGD THROUGH THE VIRTUAL ITERATE

• The virtual-iterate analysis says the actual and synchronized virtual iterates differ by at most n − 1 stochastic gradients, but this virtual iterate can be arbitrarily bad with Byzantine updates.Source: B ANALYZING ASYNCHRONOUS SGD THROUGH… · p. 15

C CONVERGENCE PROOFS

• The convergence proofs use a two-stage virtual sequence: first synchronize the asynchronous iterate, then approximate it with one free of Byzantine updates.The authors identify the de-Byzantinization step and its combination with asynchronous virtual sequences with restart as new to their analysis.Source: C CONVERGENCE PROOFS · pp. 15–16

• The analysis introduces a technique for Byzantine-robust SGD and includes momentum for generality; setting α = 1 reduces it to SGD.Source: §C.1 · p. 16
• The virtual-iterate construction, combined with prior lemmas, yields the same convergence rate up to a constant factor.Source: §C.1 · p. 17
• This construction corresponds to the special case of THROTTLE in which every round is a synchronization round, q→∞.Source: §C.1 · p. 17

C.2 PROOF OF THE MAIN THEOREM

• Theorem 1 establishes a non-convex convergence rate for q > 1 under the stated assumptions and use of a local robust aggregator.The theorem also requires G′ ≤ 3G and λt = G.Source: §C.2 · p. 18
• The proof uses two virtual-iterate comparisons: first to approximate the actual iterate by a synchronized one, then to remove Byzantine-update effects.The analysis also introduces a further virtual iterate to remove the effects of clipping and Byzantine updates.Source: §C.2 · p. 19

D.1 A GENERAL CONSTRUCTION

• Centered aggregation applies a map ψ to inputs relative to an anchor, with ψ intended to preserve honest-scale inputs while bounding arbitrary ones.The construction defines A(v; a) := a + ψ(v − a).Source: §D.1 · pp. 25–26
• Centered truncated mean is a local (c, δ)-robust aggregator when the admissible side-information pair satisfies V² ≤ Kρ², with c = 10K.The result is stated for the proposition's assumed setting.Source: §D.1 · p. 26

D.2 IMPOSSIBILITY WITHOUT SIDE INFORMATION

• For n ≥ 3, d ≥ 1, and 1/n ≤ δ < 1/2, no aggregator formed by applying the same per-input map is (c, δ)-robust for any finite c.The result concerns maps that use each input alone, without side information.Source: §D.2 · p. 27

E.1 COMMON SETTINGS AND IMPLEMENTATION

• The least-squares experiment uses real Ray workers, with the server applying gradients in arrival order and CPU contention producing delays.The MNIST experiment instead uses a single-process, event-driven simulator with simulated time.Source: §E.1 · p. 27
• For MNIST, client arrival sequences are shared across methods for each schedule and seed, and independent random streams are used for data order, schedules, initialization, and attacks.The passage also notes that communication latency is zero in the simulator.Source: §E.1 · p. 27

E.2 LEAST-SQUARES EXPERIMENT (FIGURE 3)

• The least-squares experiment evaluates F(x) − F* on all n samples every 40 accepted gradients.The stated problem uses n = 10,000 samples and d = 400.Source: §E.2 · p. 27

E.3 MNIST EXPERIMENT (FIGURE 2)

• THROTTLE maintains high test accuracy across flooding rates ρ ∈ {1, 3, 10} in the additional MNIST results.Rows show fixed-vector and random-vector flooding; the experiments use n = 25 clients, including |B| = 5 Byzantine clients.Source: Figure 6 · p. 28

E.2 LEAST-SQUARES EXPERIMENT (FIGURE 3)

• In the least-squares setup, gradient delays can greatly exceed the number of workers, with frequencies plotted on a logarithmic scale.The experiment uses 40 asynchronous workers on 20 CPU cores; delay counts server updates between dispatch and gradient arrival.Source: Figure 7 · p. 28

E.3 MNIST EXPERIMENT (FIGURE 2)

• The MNIST setup uses 20 clients, including five Byzantine clients, and runs until 16,000 honest updates; its attack schedules include periodic and flooding arrivals.The periodic schedule makes every third arrival Byzantine; flooding clients arrive as independent Poisson processes.Source: §E.4 · p. 30

E.4 COMPUTING ENVIRONMENT

• The attack implementations include omniscient Empire and ALIE updates, while flooding attacks send fixed or fresh random vectors of norm 10.The flood vectors are sent at ρ times the honest group's rate.Source: §E.4 · p. 31