Optimal non-asymptotic analysis of the Ruppert-Polyak averaging stochastic algorithm

This paper is devoted to the non-asymptotic analysis of the Ruppert-Polyak averaging method introduced in Polyak and Juditsky (1992) and Ruppert (1988)[26] for the minimization of a smooth function f with a stochastic algorithm. We first establish a general non-asymptotic optimal bound: if (theta) over capn is the position of the algorithm at step n, we prove thatE| (theta) over cap (n) - arg min(f)|(2) <= Tr(Sigma*) n + Cd, f n(-r beta),where Sigma* is the limiting covariance matrix of the CLT demonstrated in Polyak and Juditsky (1992) and Cd, fn(-r beta) is a new state-of-the-art second order term that translates the effect of the dimension. We also identify the optimal gain of the baseline SGD gamma n = gamma n(-3/4), leading to a second-order term with r(3/4) = 5/4. Second, we show that this result holds under some Kurdyka-Lojiasewicz-type condition (Kurdyka, 1988; Lojasiewicz, 1963) for function f , which is far more general than the standard uniformly strongly convex case. In particular, it makes it possible to handle some pathological examples such as on-line learning for logistic regression and recursive quantile estimation.(c) 2022 Elsevier B.V. All rights reserved.