Research map / Learning theory and algorithms / Prediction and decision losses

Unified Breakdown Analysis for Byzantine Robust Gossip

ICML 2025 · Learning theory and algorithms › Prediction and decision losses · approach: Determinantal point process inference · 0 citations (OpenAlex)

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.

Introduces F-RG, a framework that turns robust summation rules into Byzantine-robust gossip algorithms, derives a near-optimal breakdown point for sparse graphs, and proposes the Clipped Sum rule and a Spectral Heterogeneity attack.

Problem

Byzantine-robust decentralized (gossip) averaging and optimization on sparse, heterogeneous networks, where it was unclear how many Byzantine nodes can be tolerated over an arbitrary graph.

Approach

Robust gossip applies a robust summation rule to parameter differences with neighbors (x_i - eta F(w_ij, x_i - x_j)); a (b,rho)-robust summation condition yields convergence guarantees and a spectral upper bound (2b < mu_min) on tolerable Byzantine weight, with a practical adaptive clipping rule achieving rho=2.

Key results

• Clipped Sum rule (CS-tau+) is (b,2)-robust, and the framework gives a Byzantine breakdown condition 2b < mu_min, tolerating up to about 1/5 Byzantine fraction in a fully connected network versus 1/(9 sqrt|H|) in prior work.
• Theory shows no algorithm can be r-robust when 2b >= mu_2 of the honest subgraph, matching the 1/3 fully connected breakdown point.
• Experiments show CS-RG is highly resilient while NNA (GTS-RG) fails before the optimal breakdown point under the Spectral Heterogeneity attack.

Measured effects reported in the paper

Surprising findings

• NNA-type rules (GTS) fail before the theoretical optimal breakdown point in experiments.
• Clipped Sum is not (b,rho)-robust with a fixed constant clipping threshold; the threshold must adapt to inputs.

Limitations

• Practical rule achieves rho=2, not the optimal rho=1; whether rho=1 is achievable by a practical rule is open.
• Experiments are limited to small simple tasks (MNIST, CIFAR-10 with small CNN, averaging) with few seeds (1 seed for learning experiments).
• Asynchronous extension only gives a weaker robustness constant.

Experimental setup

Datasets: MNIST CIFAR-10

Benchmarks: MNIST CIFAR-10 averaging task on Two Worlds and Erdos-Renyi graphs

Metrics: relative mean square error test accuracy training loss

Baselines: ClippedGossip NNA IOS GTS-RG Dissensus ALIE FOE

Builds on: ClippedGossip NNA D-SGD with (alpha,lambda)-reduction (f,kappa)-robustness Dissensus attack

Closest papers by meaning

• Byzantine-Robust Decentralized Learning via Remove-then-Clip Aggregation (AAAI 2024 · similarity 0.89)
• On the Tension between Byzantine Robustness and No-Attack Accuracy in Distributed Learning (ICML 2025 · similarity 0.89)
• Robust Distributed Estimation: Extending Gossip Algorithms to Ranking and Trimmed Means (NeurIPS 2025 · similarity 0.87)
• Weight for Robustness: A Comprehensive Approach towards Optimal Fault-Tolerant Asynchronous ML (NeurIPS 2024 · similarity 0.87)
• Decentralized Ranking Aggregation via Gossip: Convergence and Robustness (NeurIPS 2026 · similarity 0.86)
• Byzantine Robustness and Partial Participation Can Be Achieved at Once: Just Clip Gradient Differences (NeurIPS 2024 · similarity 0.86)