Quantum Algorithm for Online Exp-concave Optimization

Jianhao He, Chengchang Liu, Xutong Liu, Lvzhou Li, John C.S. Lui
Proceedings of the 41st International Conference on Machine Learning, PMLR 235:17946-17971, 2024.

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 this Paper

BibTeX
@InProceedings{pmlr-v235-he24g, 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 = {Proceedings of the 41st International Conference on Machine Learning}, pages = {17946--17971}, year = {2024}, editor = {Salakhutdinov, Ruslan and Kolter, Zico and Heller, Katherine and Weller, Adrian and Oliver, Nuria and Scarlett, Jonathan and Berkenkamp, Felix}, volume = {235}, series = {Proceedings of Machine Learning Research}, month = {21--27 Jul}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/v235/main/assets/he24g/he24g.pdf}, url = {https://proceedings.mlr.press/v235/he24g.html}, 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}$.} }
Endnote
%0 Conference Paper %T Quantum Algorithm for Online Exp-concave Optimization %A Jianhao He %A Chengchang Liu %A Xutong Liu %A Lvzhou Li %A John C.S. Lui %B Proceedings of the 41st International Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2024 %E Ruslan Salakhutdinov %E Zico Kolter %E Katherine Heller %E Adrian Weller %E Nuria Oliver %E Jonathan Scarlett %E Felix Berkenkamp %F pmlr-v235-he24g %I PMLR %P 17946--17971 %U https://proceedings.mlr.press/v235/he24g.html %V 235 %X 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}$.
APA
He, J., Liu, C., Liu, X., Li, L. & Lui, J.C.. (2024). Quantum Algorithm for Online Exp-concave Optimization. Proceedings of the 41st International Conference on Machine Learning, in Proceedings of Machine Learning Research 235:17946-17971 Available from https://proceedings.mlr.press/v235/he24g.html.

Related Material