Research map / Learning theory and algorithms / Sample complexity
Quantum Algorithms and Lower Bounds for Finite-Sum Optimization
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Initiates quantum algorithms for finite-sum optimization via a quantum finite-sum oracle, giving a Katyusha-based quantum variance reduction algorithm with improved query complexity over classical bounds in some regimes, a SPIDER-based critical-point method, and matching-style quantum lower bounds via the adversary method.
Problem
Finite-sum optimization F(x)=(1/n)sum f_i(x)+psi(x): classical methods need Theta~(n+sqrt(n l/mu)) gradient queries, and no quantum speedup was known for this setting.
Approach
A quantum finite-sum oracle lets queries to different sub-gradients be made in superposition; unbiased quantum mean estimation (MLMC-based quantum variance reduction) replaces the variance-reduction step of Katyusha and SPIDER, and a non-boolean quantum adversary method gives lower bounds for the finite-sum setting.
Key results
- Quantum upper bound tilde-O(n+sqrt(d)+sqrt(l/mu)(n^{1/3}d^{1/3}+n^{-2/3}d^{5/6})) for strongly convex finite-sum, improving classical tilde-Theta(n+sqrt(n l/mu)) when d is small.
- Quantum lower bound tilde-Omega(n+n^{3/4}(l/mu)^{1/4}) for strongly convex case when d is large enough, showing speedup is at most polynomial.
- Nonconvex critical-point finding in tilde-O(n+(d^{1/3}n^{1/3}+sqrt(d))/epsilon^2) queries, better than classical O(n+n^{1/2}/epsilon^2) when d < sqrt(n).
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use quantum variance reduction in Q-Katyusha instead of the classical variance-reduction step | Finite-sum convex optimization · QFCO Case 1: smooth, strongly convex | query complexity: \tilde{O}\big(n+\sqrt{d}+\sqrt{\ell/\mu}\big(n^{1/3}d^{1/3}+n^{-2/3}d^{5/6}\big)\big) vs. \tilde{O}\left(n+\sqrt{\frac{n | Helped |
| Use quantum finite-sum optimization algorithms | QFCO · QFCO Cases 1–4 | query complexity | Helped |
| Replace the classical SPIDER variance-reduction step with QVRG | Finite-Sum-Q-SPIDER · QFCP: nonconvex critical-point computation | query complexity: \tilde{O}\left(n+\ell\Delta\left(d^{1/3}n^{1/3}+\sqrt{d}\right)/\epsilon^2\right) vs. O(n+n^{1/2}/\epsilon^2) | Helped |
| Apply the quantum adversary method to the finite-sum lower-bound construction | Quantum finite-sum convex optimization · QFCO Cases 1–4 | query complexity lower bound | Mixed |
Limitations
- Speedup only holds when dimension d is relatively small; the quantum bounds need d large for lower bounds.
- Lower bound not tight relative to upper bound; the matrix detection lower bound may be improvable.
- Results are theoretical with no experiments.
Experimental setup
Metrics: query complexity
Baselines: Katyusha SPIDER classical finite-sum lower bounds
Builds on: Katyusha SPIDER quantum mean estimation multilevel Monte Carlo quantum adversary method
Closest papers by meaning
- Near-Optimal Quantum Algorithm for Minimizing the Maximal Loss (ICLR 2024 · similarity 0.92)
- Quantum Algorithms for Non-smooth Non-convex Optimization (NeurIPS 2024 · similarity 0.89)
- Isotropic Noise in Stochastic and Quantum Convex Optimization (NeurIPS 2025 · similarity 0.87)
- Quantum Speedups for Stochastic Optimization with Heavy-Tailed Noise (NeurIPS 2026 · similarity 0.87)
- Optimal algorithmic complexity of inference in quantum kernel methods (NeurIPS 2026 · similarity 0.86)
- Statistical Estimation in the Spiked Tensor Model via the Quantum Approximate Optimization Algorithm (NeurIPS 2024 · similarity 0.86)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.