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(nlogT) 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 T2/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