Extremely Fast Convergence Rates for Extremum Seeking Control with Polyak-Ruppert Averaging

arXiv2206.00814MaRDI QIDQ6506004FDOQ6506004

Authors: Caio Kalil Lauand, Sean P. Meyn 

Abstract: Stochastic approximation is a foundation for many algorithms found in machine learning and optimization. It is in general slow to converge: the mean square error vanishes as $O(n^{-1})$. A deterministic counterpart known as quasi-stochastic approximation (QSA) is a viable alternative in many applications, including gradient free optimization and reinforcement learning. It was assumed in recent prior research that the optimal achievable convergence rate is $O(n^{-2})$. It is shown in this paper that through design it is possible to obtain far faster convergence, of order $O(n^{-4+delta})$, with $delta>0$ arbitrary. Two acceleration techniques are introduced for the first time to achieve this rate of convergence. The theory is also specialized within the context of gradient-free optimization, and tested on standard benchmarks. The main results are based on a combination of recent results from number theory and techniques adapted from stochastic approximation theory.

Mathematics Subject Classification ID

Stochastic approximation (62L20) Averaging method for ordinary differential equations (34C29)

This page was built for publication: Extremely Fast Convergence Rates for Extremum Seeking Control with Polyak-Ruppert Averaging

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6506004)