Research map / Learning theory and algorithms / Clustering
Near-Optimal Resilient Aggregation Rules for Distributed Learning Using 1-Center and 1-Mean Clustering with Outliers
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 CenterwO/MeanwO aggregators (2-approximations to 1-center and 1-mean clustering with outliers) for Byzantine-resilient distributed learning, plus a two-phase 2PRASHB framework that lets workers vote between inner and outer aggregates.
Problem
Byzantine-resilient aggregation in distributed learning under homogeneous and heterogeneous data, where existing aggregation rules are ad hoc and often suboptimal with respect to robustness criteria; no single rule dominates against both sneak and siege attacks.
Approach
Reduce optimal aggregation design to 1-center/1-mean clustering with outliers and use simple medoid-based 2-approximations (CenterwO, MeanwO) whose outputs are the mean of the best n-f points; a two-phase framework proposes inner (cluster) and outer (complement) aggregates and lets workers vote by loss on fresh mini-batches.
Key results
- At adversarial rate 0.4 on homogeneous FEMNIST, Cent2P achieves worst-case accuracy 0.62 and Mean2P 0.61, versus 0.20 for the best baseline (CClip).
- Cent2P and Mean2P are the only methods exceeding 0.75 accuracy under the Omn attack at rate 0.4 among those listed (Omn accuracy 0.79 for both, other methods ≤0.20).
- Theoretically, CenterwO matches the lower bound f/(n-f) for (f,λ)-resilient averaging up to a constant, and MeanwO gives O(1) agnostic robustness.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use Cent2P (two-phase aggregation with 1-center clustering) instead of the strongest baseline CClip | RASHB on FEMNIST homogeneous data, rate 0.1 · FEMNIST homogeneous, rate 0.1 | worst-case testing accuracy: 0.60 -> 0.76 | Helped |
| Use Mean2P (two-phase aggregation with 1-mean clustering) instead of the strongest baseline CClip | RASHB on FEMNIST homogeneous data, rate 0.2 · FEMNIST homogeneous, rate 0.2 | worst-case testing accuracy: 0.49 -> 0.75 | Helped |
| Use Cent2P (two-phase aggregation with 1-center clustering) instead of the strongest baseline CClip | RASHB on FEMNIST homogeneous data, rate 0.4 · FEMNIST homogeneous, rate 0.4 | worst-case testing accuracy: 0.20 -> 0.62 | Helped |
| Use Mean2P (two-phase aggregation with 1-mean clustering) instead of the strongest baseline CClip | RASHB on FEMNIST heterogeneous data, rate 0.1 · FEMNIST heterogeneous, rate 0.1 | worst-case testing accuracy: 0.43 -> 0.82 | Helped |
| Use Mean2P (two-phase aggregation with 1-mean clustering) instead of the strongest baseline CClip | RASHB on FEMNIST heterogeneous data, rate 0.2 · FEMNIST heterogeneous, rate 0.2 | worst-case testing accuracy: 0.25 -> 0.72 | Helped |
| Use Cent2P or Mean2P instead of CClip | RASHB on FEMNIST heterogeneous data, rate 0.4 · FEMNIST heterogeneous, rate 0.4 | worst-case testing accuracy: 0.12 -> 0.12 | No clear effect |
| Use Cent2P or Mean2P instead of other aggregation rules | RASHB on FEMNIST heterogeneous data under SF and Omn attacks · FEMNIST heterogeneous, rate 0.2 | testing accuracy | Helped |
| Use Avg instead of Cent2P or Mean2P | RASHB on FEMNIST heterogeneous data under Empire attack · FEMNIST heterogeneous, rate 0.2 | testing accuracy | Helped |
Surprising findings
- Avg achieves the best performance under the Empire attack in heterogeneous settings, and some resilient rules degrade significantly there.
Limitations
- No theoretical guarantee is provided for the two-phase 2PRASHB framework.
- Experiments are limited to a small CNN on FEMNIST and CIFAR-10 with 35 clients.
- Only one fixed set of hyperparameters and a single learning rate were used across attacks.
Experimental setup
Datasets: FEMNIST EMNIST CIFAR-10
Benchmarks: FEMNIST CIFAR-10
Metrics: testing accuracy worst-case accuracy across attacks
Baselines: Avg Geometric Median (Weiszfeld) CClip CWM CWTM Krum
Builds on: RASHB / resilient aggregated stochastic heavy ball minimum enclosing ball with outliers MDA NNM
Closest papers by meaning
- On the Tension between Byzantine Robustness and No-Attack Accuracy in Distributed Learning (ICML 2025 · similarity 0.90)
- Byzantine-Robust Decentralized Learning via Remove-then-Clip Aggregation (AAAI 2024 · similarity 0.88)
- Weight for Robustness: A Comprehensive Approach towards Optimal Fault-Tolerant Asynchronous ML (NeurIPS 2024 · similarity 0.87)
- Fault Tolerant ML: Efficient Meta-Aggregation and Synchronous Training (ICML 2024 · similarity 0.87)
- Flag Aggregator: Scalable Distributed Training under Failures and Augmented Losses using Convex Optimization (ICLR 2024 · similarity 0.87)
- Unified Breakdown Analysis for Byzantine Robust Gossip (ICML 2025 · similarity 0.86)
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.