mlsanityData to 14 Oct 2026

Quantum Algorithms and Lower Bounds for Finite-Sum Optimization

arXiv 2406.03006 ↗First posted 5 Jun 2024quant-ph cs.DS cs.LGcited by 4

Not on the map. Why?

Abstract (arXiv)

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 f1,ldots,fncolonℝd→ℝ be ℓ-smooth convex functions and psicolonℝd→ℝ be a μ-strongly convex proximal function. The goal is to find an ε-optimal point for F(x)=frac1nsumi=1n fi(x)+psi(x). We give a quantum algorithm with complexity tildeObig(n+√d+√ℓ/μbig(n1/3d1/3+n-2/3d5/6big)big), improving the classical tight bound tildeThetabig(n+√nℓ/μbig). We also prove a quantum lower bound tildeOmega(n+n3/4(ℓ/μ)1/4) when d is large enough. Both our quantum upper and lower bounds can extend to the cases where psi is not necessarily strongly convex, or each fi is Lipschitz but not necessarily smooth. In addition, when F is nonconvex, our quantum algorithm can find an ε-critial point using tildeO(n+ℓ(d1/3n1/3+√d)/ε2) queries.

Key facts. Cited by 4 papers in the map (data through 14 Oct 2026). Builds on 36 of its 58 references that are in the map. First posted on arXiv 5 Jun 2024.

Builds on

36 of 58 references.

References · 36

  1. 2014SAGA: A Fast Incremental Gradient Method With Support for Non-Strongly Convex Composite Objectivescited by 402
  2. 2018SPIDER: Near-Optimal Non-Convex Optimization via Stochastic Path Integrated Differential Estimatorcited by 287
  3. 2016Stochastic Variance Reduction for Nonconvex Optimizationcited by 145
  4. 2016Katyusha: The First Direct Acceleration of Stochastic Gradient Methodscited by 135
  5. 2014A Proximal Stochastic Gradient Method with Progressive Variance Reductioncited by 78
  6. 2016Variance Reduction for Faster Non-Convex Optimizationcited by 72
  7. 2016Tight Complexity Bounds for Optimizing Composite Objectivescited by 48
  8. 2017Catalyst Acceleration for First-order Convex Optimization: from Theory to Practicecited by 39
  9. 2015Improved SVRG for Non-Strongly-Convex or Sum-of-Non-Convex Objectivescited by 38
  10. 2017Neon2: Finding Local Minima via First-Order Oraclescited by 36
  11. 2017First-order Stochastic Algorithms for Escaping From Saddle Points in Almost Linear Timecited by 29
  12. 2017Quantum SDP-Solvers: Better upper and lower boundscited by 27
24 more
  1. 2021Stochastic Bias-Reduced Gradient Methodscited by 25
  2. 2016Optimal Black-Box Reductions Between Optimization Objectivescited by 21
  3. 2018Convex optimization using quantum oraclescited by 19
  4. 2018A Quantum Interior Point Method for LPs and SDPscited by 17
  5. 2021Near-Optimal Quantum Algorithms for Multivariate Mean Estimationcited by 16
  6. 2018Quantum algorithms and lower bounds for convex optimizationcited by 15
  7. 2021Quantum Sub-Gaussian Mean Estimatorcited by 15
  8. 2023Quantum speedups for stochastic optimizationcited by 12
  9. 2019Distributional property testing in a quantum worldcited by 11
  10. 2021Quantum Algorithms and Lower Bounds for Linear Regression with Norm Constraintscited by 11
  11. 2022Quantum Speedups of Optimizing Approximately Convex Functions with Applications to Logarithmic Regret Stochastic Convex Banditscited by 11
  12. 2018Quantum Chebyshev's Inequality and Applicationscited by 10
  13. 2020Quantum algorithms for escaping from saddle pointscited by 10
  14. 2022On Quantum Speedups for Nonconvex Optimization via Quantum Tunneling Walkscited by 9
  15. 2022Quantum simulation of real-space dynamicscited by 8
  16. 2016Quantum Speed-ups for Semidefinite Programmingcited by 6
  17. 2020No quantum speedup over gradient descent for non-smooth convex optimizationcited by 6
  18. 2021Near-Optimal Lower Bounds For Convex Optimization For All Orders of Smoothnesscited by 6
  19. 2022Mean estimation when you have the source code; or, quantum Monte Carlo methodscited by 6
  20. 2022A Sublinear-Time Quantum Algorithm for Approximating Partition Functionscited by 5
  21. 2022Quantum Lower Bounds for Finding Stationary Points of Nonconvex Functionscited by 5
  22. 2016SDCA without Duality, Regularization, and Individual Convexitycited by 4
  23. 2023Stochastic Quantum Sampling for Non-Logconcave Distributions and Estimating Partition Functionscited by 4
  24. 2022Robustness of Quantum Algorithms for Nonconvex Optimizationcited by 2

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2025: 2; 2026: 2.

4 papers.

  1. 2025Quantum Non-Linear Bandit Optimizationcited by 2
  2. 2026Sublinear Time Quantum Algorithm for Attention Approximationcited by 1
  3. 2025Quantum Algorithms for Projection-Free Sparse Convex Optimizationcited by 0
  4. 2026Quantum Speedups for Stochastic Optimization with Heavy-Tailed Noisecited by 0