Research map / Optimization / Distributed and compressed
Byzantine Robustness and Partial Participation Can Be Achieved at Once: Just Clip Gradient Differences
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proposes Byz-VR-MARINA-PP, the first Byzantine-robust distributed method with client sampling, using clipping of compressed stochastic gradient differences to bound Byzantine harm even when sampled clients are majority-Byzantine.
Problem
Byzantine-robust distributed learning has only been proven under full client participation; naive partial participation can let Byzantine workers form a majority in a round and break convergence.
Approach
Apply gradient clipping to the compressed stochastic gradient differences inside a recursive variance-reduced (PAGE/GeomSARAH-type, MARINA-style) estimator, with clipping level proportional to the iterate step, so that Byzantine vectors stay bounded even when they form a sampled majority; also a heuristic to add such clipping to any aggregation-based Byzantine-robust method.
Key results
- On a9a logistic regression with 15 good and 5 Byzantine workers and 20% client sampling, Byz-VR-MARINA-PP with clipping converges linearly while the no-clipping variant stalls at the starting point under the shift-back attack.
- Theory recovers the Byz-VR-MARINA O(1/K) non-convex rate and PL linear rate to a heterogeneity-dependent neighborhood; in the full-participation case with C=n, the stepsize bound is worse than Byz-VR-MARINA's.
- On MNIST with 20 clients (5 malicious), clipping performs on par or better than no clipping for coordinate median and RFA under bit flipping, label flipping, ALIE and shift-back attacks.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| add clipping to gradient differences (ablation) | Byz-VR-MARINA-PP · a9a | optimality gap | Helped |
| use partial participation with clipping instead of full participation | Byz-VR-MARINA-PP · a9a | convergence speed per epochs | Helped |
| vary the clipping multiplier λ (ablation) | Byz-VR-MARINA-PP · a9a | convergence | Mixed |
| add clipping (ablation) | Byzantine Robust Momentum SGD · MNIST heterogeneous split | training loss | No clear effect |
| remove clipping (ablation) | Byzantine Robust Momentum SGD with coordinate median or RFA · MNIST heterogeneous split, shift-back attack | training loss | Hurt |
Surprising findings
- With C>=max(1, delta n/delta) and small p, the method achieves the same convergence rate as Byz-VR-MARINA while using on average only O(C) clients per step instead of n.
- With full participation the clipped method's step size bound is worse than Byz-VR-MARINA, so the theory does not fully recover the full-participation result.
Limitations
- Step-size and complexity bounds are worse than Byz-VR-MARINA with full participation; the authors do not recover that result exactly.
- Convergence bounds depend on the compressor parameter omega and a bounded-compressor constant D_Q that can be large (proportional to d) in general.
- Heuristic extension to other Byzantine-robust methods is not theoretically proven and is only illustrated experimentally.
Experimental setup
Datasets: a9a MNIST
Benchmarks: a9a MNIST
Metrics: optimality gap f(x)-f(x*) training loss test accuracy
Baselines: Byz-VR-MARINA Byrd-SAGA coordinate-wise median with bucketing without clipping RFA Client Momentum
Builds on: Byz-VR-MARINA PAGE Bucketing CenteredClip Byrd-SAGA
Closest papers by meaning
- From Inexact Gradients to Byzantine Robustness: Acceleration and Optimization under Similarity (NeurIPS 2026 · similarity 0.91)
- Fault Tolerant ML: Efficient Meta-Aggregation and Synchronous Training (ICML 2024 · similarity 0.90)
- Byzantine-Robust Decentralized Learning via Remove-then-Clip Aggregation (AAAI 2024 · similarity 0.90)
- On the Tension between Byzantine Robustness and No-Attack Accuracy in Distributed Learning (ICML 2025 · similarity 0.90)
- Dynamic Byzantine-Robust Learning: Adapting to Switching Byzantine Workers (ICML 2024 · similarity 0.89)
- Weight for Robustness: A Comprehensive Approach towards Optimal Fault-Tolerant Asynchronous ML (NeurIPS 2024 · similarity 0.89)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.