Quantum Algorithms and Lower Bounds for Finite-Sum Optimization
Fuente:
arXiv
Guardado en:
| Autores principales: | , , , , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2024
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866916274859147264 |
|---|---|
| author | Zhang, Yexin Zhang, Chenyi Fang, Cong Wang, Liwei Li, Tongyang |
| author_facet | Zhang, Yexin Zhang, Chenyi Fang, Cong Wang, Liwei Li, Tongyang |
| contents | 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\colon\mathbb{R}^d\to\mathbb{R}$ be $\ell$-smooth convex functions and $ψ\colon\mathbb{R}^d\to\mathbb{R}$ be a $μ$-strongly convex proximal function. The goal is to find an $ε$-optimal point for $F(\mathbf{x})=\frac{1}{n}\sum_{i=1}^n f_i(\mathbf{x})+ψ(\mathbf{x})$. We give a quantum algorithm with complexity $\tilde{O}\big(n+\sqrt{d}+\sqrt{\ell/μ}\big(n^{1/3}d^{1/3}+n^{-2/3}d^{5/6}\big)\big)$, improving the classical tight bound $\tildeΘ\big(n+\sqrt{n\ell/μ}\big)$. We also prove a quantum lower bound $\tildeΩ(n+n^{3/4}(\ell/μ)^{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 $f_i$ is Lipschitz but not necessarily smooth. In addition, when $F$ is nonconvex, our quantum algorithm can find an $ε$-critial point using $\tilde{O}(n+\ell(d^{1/3}n^{1/3}+\sqrt{d})/ε^2)$ queries. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2406_03006 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Quantum Algorithms and Lower Bounds for Finite-Sum Optimization Zhang, Yexin Zhang, Chenyi Fang, Cong Wang, Liwei Li, Tongyang Quantum Physics Data Structures and Algorithms Machine Learning Optimization and Control 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\colon\mathbb{R}^d\to\mathbb{R}$ be $\ell$-smooth convex functions and $ψ\colon\mathbb{R}^d\to\mathbb{R}$ be a $μ$-strongly convex proximal function. The goal is to find an $ε$-optimal point for $F(\mathbf{x})=\frac{1}{n}\sum_{i=1}^n f_i(\mathbf{x})+ψ(\mathbf{x})$. We give a quantum algorithm with complexity $\tilde{O}\big(n+\sqrt{d}+\sqrt{\ell/μ}\big(n^{1/3}d^{1/3}+n^{-2/3}d^{5/6}\big)\big)$, improving the classical tight bound $\tildeΘ\big(n+\sqrt{n\ell/μ}\big)$. We also prove a quantum lower bound $\tildeΩ(n+n^{3/4}(\ell/μ)^{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 $f_i$ is Lipschitz but not necessarily smooth. In addition, when $F$ is nonconvex, our quantum algorithm can find an $ε$-critial point using $\tilde{O}(n+\ell(d^{1/3}n^{1/3}+\sqrt{d})/ε^2)$ queries. |
| title | Quantum Algorithms and Lower Bounds for Finite-Sum Optimization |
| topic | Quantum Physics Data Structures and Algorithms Machine Learning Optimization and Control |
| url | https://arxiv.org/abs/2406.03006 |