📊 statistics

A Function-Space Dichotomy for Compositional Learning: Exponential Sub-Optimality of the Neural Tangent Kernel

本文建立了一个函数空间二分法，证明了在组合任务上，神经切线核相对于有限宽神经网络存在指数级的次优性，这一差距是由核函数的平滑偏好与目标函数的架构复杂度之间的不匹配所驱动，而非通用的核与网络之间的局限性。

原作者： Arkaprabha Ganguli, Emil Constantinescu

发布于 2026-07-08

📖 1 分钟阅读☕ 轻松阅读

原作者： Arkaprabha Ganguli, Emil Constantinescu

原始论文采用 CC BY 4.0 许可（http://creativecommons.org/licenses/by/4.0/）。 ✨ 这是对下方论文的AI生成解释。它不是由作者撰写或认可的。如需技术准确性，请参阅原始论文。阅读完整免责声明

大局观：为什么“懒惰型”学习无法构建复杂事物

想象一下，你正试图教一台计算机识别模式。长期以来，研究人员一直使用一种叫做**神经切线核（Neural Tangent Kernel, NTK）**的工具来预测神经网络的学习效果。你可以把 NTK 想象成一位“懒惰”的老师。这位老师非常擅长平滑掉粗糙的边缘并学习平缓的曲线，但他们拒绝改变主意或学习新技巧。他们只是坚持一种非常僵化、预设好的观察世界的方式。

这篇论文提出了一个简单的问题：这种“懒惰”的老师在什么时候会失败，以及为什么会失败？

作者发现，当任务涉及**组合（Composition）**时——即通过将简单的层堆叠在一起来构建复杂的事物（就像俄罗斯套娃，或者一个包含许多步骤的食谱）——这位“懒惰”的老师会表现得极其糟糕。在这种情况下，一位“丰富”的老师（即一个真正学习并改变其权重的标准神经网络）比懒惰的老师要优秀得多，且效率呈指数级提升。

衡量难度的两种方式

为了解释这一点，作者通过两个不同的视角来观察目标函数（即你想要计算机学习的模式）：

“平滑度”视角（傅里叶复杂度）：
想象目标是一个音符。如果这个音符是一个低沉、平滑的嗡鸣声，它很容易描述。如果它是一个超快、锯齿状的尖叫声，每秒钟振动数千次，那么它在平滑度方面就是“复杂”的。
- NTK 的视角： 懒惰的老师讨厌锯齿状、高频振动的声音。为了学习高频的尖叫声，NTK 需要海量的数据（样本）才能搞定它。它把每一次细微的波动都视为巨大的障碍。
“架构”视角（架构复杂度）：
现在，假设你想制造一台能发出这种尖叫声的机器。
- 神经网络的视角： 标准的神经网络就像一位大师级的建筑师。即使声音听起来是疯狂、快速的尖叫，建筑师也可以通过将几个简单的齿轮（层）堆叠在一起来创造它。即使结果看起来很混乱，其“构建成本”也是很低的。

冲突点： 论文表明，对于某些任务，其“平滑度”成本是天文数字，但其“架构”成本却微乎其微。懒惰的老师（NTK）看到了天文数字般的成本并选择了放弃，而聪明的建筑师（神经网络）看到了微小的成本并轻松完成了构建。

明星案例：“锯齿波”（Sawtooth Wave）

作者使用了一个特定的形状——锯齿波来证明他们的观点。想象一个上下波动的三角形波：

深度 1： 一个三角形。简单。
深度 2： 一个大三角形内嵌套了两个小三角形。
深度 10： 一个前后往复摆动数千次的波浪。

关键在于：

对于神经网络： 你可以通过堆叠仅仅 10 个简单的层来构建这个疯狂的锯齿波。这是一种廉价且高效的构造方式。
对于 NTK： 对懒惰的老师来说，这个波浪看起来频率高达 $2^{10}$ （超过 1,000）。因为 NTK 偏好平滑性，它认为这极其困难。

结果：
论文证明了，为了学习这个 10 层的锯齿波：

神经网络只需要适量的样本（多项式级增长）。
NTK 则需要一个呈指数级增长的样本量（例如 $4^{10}$ ）。
用通俗的话说： 当深度达到 12 层时，为了获得同样的结果，懒惰的老师所需的样本量将比聪明的建筑师多出 1000 万倍。

“懒惰”与“丰富”机制

论文区分了神经网络学习的两种方式：

懒惰机制（NTK）： 网络非常宽，且训练过程非常温和，以至于其内部设置几乎不动。它表现得像一个固定的数学公式（一个核函数）。它擅长处理平滑、简单的东西，但处理复杂的层级结构时表现极差。
丰富机制（标准训练）： 网络会真正改变其内部权重。它学习的是“特征”。这使得它能够高效地构建复杂的结构，即使这些结构看起来很杂乱。

实验展示了什么

作者不仅做了数学推导，还通过实验证实了他们的理论：

平滑目标： 当他们给计算机一个平滑、简单的波形（如温和的正弦波）时，懒惰的老师（NTK）和聪明的建筑师的表现几乎完全一样。在这种情况下，NTK 表现良好。
复杂目标（奇偶校验/Parity）： 他们测试了一个“稀疏奇偶校验”问题（一个涉及将特定数字相乘的逻辑谜题）。
- NTK 始终卡在底层，无论给予多少数据，它都只能进行随机猜测。
- 神经网络则迅速学会了模式，其表现领先 NTK 10,000 到 1,000,000 倍。

核心结论

论文得出结论：神经网络与核方法之间的差距不仅仅是“核函数 vs 网络”的区别，更是工具不匹配的问题。

如果你的问题是平滑且简单的，那么“懒惰”的核函数是一个高效且优秀的工具。
如果你的问题是由层层组合构建的（如深层层级结构或复杂的逻辑），那么“懒惰”的工具就是错误的工具。它在原本只是简单阶梯的地方，看到了难以逾越的高山。

标题中提到的“指数级次优性”（exponential sub-optimality）意味着，对于这类特定的复杂层级问题，使用懒惰的核函数方法不仅是略逊一筹，而是相对于让网络进行实际学习而言，其效率低下的程度是灾难性的。

技术摘要：组合学习中的函数空间二分性

问题陈述
深度学习中一个持久的经验观察是，在具有组合或层次结构的任务上，经过训练的神经网络始终优于其神经切线核（NTK）极限。虽然现有文献将核与网络之间的差距主要归因于维度灾难（即核在处理高维输入的低维投影时表现不佳），但对于在固定输入维度下——特别是受深度和组合结构驱动的——这种差距的定量解释仍然缺失。本文旨在探讨以下问题：对于哪些目标函数，以及在多大程度上，NTK 是次优的？又是什么特定的属性阻碍了核函数对这些目标的利用？

方法论与设置
作者在单位圆 $S^1$ 上分析了这一问题，在此处 NTK 具有清晰的傅里叶描述。他们为目标函数 $f^*$ 引入了两种复杂度度量之间的二分性：

傅里叶复杂度（Fourier Complexity）： 控制通过 NTK 进行学习的成本（懒惰机制）。研究表明，NTK 再生核希尔伯特空间（RKHS）范数与 Sobolev $H^1$ 范数（惩罚高频振荡）在常数倍关系下（取决于深度）是等价的。
架构复杂度（Architectural Complexity）： 控制通过权重衰减训练在“丰富”机制下的学习成本。这由深层变分范数（ $RBV^2_{deep}$ ）来衡量，该范数量化了构建目标函数所需的最小深度为 $L$ 、宽度为 $w$ 的 ReLU 网络的大小。

作者定义了架构类 $\mathcal{C}_{L,w,R}$ 为具有有界深层变分范数 $R$ 的深度为 $L$ 、宽度为 $w$ 的 ReLU 网络。他们对比了 NTK 估计器（核岭回归）与针对该架构类的极小极大下界（minimax lower bound）的样本复杂度。

核心贡献

深层架构类的极小极大特征化：
本文确定了类 $\mathcal{C}_{L,w,R}$ 的极小极大 $L^2$ 速率。该速率被锁定在 $\Omega(Lw^2R^2/n)$ 与 $\tilde{O}(L^2w^2R^2/n)$ 之间。这一结果在单个 $L$ 因子上是紧致的，代表了该类估计器的统计底线。值得注意的是，该速率由架构参数 $(L, w, R)$ 索引，而非目标函数的平滑指数。
指数级的 NTK 次优性：
作者证明，当目标的傅里叶复杂度与其架构复杂度发生解耦时，NTK 估计器会处于指数级高于极小极大底线的状态。具体而言，对于一个具有主导频率 $k^*$ 的目标，NTK 需要 $\Omega((k^*)^2)$ 个样本，而架构类仅需要其结构参数的多项式资源。
- 见证者（The Witness）： 深度为 $L$ 的迭代锯齿函数（Telgarsky 2016）作为解析见证者。它可以由一个宽度为 2、深度为 $L$ 、拥有 $O(L)$ 个权重的网络构建（低架构复杂度），但会产生 $2^{L-1}$ 次振荡（高傅里叶复杂度）。
- 差距： 对于锯齿函数，NTK 需要 $\Omega(4^L)$ 个样本，而极小极大底线仅为 $L$ 的多项式级别（介于 $L^3$ 和 $L^4$ 之间）。这产生了样本复杂度的指数级分离。
数值验证：
数值实验从三个方面证实了理论主张：
- NTK 光谱： 在 $S^1$ 上的 NTK 特征值衰减遵循预测的 $k^{-2}$ 衰减，证实了“深度等于浅层”的现象，即深度并不会改变谱衰减率。
- 平滑目标： 对于带限（bandlimited）的平滑目标，NTK 与宽网络相比具有竞争力甚至更优，不存在指数级差距。
- 组合目标： 在超立方体上的稀疏奇偶校验模型（另一个 SGD 已知能成功的领域）中，标准的两层网络在测试误差上比 NTK 高出四个到六个数量级，实现了预测的端到端分离。

结果与意义
本文得出结论，NTK 与训练网络之间的性能差距并非通用的“核与网络”现象，而是一种特定的函数空间属性。这种差距源于核函数固有的平滑偏差（偏好低频函数）与目标函数的组合结构（可以通过组合廉价地生成高频振荡）之间的不匹配。

理论洞察： 本研究提供了一个精确的机制来解释深度为何有效：它允许网络通过组合高效地表示高频振荡函数，而 NTK（其行为类似于固定的 Sobolev 核）缺乏这种能力。
极小极大底线： 深层变分空间的极小极大速率推导本身也是一项独立的贡献，它提供了基于架构参数的组合问题样本复杂度的直接、无需核函数的估计。
适用范围： 作者澄清，这种差距并非普遍存在的；对于傅里叶复杂度与架构复杂度一致的平滑带限目标，差距会消失。此外，他们区分了统计极限与算法可行性，指出虽然锯齿函数在统计上可以被该架构类学习，但对于梯度下降优化而言极其困难；而稀疏奇偶校验模型在统计和算法上都是可学习的。

总而言之，本文认为 NTK 对于 $H^1$ 平滑目标是近乎最优的，但对于那些通过组合结构实现“廉价”高频表示的目标，则是指数级次优的，而在这种情况下，进行“丰富机制”训练在统计上是必要的。