On the Rates of Convergence for Learning with Convolutional Neural Networks¶
作者: Yunfei Yang, Han Feng, Ding-Xuan Zhou
来源: SIAM Journal on Mathematics of Data Science
主题: 非参数 / 半参数
相关性: 5/10
机构绿灯: University of Hong Kong(US News 前 50,免分进入精读)
链接: https://doi.org/10.1137/24m1652945
一、领域脉络与小综述¶
-
这个方向是什么:本文属于"深度学习的统计学习理论"这一子方向,其根本问题是:当假设空间由深度神经网络(特别是卷积神经网络 CNN)构成时,经验风险最小化(ERM)估计量的泛化误差如何随样本量 n、网络深度 L、宽度 J 等参数衰减?该方向的核心张力在于逼近误差(approximation error,网络能多好地逼近目标函数)与估计误差(estimation error,有限样本下在假设空间内搜索的统计代价)之间的权衡。当前该方向的成熟度较高,已有大量关于全连接网络(FNN)的逼近与估计理论,但针对 CNN 结构特性的精细刻画(尤其是权重范数约束下的逼近与覆盖数)仍在发展中。
-
发展脉络(history):
- 奠基工作:Yarotsky (2017, [38]) 和 Yarotsky (2018, [39]) 建立了深度 ReLU 网络对光滑函数的逼近理论,证明了深度网络在逼近 Sobolev 类函数时能避免维度灾难(curse of dimensionality),其逼近误差为 O(L^{-α/d}) 量级。这是后续所有工作的基础。
- 统计学习理论框架:Schmidt-Hieber (2021, [25]) 将逼近理论与非参数回归的统计推断结合,证明了基于 FNN 的最小二乘估计量在 Sobolev 光滑类上能达到 minimax 最优速率 n^{-2α/(2α+d)}(忽略对数因子)。这是"深度网络能同时逼近且可估计"的标志性工作。Kohler & Langer (2021, [15]) 进一步简化并推广了这些结果。
- CNN 的逼近理论:Zhou (2020, [42]) 证明了 CNN 的普适逼近性(universality),并给出了下采样(downsampling)CNN 的逼近界。Fang et al. (2020, [7]) 和 Lin et al. (2020, [22]) 等进一步研究了 CNN 对特殊函数类(如径向函数、谱类函数)的逼近优势。这些工作确立了 CNN 在逼近意义上不弱于 FNN,但尚未给出精细的统计学习速率。
- CNN 的统计学习理论(本文的直接前作):Zhou & Huo (2024, [44]) 研究了插值型深度 CNN 的学习能力,但速率不优。Liu et al. (2022, [19]) 和 Feng et al. (2023, [8]) 分别对残差 CNN 和球面 CNN 建立了学习速率,但均未达到 minimax 最优,且对权重约束的刻画不够精细。本文的定位:作者在引言中明确指出,"in contrast with the minimax optimal learning rates for fully connected neural networks [25, 15, 13], many of these results for CNNs are not optimal",即填补"CNN 学习速率非最优"这一缺口。
-
子线索聚类:
- 线索 A:逼近理论(Approximation theory):Yarotsky [38, 39], Zhou [42], Fang et al. [7], Mao et al. [22], Yang & Zhou [37]。这一簇关注"网络能以多快的速度逼近目标函数",通常以深度 L 或参数个数 N 为变量,给出 L∞ 或 L2 误差界。本文的 Theorem 2.1 属于此线索,但关键贡献在于显式控制了权重范数约束 κ(θ) ≤ M,这是后续覆盖数估计的前提。
- 线索 B:统计学习速率(Statistical rates):Schmidt-Hieber [25], Kohler & Langer [15], Kim et al. [13], Bos & Schmidt-Hieber [5], Zhou & Huo [44], Liu et al. [19], Feng et al. [8]。这一簇关注"ERM 估计量的泛化误差",通常结合逼近界与复杂度界(覆盖数、Rademacher 复杂度)得到最终速率。本文的 Theorem 3.1、4.1、4.2 属于此线索,核心贡献是给出了 CNN 的覆盖数新界(Theorem 2.7),从而导出 minimax 最优速率。
- 线索 C:分类与 margin 条件:Audibert & Tsybakov (2007, [1])、Tsybakov (2004, [34])、Steinwart & Scovel (2012, [6])。这一簇研究在 Tsybakov 噪声条件下的分类问题,给出了比 O(n^{-1/2}) 更快的速率。本文的 Theorem 4.1 和 4.2 将 CNN 的学习速率与这些已知的 minimax 下界进行匹配。
-
这个方向在追问的核心问题:
- 逼近与估计的权衡:给定深度 L 和宽度 J,如何选择网络规模以平衡逼近误差(随 L 增大而减小)与估计误差(随 L 增大而增大)?最优速率是多少?
- 权重约束的作用:对权重范数施加约束(如 κ(θ) ≤ M)如何影响逼近速率和覆盖数?约束是"免费午餐"还是以逼近精度为代价?
- CNN 结构是否带来统计优势:卷积的权值共享(weight sharing)和局部连接(local connectivity)是否能在统计意义上(而非仅逼近意义)带来比 FNN 更优的速率?目前已知的答案是:在光滑函数类上,CNN 与 FNN 的 minimax 速率相同,但 CNN 的常数可能更小(本文未讨论常数)。
- 损失函数的影响:对于分类问题,不同的损失函数(hinge、logistic)在 Tsybakov 噪声条件下如何影响速率?已知瓶颈是 logistic 损失的速率依赖于 margin 条件,且可能达不到分类误差的 minimax 最优。
-
⚠️ 作者的 framing(这是作者的说法):作者将缺口 frame 为"CNN 的学习速率在光滑函数类上尚未达到 minimax 最优",并将原因归结为两点:(1) 现有逼近结果(如 [24, 19])依赖残差结构或对权重无显式约束,导致覆盖数估计过松;(2) 现有覆盖数分析(如 [8])对权重规模的依赖不精细,得到 O(L² log(L/ε)) 而非 O(L log(LM/ε))。作者通过"显式构造 CNN 实现浅层网络 + 精细覆盖数分析"两步,将速率提升至 minimax 最优。被淡化的竞争路线:作者回避了"CNN 在低维流形或特殊结构数据上可能超越 FNN minimax 速率"这一方向(如 [19, 26] 处理的低维流形情形),而专注于标准光滑函数类。值得研究者去查的问题:为什么作者将光滑度限制在 α < (d+3)/2?这个条件在 [37] 的逼近理论中是否是本质的?如果 α 更大,是否可以通过更深的网络或不同的构造突破?另外,作者没有讨论计算复杂度——ERM 在 CNN 上是否可高效求解?这在实际中可能比统计速率更关键。
-
张力:未见明显对立引用。但存在一个微妙的张力:逼近理论中的"最优"与统计学习中的"最优"可能不一致。例如,[26] 声称 CNN 在 Sobolev 空间上可达到 O(L^{-2α/d}) 的"超收敛"速率(通过下采样),而本文的 Theorem 2.1 在相同条件下只给出 O(L^{-α/d})。作者在 Remark 2.4 中承认了这一点,但指出 [26] 的构造需要下采样层,且其权重范数约束可能过大(M 随 L 指数增长),从而在统计学习中无法利用该超收敛性。这是一个值得深挖的张力点:是否存在一种 CNN 结构,既能实现超收敛逼近,又能保持权重范数多项式增长?
二、最核心、最简单的例子 / 数学问题¶
第一步:符号、模型、可观测数据¶
- 输入空间:\( x \in [0,1]^d \),d 为输入维度(固定整数,d ≥ 2)。
- 输出:回归问题中 \( Y \in \mathbb{R} \);分类问题中 \( Y \in \{-1, +1\} \)。
- 数据:\( D_n = \{(X_i, Y_i)\}_{i=1}^n \),i.i.d. 来自联合分布 \( P_{X,Y} \)。边际分布 \( \mu = P_X \) 支撑在 \( [0,1]^d \) 上。
- 目标函数(estimand):
- 回归:\( h(x) = \mathbb{E}[Y | X = x] \),假设 \( h \in H^\alpha(R) \),即 Hölder 光滑类,光滑度 α > 0,半径 R > 0。
- 分类:\( \eta(x) = P(Y = 1 | X = x) \),假设 \( \eta \in H^\alpha(R) \),且满足 Tsybakov 噪声条件(见下文)。
- 假设空间:\( \mathcal{F}_n = \text{CNN}(s, J, L_n, M_n) \),即深度为 \( L_n \)、通道数为 J、滤波器大小为 s、权重约束 \( \kappa(\theta) \le M_n \) 的 CNN 函数类。注意:这里的"深度" \( L_n \) 是网络的层数(不含输入层),每层有 J 个通道,每个通道是一个 d 维向量(即特征图宽度保持为 d,通过 one-sided zero-padding 实现)。
- 权重约束:\( \kappa(\theta) := \|w^{(L)}\|_1 \prod_{\ell=0}^{L-1} (\|(w^{(\ell)}, b^{(\ell)})\| + 1) \),其中 \( \|(w, b)\| = \max_{j'} (\|w_{:,j',:}\|_1 + |b_{j'}|) \)。这个约束是本文的关键技术点,它度量了网络权重的"总规模",并直接控制网络的 Lipschitz 常数。
- 估计量:经验风险最小化(ERM):
- 回归:\( \hat{f}_n = \arg\min_{f \in \mathcal{F}_n} \frac{1}{n} \sum_{i=1}^n (\hat{f}(X_i) - Y_i)^2 \),并截断 \( \hat{f}_n \) 到 \( [-B_n, B_n] \)(\( B_n = c_1 \log n \))。
- 分类:\( \hat{f}_{\phi,n} = \arg\min_{f \in \mathcal{F}_n} \frac{1}{n} \sum_{i=1}^n \phi(Y_i f(X_i)) \),其中 \( \phi \) 是 hinge 或 logistic 损失。
- 性能度量:
- 回归:\( L^2(\mu) \) 范数 \( \|\hat{f}_n - h\|_{L^2(\mu)}^2 \)。
- 分类:分类误差 \( R(f) = P(\text{sign}(f(X)) \neq Y) \) 与贝叶斯误差 \( R^* \) 之差;以及 excess \(\phi\)-risk \( R_\phi(f) = L_\phi(f) - L_\phi(f^*_\phi) \)。
- 关键假设:
- Hölder 光滑:\( h \in H^\alpha(R) \),即 \( h \) 的直到 \( \lfloor \alpha \rfloor \) 阶导数有界,且 \( \lfloor \alpha \rfloor \) 阶导数是 Hölder 连续的(指数 \( \alpha - \lfloor \alpha \rfloor \))。
- Tsybakov 噪声条件(分类):存在 \( q \in [0, \infty] \), \( c_q > 0 \),使得 \( P_X(|2\eta(X) - 1| \le t) \le c_q t^q \)。q 越大,说明类别越可分。
- SVB 条件(logistic 损失):存在 \( \gamma \in [0,1] \), \( C_\gamma > 0 \),使得 \( P_X(\eta(X) \le t) \le C_\gamma t^\gamma \) 且 \( P_X(1 - \eta(X) \le t) \le C_\gamma t^\gamma \)。这控制 \( \eta \) 在 0 和 1 附近的退化行为。
- 矩条件(回归):\( \mathbb{E}[Y^2] < \infty \),且 \( \mathbb{E}[Y^2 | X] \le M_Y^2 \) 几乎处处成立。
第二步:最小内核¶
核心命题(最小内核):考虑最简单的非参数回归问题:\( d=1 \),\( h \in H^\alpha(R) \)(即 \( h \) 是 \( [0,1] \) 上 Hölder 光滑函数),使用深度为 L、宽度为 J 的 CNN 做 ERM。本文的核心结果是:
这个结果为什么成立? 它由两个关键引理支撑:
-
逼近引理(Theorem 2.1 的特例):存在一个 CNN \( f \in \text{CNN}(s, J, L, M) \),使得
\[\|f - h\|_{L^\infty([0,1])} \lesssim L^{-\alpha}\]且权重约束 \( M \lesssim L^{3} \)。关键点:逼近误差只依赖于深度 L,且权重约束是 L 的多项式(而非指数)。这个构造的核心思想是:CNN 可以通过"分而治之"的策略,用深度 L 模拟一个具有 \( O(L) \) 个节点的浅层网络,而浅层网络对 Hölder 函数的逼近误差为 \( O(L^{-\alpha}) \)。技术难点:CNN 的卷积结构限制了每一层只能做局部线性变换,如何用这种受限结构实现全局的"分段多项式逼近"?作者的技巧是:利用 one-sided zero-padding 和多个通道,将"信息传递"和"非线性激活"分离,通过深度堆叠实现"感受野"的指数增长。 -
覆盖数引理(Theorem 2.7 的特例):对于 \( \epsilon > 0 \),CNN 函数类的 \( \epsilon \)-覆盖数满足
\[\log N(\epsilon, \text{CNN}(s, J, L, M), \|\cdot\|_{L^\infty}) \lesssim L \log \left( \frac{L M}{\epsilon} \right)\]关键点:覆盖数的对数(即度量熵)是 \( O(L \log(LM/\epsilon)) \),而不是 \( O(L^2 \log(L/\epsilon)) \)。技术难点:如何利用权重约束 \( \kappa(\theta) \le M \) 来压缩假设空间的复杂度?作者的技巧是:将网络输出视为输入的 Lipschitz 函数,利用权重约束控制 Lipschitz 常数,然后对参数空间进行离散化。为什么这个界比现有文献好? 现有文献(如 [8])通常假设每个权重独立有界,得到 \( O(L^2) \) 的熵界;而本文利用乘积结构的权重约束,将熵界降至 \( O(L) \)。
这两个引理如何结合? 将 ERM 的误差分解为逼近误差和估计误差:
这个最小内核揭示了本文的本质贡献:CNN 的统计学习速率完全由两个量决定——逼近误差(由深度 L 控制)和度量熵(由权重约束 M 控制)。本文的贡献在于同时优化了这两个量,使得 CNN 在光滑函数类上达到 minimax 最优。这个"最小内核"可以直接推广到分类问题(用 Tsybakov 噪声条件替代光滑性假设)和高维情形(d > 1),但核心逻辑不变。
三、这篇论文做了什么¶
三句话¶
- 研究了什么问题:本文研究了带 one-sided zero-padding 和多通道的 CNN 在非参数回归和二分类中的收敛速率,目标是证明 CNN 估计量在 Hölder 光滑函数类上达到 minimax 最优速率。
- 核心工具/方法:本文的核心工具是 (i) 一个新的逼近定理,显式构造 CNN 实现浅层网络,并控制权重范数约束 \( \kappa(\theta) \le M \);(ii) 一个新的覆盖数估计框架,利用权重约束得到 \( O(L \log(LM/\epsilon)) \) 的度量熵界。
- 主要结论:对于回归问题,CNN 最小二乘估计量达到 minimax 最优速率 \( n^{-2\alpha/(2\alpha+d)} \)(忽略对数因子);对于分类问题,hinge 损失在 Tsybakov 噪声条件下达到 minimax 最优速率 \( n^{-(q+1)\alpha/((q+2)\alpha+d)} \),logistic 损失在 SVB 条件下达到 \( n^{-(1+\gamma)\alpha/((1+\gamma)\alpha+d)} \)。
关键设定与假设¶
- CNN 架构:深度为 L,通道数为 J(每层固定),滤波器大小为 s(s ∈ [2, d]),使用 one-sided zero-padding 保持特征图宽度为 d。与已有文献的区别:本文不使用残差连接(residual connection),而是直接堆叠卷积层。这使得架构更简单,但逼近构造更难。
- 权重约束:\( \kappa(\theta) \le M \),其中 \( \kappa(\theta) \) 是乘积形式的范数(见上文)。相比已有文献:现有工作(如 [24, 19])通常假设权重逐元素有界(\( |w_{i,j,k}| \le B \)),这会导致覆盖数估计中出现 \( L^2 \) 因子;本文的乘积范数约束更精细,得到 \( O(L) \) 的熵界。
- 光滑性假设:\( h \in H^\alpha(R) \),且 \( \alpha < (d+3)/2 \)。相比已有文献:这个限制来自逼近定理(Theorem 2.1),其证明依赖于 [37] 的浅层网络逼近结果。对于 \( \alpha \ge (d+3)/2 \),作者在 Remark 2.4 中讨论了可能的扩展,但未给出完整证明。
- Tsybakov 噪声条件:\( P_X(|2\eta(X) - 1| \le t) \le c_q t^q \)。相比已有文献:这是分类问题的标准假设,用于控制贝叶斯误差附近的难度。
- SVB 条件:\( P_X(\eta(X) \le t) \le C_\gamma t^\gamma \)。相比已有文献:这是 [5] 提出的条件,用于 logistic 损失的分析。它比 Tsybakov 条件更强,因为它要求 \( \eta \) 在 0 和 1 附近不退化。
主要结果¶
定理 3.1(回归):设 \( h \in H^\alpha(R) \),\( 0 < \alpha < (d+3)/2 \),\( \hat{f}_n \) 是 CNN 最小二乘估计量,则
定理 4.1(hinge 损失):设 \( \eta \in H^\alpha(R) \),Tsybakov 噪声条件成立,则
定理 4.2(logistic 损失):设 \( \eta \in H^\alpha(R) \),SVB 条件成立,则
证明路线与技术技巧¶
整体路线(以定理 3.1 为例):
- 误差分解:将 ERM 的 L2 误差分解为逼近误差和估计误差(标准技巧,见 [25])。
- 逼近误差:利用定理 2.1,构造 CNN 逼近 \( h \),误差为 \( O(L^{-\alpha/d}) \)。
- 估计误差:利用定理 2.7 的覆盖数界,结合局部 Rademacher 复杂度(local Rademacher complexity)或熵积分(entropy integral)得到估计误差 \( O(L \log n / n) \)。
- 平衡:选择 \( L \asymp (n/\log^3 n)^{d/(2\alpha+d)} \),得到最优速率。
关键跳跃点:
- 定理 2.1 的证明:这是全文最核心的技术难点。作者没有直接构造 CNN 逼近 \( h \),而是先利用 [37] 的浅层网络逼近结果,得到一个具有 \( N \) 个节点的浅层网络 \( g \) 逼近 \( h \),误差为 \( O(N^{-\alpha/d}) \)。然后,关键步骤是用 CNN 实现这个浅层网络。作者的构造分为两步:
- 用 CNN 实现"分段常数函数":通过 one-sided zero-padding 和 ReLU 激活,CNN 可以计算输入的分段线性函数。
-
用 CNN 实现"求和":通过多通道设计,CNN 可以将多个分段线性函数相加。 最终,作者证明了存在 CNN 精确实现浅层网络 \( g \),且权重范数 \( \kappa(\theta) \le M \) 满足 \( M \lesssim L^{(3d+3-2\alpha)/(2d)} \)。难点:CNN 的卷积操作是局部的,如何用局部操作实现全局的求和?作者的技巧是:利用 zero-padding 将信息"传递"到相邻位置,通过深度堆叠实现"信息汇聚"。
-
定理 2.7 的证明:作者没有直接估计 CNN 的覆盖数,而是先证明 CNN 函数类可以嵌入到一个"浅层网络函数类"中,然后利用 [37] 的覆盖数结果。具体来说,作者证明了每个 CNN 都可以表示为一个具有 \( O(L) \) 个节点、权重范数 \( O(M) \) 的浅层网络。难点:CNN 的权重是共享的(卷积核在不同位置复用),如何将这种共享结构"展开"成浅层网络?作者的技巧是:利用 one-sided zero-padding 的性质,将卷积操作分解为多个独立的线性变换,然后组合成浅层网络。
技术技巧点名:
- 乘积范数约束:\( \kappa(\theta) \) 的定义是本文的核心创新之一。它比逐元素范数约束更精细,使得覆盖数界从 \( O(L^2) \) 降至 \( O(L) \)。这个技巧可以类比于高维统计中的"稀疏性"约束——通过约束"有效参数"而非"总参数"来降低复杂度。
- 局部 Rademacher 复杂度:用于估计误差的界。作者没有使用全局 Rademacher 复杂度(会得到次优速率),而是利用覆盖数界和方差-复杂度权衡(variance-complexity trade-off)得到最优速率。
- 截断算子:在回归问题中,作者使用截断算子 \( \mathcal{T}_{B_n} \) 将估计量限制在 \( [-B_n, B_n] \),以控制估计量的范数。这是处理重尾响应的标准技巧。
- 校准不等式:在分类问题中,作者使用 (4.4) 和 (4.9) 将 excess classification risk 转化为 excess \(\phi\)-risk,从而利用 ERM 的分析框架。
🔎 结论是否比证明窄¶
- 定理 2.1 的逼近界:作者在 Remark 2.4 中承认,对于 \( \alpha \ge (d+3)/2 \),可以通过 [37] 的另一个结果得到 \( O(L^{-2\alpha/d}) \) 的逼近界,但没有给出完整的证明。这是一个明确的"结论比证明窄"的地方。
- 定理 4.2 的 logistic 损失:作者在定理 4.2 中假设 SVB 条件 (4.10) 成立,但没有讨论 SVB 条件与 Tsybakov 噪声条件的关系。在 Remark 4.3 中,作者提到 SVB 条件比 Tsybakov 条件更强,但未给出具体例子说明两者的差距。
- 高维情形:作者在引言中提到"我们的方法可以推广到高维输入",但没有给出高维情形的具体结果。在高维情形下,CNN 的逼近和估计速率可能依赖于输入维度 d 与光滑度 α 的关系,这是一个未解决的问题。
- 计算可行性:作者没有讨论 ERM 在 CNN 上的计算复杂度。在实际中,CNN 的 ERM 通常通过随机梯度下降(SGD)求解,但本文的理论分析假设 ERM 可以精确求解。这是一个理论分析与实际算法之间的 gap。
四、开放问题¶
-
高光滑度情形(\( \alpha \ge (d+3)/2 \)):作者在 Remark 2.4 中提出,对于高光滑度函数,CNN 可能达到 \( O(L^{-2\alpha/d}) \) 的逼近界,但未给出完整证明。要证什么:构造 CNN 逼近 \( H^\alpha \) 函数,且权重范数 \( \kappa(\theta) \le M \) 保持多项式增长,逼近误差为 \( O(L^{-2\alpha/d}) \)。扎根于:Remark 2.4 和 [37] 的讨论。
-
低维流形上的 CNN 学习:作者在引言中提到 [19, 26] 处理了低维流形上的 CNN 学习,但本文未涉及。要证什么:当输入数据分布在一个 d' 维流形上(d' < d)时,CNN 的 minimax 速率是否变为 \( n^{-2\alpha/(2\alpha+d')} \)?扎根于:引言中对 [19, 26] 的讨论。
-
SVB 条件与 Tsybakov 条件的关系:作者在定理 4.2 中假设 SVB 条件,但未讨论它与 Tsybakov 条件的关系。要算什么:是否存在一个函数 \( \eta \in H^\alpha \) 满足 Tsybakov 条件但不满足 SVB 条件?如果存在,logistic 损失的速率是否会变差?扎根于:定理 4.2 的假设和 Remark 4.3。
-
CNN 的计算复杂度:作者没有讨论 ERM 在 CNN 上的计算可行性。要研究什么:SGD 能否在多项式时间内找到接近 ERM 最优解的 CNN 参数?这与统计-计算权衡(statistical-computational tradeoff)有关。扎根于:引言中对"深度学习的成功"的讨论,以及全文对 ERM 的假设。
-
自适应速率(Adaptive rates):作者假设光滑度 α 已知,但在实际中 α 未知。要研究什么:是否存在自适应于 α 的 CNN 估计器,其速率在未知 α 时仍能达到 minimax 最优?扎根于:定理 3.1 中对 α 的依赖。
给研究者的提醒:要确认上述开放问题是否是真 gap,建议去读以下近期论文的引言部分(约 5 篇):(1) 关于 CNN 逼近理论的最新进展(如 [26] 的后续工作);(2) 关于深度网络自适应估计的文献(如 Suzuki 等人的工作);(3) 关于深度网络统计-计算权衡的文献(如 Abbe 等人的工作)。如果这些论文的引言都指向同一个问题,那大概率是共识性 gap;如果互相打架,那可能是机会。
Maintained by 陈星宇 · Homepage · Source on GitHub