Research map / Optimization / Distributed and compressed
On the Tension between Byzantine Robustness and No-Attack Accuracy in Distributed Learning
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.
Theoretically and empirically shows that robust gradient aggregators in Byzantine-robust distributed learning incur an aggregation error without attackers that grows with the number of tolerated Byzantine workers f, creating a tension between robustness and no-attack accuracy.
Problem
Robust aggregators used in Byzantine-robust distributed learning introduce aggregation error even when no Byzantine workers exist, but this cost had not been theoretically characterized.
Approach
Defines epsilon-accuracy for aggregators without Byzantine workers, proves a worst-case lower bound f/(n-f) on epsilon that matches coordinate-wise trimmed mean, and derives matching lower and upper bounds on gradient descent convergence with robust aggregators that grow with f.
Key results
- Coordinate-wise trimmed mean with multi-Krum-style tolerance f=7 under no attack drops ResNet-20 CIFAR-10 accuracy from 89.42% to 40.31% (alpha=0.1) versus f=0.
- Coordinate-wise trimmed mean with f=7 and alpha=0.1 drops accuracy to 10.00% without NNM; with NNM at fNNM=7 it recovers to 61.09%.
- Proves epsilon >= f/(n-f) lower bound for any (f,kappa)-robust aggregator without attacks, shown tight by coordinate-wise trimmed mean.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Increase Multi-Krum Byzantine tolerance f from 0 to 7 | Multi-Krum on ResNet-20 · CIFAR-10 test, α = 0.1 | top-1 test accuracy: 89.42% -> 40.31% (-49.11%) | Hurt |
| Increase Multi-Krum Byzantine tolerance f from 0 to 7 | Multi-Krum on ResNet-20 · CIFAR-10 test, α = 1.0 | top-1 test accuracy: 89.36% -> 68.54% (-20.82%) | Hurt |
| Increase Multi-Krum Byzantine tolerance f from 0 to 7 | Multi-Krum on ResNet-20 · CIFAR-10 test, α = 10.0 | top-1 test accuracy: 89.55% -> 73.69% (-15.86%) | Hurt |
| Increase trimmed-mean Byzantine tolerance f from 0 to 7 | Coordinate-wise trimmed mean on ResNet-20 · CIFAR-10 test, α = 0.1 | top-1 test accuracy: 89.42% -> 10.00% (-79.42%) | Hurt |
| Increase trimmed-mean Byzantine tolerance f from 0 to 7 | Coordinate-wise trimmed mean on ResNet-20 · CIFAR-10 test, α = 1.0 | top-1 test accuracy: 89.36% -> 40.54% (-48.82%) | Hurt |
| Increase trimmed-mean Byzantine tolerance f from 0 to 7 | Coordinate-wise trimmed mean on ResNet-20 · CIFAR-10 test, α = 10.0 | top-1 test accuracy: 89.55% -> 83.15% (-6.40%) | Hurt |
| Add nearest neighbour mixing (NNM) with fNNM = 7 to Multi-Krum (f = 7) (ablation) | Multi-Krum on ResNet-20 · CIFAR-10 test, α = 0.1 | top-1 test accuracy: 40.31% -> 75.03% | Helped |
| Add nearest neighbour mixing (NNM) with fNNM = 7 to Multi-Krum (f = 7) (ablation) | Multi-Krum on ResNet-20 · CIFAR-10 test, α = 1.0 | top-1 test accuracy: 68.54% -> 83.88% | Helped |
| Add nearest neighbour mixing (NNM) with fNNM = 7 to trimmed mean (f = 7) (ablation) | Coordinate-wise trimmed mean on ResNet-20 · CIFAR-10 test, α = 0.1 | top-1 test accuracy: 10.00% -> 61.09% | Helped |
| Add nearest neighbour mixing (NNM) with fNNM = 7 to trimmed mean (f = 7) (ablation) | Coordinate-wise trimmed mean on ResNet-20 · CIFAR-10 test, α = 1.0 | top-1 test accuracy: 40.54% -> 82.77% | Helped |
| Add nearest neighbour mixing (NNM) with fNNM = 7 to trimmed mean (f = 7) (ablation) | Coordinate-wise trimmed mean on ResNet-20 · CIFAR-10 test, α = 10.0 | top-1 test accuracy: 83.15% -> 87.79% | Helped |
| Decrease NNM fNNM from 7 to 1 (ablation) | Multi-Krum (f = 7) on ResNet-20 · CIFAR-10 test, α = 0.1 | top-1 test accuracy: 75.03% -> 88.81% | Helped |
Surprising findings
- Coordinate-wise trimmed mean with f=7 reaches 10.00% accuracy under alpha=0.1 with no Byzantine workers, i.e. chance-level on CIFAR-10.
- Worst-case aggregation error is largest when data is highly skewed across workers, so heterogeneity amplifies the accuracy cost of robustness.
Limitations
- Experiments limited to a single model (ResNet-20) and dataset (CIFAR-10).
- Analysis is for the no-attack case only; does not study the robustness side under actual attacks.
- Convergence lower bounds are shown via constructed worst-case functions rather than typical practical settings.
Experimental setup
Datasets: CIFAR-10
Benchmarks: CIFAR-10
Metrics: top-1 test accuracy aggregation error bound (epsilon) convergence lower bound
Baselines: multi-Krum coordinate-wise trimmed mean vanilla mean
Builds on: (f, κ)-robustness (Allouah et al., 2023) ByzSGD nearest neighbour mixing Krum coordinate-wise trimmed mean
Closest papers by meaning
- Byzantine-Robust Decentralized Learning via Remove-then-Clip Aggregation (AAAI 2024 · similarity 0.93)
- 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.91)
- Weight for Robustness: A Comprehensive Approach towards Optimal Fault-Tolerant Asynchronous ML (NeurIPS 2024 · similarity 0.91)
- Near-Optimal Resilient Aggregation Rules for Distributed Learning Using 1-Center and 1-Mean Clustering with Outliers (AAAI 2024 · similarity 0.90)
- Byzantine Robustness and Partial Participation Can Be Achieved at Once: Just Clip Gradient Differences (NeurIPS 2024 · similarity 0.90)
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.