# Constructive Universal Approximation and Finite Sample Memorization by Narrow Deep ReLU Networks

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

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 19 of its 45 references that are in the map.
- First posted on arXiv 10 Sep 2024.

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

- [Understanding deep learning requires rethinking generalization](https://mlsanity.com/paper/1611.03530/) (2016)
- [The Expressive Power of Neural Networks: A View from the Width](https://mlsanity.com/paper/1709.02540/) (2017)
- [Benefits of depth in neural networks](https://mlsanity.com/paper/1602.04485/) (2016)
- [Universal Approximation with Deep Narrow Networks](https://mlsanity.com/paper/1905.08539/) (2019)
- [Approximating Continuous Functions by ReLU Nets of Minimal Width](https://mlsanity.com/paper/1710.11278/) (2017)
- [Identity Matters in Deep Learning](https://mlsanity.com/paper/1611.04231/) (2016)
- [Universal Function Approximation by Deep Neural Nets with Bounded Width and ReLU Activations](https://mlsanity.com/paper/1708.02691/) (2017)
- [Minimum Width for Universal Approximation](https://mlsanity.com/paper/2006.08859/) (2020)
- [Small ReLU networks are powerful memorizers: a tight analysis of memorization capacity](https://mlsanity.com/paper/1810.07770/) (2018)
- [Neural ODE control for classification, approximation and transport](https://mlsanity.com/paper/2104.05278/) (2021)
- [Optimal Approximation Rates for Deep ReLU Neural Networks on Sobolev and Besov Spaces](https://mlsanity.com/paper/2211.14400/) (2022)
- [On the Optimal Memorization Power of ReLU Neural Networks](https://mlsanity.com/paper/2110.03187/) (2021)
- [Provable Memorization via Deep Neural Networks using Sub-linear Parameters](https://mlsanity.com/paper/2010.13363/) (2020)
- [Achieve the Minimum Width of Neural Networks for Universal Approximation](https://mlsanity.com/paper/2209.11395/) (2022)
- [Minimum width for universal approximation using ReLU networks on compact domain](https://mlsanity.com/paper/2309.10402/) (2023)
- [Minimum Width of Leaky-ReLU Neural Networks for Uniform Universal Approximation](https://mlsanity.com/paper/2305.18460/) (2023)
- [Minimal Width for Universal Property of Deep RNN](https://mlsanity.com/paper/2211.13866/) (2022)
- [Interplay between depth and width for interpolation in neural ODEs](https://mlsanity.com/paper/2401.09902/) (2024)
- [Controllability of ensembles of linear dynamical systems](https://mlsanity.com/paper/1504.06167/) (2015)

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

- [Representation and Regression Problems in Neural Networks: Relaxation, Generalization, and Numerics](https://mlsanity.com/paper/2412.01619/) (2024)
- [Exact Sequence Interpolation with Transformers](https://mlsanity.com/paper/2502.02270/) (2025)

## Abstract (arXiv)

We present a fully constructive analysis of deep ReLU neural networks for classification and function approximation tasks. First, we prove that any dataset with N distinct points in ℝd and M output classes can be exactly classified using a multilayer perceptron (MLP) of width 2 and depth at most 2N + 4M - 1, with all network parameters constructed explicitly. This result is sharp with respect to width and is interpreted through the lens of simultaneous or ensemble controllability in discrete nonlinear dynamics. Second, we show that these explicit constructions yield uniform bounds on the parameter norms and, in particular, provide upper estimates for minimizers of standard regularized training loss functionals in supervised learning. As the regularization parameter vanishes, the trained networks converge to exact classifiers with bounded norm, explaining the effectiveness of overparameterized training in the small-regularization regime. We also prove a universal approximation theorem in Lp(Omega; ℝ_+) for any bounded domain Omega subset ℝd and p ∈ [1, ∞), using MLPs of fixed width d + 1. The proof is constructive, geometrically motivated, and provides explicit estimates on the network depth when the target function belongs to the Sobolev space W1,p. We also extend the approximation and depth estimation results to Lp(Omega; ℝm) for any m ≥ 1. Our results offer a unified and interpretable framework connecting controllability, expressivity, and training dynamics in deep neural networks.