Gradient Descent Finds Global Minima of Deep Neural Networks
Simon S. Du Jason D. Lee Haochuan Li Liwei Wang Xiyu Zhai
Abstract
Gradient descent finds a global minimum in training deep neural networks despite the objective function being non-convex. The current paper proves gradient descent achieves zero training loss in polynomial time for a deep over-parameterized neural network with residual connections (ResNet). Our analysis relies on the particular structure of the Gram matrix induced by the neural network architecture. This structure allows us to show the Gram matrix is stable throughout the training process and this stability implies the global optimality of the gradient descent algorithm. We further extend our analysis to deep residual convolutional neural networks and obtain a similar convergence result.
中文速览
深度神经网络在训练时明明面对非凸优化问题，梯度下降却总能找到全局最优解，这背后的原因一直没有严格的理论解释。这篇论文针对带残差连接的深度过参数化神经网络（ResNet），从理论上证明了随机初始化的梯度下降能在多项式时间内把训练损失降到零。核心思路是分析网络结构诱导出的Gram矩阵（格拉姆矩阵）：只要网络足够宽，训练过程中每层权重几乎不会偏离初始值，由此保证Gram矩阵的最小特征值始终为正，从而确保梯度下降以线性速率收敛到全局最优。关键发现是，ResNet所需的宽度仅需与样本量和层数呈多项式关系（$m=\Omega(\mathrm{poly}(n,H))$），而普通全连接深网络的宽度要求则随层数指数级增长，这从理论上首次量化地解释了残差连接为何能让"更深的网络更好训练"。
原文 arXiv:1811.03804;中英对照 + 大白话阅读 https://aha.fim.ai/paper/1811.03804v4