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) =1n₈=₁ⁿ fᵢ (x) + (x). We give a quantum algorithm with complexity O (n+d+/ (n^1/3d^1/3+n^-2/3d^5/6) ), improving the classical tight bound (n+n/). We also prove a quantum lower bound (n+n^3/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 O (n+ (d^1/3n^1/3+d) /²) queries.