A High Probability Analysis of Adaptive SGD with Momentum
This work addresses a foundational gap in optimization theory for machine learning practitioners, offering rigorous guarantees for widely used algorithms.
The paper tackles the incomplete theoretical understanding of adaptive SGD with momentum in nonconvex settings by providing a high probability analysis under weak assumptions, proving for the first time that gradients converge to zero in high probability for Delayed AdaGrad with momentum.
Stochastic Gradient Descent (SGD) and its variants are the most used algorithms in machine learning applications. In particular, SGD with adaptive learning rates and momentum is the industry standard to train deep networks. Despite the enormous success of these methods, our theoretical understanding of these variants in the nonconvex setting is not complete, with most of the results only proving convergence in expectation and with strong assumptions on the stochastic gradients. In this paper, we present a high probability analysis for adaptive and momentum algorithms, under weak assumptions on the function, stochastic gradients, and learning rates. We use it to prove for the first time the convergence of the gradients to zero in high probability in the smooth nonconvex setting for Delayed AdaGrad with momentum.