提出一种兼具强逼近能力与良好泛化性的ReLU MLP结构。
Bridging the Gap Between Approximation and Learning via Optimal Approximation by ReLU MLPs of Maximal Regularity
- 用Kuhn三角剖分构造带稀疏连接的ReLU MLP，保持函数正则性。
- 对Hölder函数可实现均匀误差O(1/n)，样本复杂度近最优。
- 适合关注深度学习理论统一性的研究者参考。
深度学习的理论基础面临近似与学习理论的对立：前者青睐大而表达力强的模型，后者关注能泛化的紧凑类。针对现实中的深度网络既表达力强又统计可靠的现象，本文构建了一类高度结构化的ReLU多层感知机（MLP），既能作为通用逼近器，又具备良好的统计行为。证明任意从[0,1]^d到[-n,n]的(L,α)-Hölder函数，可用宽度O(dn^{d/α})、深度O(log d)、含O(dn^{d/α})个非零参数的稀疏连接ReLU MLP，以均匀误差O(1/n)逼近，且权重和偏置仅取值于{0,±1/2}（首尾层除外，其绝对值不超过n）。该类网络在给定N个独立同分布的归一化次高斯训练样本时，达到近最优样本复杂度O(log N / √N)。通过结合Kuhn三角剖分与新证明技巧，确保构造保持了原函数及任何一致连续函数的正则性。结果表明神经网络可在有限集上解决McShane延拓问题。
原文摘要 · Abstract (English)
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ölder function from $[0,1]^d$ to $[-n,n]$ can be approximated to a uniform $\mathcal{O}(1/n)$ error on $[0,1]^d$ with a sparsely connected ReLU MLP with the same Hölder exponent $α$ and coefficient $L$, of width $\mathcal{O}(dn^{d/α})$, depth $\mathcal{O}(\log(d))$, with $\mathcal{O}(dn^{d/α})$ nonzero parameters, and whose weights and biases take values in $\{0,\pm 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 $\mathcal{O}(\log(N)/\sqrt{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ölder functions, but also any uniformly continuous function. Our results imply that neural networks can solve the McShane extension problem on suitable finite sets.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。