Research map / Optimization / Distributed and compressed
Dynamic Byzantine-Robust Learning: Adapting to Switching Byzantine Workers
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 DynaBRO, a Byzantine-robust distributed SGD that uses MLMC gradient estimation on robustly aggregated gradients plus a fail-safe filter, tolerating up to O(sqrt(T)) identity-switching rounds while matching static convergence rates.
Problem
Byzantine-robust distributed learning when the identities of Byzantine workers change over time (dynamic/switching Byzantine behavior), where history-dependent static methods become unreliable.
Approach
Apply a multi-level Monte Carlo gradient estimator after robust aggregation (bias reduction on aggregated gradients) with a fail-safe event filter that reverts to single-sample aggregation when level-consistency checks fail; the MLMC window is O(log T) in expectation, limiting exposure to past identity changes. Adds a median-filtered mean aggregator and AdaGrad-Norm step sizes for adaptivity.
Key results
- Theory: DynaBRO tolerates |B| in O~(sqrt(T/gamma)) dynamic rounds while matching the static non-convex convergence rate O~(V sqrt(L Delta_1 (delta+1/m)/T)) when kappa_delta = O(delta).
- On MNIST with Periodic(K) switching (m=17, 8 Byzantine), DynaBRO's accuracy stays stable across K, while worker momentum with beta=0.99 fails at K=100 and beta=0.9 at lower K.
- On CIFAR-10 with Bernoulli switching and up to 72% Byzantine workers per iteration, DynaBRO significantly outperforms SGD and momentum in configurations with many iterations having delta>0.5; momentum beta=0.9 slightly wins in the lowest-Byzantine configuration.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Add the MLMC fail-safe filter to robustly aggregated gradients | DynaBRO · Dynamic Byzantine setting | average squared gradient norm: The bound includes the dynamic-round term 16C^2\calig{V}^2\gamma\frac{\abs{\badrounds}\log{T}}{T} | Helped |
| Use MFM instead of a (δ, κδ)-robust aggregator | DynaBRO · Static Byzantine setting | aggregated-gradient squared error: \Otilde\brac{\frac{\calig{V}^2}{\ensuremath{N}}\brac{\delta^2 + \frac{1}{m}}} versus \Otilde\!\brac{\frac{\calig{V}^2}{\ | Helped |
| Use AdaGrad-Norm instead of a specifically tuned fixed learning rate | DynaBRO with MFM · Dynamic Byzantine setting | average squared gradient norm: \Otilde\brac{\zeta\calig{V}\sqrt{\frac{\tilde{\gamma}}{T}} + \frac{\zeta^2}{T} + \calig{V}^2\frac{\abs{\badrounds}}{T}} | Mixed |
| Increase the rate of identity switches by decreasing Periodic K | Worker-momentum (β=0.99) · MNIST, Periodic(K) | final test accuracy | Hurt |
| Increase the rate of identity switches by decreasing Periodic K | DynaBRO · MNIST, Periodic(K) | final test accuracy | No clear effect |
| Use DynaBRO instead of SGD and worker-momentum | CIFAR-10 under Bernoulli(p,D,δmax), configurations 2 and 3 · CIFAR-10 | test accuracy | Helped |
| Use worker-momentum (β=0.9) instead of DynaBRO | CIFAR-10 under Bernoulli(p=0.01,D=10,δmax=0.72) · CIFAR-10 | test accuracy | Helped |
Surprising findings
- In the lowest-Byzantine-count CIFAR-10 configuration, momentum with beta=0.9 slightly outperforms DynaBRO.
- Worker momentum can be broken by a momentum-tailored dynamic attack requiring only O(sqrt(T)) identity switches.
Limitations
- Analysis restricted to homogeneous setting where all workers sample from the same distribution.
- Bounded-noise assumption is stronger than standard bounded-variance assumption; adaptive variant needs knowledge of noise level V for MFM threshold and bounded objective.
- Adaptive (MFM + AdaGrad-Norm) variant tolerates fewer dynamic rounds, O~(sqrt(gamma~ T)), than the non-adaptive variant.
Experimental setup
Datasets: MNIST CIFAR-10
Benchmarks: MNIST CIFAR-10
Metrics: test accuracy
Baselines: SGD worker momentum (beta=0.9) worker momentum (beta=0.99)
Builds on: AdaGrad-Norm worker momentum (Karimireddy et al.) ByzantineSGD SafeguardSGD MLMC estimation
Closest papers by meaning
- Weight for Robustness: A Comprehensive Approach towards Optimal Fault-Tolerant Asynchronous ML (NeurIPS 2024 · similarity 0.90)
- On the Tension between Byzantine Robustness and No-Attack Accuracy in Distributed Learning (ICML 2025 · similarity 0.89)
- Fault Tolerant ML: Efficient Meta-Aggregation and Synchronous Training (ICML 2024 · similarity 0.89)
- Byzantine Robustness and Partial Participation Can Be Achieved at Once: Just Clip Gradient Differences (NeurIPS 2024 · similarity 0.89)
- Byzantine-Robust Decentralized Learning via Remove-then-Clip Aggregation (AAAI 2024 · similarity 0.89)
- From Inexact Gradients to Byzantine Robustness: Acceleration and Optimization under Similarity (NeurIPS 2026 · similarity 0.88)
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.