What does compressing the pseudo-gradient cost local SGD, and is it better than syncing less often?

research/compressed-sync

Local SGD with compressed displacements: exact floor (1+ω) and stability limit αs(1+ω/N)<2 for rand-k (more workers restore the step, not the floor), closed form for norm-scaled quantisation, and at equal bytes syncing less often beats compressing.

9 tests

What it found

Unbiased compression of each worker's displacement (rand-k, relative variance ω) gives an exact stationary variance αV_w(1+ω)/(N s((2−αs)−αsω/N)) and shrinks the stable outer step to 2/(s(1+ω/N)): more workers restore the step (0.47 → 2.44 for ω=99, N=16 → 256) but never the floor, which stays (1+ω)×. Norm-scaled (QSGD-style) quantisation has a closed form through one scalar T = E|d|²; at equal error energy its loss equals coordinate-wise at H=1 and is about 10% worse at H=16, with the stiff mode's variance doubling. For equal bytes, syncing 1/ρ times less often leaves the floor unchanged at α=1 while keeping a fraction ρ multiplies it by 1/ρ. Matched to simulation within 2%. Stylised: quadratic, shared curvature (no client drift), unbiased compressors only.

A figure from its own output

Figure produced by research/compressed-sync: stability_vs_workers — compressed-sync/experiments/stability_vs_workers.svg, written by the project's own experiment code.

Paper, code and results

More in Decentralised training systems

How much outer step does overlapping communication with compute cost, and how many rounds should be in flight?Overlapping communication in local SGD with τ-round-late outer updates: exact stable step 2 sin(π/(4τ+2)) (shrinks ~1/τ), double-root rate τ/(τ+1), exact noise floor matched to simulation, free at small steps, wall-clock-optimal delay ⌈L/T_c⌉ (1.9–7.5× faster than no overlap).
Does error feedback rescue the noise floor that compressed local SGD loses?Error feedback in compressed local SGD: exact stability limit 2(2−ρ)Nρ/(Nρ²+4(1−ρ)) and closed-form floor that returns to the uncompressed one at small steps (unbiased compression pays 1/ρ), dropping is biased to the send-rate-weighted mean and the residual removes it at a variance price.
How should a server weight workers that ran different numbers of inner steps?Weighting workers that ran different numbers of inner steps: exact floor α²Σw²V/(r(2−r)), worker information I∞·tanh(λH/2) saturates, optimal weights span ≤2× so equal weights lose ≤9/8 (measured ≤1.09) while step-proportional weights lose up to 1.76× per mode and 10.5× on three modes.
What does a median or trimmed-mean outer step cost local SGD, and what does it buy against Byzantine workers?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.
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.

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.