# Byzantine-Robust Optimization under (L0, L1)-Smoothness

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 48 of its 58 references that are in the map.
- First posted on arXiv 12 Mar 2026.

## Builds on (most cited first, 30 of 48)

- [Byzantine-Robust Distributed Learning: Towards Optimal Statistical Rates](https://mlsanity.com/paper/1803.01498/) (2018)
- [Federated Optimization: Distributed Machine Learning for On-Device Intelligence](https://mlsanity.com/paper/1610.02527/) (2016)
- [Why gradient clipping accelerates training: A theoretical justification for adaptivity](https://mlsanity.com/paper/1905.11881/) (2019)
- [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)
- [A Tail-Index Analysis of Stochastic Gradient Noise in Deep Neural Networks](https://mlsanity.com/paper/1901.06053/) (2019)
- [Federated Optimization:Distributed Optimization Beyond the Datacenter](https://mlsanity.com/paper/1511.03575/) (2015)
- [Training Deep Learning Models with Norm-Constrained LMOs](https://mlsanity.com/paper/2502.07529/) (2025)
- [Fall of Empires: Breaking Byzantine-tolerant SGD by Inner Product Manipulation](https://mlsanity.com/paper/1903.03936/) (2019)
- [Momentum Improves Normalized SGD](https://mlsanity.com/paper/2002.03305/) (2020)
- [Stochastic Polyak Step-size for SGD: An Adaptive Learning Rate for Fast Convergence](https://mlsanity.com/paper/2002.10542/) (2020)
- [Learning from History for Byzantine Robust Optimization](https://mlsanity.com/paper/2012.10333/) (2020)
- [Byzantine-Robust Learning on Heterogeneous Datasets via Bucketing](https://mlsanity.com/paper/2006.09365/) (2020)
- [Distributed Learning with Compressed Gradient Differences](https://mlsanity.com/paper/1901.09269/) (2019)
- [Convergence of Adam Under Relaxed Assumptions](https://mlsanity.com/paper/2304.13972/) (2023)
- [Understanding Gradient Orthogonalization for Deep Learning via Non-Euclidean Trust-Region Optimization](https://mlsanity.com/paper/2503.12645/) (2025)
- [Improved Analysis of Clipping Algorithms for Non-convex Optimization](https://mlsanity.com/paper/2010.02519/) (2020)
- [Revisiting Gradient Clipping: Stochastic bias and tight convergence guarantees](https://mlsanity.com/paper/2305.01588/) (2023)
- [Robustness to Unbounded Smoothness of Generalized SignSGD](https://mlsanity.com/paper/2208.11195/) (2022)
- [Federated Variance-Reduced Stochastic Gradient Descent with Robustness to Byzantine Attacks](https://mlsanity.com/paper/1912.12716/) (2019)
- [Fixing by Mixing: A Recipe for Optimal Byzantine ML under Heterogeneity](https://mlsanity.com/paper/2302.01772/) (2023)
- [Convergence of AdaGrad for Non-convex Objectives: Simple Proofs and Relaxed Assumptions](https://mlsanity.com/paper/2305.18471/) (2023)
- [From Gradient Clipping to Normalization for Heavy Tailed SGD](https://mlsanity.com/paper/2410.13849/) (2024)
- [Challenges and Approaches for Mitigating Byzantine Attacks in Federated Learning](https://mlsanity.com/paper/2112.14468/) (2021)
- [Beyond Uniform Smoothness: A Stopped Analysis of Adaptive SGD](https://mlsanity.com/paper/2302.06570/) (2023)
- [Generalized-Smooth Nonconvex Optimization is As Efficient As Smooth Nonconvex Optimization](https://mlsanity.com/paper/2303.02854/) (2023)
- [Parameter-Agnostic Optimization under Relaxed Smoothness](https://mlsanity.com/paper/2311.03252/) (2023)
- [Robust Distributed Learning: Tight Error Bounds and Breakdown Point under Data Heterogeneity](https://mlsanity.com/paper/2309.13591/) (2023)
- [Methods for Convex (L0,L1)-Smooth Optimization: Clipping, Acceleration, and Adaptivity](https://mlsanity.com/paper/2409.14989/) (2024)
- [MoMo: Momentum Models for Adaptive Learning Rates](https://mlsanity.com/paper/2305.07583/) (2023)

## Abstract (arXiv)

We consider distributed optimization under Byzantine attacks in the presence of (L0,L1)-smoothness, a generalization of standard L-smoothness that captures functions with state-dependent gradient Lipschitz constants. We propose Byz-NSGDM, a normalized stochastic gradient descent method with momentum that achieves robustness against Byzantine workers while maintaining convergence guarantees. Our algorithm combines momentum normalization with Byzantine-robust aggregation enhanced by Nearest Neighbor Mixing (NNM) to handle both the challenges posed by (L0,L1)-smoothness and Byzantine adversaries. We prove that Byz-NSGDM achieves a convergence rate of O(K-1/4) up to a Byzantine bias floor proportional to the robustness coefficient and gradient heterogeneity. Experimental validation on heterogeneous MNIST classification, synthetic (L0,L1)-smooth optimization, and character-level language modeling with a small GPT model demonstrates the effectiveness of our approach against various Byzantine attack strategies. An ablation study further shows that Byz-NSGDM is robust across a wide range of momentum and learning rate choices.