Quantum Algorithms and Lower Bounds for Finite-Sum Optimization

Yexin Zhang, Chenyi Zhang, Cong Fang, Liwei Wang, Tongyang Li
Proceedings of the 41st International Conference on Machine Learning, PMLR 235:60244-60270, 2024.

Abstract

Finite-sum optimization has wide applications in machine learning, covering important problems such as support vector machines, regression, etc. In this paper, we initiate the study of solving finite-sum optimization problems by quantum computing. Specifically, let f1,…,fn:Rd→R be ℓ-smooth convex functions and ψ:Rd→R be a μ-strongly convex proximal function. The goal is to find an ϵ-optimal point for F(x)=1n∑ni=1fi(x)+ψ(x). We give a quantum algorithm with complexity ˜O(n+√d+√ℓ/μ(n1/3d1/3+n−2/3d5/6)), improving the classical tight bound ˜Θ(n+√nℓ/μ). We also prove a quantum lower bound ˜Ω(n+n3/4(ℓ/μ)1/4) when d is large enough. Both our quantum upper and lower bounds can extend to the cases where ψ is not necessarily strongly convex, or each fi is Lipschitz but not necessarily smooth. In addition, when F is nonconvex, our quantum algorithm can find an ϵ-critial point using ˜O(n+ℓ(d1/3n1/3+√d)/ϵ2) queries.

Cite this Paper

BibTeX
@InProceedings{pmlr-v235-zhang24bz, title = {Quantum Algorithms and Lower Bounds for Finite-Sum Optimization}, author = {Zhang, Yexin and Zhang, Chenyi and Fang, Cong and Wang, Liwei and Li, Tongyang}, booktitle = {Proceedings of the 41st International Conference on Machine Learning}, pages = {60244--60270}, 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/zhang24bz/zhang24bz.pdf}, url = {https://proceedings.mlr.press/v235/zhang24bz.html}, abstract = {Finite-sum optimization has wide applications in machine learning, covering important problems such as support vector machines, regression, etc. In this paper, we initiate the study of solving finite-sum optimization problems by quantum computing. Specifically, let $f_1,\ldots,f_n:\mathbb{R}^d\to\mathbb{R}$ be $\ell$-smooth convex functions and $\psi:\mathbb{R}^d\to\mathbb{R}$ be a $\mu$-strongly convex proximal function. The goal is to find an $\epsilon$-optimal point for $F(\mathbf{x})=\frac{1}{n}\sum_{i=1}^n f_i(\mathbf{x})+\psi(\mathbf{x})$. We give a quantum algorithm with complexity $\tilde{O}\big(n+\sqrt{d}+\sqrt{\ell/\mu}\big(n^{1/3}d^{1/3}+n^{-2/3}d^{5/6}\big)\big)$, improving the classical tight bound $\tilde{\Theta}\big(n+\sqrt{n\ell/\mu}\big)$. We also prove a quantum lower bound $\tilde{\Omega}(n+n^{3/4}(\ell/\mu)^{1/4})$ when $d$ is large enough. Both our quantum upper and lower bounds can extend to the cases where $\psi$ is not necessarily strongly convex, or each $f_i$ is Lipschitz but not necessarily smooth. In addition, when $F$ is nonconvex, our quantum algorithm can find an $\epsilon$-critial point using $\tilde{O}(n+\ell(d^{1/3}n^{1/3}+\sqrt{d})/\epsilon^2)$ queries.} }
Endnote
%0 Conference Paper %T Quantum Algorithms and Lower Bounds for Finite-Sum Optimization %A Yexin Zhang %A Chenyi Zhang %A Cong Fang %A Liwei Wang %A Tongyang Li %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-zhang24bz %I PMLR %P 60244--60270 %U https://proceedings.mlr.press/v235/zhang24bz.html %V 235 %X Finite-sum optimization has wide applications in machine learning, covering important problems such as support vector machines, regression, etc. In this paper, we initiate the study of solving finite-sum optimization problems by quantum computing. Specifically, let $f_1,\ldots,f_n:\mathbb{R}^d\to\mathbb{R}$ be $\ell$-smooth convex functions and $\psi:\mathbb{R}^d\to\mathbb{R}$ be a $\mu$-strongly convex proximal function. The goal is to find an $\epsilon$-optimal point for $F(\mathbf{x})=\frac{1}{n}\sum_{i=1}^n f_i(\mathbf{x})+\psi(\mathbf{x})$. We give a quantum algorithm with complexity $\tilde{O}\big(n+\sqrt{d}+\sqrt{\ell/\mu}\big(n^{1/3}d^{1/3}+n^{-2/3}d^{5/6}\big)\big)$, improving the classical tight bound $\tilde{\Theta}\big(n+\sqrt{n\ell/\mu}\big)$. We also prove a quantum lower bound $\tilde{\Omega}(n+n^{3/4}(\ell/\mu)^{1/4})$ when $d$ is large enough. Both our quantum upper and lower bounds can extend to the cases where $\psi$ is not necessarily strongly convex, or each $f_i$ is Lipschitz but not necessarily smooth. In addition, when $F$ is nonconvex, our quantum algorithm can find an $\epsilon$-critial point using $\tilde{O}(n+\ell(d^{1/3}n^{1/3}+\sqrt{d})/\epsilon^2)$ queries.
APA
Zhang, Y., Zhang, C., Fang, C., Wang, L. & Li, T.. (2024). Quantum Algorithms and Lower Bounds for Finite-Sum Optimization. Proceedings of the 41st International Conference on Machine Learning, in Proceedings of Machine Learning Research 235:60244-60270 Available from https://proceedings.mlr.press/v235/zhang24bz.html.

Related Material