What does a median or trimmed-mean outer step cost local SGD, and what does it buy against Byzantine workers?

research/robust-outer

Median and trimmed-mean outer aggregation in local SGD: exact linear loop with floor and bias split, π/2 variance price with no attackers, bounded worst-case bias Φ(z)=1/(2(1−ε)) that more workers cannot average away but a longer inner loop shrinks.

11 tests

What it found

Because the median and trimmed mean commute with shifts, the outer loop stays exactly linear: floor αV_wv/(s(2−αs)) plus a bias V_wm²/s², with the same stability limit as averaging. With no attackers the median costs N·Var = 1.35 to 1.56 (→ π/2). With a fraction ε of attackers its bias is bounded (Φ(z) = 1/(2(1−ε)): 0.18 noise-sigmas at ε = 1/8) and beats averaging once the attack offset exceeds about 1.4 sigmas; more workers shrink only the variance part (total loss 0.103 → 0.102 from N=8 to 128), while a longer inner loop shrinks the bias (39× from H=1 to 256). Trimming exactly the attacker count is worse than the median. Matched to simulation within 1.3%. Stylised: quadratic, Gaussian noise, shared curvature, constant-offset attackers.

A figure from its own output

Figure produced by research/robust-outer: biasloss — robust-outer/experiments/biasloss.svg, written by the project's own experiment code.

Paper, code and results

More in Decentralised training systems

Which of sync interval, compression, delay, momentum and robust aggregation sets the final loss of low-communication training?Research programme (proposal stage): a predictive theory of DiLoCo-style low-communication training, testing on real small transformers the closed forms derived in about a dozen quadratic-model projects, with 16 references, hypotheses H1 to H6 and an ICML/NeurIPS workshop as the first target
How far over its limit can a rate limiter be pushed in a true rolling window?How far over its limit can a rate limiter be pushed in a true rolling window? Adversarial search over fixed window, sliding log, sliding-window counter, token bucket and leaky bucket: only the sliding log holds the limit; the sliding counter admits up to about 1.5 L and the buckets nearly 2 L, and under Poisson overload at 1.5x load 39-47% of rolling windows exceed the limit for fixed window and buckets. Stylised.
What can one stubborn node do to gossip training?Pairwise gossip for decentralised training: exact contraction (n−2)/(2(n−1))≈½ per matching round (~20 rounds at any n), noise floor (n−1)(n−2)s²/n, one stubborn node captures consensus at rate 1−1/(n(n−1)), trust-region clipping caps drift at τ/(n(n−1)) per step.
What does infrequent averaging do to the answer?Local-SGD/DiLoCo-style averaging on heterogeneous quadratics: exact fixed point with saturating weights 1-(1-ηa_i)^H, non-monotone bias to the unweighted mean, exact a_i/w_i correction, step-count inflation moves the fixed point 0.50→0.91, wall-clock-optimal sync interval.
How often should preemptible workers checkpoint?Checkpoint interval for preemptible decentralised training: exact Lambert-W optimum independent of restart cost, Young/Daly overshoot 5–25%, flat within 2×, synchronous efficiency wall (50% at n≈691), flaky workers cut throughput 5×.
Should a pipeline replicate stages or skip them?Replicate or skip? pipeline stages on unreliable workers: exact binomial drop law, replicas cannot beat the shared-domain floor (1−ρ)^L, a 4-stage skip budget halves workers for a 1e-3 drop rate (240 → 96), cost-optimal design shifts from skipping to replication as skips get costly.

All 23 Decentralised training systems projects →

Other research topics

Proper scoring & elicitation28 Effort & peer prediction9 Verification games & slashing19 Detection & tolerances14 Markets as routers13 Prediction-market design9 Paying contributors8 Decentralised training systems23 Digital twins & sim-to-real164 LLM chip design loops40 Robot manufacturing loops53 Ambient AI assistant46 Self-replicating manufacturing34 Simulation-first design64 Engineered clothing45 Task-specific AI accelerators40 Algorithmic chip-design loops42 Open-source purpose-built robots44 The software-engineering loop43 Adversarial human imitation41 Open-source residential construction41 Autonomous multi-angle capture34 Sensing, imaging and 3D31 Energy supply and dense energy storage39 Robot societies among people31 Agentic co-design of low-cost robots27 Laundry-hanging robots25 Machine learning on qualitative data23 Robots on the building site27 Civilizations & group psychology1 History & human sciences1

Produced with AI assistance (Claude). Results are from the code in this repository and are simulated or stylised unless the abstract says otherwise; nothing here implies affiliation with or endorsement by any lab, researcher or company cited. MIT licensed.