Research map / Optimization / Distributed and compressed

From Inexact Gradients to Byzantine Robustness: Acceleration and Optimization under Similarity

NeurIPS 2026 · Optimization › Distributed and compressed · approach: Byzantine-robust learning · 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.

Casts Byzantine-robust distributed optimization as inexact gradient oracles, yielding an accelerated robust method and a preconditioned proximal scheme (PIGS) under Hessian similarity.

Problem

Byzantine-robust distributed learning relies on ad-hoc analyses for robust aggregation, which hinders developing complex (e.g., accelerated) robust algorithms; heterogeneity and Byzantine fraction limit the achievable asymptotic error.

Approach

Show that robust aggregation of honest gradients yields a (zeta^2, alpha)-inexact gradient oracle (additive plus multiplicative error), so generic inexact-gradient results (accelerated fast gradient and similarity-based proximal methods) transfer directly to the Byzantine setting.

Key results

• PIGS reaches the asymptotic error in 5 iterations versus 41 for D-NAG and 135 for D-GD in one highly heterogeneous experiment.
• Accelerated robust method achieves O(sqrt(kappa) log(1/eps)) iteration complexity to an asymptotic error, the first such accelerated rate in the Byzantine setting per the authors.
• PIGS allows step size up to eta=8 in the i.i.d. setting while still converging, versus about eta=2 max in the highly heterogeneous setting.

Surprising findings

• Plain GD on standard robust aggregation attains the optimal asymptotic error without observing client identities, matching the lower bound.
• Neither ALIE nor IPM attacks destabilize PIGS at large learning rates; the attacks slow or bias rather than destabilize.

Limitations

• Accelerated method's asymptotic error is inflated by a sqrt(kappa) factor relative to the lower bound.
• Analysis restricted to strongly convex smooth losses and experiments limited to logistic regression on MNIST.
• Stochastic setting: memoryless abstraction cannot reach optimal asymptotic error with unbiased stochastic gradients.

Experimental setup

Datasets: MNIST

Benchmarks: MNIST

Metrics: communication rounds to asymptotic error loss suboptimality test accuracy

Baselines: D-GD D-NAG

Builds on: (delta,L,mu) oracle framework optimization under similarity NNM pre-aggregation ALIE attack ByzFL

Closest papers by meaning

• Byzantine-Robust Distributed Learning: Towards Optimal Statistical Rates (ICML 2018 · similarity 0.94)
• On the Tension between Byzantine Robustness and No-Attack Accuracy in Distributed Learning (ICML 2025 · similarity 0.91)
• Fault Tolerant ML: Efficient Meta-Aggregation and Synchronous Training (ICML 2024 · similarity 0.91)
• Byzantine Robustness and Partial Participation Can Be Achieved at Once: Just Clip Gradient Differences (NeurIPS 2024 · similarity 0.91)
• Weight for Robustness: A Comprehensive Approach towards Optimal Fault-Tolerant Asynchronous ML (NeurIPS 2024 · similarity 0.90)
• Byzantine-Robust Decentralized Learning via Remove-then-Clip Aggregation (AAAI 2024 · similarity 0.89)