We consider non-convex stochastic optimization using first-order algorithms for which the gradient estimates may have heavy tails. We show that a combination of gradient clipping, momentum, and normalized gradient descent yields convergence to critical points in high-probability with best-known rates for smooth losses when the gradients only have bounded $\mathfrak{p}$th moments for some $\mathfrak{p}\in(1,2]$. We then consider the case of second-order smooth losses, which to our knowledge have not been studied in this setting, and again obtain high-probability bounds for any $\mathfrak{p}$. Moreover, our results hold for arbitrary smooth norms, in contrast to the typical SGD analysis which requires a Hilbert space norm. Further, we show that after a suitable "burn-in" period, the objective value will monotonically decrease for every iteration until a critical point is identified, which provides intuition behind the popular practice of learning rate "warm-up" and also yields a last-iterate guarantee.

本研究讨论了使用第一阶梯度算法进行的非凸随机优化问题，其中梯度估计可能具有重尾特征，结果表明梯度剪裁，动量和归一化梯度下降的组合可以在高概率下收敛于关键点，特别适用于光滑损失的已知最佳速率，适用于任意光滑度规范，并针对克服该领域二阶光滑损失引发的问题进行讨论。

非凸随机优化中重尾的高概率界限