Saved in:
| Main Authors: | , , , , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2410.19688 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866916454656376832 |
|---|---|
| author | He, Jianhao Liu, Chengchang Liu, Xutong Li, Lvzhou Lui, John C. S. |
| author_facet | He, Jianhao Liu, Chengchang Liu, Xutong Li, Lvzhou Lui, John C. S. |
| contents | We explore whether quantum advantages can be found for the zeroth-order feedback online exp-concave optimization problem, which is also known as bandit exp-concave optimization with multi-point feedback. We present quantum online quasi-Newton methods to tackle the problem and show that there exists quantum advantages for such problems. Our method approximates the Hessian by quantum estimated inexact gradient and can achieve $O(n\log T)$ regret with $O(1)$ queries at each round, where $n$ is the dimension of the decision set and $T$ is the total decision rounds. Such regret improves the optimal classical algorithm by a factor of $T^{2/3}$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2410_19688 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Quantum Algorithm for Online Exp-concave Optimization He, Jianhao Liu, Chengchang Liu, Xutong Li, Lvzhou Lui, John C. S. Quantum Physics We explore whether quantum advantages can be found for the zeroth-order feedback online exp-concave optimization problem, which is also known as bandit exp-concave optimization with multi-point feedback. We present quantum online quasi-Newton methods to tackle the problem and show that there exists quantum advantages for such problems. Our method approximates the Hessian by quantum estimated inexact gradient and can achieve $O(n\log T)$ regret with $O(1)$ queries at each round, where $n$ is the dimension of the decision set and $T$ is the total decision rounds. Such regret improves the optimal classical algorithm by a factor of $T^{2/3}$. |
| title | Quantum Algorithm for Online Exp-concave Optimization |
| topic | Quantum Physics |
| url | https://arxiv.org/abs/2410.19688 |