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₁,…,fₙᵈ be -smooth convex functions and ψᵈ be a μ-strongly convex proximal function. The goal is to find an ε-optimal point for F(x)=1/n∑ᵢ₌₁ⁿ fᵢ(x)+ψ(x). We give a quantum algorithm with complexity Õ(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 fᵢ is Lipschitz but not necessarily smooth. In addition, when F is nonconvex, our quantum algorithm can find an ε-critial point using Õ(n+(d1/3n1/3+√d)/ε²) queries.