Online Newton Method for Bandit Convex Optimisation
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , , , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2024
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866914830848360448 |
|---|---|
| author | Fokkema, Hidde van der Hoeven, Dirk Lattimore, Tor Mayo, Jack J. |
| author_facet | Fokkema, Hidde van der Hoeven, Dirk Lattimore, Tor Mayo, Jack J. |
| contents | We introduce a computationally efficient algorithm for zeroth-order bandit convex optimisation and prove that in the adversarial setting its regret is at most $d^{3.5} \sqrt{n} \mathrm{polylog}(n, d)$ with high probability where $d$ is the dimension and $n$ is the time horizon. In the stochastic setting the bound improves to $M d^{2} \sqrt{n} \mathrm{polylog}(n, d)$ where $M \in [d^{-1/2}, d^{-1 / 4}]$ is a constant that depends on the geometry of the constraint set and the desired computational properties. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2406_06506 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Online Newton Method for Bandit Convex Optimisation Fokkema, Hidde van der Hoeven, Dirk Lattimore, Tor Mayo, Jack J. Optimization and Control Machine Learning We introduce a computationally efficient algorithm for zeroth-order bandit convex optimisation and prove that in the adversarial setting its regret is at most $d^{3.5} \sqrt{n} \mathrm{polylog}(n, d)$ with high probability where $d$ is the dimension and $n$ is the time horizon. In the stochastic setting the bound improves to $M d^{2} \sqrt{n} \mathrm{polylog}(n, d)$ where $M \in [d^{-1/2}, d^{-1 / 4}]$ is a constant that depends on the geometry of the constraint set and the desired computational properties. |
| title | Online Newton Method for Bandit Convex Optimisation |
| topic | Optimization and Control Machine Learning |
| url | https://arxiv.org/abs/2406.06506 |