Learning Overparameterized Neural Networks via Stochastic Gradient Descent on Structured Data
Yuanzhi Li Computer Science Department Stanford University Stanford, CA 94305、Yingyu Liang Department of Computer Sciences University of Wisconsin-Madison Madison, WI 53706
Abstract
Neural networks have many successful applications, while much less theoretical understanding has been gained. Towards bridging this gap, we study the problem of learning a two-layer overparameterized ReLU neural network for multi-class classification via stochastic gradient descent (SGD) from random initialization. In the overparameterized setting, when the data comes from mixtures of well-separated distributions, we prove that SGD learns a network with a small generalization error, albeit the network has enough capacity to fit arbitrary labels. Furthermore, the analysis provides interesting insights into several aspects of learning neural networks and can be verified based on empirical studies on synthetic data and on the MNIST dataset.
中文速览
训练过参数化神经网络时，人们早就发现SGD不会过拟合，却一直说不清楚为什么——现有理论要么假设数据是高斯分布或线性可分，要么干脆解释不了优化算法的隐式正则化效果。这项工作针对一个更贴近现实的数据假设——每个类别由若干"小团簇"组成、不同类别的团簇之间距离足够远——从理论上证明了：只要网络足够过参数化、从随机初始化出发跑SGD，最终学到的两层ReLU网络就能取得低泛化误差，哪怕这个网络本身有能力死记硬背任意随机标签。核心机制在于，过参数化让每个神经元在有限次迭代内几乎不改变激活模式，从而使SGD的梯度可以与一个"伪梯度"过程紧密耦合，而后者有良好的优化地形；数据的簇结构再进一步保证找到的解泛化良好。这一结论完全与数据维度无关、只依赖类别数、簇数和类间距离，不仅在理论上首次解释了过参数化与随机初始化如何共同催生SGD的归纳偏置，也在合成数据和MNIST上得到了实验验证。
原文 arXiv:1808.01204;中英对照 + 大白话阅读 https://aha.fim.ai/paper/1808.01204v3