Function approximation and nonparametric regression with binary and ternary ReLU networks

技术摘要：二值与三值 ReLU 网络中的函数逼近与非参数回归

问题陈述
深度神经网络（DNN）已成为分类、模式识别和预测的标准工具。然而，实现高精度往往需要具有显著参数量的模型，这导致了高昂的计算成本和内存需求。这为在低容量设备上的部署带来了挑战。为了解决这一问题，研究人员探索了将网络权重限制在离散集合中，特别是二值权重 $\{ \pm 1 \}$ 和三值权重 $\{ 0, \pm 1 \}$。虽然此类网络在内存减少和能效方面具有优势，但在理论上仍存在差距，即：深层二值和三值 ReLU 网络是否能够逼近复杂的平滑函数，并在非参数回归中达到与实值网络相当的最优统计速率。

方法论
本文研究了具有受限权重集的深层稀疏 ReLU 网络之逼近能力。作者基于现有关于权重在区间 $[-1, 1]$ 以及特定集合 $\{0, \pm 1/2, \pm 1, 2\}$ 中的深层稀疏 ReLU 网络逼近 $\beta$-Hölder 函数的结果展开研究。

核心方法论贡献在于构建显式映射，以利用具有严格二值 $\{ \pm 1 \}$ 或三值 $\{ 0, \pm 1 \}$ 权重的网络来模拟具有权重 $\{0, \pm 1/2, \pm 1, 2\}$ 的网络。这是通过以下方式实现的：

1. 权重缩放与齐次性： 利用 ReLU 激活函数的正齐次性（$\sigma(ax) = a\sigma(x)$ 对于 $a > 0$）将缩放因子吸收进网络架构中。
2. 层扩展： 引入额外的隐藏层来复制特定的线性组合和缩放操作。
   • 为了模拟权重为 $\{0, \pm 1/2, \pm 1, 2\}$ 的网络，作者构建了一个使用三值权重 $\{0, \pm 1\}$（经由 $1/2^{L+3}$ 缩放）的网络，该过程使用了 2 个额外的隐藏层。这涉及复制输入坐标并使用 $\{0, \pm 1/2\}$ 的线性组合来表示目标权重。
   • 为了模拟三值权重 $\{0, \pm 1/2\}$，作者构建了一个使用二值权重 $\{ \pm 1 \}$（经由 $1/4^{L+6}$ 缩放）的网络，该过程使用了 3 个额外的隐藏层。这涉及使用权重 $\pm 1/4$ 计算输入的特定线性组合，以重建必要的值。
3. 非参数回归分析： 将这些逼近结果应用于非参数回归的经验风险最小化问题。作者定义了一类具有权重 $\{0, \pm 1\}$ 的稀疏三值 ReLU 网络，并分析了该类网络中经验风险最小化器的预测误差。

主要贡献与结果

1. 函数逼近（定理 2.2）：
   本文证明了属于 $[0, 1]^d$ 上 Hölder 球 $C^\beta_d(K)$ 的任何函数 $f_0$ 都可以被以下网络 $\epsilon$-逼近：

   • 深层稀疏三值 ReLU 网络： 权重在 $\{0, \pm 1\}$ 中（经由 $1/2^{L+3}$ 缩放）的网络。
   • 深层二值 ReLU 网络： 权重在 $\{ \pm 1 \}$ 中（经由 $1/4^{L+6}$ 缩放）的网络。

   研究表明，这些网络的深度和宽度与权重在 $\{0, \pm 1/2, \pm 1, 2\}$ 中所需的网络相比，仅在宽度上增加了一个常数因子，并在深度上仅增加了较小的加性增量。逼近误差界保持在 $O(N^{-\beta/d} + N^{-m})$ 的阶数，其中 $N$ 是与网络规模和样本复杂度相关的参数。

2. 非参数回归（定理 3.1）：
   作者将逼近结果应用于从带有噪声观测值 $Y_i = f_0(X_i) + \epsilon_i$ 中恢复未知回归函数 $f_0$ 的问题。他们定义了一个由具有权重 $\{0, \pm 1\}$ 的深层稀疏三值 ReLU 网络组成的假设空间 $\mathcal{F}_n$。

   主要结果确立了 $\mathcal{F}_n$ 上经验风险最小化器 $\hat{f}_n$ 的预测误差（均方误差）满足：
   $$R(\hat{f}_n, f_0) \leq C n^{-\frac{2\beta}{2\beta+d}} \log^2 n$$
   其中 $n$ 是样本量，$\beta$ 是平滑参数，$d$ 是维度。

意义与主张
本文声称，具有权重 $\{0, \pm 1\}$ 的深层稀疏三值 ReLU 网络在理论上足以实现 $\beta$-光滑回归函数的极小极大预测速率（minimax rate of prediction），仅差一个对数因子。这表明，只要适当调整网络的深度和稀疏度，将权重极端量化为二值或三值集合并不会从根本上降低模型在非参数回归任务中的统计效率。

作者强调，其工作扩展了先前关于权重为 $\{0, \pm 1/2, \pm 1, 2\}$ 网络（见参考文献 [3]）的发现，证明了这些逼近可以通过严格的二值和三值权重来实现。这些结果为使用二值和三值网络进行高精度回归任务提供了理论依据，表明此类网络的计算和内存优势可以在不牺牲最优收敛速率的情况下得以实现。