High-probability zeroth-order online convex optimisation beyond Euclidean geometry
Fuente:
arXiv
Salvato in:
| Autori principali: | , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2025
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866909027487711232 |
|---|---|
| author | Janz, David El-Mhamdi, El-Mahdi Akhavan, Arya |
| author_facet | Janz, David El-Mhamdi, El-Mahdi Akhavan, Arya |
| contents | We study online convex optimisation with $\ell_q$-Lipschitz losses, $\ell_p$-regularised FTRL, and randomised two-point finite-difference gradient estimators based on cone-measure sampling from $\ell_r$-spheres. For random Lipschitz losses whose mean is convex, we prove unified high-probability regret bounds for all $p,q,r \in [1,\infty]$. The analysis is driven by all-moment bounds for the gradient estimator in the dual FTRL norm, yielding time-uniform control of the quadratic variation. The algorithm is anytime and data-driven; in the special cases previously studied, its rates recover the known in-expectation guarantees while strengthening them to time-uniform high probability. Together with constant-probability lower bounds, these results establish optimality for $q\in[1,2]$ under appropriate sampling geometry, and expose a gap for $q>2$ that appears intrinsic to the estimators themselves. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2509_21484 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | High-probability zeroth-order online convex optimisation beyond Euclidean geometry Janz, David El-Mhamdi, El-Mahdi Akhavan, Arya Machine Learning We study online convex optimisation with $\ell_q$-Lipschitz losses, $\ell_p$-regularised FTRL, and randomised two-point finite-difference gradient estimators based on cone-measure sampling from $\ell_r$-spheres. For random Lipschitz losses whose mean is convex, we prove unified high-probability regret bounds for all $p,q,r \in [1,\infty]$. The analysis is driven by all-moment bounds for the gradient estimator in the dual FTRL norm, yielding time-uniform control of the quadratic variation. The algorithm is anytime and data-driven; in the special cases previously studied, its rates recover the known in-expectation guarantees while strengthening them to time-uniform high probability. Together with constant-probability lower bounds, these results establish optimality for $q\in[1,2]$ under appropriate sampling geometry, and expose a gap for $q>2$ that appears intrinsic to the estimators themselves. |
| title | High-probability zeroth-order online convex optimisation beyond Euclidean geometry |
| topic | Machine Learning |
| url | https://arxiv.org/abs/2509.21484 |