Optimal non-asymptotic bound of the Ruppert-Polyak averaging without strong convexity

Abstract

This paper is devoted to the non-asymptotic control of the mean-squared error for the Ruppert-Polyak stochastic averaged gradient descent introduced in the seminal contributions of [Rup88] and [PJ92]. In our main results, we establish non-asymptotic tight bounds (optimal with respect to the Cramer-Rao lower bound) in a very general framework that includes the uniformly strongly convex case as well as the one where the function f to be minimized satisfies a weaker Kurdyka-Lojiasewicz-type condition [Loj63, Kur98]. In particular, it makes it possible to recover some pathological examples such as on-line learning for logistic regression (see [Bac14]) and recursive quan- tile estimation (an even non-convex situation).

41 pages

References in corpus (2)

• Efficient and fast estimation of the geometric median in Hilbert spaces with an averaged stochastic gradient algorithm
• Online estimation of the geometric median in Hilbert spaces : non asymptotic confidence balls

Cited by in corpus (5)

• Communication trade-offs for synchronized distributed SGD with large step size
• Convergence Rates of Stochastic Gradient Descent under Infinite Noise Variance
• An efficient Averaged Stochastic Gauss-Newton algorithm for estimating parameters of non linear regressions models
• Asymptotic study of stochastic adaptive algorithm in non-convex landscape
• Logarithmic Regret for parameter-free Online Logistic Regression