# Bridging the Gap Between Approximation and Learning via Optimal Approximation by ReLU MLPs of Maximal Regularity

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

## Key facts

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

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

- [Neural Operators Can Play Dynamic Stackelberg Games](https://mlsanity.com/paper/2411.09644/) (2024)
- [One model to solve them all: 2BSDE families via neural operators](https://mlsanity.com/paper/2511.01125/) (2025)
- [Simultaneously Solving Infinitely Many LQ Mean Field Games In Hilbert Spaces: The Power of Neural Operators](https://mlsanity.com/paper/2510.20017/) (2025)
- [Beyond Universal Approximation Theorems: Algorithmic Uniform Approximation by Neural Networks Trained with Noisy Data](https://mlsanity.com/paper/2509.00924/) (2025)
- [Autonomous-Flow-Based Generation](https://mlsanity.com/paper/2511.09902/) (2025)
- [Algorithmic Foundations of Deep Learning: Complexity-Theoretic Rates and a Characterization of Universal Approximation](https://mlsanity.com/paper/2606.26705/) (2026)
- [Structure-Preserving Reconstruction of Convex Lipschitz Functionals on Hilbert Spaces from Finite Samples](https://mlsanity.com/paper/2605.08559/) (2026)
- [NeuralChaos: Optimal Adapted Approximation of Square Integrable Predictable Processes](https://mlsanity.com/paper/2607.14361/) (2026)
- [A Closed-Form Formula for Consistent Lipschitz Regression on Metric Spaces with Sparse Neural Network Realizations](https://mlsanity.com/paper/2609.03129/) (2026)
- [Into the danger zone: stable extrapolation in high-dimensional function and operator learning](https://mlsanity.com/paper/2609.36709/) (2026)

## Abstract (arXiv)

The foundations of deep learning are supported by the seemingly opposing perspectives of approximation or learning theory. The former advocates for large/expressive models that need not generalize, while the latter considers classes that generalize but may be too small/constrained to be universal approximators. Motivated by real-world deep learning implementations that are both expressive and statistically reliable, we ask: "Is there a class of neural networks that is both large enough to be universal but structured enough to generalize?" This paper constructively provides a positive answer to this question by identifying a highly structured class of ReLU multilayer perceptions (MLPs), which are optimal function approximators and are statistically well-behaved. We show that any (L,α)-H"older function from [0,1]d to [-n,n] can be approximated to a uniform O(1/n) error on [0,1]d with a sparsely connected ReLU MLP with the same H"older exponent α and coefficient L, of width O(dnd/α), depth O(log(d)), with O(dnd/α) nonzero parameters, and whose weights and biases take values in 0,± 1/2 except in the first and last layers which instead have magnitude at-most n. Further, our class of MLPs achieves a near-optimal sample complexity of O(log(N)/√N) when given N i.i.d. normalized sub-Gaussian training samples. We achieve this through a new construction that perfectly fits together linear pieces using Kuhn triangulations, along with a new proof technique which shows that our construction preserves the regularity of not only the H"older functions, but also any uniformly continuous function. Our results imply that neural networks can solve the McShane extension problem on suitable finite sets.