Optimal non-asymptotic bound of the Ruppert-Polyak averaging without strong convexity
By Sébastien Gadat, Fabien Panloup. 2017
41 citations recorded by the source corpus.
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). Finally, our bound is optimal when the decreasing step (γn) n≥1 satisfies: γn = γn −β with β = 3/4, leading to a second-order term in O(n −5/4).
Subfields: Computational Theory and Mathematics, Mathematical Physics
How researchers see this paper
The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.
In Computational Theory and Mathematics
In Mathematical Physics
Citations in the corpus
- Communication trade-offs for synchronized distributed SGD with large step size (2019, methodology): “This type of analysis has been successfully used recently (Bach and Moulines, 2011; Dieuleveut et al., 2017; Godichon and Saadane, 2017; Gadat and Panloup, 2017).”
- Communication trade-offs for Local-SGD with large step size (2019, methodology): “This type of analysis has been successfully used recently [10, 15, 25, 26].”