Extremely Fast Convergence Rates for Extremum Seeking Control with Polyak-Ruppert Averaging
Fuente:
arXiv
Salvato in:
| Autori principali: | , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2022
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866911810964160512 |
|---|---|
| author | Lauand, Caio Kalil Meyn, Sean |
| author_facet | Lauand, Caio Kalil Meyn, Sean |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2206_00814 |
| institution | arXiv |
| publishDate | 2022 |
| record_format | arxiv |
| spellingShingle | Extremely Fast Convergence Rates for Extremum Seeking Control with Polyak-Ruppert Averaging Lauand, Caio Kalil Meyn, Sean Optimization and Control 62L20, 34C29 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. |
| title | Extremely Fast Convergence Rates for Extremum Seeking Control with Polyak-Ruppert Averaging |
| topic | Optimization and Control 62L20, 34C29 |
| url | https://arxiv.org/abs/2206.00814 |