What Can ResNet Learn Efficiently, Going Beyond Kernels?
Zeyuan Allen-Zhu Microsoft Research AI Yuanzhi Li Stanford University
Abstract
How can neural networks such as ResNet efficiently learn CIFAR-10 with test accuracy more than $96\%$ , while other methods, especially kernel methods, fall relatively behind? Can we more provide theoretical justifications for this gap?
中文速览
神经网络在图像识别等任务上远超核方法（kernel methods），但理论上一直缺乏对这种差距的严格解释。这篇论文在"无分布假设"的PAC学习框架下，从理论上证明了三层残差网络（ResNet）能够高效学习一类由"基础信号+复合信号"构成的目标函数，而这个学习过程通过随机梯度下降（SGD）就能实现。核心发现是：神经网络借助不同层级隐式地完成"分层学习"——第一层先学简单的基础特征，第二层再借助这些特征学习更复杂的组合结构，从而把所需训练样本数从核方法所需的指数级（如$d^{10}$）大幅降至多项式级（如$d$）。论文同时给出了严格的分离定理，证明在同等训练样本下神经网络的泛化误差可以远小于任意核方法（包括神经切核NTK），这是首次在无分布假设的设定中为神经网络相对于核方法的优势提供可证明、可高效实现的理论依据。
原文 arXiv:1905.10337;中英对照 + 大白话阅读 https://aha.fim.ai/paper/1905.10337v3