This paper analyzes the trajectories of stochastic gradient descent (SGD) to help understand the algorithm's convergence properties in non-convex problems. We first show that the sequence of iterates generated by SGD remains bounded and converges with probability $1$ under a very broad range of step-size schedules. Subsequently, going beyond existing positive probability guarantees, we show that SGD avoids strict saddle points/manifolds with probability $1$ for the entire spectrum of step-size policies considered. Finally, we prove that the algorithm's rate of convergence to Hurwicz minimizers is $\mathcal{O}(1/n^{p})$ if the method is employed with a $\Theta(1/n^p)$ step-size schedule. This provides an important guideline for tuning the algorithm's step-size as it suggests that a cool-down phase with a vanishing step-size could lead to faster convergence; we demonstrate this heuristic using ResNet architectures on CIFAR.

本文针对随机梯度下降算法在非凸问题中的收敛性进行轨迹分析，首先证明了在广泛的步长策略范围内，SGD生成的迭代序列保持有界并以概率1收敛，随后证明了SGD避开了严格的鞍点/流形的概率是1，最后证明了算法在采用Theta(1/n^p)步长时收敛速度为O(1/n^p)，这为调整算法步长提供了重要的指导建议，并且在CIFAR的ResNet架构中，展示了此启发式方法加速收敛的效果。

随机梯度下降在非凸问题中的几乎必然收敛