Research map / Optimization / Nonconvex and smooth optimization
Quantum Speedups for Stochastic Optimization with Heavy-Tailed Noise
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.
Proposes quantum mean estimators (QHTME, QUHTME) for multivariate heavy-tailed vectors and uses them in quantum normalized SGD (nonconvex) and projected SGD (convex), claiming query speedups over classical lower bounds in low dimension.
Problem
Stochastic optimization with heavy-tailed gradient noise (bounded p-th central moment, p in (1,2]) has classical query complexities that are not improved by quantum methods, and no quantum mean estimators existed for multivariate heavy-tailed vectors.
Approach
Center a classical geometric-median-of-means estimate, truncate at a radius B to get bounded trace covariance, and apply a bounded-variance quantum mean estimator; wrap this in a generalized MLMC scheme for unbiasedness, then plug the estimators into normalized SGD and projected SGD.
Key results
- QHTME uses O~(d^{1/2}(sigma/eps)^{p/(2(p-1))}) quantum queries versus classical optimal O~((sigma/eps)^{p/(p-1)}), a speedup when d is small.
- QNSGD finds an eps-stationary point with O~(sqrt(d) eps^{-(5p-4)/(2p-2)}) quantum queries, beating the classical lower bound eps^{-(3p-2)/(p-1)} when d is below about eps^{-p/(p-1)}.
- QPSGD for convex problems uses O~(sqrt(d) eps^{-(3p-2)/(2(p-1))} + eps^{-2}) expected queries, improving the classical eps^{-p/(p-1)} when d is small.
Limitations
- Results are theoretical query-complexity claims with no experiments; speedup holds only in low dimension.
- Requires fault-tolerant quantum hardware; circuits too deep for near-term devices.
- Joint dependence on d, sigma, eps for p<2 lower bounds remains open.
Experimental setup
Metrics: query complexity lower bound order
Baselines: CHTME (classical geometric median-of-means) classical NSGD clipped SGD quantum SGD for bounded variance (d^{1/2}epsilon^{-3}) classical lower bounds
Builds on: quantum multivariate mean estimation (QEstimator) geometric median-of-means multilevel Monte Carlo normalized SGD clipped SGD for heavy-tailed noise
Closest papers by meaning
- Quantum Algorithms for Non-smooth Non-convex Optimization (NeurIPS 2024 · similarity 0.90)
- Isotropic Noise in Stochastic and Quantum Convex Optimization (NeurIPS 2025 · similarity 0.89)
- Stochastic Zeroth-Order Optimization Under Heavy-Tailed Noise (NeurIPS 2026 · similarity 0.87)
- Nonconvex Stochastic Optimization under Heavy-Tailed Noises: Optimal Convergence without Gradient Clipping (ICLR 2025 · similarity 0.87)
- Quantum Algorithms and Lower Bounds for Finite-Sum Optimization (ICML 2024 · similarity 0.87)
- Quantum speedup of non-linear Monte Carlo problems (NeurIPS 2025 · similarity 0.87)
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.