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

arXiv: https://arxiv.org/abs/2602.03329 · HTML: https://mlsanity.com/paper/2602.03329/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 29 of its 39 references that are in the map.
- First posted on arXiv 3 Feb 2026.

## Builds on (most cited first, 29 of 29)

- [Measuring the Effects of Non-Identical Data Distribution for Federated Visual Classification](https://mlsanity.com/paper/1909.06335/) (2019)
- [Byzantine-Robust Distributed Learning: Towards Optimal Statistical Rates](https://mlsanity.com/paper/1803.01498/) (2018)
- [An Introduction to Matrix Concentration Inequalities](https://mlsanity.com/paper/1501.01571/) (2015)
- [Robust Aggregation for Federated Learning](https://mlsanity.com/paper/1912.13445/) (2019)
- [A Little Is Enough: Circumventing Defenses For Distributed Learning](https://mlsanity.com/paper/1902.06156/) (2019)
- [Robust Estimators in High Dimensions without the Computational Intractability](https://mlsanity.com/paper/1604.06443/) (2016)
- [Fall of Empires: Breaking Byzantine-tolerant SGD by Inner Product Manipulation](https://mlsanity.com/paper/1903.03936/) (2019)
- [Learning from History for Byzantine Robust Optimization](https://mlsanity.com/paper/2012.10333/) (2020)
- [Communication Efficient Distributed Optimization using an Approximate Newton-type Method](https://mlsanity.com/paper/1312.7853/) (2013)
- [Byzantine-Robust Learning on Heterogeneous Datasets via Bucketing](https://mlsanity.com/paper/2006.09365/) (2020)
- [On the Convergence of SGD with Biased Gradients](https://mlsanity.com/paper/2008.00051/) (2020)
- [Fixing by Mixing: A Recipe for Optimal Byzantine ML under Heterogeneity](https://mlsanity.com/paper/2302.01772/) (2023)
- [Byzantine Machine Learning Made Easy by Resilient Averaging of Momentums](https://mlsanity.com/paper/2205.12173/) (2022)
- [Optimal and Practical Algorithms for Smooth and Strongly Convex Decentralized Optimization](https://mlsanity.com/paper/2006.11773/) (2020)
- [Statistically Preconditioned Accelerated Gradient Method for Distributed Optimization](https://mlsanity.com/paper/2002.10726/) (2020)
- [Robust Distributed Learning: Tight Error Bounds and Breakdown Point under Data Heterogeneity](https://mlsanity.com/paper/2309.13591/) (2023)
- [Distributed Newton Can Communicate Less and Resist Byzantine Workers](https://mlsanity.com/paper/2006.08737/) (2020)
- [A Robust Accelerated Optimization Algorithm for Strongly Convex Functions](https://mlsanity.com/paper/1710.04753/) (2017)
- [Robust Collaborative Learning with Linear Gradient Overhead](https://mlsanity.com/paper/2209.10931/) (2022)
- [Communication Compression for Byzantine Robust Learning: New Efficient Algorithms and Improved Rates](https://mlsanity.com/paper/2310.09804/) (2023)
- [Unified Breakdown Analysis for Byzantine Robust Gossip](https://mlsanity.com/paper/2410.10418/) (2024)
- [Towards Trustworthy Federated Learning with Untrusted Participants](https://mlsanity.com/paper/2505.01874/) (2025)
- [A frequency-domain analysis of inexact gradient methods](https://mlsanity.com/paper/1912.13494/) (2019)
- [Two Losses Are Better Than One: Faster Optimization Using a Cheaper Proxy](https://mlsanity.com/paper/2302.03542/) (2023)
- [Byzantine Robustness and Partial Participation Can Be Achieved at Once: Just Clip Gradient Differences](https://mlsanity.com/paper/2311.14127/) (2023)
- [ByzFL: Research Framework for Robust Federated Learning](https://mlsanity.com/paper/2505.24802/) (2025)
- [Accelerated gradient methods with absolute and relative noise in the gradient](https://mlsanity.com/paper/2102.02921/) (2021)
- [Byzantine-Robust and Communication-Efficient Distributed Learning via Compressed Momentum Filtering](https://mlsanity.com/paper/2409.08640/) (2024)
- [A Byzantine-Robust Federated Learning with Nesterov Momentum](https://mlsanity.com/paper/2511.02657/) (2025)

## Abstract (arXiv)

Standard federated learning algorithms are vulnerable to adversarial nodes, a.k.a. Byzantine failures. To solve this issue, robust distributed learning algorithms have been developed, which typically replace parameter averaging by robust aggregations. While generic conditions on these aggregations exist to guarantee the convergence of (Stochastic) Gradient Descent (SGD), the analyses remain rather ad-hoc. This hinders the development of more complex robust algorithms, such as accelerated ones. In this work, we show that Byzantine-robust distributed optimization can, under standard generic assumptions, be cast as a general optimization with inexact gradient oracles (with both additive and multiplicative error terms), an active field of research. This allows for instance to directly show that GD on top of standard robust aggregation procedures obtains optimal asymptotic error in the Byzantine setting. Going further, we propose two optimization schemes to speed up the convergence. The first one is a Nesterov-type accelerated scheme whose proof directly derives from accelerated inexact gradient results applied to our formulation. The second one hinges on Optimization under Similarity, in which the server leverages an auxiliary loss function that approximates the global loss. Both approaches allow to drastically reduce the communication complexity compared to previous methods, as we show theoretically and empirically.