Overparameterized Nonlinear Learning: Gradient Descent Takes the Shortest Path?
Overparameterized Nonlinear Learning: Gradient Descent Takes the Shortest Path?
复制标题
DOI：
--
复制
发表时间：
2018-12
期刊：
影响因子：
--
通讯作者：
Samet Oymak;M. Soltanolkotabi
中科院分区：
文献类型：
--
作者：
Samet Oymak;M. Soltanolkotabi
许多现代学习任务涉及将非线性模型拟合到在过参数化机制中训练的数据，其中模型的参数超过训练数据集的大小。由于这种过度参数化，训练损失可能有无穷多个全局最小值，理解一阶优化方案（如从不同初始化开始的（随机）梯度下降）找到的解的性质至关重要。在本文中，我们证明了当损失在初始点的极小邻域上具有某些性质时，一阶方法，如（随机）梯度下降有一些有趣的特性：（1）即使损失是非凸的，迭代也以几何速率收敛到全局最优，（2）在损失的所有全局最优解中，迭代收敛到一个离初始点最近的全局最优解;（3）迭代从初始点到全局最优解的路径是一条近直接的路径。作为我们的证明技术的一部分，我们引入了一个新的势函数，它可以在迭代过程中捕获损失函数和到初始点的距离之间的精确权衡。对于随机梯度下降（SGD），我们开发了新颖的鞅技术，可以保证SGD永远不会离开初始化的小邻域，即使学习率相当大。我们证明了我们的一般理论的效用，各种问题域跨越低秩矩阵恢复神经网络训练。我们的分析是新的见解，可能对更复杂的学习问题（包括涉及深度神经网络架构的问题）的训练和泛化产生影响。
Many modern learning tasks involve fitting nonlinear models to data which are trained in an overparameterized regime where the parameters of the model exceed the size of the training dataset. Due to this overparameterization, the training loss may have infinitely many global minima and it is critical to understand the properties of the solutions found by first-order optimization schemes such as (stochastic) gradient descent starting from different initializations. In this paper we demonstrate that when the loss has certain properties over a minimally small neighborhood of the initial point, first order methods such as (stochastic) gradient descent have a few intriguing properties: (1) the iterates converge at a geometric rate to a global optima even when the loss is nonconvex, (2) among all global optima of the loss the iterates converge to one with a near minimal distance to the initial point, (3) the iterates take a near direct route from the initial point to this global optima. As part of our proof technique, we introduce a new potential function which captures the precise tradeoff between the loss function and the distance to the initial point as the iterations progress. For Stochastic Gradient Descent (SGD), we develop novel martingale techniques that guarantee SGD never leaves a small neighborhood of the initialization, even with rather large learning rates. We demonstrate the utility of our general theory for a variety of problem domains spanning low-rank matrix recovery to neural network training. Underlying our analysis are novel insights that may have implications for training and generalization of more sophisticated learning problems including those involving deep neural network architectures.