# Approaching the Harm of Gradient Attacks While Only Flipping Labels

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 31 of its 45 references that are in the map.
- First posted on arXiv 28 Feb 2025.

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

- [Learning Transferable Visual Models From Natural Language Supervision](https://mlsanity.com/paper/2103.00020/) (2021)
- [A Simple Framework for Contrastive Learning of Visual Representations](https://mlsanity.com/paper/2002.05709/) (2020)
- [Communication-Efficient Learning of Deep Networks from Decentralized Data](https://mlsanity.com/paper/1602.05629/) (2016)
- [Supervised Contrastive Learning](https://mlsanity.com/paper/2004.11362/) (2020)
- [Understanding deep learning requires rethinking generalization](https://mlsanity.com/paper/1611.03530/) (2016)
- [Byzantine-Robust Distributed Learning: Towards Optimal Statistical Rates](https://mlsanity.com/paper/1803.01498/) (2018)
- [Poison Frogs! Targeted Clean-Label Poisoning Attacks on Neural Networks](https://mlsanity.com/paper/1804.00792/) (2018)
- [Rethinking Few-Shot Image Classification: a Good Embedding Is All You Need?](https://mlsanity.com/paper/2003.11539/) (2020)
- [The Hidden Vulnerability of Distributed Learning in Byzantium](https://mlsanity.com/paper/1802.07927/) (2018)
- [Certified Defenses for Data Poisoning Attacks](https://mlsanity.com/paper/1706.03691/) (2017)
- [A Little Is Enough: Circumventing Defenses For Distributed Learning](https://mlsanity.com/paper/1902.06156/) (2019)
- [Can You Really Backdoor Federated Learning?](https://mlsanity.com/paper/1911.07963/) (2019)
- [Witches' Brew: Industrial Scale Data Poisoning via Gradient Matching](https://mlsanity.com/paper/2009.02276/) (2020)
- [Stronger Data Poisoning Attacks Break Data Sanitization Defenses](https://mlsanity.com/paper/1811.00741/) (2018)
- [Byzantine-Robust Learning on Heterogeneous Datasets via Bucketing](https://mlsanity.com/paper/2006.09365/) (2020)
- [MetaPoison: Practical General-purpose Clean-label Data Poisoning](https://mlsanity.com/paper/2004.00225/) (2020)
- [Generalized Byzantine-tolerant SGD](https://mlsanity.com/paper/1802.10116/) (2018)
- [Label Sanitization against Label Flipping Poisoning Attacks](https://mlsanity.com/paper/1803.00992/) (2018)
- [Label Poisoning is All You Need](https://mlsanity.com/paper/2310.18933/) (2023)
- [On the Impossible Safety of Large AI Models](https://mlsanity.com/paper/2209.15259/) (2022)
- [Indiscriminate Data Poisoning Attacks on Neural Networks](https://mlsanity.com/paper/2204.09092/) (2022)
- [An Equivalence Between Data Poisoning and Byzantine Gradient Attacks](https://mlsanity.com/paper/2202.08578/) (2022)
- [Byzantine-Robust Learning on Heterogeneous Data via Gradient Splitting](https://mlsanity.com/paper/2302.06079/) (2023)
- [Tournesol: A quest for a large, secure and trustworthy database of reliable human judgments](https://mlsanity.com/paper/2107.07334/) (2021)
- [Delegating Data Collection in Decentralized Machine Learning](https://mlsanity.com/paper/2309.01837/) (2023)
- [Unravelling in Collaborative Learning](https://mlsanity.com/paper/2407.14332/) (2024)
- [Adversarial Training for Defense Against Label Poisoning Attacks](https://mlsanity.com/paper/2502.17121/) (2025)
- [Transferable Availability Poisoning Attacks](https://mlsanity.com/paper/2310.05141/) (2023)
- [Mean Aggregator is More Robust than Robust Aggregators under Label Poisoning Attacks on Distributed Heterogeneous Data](https://mlsanity.com/paper/2404.13647/) (2024)
- [The poison of dimensionality](https://mlsanity.com/paper/2409.17328/) (2024)

## Abstract (arXiv)

Machine learning systems deployed in distributed or federated environments are highly susceptible to adversarial manipulations, particularly availability attacks -- rendering the trained model unavailable. Prior research in distributed ML has demonstrated such adversarial effects through the injection of gradients or data poisoning. In this work, we ask whether comparable degradation is still possible under a substantially more constrained action space: the adversary may only flip a limited number of labels of existing training examples, without modifying features, injecting samples, or directly controlling gradients. We analyze the extent of damage caused by constrained label flipping attacks against distributed learning under mean aggregation -- the dominant baseline in research and production. Focusing on classification problems, (1) we propose a novel formalization of label flipping attacks as a per-round constrained optimization problem, derive a greedy label-selection rule for logistic regression, and empirically evaluate it beyond its derivation setting, including on MLPs and robust aggregators. The rule is provably per-epoch optimal for the attacker under the mean aggregator. (2) Empirically, we show that optimized label flipping can cause substantial accuracy degradation while outperforming random label flipping under similar budgets. (3) We shed light on an interesting interplay between what the attacker gains from more write-access versus what they gain from more flipping budget. (4) Finally, although the attack is derived for mean aggregation, we find that it can transfer empirically to the coordinate-wise median and trimmed mean aggregators, where its effectiveness approaches that of the Little-is-Enough gradient attack. This demonstrates that even highly constrained label-flipping adversaries can pose a significant availability threat to distributed learning.