# Gradient Methods Provably Converge to Non-Robust Networks

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

## Key facts

- Cited by 27 papers in the map (data through 14 Oct 2026).
- Builds on 33 of its 40 references that are in the map.
- First posted on arXiv 9 Feb 2022.

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

- [PyTorch: An Imperative Style, High-Performance Deep Learning Library](https://mlsanity.com/paper/1912.01703/) (2019)
- [Explaining and Harnessing Adversarial Examples](https://mlsanity.com/paper/1412.6572/) (2014)
- [Towards Deep Learning Models Resistant to Adversarial Attacks](https://mlsanity.com/paper/1706.06083/) (2017)
- [Intriguing properties of neural networks](https://mlsanity.com/paper/1312.6199/) (2013)
- [Reliable evaluation of adversarial robustness with an ensemble of diverse parameter-free attacks](https://mlsanity.com/paper/2003.01690/) (2020)
- [Obfuscated Gradients Give a False Sense of Security: Circumventing Defenses to Adversarial Examples](https://mlsanity.com/paper/1802.00420/) (2018)
- [Practical Black-Box Attacks against Machine Learning](https://mlsanity.com/paper/1602.02697/) (2016)
- [Universal adversarial perturbations](https://mlsanity.com/paper/1610.08401/) (2016)
- [Distillation as a Defense to Adversarial Perturbations against Deep Neural Networks](https://mlsanity.com/paper/1511.04508/) (2015)
- [Provable defenses against adversarial examples via the convex outer adversarial polytope](https://mlsanity.com/paper/1711.00851/) (2017)
- [Adversarial Examples Are Not Easily Detected: Bypassing Ten Detection Methods](https://mlsanity.com/paper/1705.07263/) (2017)
- [Delving into Transferable Adversarial Examples and Black-box Attacks](https://mlsanity.com/paper/1611.02770/) (2016)
- [Threat of Adversarial Attacks on Deep Learning in Computer Vision: A Survey](https://mlsanity.com/paper/1801.00553/) (2018)
- [The Pitfalls of Simplicity Bias in Neural Networks](https://mlsanity.com/paper/2006.07710/) (2020)
- [Gradient Descent Maximizes the Margin of Homogeneous Neural Networks](https://mlsanity.com/paper/1906.05890/) (2019)
- [Adversarially Robust Generalization Requires More Data](https://mlsanity.com/paper/1804.11285/) (2018)
- [High Frequency Component Helps Explain the Generalization of Convolutional Neural Networks](https://mlsanity.com/paper/1905.13545/) (2019)
- [Audio Adversarial Examples: Targeted Attacks on Speech-to-Text](https://mlsanity.com/paper/1801.01944/) (2018)
- [Directional convergence and alignment in deep learning](https://mlsanity.com/paper/2006.06657/) (2020)
- [Making an Invisibility Cloak: Real World Adversarial Attacks on Object Detectors](https://mlsanity.com/paper/1910.14667/) (2019)
- [Are adversarial examples inevitable?](https://mlsanity.com/paper/1809.02104/) (2018)
- [Feature Purification: How Adversarial Training Performs Robust Deep Learning](https://mlsanity.com/paper/2005.10190/) (2020)
- [Adversarial examples from computational constraints](https://mlsanity.com/paper/1805.10204/) (2018)
- [Adversarial vulnerability for any classifier](https://mlsanity.com/paper/1802.08686/) (2018)
- [A Survey On Universal Adversarial Attack](https://mlsanity.com/paper/2103.01498/) (2021)
- [On the Geometry of Adversarial Examples](https://mlsanity.com/paper/1811.00525/) (2018)
- [The Dimpled Manifold Model of Adversarial Examples in Machine Learning](https://mlsanity.com/paper/2106.10151/) (2021)
- [On Margin Maximization in Linear and ReLU Networks](https://mlsanity.com/paper/2110.02732/) (2021)
- [A Simple Explanation for the Existence of Adversarial Examples with Small Hamming Distance](https://mlsanity.com/paper/1901.10861/) (2019)
- [A single gradient step finds adversarial examples on random two-layers neural networks](https://mlsanity.com/paper/2104.03863/) (2021)

## Built on by (most cited first, 27 of 27)

- [On the Implicit Bias in Deep-Learning Algorithms](https://mlsanity.com/paper/2208.12591/) (2022)
- [Shortcut Learning of Large Language Models in Natural Language Understanding](https://mlsanity.com/paper/2208.11857/) (2022)
- [Implicit Bias in Leaky ReLU Networks Trained on High-Dimensional Data](https://mlsanity.com/paper/2210.07082/) (2022)
- [The Implicit Bias of Adam on Separable Data](https://mlsanity.com/paper/2406.10650/) (2024)
- [Benign Overfitting in Linear Classifiers and Leaky ReLU Networks from KKT Conditions for Margin Maximization](https://mlsanity.com/paper/2303.01462/) (2023)
- [Simplicity Bias in 1-Hidden Layer Neural Networks](https://mlsanity.com/paper/2302.00457/) (2023)
- [The Double-Edged Sword of Implicit Bias: Generalization vs. Robustness in ReLU Networks](https://mlsanity.com/paper/2303.01456/) (2023)
- [Implicit Bias of Gradient Descent for Two-layer ReLU and Leaky ReLU Networks on Nearly-orthogonal Data](https://mlsanity.com/paper/2310.18935/) (2023)
- [Learning a Neuron by a Shallow ReLU Network: Dynamics and Implicit Bias for Correlated Inputs](https://mlsanity.com/paper/2306.06479/) (2023)
- [Adversarial Examples in Random Neural Networks with General Activations](https://mlsanity.com/paper/2203.17209/) (2022)
- [The Implicit Bias of Adam and Muon on Smooth Homogeneous Neural Networks](https://mlsanity.com/paper/2602.16340/) (2026)
- [Adversarial Reprogramming Revisited](https://mlsanity.com/paper/2206.03466/) (2022)
- [Adversarial Examples Exist in Two-Layer ReLU Networks for Low Dimensional Linear Subspaces](https://mlsanity.com/paper/2303.00783/) (2023)
- [Adversarial Robustness is at Odds with Lazy Training](https://mlsanity.com/paper/2207.00411/) (2022)
- [Deep ReLU Networks Have Surprisingly Simple Polytopes](https://mlsanity.com/paper/2305.09145/) (2023)
- [Fundamental Limits of Membership Inference Attacks on Machine Learning Models](https://mlsanity.com/paper/2310.13786/) (2023)
- [Effect of Ambient-Intrinsic Dimension Gap on Adversarial Vulnerability](https://mlsanity.com/paper/2403.03967/) (2024)
- [The Price of Implicit Bias in Adversarially Robust Generalization](https://mlsanity.com/paper/2406.04981/) (2024)
- [Robust Linear Regression: Gradient-descent, Early-stopping, and Beyond](https://mlsanity.com/paper/2301.13486/) (2023)
- [When Are Bias-Free ReLU Networks Effectively Linear Networks?](https://mlsanity.com/paper/2406.12615/) (2024)
- [Provable Privacy Attacks on Trained Shallow Neural Networks](https://mlsanity.com/paper/2410.07632/) (2024)
- [Upper and lower bounds for the Lipschitz constant of random neural networks](https://mlsanity.com/paper/2311.01356/) (2023)
- [Is Certifying ℓp Robustness Still Worthwhile?](https://mlsanity.com/paper/2310.09361/) (2023)
- [Feature compression is the root cause of adversarial fragility in neural network classifiers](https://mlsanity.com/paper/2406.16200/) (2024)
- [MALT Powers Up Adversarial Attacks](https://mlsanity.com/paper/2407.02240/) (2024)
- [A Provable Energy-Guided Test-Time Defense Boosting Adversarial Robustness of Large Vision-Language Models](https://mlsanity.com/paper/2603.26984/) (2026)
- [Existence of Adversarial Examples for Random Convolutional Networks via Isoperimetric Inequalities on mathbbso(d)](https://mlsanity.com/paper/2506.12613/) (2025)

## Abstract (arXiv)

Despite a great deal of research, it is still unclear why neural networks are so susceptible to adversarial examples. In this work, we identify natural settings where depth-2 ReLU networks trained with gradient flow are provably non-robust (susceptible to small adversarial ℓ2-perturbations), even when robust networks that classify the training dataset correctly exist. Perhaps surprisingly, we show that the well-known implicit bias towards margin maximization induces bias towards non-robust networks, by proving that every network which satisfies the KKT conditions of the max-margin problem is non-robust.