Constructive Universal Approximation and Finite Sample Memorization by Narrow Deep Relu Networks

Hernández Salinas M, Zuazua Iriondo E (2025)

Publication Language: English

Publication Status: Submitted

Publication Type: Unpublished / Preprint

Future Publication Type: Journal article

Publication year: 2025

Open Access Link: https://dcn.nat.fau.eu/wp-content/uploads/Constructive_Universal_Approximation_and_Memorization_by_Deep_Networks_MH_EZ.pdf

Abstract

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 Rd 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(Ω; R+) for any bounded domain Ω ⊂ Rd 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(Ω; Rm) for any m ≥ 1. Our results offer a unified and interpretable framework connecting controllability, expressivity, and training dynamics in deep neural networks.

Authors with CRIS profile

Martin Hernández Salinas Lehrstuhl für Dynamics, Control, Machine Learning and Numerics (Alexander von Humboldt-Professur) Enrique Zuazua Iriondo Lehrstuhl für Dynamics, Control, Machine Learning and Numerics (Alexander von Humboldt-Professur)

How to cite

APA:

Hernández Salinas, M., & Zuazua Iriondo, E. (2025). Constructive Universal Approximation and Finite Sample Memorization by Narrow Deep Relu Networks. (Unpublished, Submitted).

MLA:

Hernández Salinas, Martin, and Enrique Zuazua Iriondo. Constructive Universal Approximation and Finite Sample Memorization by Narrow Deep Relu Networks. Unpublished, Submitted. 2025.

BibTeX: Download