# The Restricted Isometry of ReLU Networks: Generalization through Norm Concentration

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

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 1 Jul 2020.

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

- [Convergence bounds for nonlinear least squares and applications to tensor recovery](https://mlsanity.com/paper/2108.05237/) (2021)
- [Convergence bounds for local least squares approximation](https://mlsanity.com/paper/2208.10954/) (2022)
- [Non-Negative Stiefel Approximating Flow: Orthogonalish Matrix Optimization for Interpretable Embeddings](https://mlsanity.com/paper/2511.06425/) (2025)
- [Towards Atoms of Large Language Models](https://mlsanity.com/paper/2509.20784/) (2025)

## Abstract (arXiv)

While regression tasks aim at interpolating a relation on the entire input space, they often have to be solved with a limited amount of training data. Still, if the hypothesis functions can be sketched well with the data, one can hope for identifying a generalizing model. In this work, we introduce with the Neural Restricted Isometry Property (NeuRIP) a uniform concentration event, in which all shallow ReLU networks are sketched with the same quality. To derive the sample complexity for achieving NeuRIP, we bound the covering numbers of the networks in the Sub-Gaussian metric and apply chaining techniques. In case of the NeuRIP event, we then provide bounds on the expected risk, which hold for networks in any sublevel set of the empirical risk. We conclude that all networks with sufficiently small empirical risk generalize uniformly.