Quantum Algorithms and Lower Bounds for Finite-Sum Optimization

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₁,ldots,f_ncolonmathbb{R}^d→mathbb{R} be ell-smooth convex functions and ψcolonmathbb{R}^d→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ⁿ f_i\(mathbf{x}\)+ψ\(mathbf{x}\). We give a quantum algorithm with complexity {O}big\(n+sqrt{d}+sqrt{ell/μ}big(n^1/3d^1/3+n^-2/3d^5/6big\)big), improving the classical tight bound Θbig\(n+sqrt{nell/μ}big\). We also prove a quantum lower bound Ω\(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 {O}\(n+ell(d^1/3n^1/3+sqrt{d}\)/ε²) queries.