# Theoretical Lower Bounds on the Robustness of Deep ReLU Networks

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

## Key facts

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

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

- [Explaining and Harnessing Adversarial Examples](https://mlsanity.com/paper/1412.6572/) (2014)
- [Intriguing properties of neural networks](https://mlsanity.com/paper/1312.6199/) (2013)
- [Adversarial Examples: Attacks and Defenses for Deep Learning](https://mlsanity.com/paper/1712.07107/) (2017)
- [Nearly-tight VC-dimension and pseudodimension bounds for piecewise linear neural networks](https://mlsanity.com/paper/1703.02930/) (2017)
- [Towards Fast Computation of Certified Robustness for ReLU Networks](https://mlsanity.com/paper/1804.09699/) (2018)
- [Blessing of dimensionality: mathematical foundations of the statistical physics of data](https://mlsanity.com/paper/1801.03421/) (2018)
- [Provable Robustness of ReLU networks via Maximization of Linear Regions](https://mlsanity.com/paper/1810.07481/) (2018)
- [Attacks in Adversarial Machine Learning: A Systematic Survey from the Life-cycle Perspective](https://mlsanity.com/paper/2302.09457/) (2023)
- [The unreasonable effectiveness of small neural ensembles in high-dimensional brain](https://mlsanity.com/paper/1809.07656/) (2018)
- [Relative intrinsic dimensionality is intrinsic to learning](https://mlsanity.com/paper/2311.07579/) (2023)
- [The Boundaries of Verifiable Accuracy, Robustness, and Generalisation in Deep Learning](https://mlsanity.com/paper/2309.07072/) (2023)
- [Feature compression is the root cause of adversarial fragility in neural network classifiers](https://mlsanity.com/paper/2406.16200/) (2024)

## Abstract (arXiv)

We present a theoretical study of the robustness of parameterized neural networks to random input perturbations. Specifically, we analyze local robustness by quantifying the probability that a random L_2-perturbation of a given input results in a correct classification. For deep ReLU networks, we derive lower bounds on local robustness by combining tools from high-dimensional geometry, in particular concentration of measure, with a new characterization of the geometric structure induced by their input-output functions. We prove that each convex polyhedral region in the partition of the input space induced by a ReLU network has at most as many faces as there are network units, regardless of the network depth or architecture. This geometric property serves as the key ingredient in our robustness analysis. Finally, we analyze how local robustness scales with input dimension and characterize the sets of inputs whose neighborhoods are most likely to contain adversarial examples. We show that the width of decision-boundary neighborhoods containing vulnerable points shrinks rapidly as dimension increases and grows only logarithmically with the number of network units. We also discuss the volume of a set of vulnerable points in terms of approximately space-filling shapes of decision boundaries.