揭示SGD在非凸损失函数中收敛到全局最小值的精确时间
The global convergence time of stochastic gradient descent in non-convex landscapes: Sharp estimates via large deviations
- 基于随机扰动系统与大偏差理论，建立收敛时间上下界
- 收敛时间由最棘手的障碍集决定，反映损失曲面全局结构
- 适用于深度神经网络训练分析，尤其对浅局部极小值有效
本文研究随机梯度下降（SGD）在一般非凸损失函数下到达全局最小值所需的时间。通过随机扰动动力系统与大偏差理论的视角，我们给出了收敛时间的紧致刻画，即上下界匹配。这些界限由算法从给定初始化出发可能需克服的最“昂贵”障碍集主导，从而将损失曲面的全局几何与过程噪声的统计特性相耦合。此外，针对深度神经网络训练的应用需求，我们还对具有浅局部极小值的损失函数进行了多组分析改进与扩展。
原文摘要 · Abstract (English)
In this paper, we examine the time it takes for stochastic gradient descent (SGD) to reach the global minimum of a general, non-convex loss function. We approach this question through the lens of randomly perturbed dynamical systems and large deviations theory, and we provide a tight characterization of the global convergence time of SGD via matching upper and lower bounds. These bounds are dominated by the most "costly" set of obstacles that the algorithm may need to overcome in order to reach a global minimizer from a given initialization, coupling in this way the global geometry of the underlying loss landscape with the statistics of the noise entering the process. Finally, motivated by applications to the training of deep neural networks, we also provide a series of refinements and extensions of our analysis for loss functions with shallow local minima.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。