Quantum Algorithm for Online Exp-Concave Optimization
Abstract
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}$.
Cite
Text
He et al. "Quantum Algorithm for Online Exp-Concave Optimization." International Conference on Machine Learning, 2024.Markdown
[He et al. "Quantum Algorithm for Online Exp-Concave Optimization." International Conference on Machine Learning, 2024.](https://mlanthology.org/icml/2024/he2024icml-quantum/)BibTeX
@inproceedings{he2024icml-quantum,
title = {{Quantum Algorithm for Online Exp-Concave Optimization}},
author = {He, Jianhao and Liu, Chengchang and Liu, Xutong and Li, Lvzhou and Lui, John C.S.},
booktitle = {International Conference on Machine Learning},
year = {2024},
pages = {17946-17971},
volume = {235},
url = {https://mlanthology.org/icml/2024/he2024icml-quantum/}
}