# Covering Numbers for Deep ReLU Networks with Applications to Function Approximation and Nonparametric Regression

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

## Key facts

- Cited by 11 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 8 Oct 2024.

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

- [Generalization Bounds and Statistical Guarantees for Multi-Task and Multiple Operator Learning with MNO Networks](https://mlsanity.com/paper/2604.01961/) (2026)
- [A Statistical Learning Perspective on Semi-dual Adversarial Neural Optimal Transport Solvers](https://mlsanity.com/paper/2502.01310/) (2025)
- [A Theory for Conditional Generative Modeling on Multiple Data Sources](https://mlsanity.com/paper/2502.14583/) (2025)
- [Estimating Heterogeneous Causal Effect on Networks via Orthogonal Learning](https://mlsanity.com/paper/2509.18484/) (2025)
- [Fast Rates for Nonstationary Weighted Risk Minimization](https://mlsanity.com/paper/2602.05742/) (2026)
- [Provable Offline Reinforcement Learning for Structured Cyclic MDPs](https://mlsanity.com/paper/2602.11679/) (2026)
- [α-Fair Insurance Pricing: A Fairness Continuum](https://mlsanity.com/paper/2606.14898/) (2026)
- [Expressivity and Statistical Trade-offs in Diffusion Policy Learning](https://mlsanity.com/paper/2607.07967/) (2026)
- [Depth Enables Local Entropy: Quadratic Depth Dependence in Deep Variation-Norm ReLU Regression](https://mlsanity.com/paper/2608.17434/) (2026)
- [Optimal Tradeoffs Between Network Size and Parameter Magnitude in Neural Approximation and Minimax Regression](https://mlsanity.com/paper/2609.25710/) (2026)
- [Approximation Property of Dropout Neural Networks: Sobolev Rates and Confidence Bounds](https://mlsanity.com/paper/2610.02253/) (2026)

## Abstract (arXiv)

Covering numbers of (deep) ReLU networks have been used to characterize approximation-theoretic performance, to upper-bound prediction error in nonparametric regression, and to quantify classification capacity. These results rely on covering number upper bounds obtained via explicit constructions of coverings. Lower bounds on covering numbers do not appear to be available in the literature. The present paper fills this gap by deriving tight (up to multiplicative constants) lower and upper bounds on the metric entropy (i.e., the logarithm of the covering numbers) of fully connected networks with bounded weights, sparse networks with bounded weights, and fully connected networks with quantized weights. The tightness of these bounds yields a fundamental understanding of the impact of sparsity, quantization, bounded versus unbounded weights, and network output truncation. Moreover, the bounds allow one to characterize fundamental limits of neural network transformation, including network compression, and lead to sharp upper bounds on the prediction error in nonparametric regression through deep networks. In particular, we remove a log6(n)-factor from the best known sample complexity rate for estimating Lipschitz functions via deep networks, thereby establishing optimality. Finally, we identify a systematic relation between optimal nonparametric regression and optimal approximation through deep networks, unifying numerous results in the literature and revealing underlying general principles.