arXiv:2410.06378stat.MLcs.AI2024-10被引 8

首次给出深度ReLU网络覆盖数的紧致上下界,揭示稀疏性与量化对模型容量的本质影响。

Covering Numbers for Deep ReLU Networks with Applications to Function Approximation and Nonparametric Regression

  • 通过构造覆盖集和推导下界,获得权重有界网络的熵紧致估计
  • 消除非参数回归中估计Lipschitz函数的样本复杂度中log⁶(n)因子,实现最优率
  • 揭示深度网络逼近与非参数回归之间的统一原理,适用于模型压缩分析

深度ReLU网络的覆盖数被广泛用于刻画逼近性能、上界非参数回归预测误差以及量化分类能力。现有研究依赖于显式构造所得到的覆盖数上界,但文献中缺乏覆盖数的下界。本文填补了这一空白,推导出全连接有界权重网络、稀疏有界权重网络及量化权重全连接网络的度量熵(即覆盖数的对数)的紧致上下界(乘法常数意义下)。这些紧致边界揭示了稀疏性、量化、有界与无界权重、输出截断对网络表达能力的根本影响。此外,边界可刻画神经网络变换的基本极限,包括网络压缩,并导出基于深度网络的非参数回归预测误差的尖锐上界。特别地,本文消除了现有最优样本复杂度率中log⁶(n)的因子,从而确立了最优性。最后,我们发现最优非参数回归与深度网络最优逼近之间存在系统性关联,统一了大量已有结果,揭示了深层原理。

原文摘要 · Abstract (English)

Covering numbers of (deep) ReLU networks have been used to characterize approximation-theoretic performance, to upper-bound prediction error in nonparametric regression, and to quantify classification capacity. These results rely on covering number upper bounds obtained via explicit constructions of coverings. Lower bounds on covering numbers do not appear to be available in the literature. The present paper fills this gap by deriving tight (up to multiplicative constants) lower and upper bounds on the metric entropy (i.e., the logarithm of the covering numbers) of fully connected networks with bounded weights, sparse networks with bounded weights, and fully connected networks with quantized weights. The tightness of these bounds yields a fundamental understanding of the impact of sparsity, quantization, bounded versus unbounded weights, and network output truncation. Moreover, the bounds allow one to characterize fundamental limits of neural network transformation, including network compression, and lead to sharp upper bounds on the prediction error in nonparametric regression through deep networks. In particular, we remove a $\log^6(n)$-factor from the best known sample complexity rate for estimating Lipschitz functions via deep networks, thereby establishing optimality. Finally, we identify a systematic relation between optimal nonparametric regression and optimal approximation through deep networks, unifying numerous results in the literature and revealing underlying general principles.

深度网络覆盖数非参数回归逼近理论

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