# Quantum Algorithms and Lower Bounds for Finite-Sum Optimization

arXiv: https://arxiv.org/abs/2406.03006 · HTML: https://mlsanity.com/paper/2406.03006/

## 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 (most cited first, 30 of 36)

- [SAGA: A Fast Incremental Gradient Method With Support for Non-Strongly Convex Composite Objectives](https://mlsanity.com/paper/1407.0202/) (2014)
- [SPIDER: Near-Optimal Non-Convex Optimization via Stochastic Path Integrated Differential Estimator](https://mlsanity.com/paper/1807.01695/) (2018)
- [Stochastic Variance Reduction for Nonconvex Optimization](https://mlsanity.com/paper/1603.06160/) (2016)
- [Katyusha: The First Direct Acceleration of Stochastic Gradient Methods](https://mlsanity.com/paper/1603.05953/) (2016)
- [A Proximal Stochastic Gradient Method with Progressive Variance Reduction](https://mlsanity.com/paper/1403.4699/) (2014)
- [Variance Reduction for Faster Non-Convex Optimization](https://mlsanity.com/paper/1603.05643/) (2016)
- [Tight Complexity Bounds for Optimizing Composite Objectives](https://mlsanity.com/paper/1605.08003/) (2016)
- [Catalyst Acceleration for First-order Convex Optimization: from Theory to Practice](https://mlsanity.com/paper/1712.05654/) (2017)
- [Improved SVRG for Non-Strongly-Convex or Sum-of-Non-Convex Objectives](https://mlsanity.com/paper/1506.01972/) (2015)
- [Neon2: Finding Local Minima via First-Order Oracles](https://mlsanity.com/paper/1711.06673/) (2017)
- [First-order Stochastic Algorithms for Escaping From Saddle Points in Almost Linear Time](https://mlsanity.com/paper/1711.01944/) (2017)
- [Quantum SDP-Solvers: Better upper and lower bounds](https://mlsanity.com/paper/1705.01843/) (2017)
- [Stochastic Bias-Reduced Gradient Methods](https://mlsanity.com/paper/2106.09481/) (2021)
- [Optimal Black-Box Reductions Between Optimization Objectives](https://mlsanity.com/paper/1603.05642/) (2016)
- [Convex optimization using quantum oracles](https://mlsanity.com/paper/1809.00643/) (2018)
- [A Quantum Interior Point Method for LPs and SDPs](https://mlsanity.com/paper/1808.09266/) (2018)
- [Near-Optimal Quantum Algorithms for Multivariate Mean Estimation](https://mlsanity.com/paper/2111.09787/) (2021)
- [Quantum algorithms and lower bounds for convex optimization](https://mlsanity.com/paper/1809.01731/) (2018)
- [Quantum Sub-Gaussian Mean Estimator](https://mlsanity.com/paper/2108.12172/) (2021)
- [Quantum speedups for stochastic optimization](https://mlsanity.com/paper/2308.01582/) (2023)
- [Distributional property testing in a quantum world](https://mlsanity.com/paper/1902.00814/) (2019)
- [Quantum Algorithms and Lower Bounds for Linear Regression with Norm Constraints](https://mlsanity.com/paper/2110.13086/) (2021)
- [Quantum Speedups of Optimizing Approximately Convex Functions with Applications to Logarithmic Regret Stochastic Convex Bandits](https://mlsanity.com/paper/2209.12897/) (2022)
- [Quantum Chebyshev's Inequality and Applications](https://mlsanity.com/paper/1807.06456/) (2018)
- [Quantum algorithms for escaping from saddle points](https://mlsanity.com/paper/2007.10253/) (2020)
- [On Quantum Speedups for Nonconvex Optimization via Quantum Tunneling Walks](https://mlsanity.com/paper/2209.14501/) (2022)
- [Quantum simulation of real-space dynamics](https://mlsanity.com/paper/2203.17006/) (2022)
- [Quantum Speed-ups for Semidefinite Programming](https://mlsanity.com/paper/1609.05537/) (2016)
- [No quantum speedup over gradient descent for non-smooth convex optimization](https://mlsanity.com/paper/2010.01801/) (2020)
- [Near-Optimal Lower Bounds For Convex Optimization For All Orders of Smoothness](https://mlsanity.com/paper/2112.01118/) (2021)

## Built on by (most cited first, 4 of 4)

- [Quantum Non-Linear Bandit Optimization](https://mlsanity.com/paper/2503.03023/) (2025)
- [Sublinear Time Quantum Algorithm for Attention Approximation](https://mlsanity.com/paper/2602.00874/) (2026)
- [Quantum Algorithms for Projection-Free Sparse Convex Optimization](https://mlsanity.com/paper/2507.08543/) (2025)
- [Quantum Speedups for Stochastic Optimization with Heavy-Tailed Noise](https://mlsanity.com/paper/2607.25492/) (2026)

## 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.