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

Sébastien Gadat and Fabien Panloup

Stochastic Processes and their Applications, 2023, vol. 156, issue C, 312-348

Abstract: 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 θˆn is the position of the algorithm at step n, we prove that E|θˆn−argmin(f)|2⩽Tr(Σ⋆)n+Cd,fn−rβ,where Σ⋆ is the limiting covariance matrix of the CLT demonstrated in Polyak and Juditsky (1992) and Cd,fn−rβ 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 γn=γn−3/4, leading to a second-order term with r3/4=5/4. Second, we show that this result holds under some Kurdyka-Łojiasewicz-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.

Keywords: Optimization; Averaging; Stochastic Gradient Descent (search for similar items in EconPapers)
Date: 2023
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0304414922002447
Full text for ScienceDirect subscribers only

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:eee:spapps:v:156:y:2023:i:c:p:312-348

Ordering information: This journal article can be ordered from
http://http://www.elsevier.com/wps/find/supportfaq.cws_home/regional
https://shop.elsevie ... _01_ooc_1&version=01

DOI: 10.1016/j.spa.2022.11.012

Access Statistics for this article

Stochastic Processes and their Applications is currently edited by T. Mikosch

More articles in Stochastic Processes and their Applications from Elsevier
Bibliographic data for series maintained by Catherine Liu ().