On the Convergence of Stochastic Gradient Descent with Adaptive Stepsizes

Stochastic gradient descent is the method of choice for large scale of machine learning objective functions. Yet, its performance is variable and heavily depends on the choice of the stepsizes. This has a large body of research on adaptive stepsizes. However, there is a gap in our theoretical understanding of these methods, especially the non-convex setting. In this paper, we start closing this gap: we analyze in the convex and non-convex settings a generalized of the AdaGrad stepsizes. We show sufficient conditions for these to achieve almost sure asymptotic convergence of the gradients to, proving the first guarantee for generalized AdaGrad stepsizes in the-convex setting. Moreover, we show that these stepsizes allow to adapt to the level of noise of the stochastic gradients in both convex and non-convex settings, interpolating between O (1/T) andO (1/), up to logarithmic terms.