2022/06/02 by Caio Kalil Lauand, Sean Meyn, Lauand, Caio Kalil +1
Engineering · Materials Science · #34C29 #62L20 #Advancements in Semiconductor Devices and Circuit Design #Diamond and Carbon-based Materials Research #Extremum Seeking Control Systems #FOS: Mathematics #Optimization and Control (math.OC)
paper · pdf · doi:10.48550/arxiv.2206.00814
openalex publication_date 2022/06/02 · openalex created_date 2022/06/13 · openalex updated_date 2026/07/28
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 is a viable alternative in many applications, including gradient-free optimization and reinforcement learning. It was assumed in 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+δ), with δ>0 arbitrary. Two 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 novel application of results from number theory and techniques adapted from stochastic approximation theory.