arXiv:2409.06555stat.MLcs.LG2024-09被引 3

窄深ReLU网络可精确分类数据并逼近函数,参数构造明确且有界。

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

  • 用宽度为2的深度网络精确分类任意数据,深度不超过2N+4M-1
  • 网络参数有显式上界,小正则化下训练收敛到低范数解
  • 提供固定宽度网络逼近函数的几何构造方法,适合理论研究者

我们对窄深ReLU神经网络在分类和函数逼近任务中进行了完全构造性分析。首先,证明任意R^d中N个不同点、M个输出类的数据集,可用宽度为2、深度不超过2N+4M-1的多层感知机(MLP)精确分类,所有参数均可显式构造。该结果在宽度上是紧的,可从离散非线性动力系统的协同或集合可控性角度理解。其次,这些显式构造给出了参数范数的统一上界,尤其提供了标准正则化训练损失最小化解的上界估计。当正则化参数趋于零时,训练网络收敛至有界范数的精确分类器,解释了小正则化下过参数化训练的有效性。我们还证明了在任意有界域Ω⊂R^d及p∈[1,∞)下,使用宽度为d+1的MLP可在L^p(Ω; R_+)中实现泛函逼近,证明是构造性的,具有几何动机,并给出目标函数属于Sobolev空间W^{1,p}时的深度估计。我们还将逼近与深度估计结果推广至L^p(Ω; R^m),任意m≥1。这些结果构建了一个统一且可解释的框架,连接了控制性、表达能力与训练动态。

原文摘要 · Abstract (English)

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 $\mathbb{R}^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 $L^p(Ω; \mathbb{R}_+)$ for any bounded domain $Ω\subset \mathbb{R}^d$ and $p \in [1, \infty)$, 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 $W^{1,p}$. We also extend the approximation and depth estimation results to $L^p(Ω; \mathbb{R}^m)$ for any $m \geq 1$. Our results offer a unified and interpretable framework connecting controllability, expressivity, and training dynamics in deep neural networks.

神经网络理论函数逼近深度学习

Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。