Quantum Algorithms and Lower Bounds for Finite-Sum Optimization

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,\dots ,f_n:{\mathbb{R}}^d\to \mathbb{R}$ be $\ell$-smooth convex functions and $\ddot{I}ˆ:{\mathbb{R}}^d\to \mathbb{R}$ be a $\hat{I}¼$-strongly convex proximal function. The goal is to find an $\hat{I}\mu$-optimal point for $F(\mathbf{x})=\frac{1}{n}{\sum }_{i=1}^n{f}_i(\mathbf{x})+\ddot{I}ˆ(\mathbf{x})$. We give a quantum algorithm with complexity $\tilde{O}(n+\sqrt{d}+\sqrt{\ell /\hat{I}¼}(n^{1/3}{d}^{1/3}+n^{-2/3}{d}^{5/6}\left)\right)$, improving the classical tight bound $\tilde{\hat{I}}˜(n+\sqrt{n\ell /\hat{I}¼})$. We also prove a quantum lower bound $\tilde{\hat{I}}\text{c◯}(n+n^{3/4}(\ell /\hat{I}¼{)}^{1/4})$ when $d$ is large enough. Both our quantum upper and lower bounds can extend to the cases where $\ddot{I}ˆ$ 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 $\hat{I}\mu$-critial point using $\tilde{O}(n+\ell (d^{1/3}{n}^{1/3}+\sqrt{d})/\hat{I}{\mu }^2)$ queries.

27 pages. To appear in the Forty-first International Conference on Machine Learning International Conference on Machine Learning (ICML 2024)