# Quantum Speedups for Stochastic Optimization with Heavy-Tailed Noise

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 15 of its 63 references that are in the map.
- First posted on arXiv 28 Jul 2026.

## Builds on (most cited first, 15 of 15)

- [Mean estimation and regression under heavy-tailed distributions--a survey](https://mlsanity.com/paper/1906.04280/) (2019)
- [From Gradient Clipping to Normalization for Heavy Tailed SGD](https://mlsanity.com/paper/2410.13849/) (2024)
- [On Proximal Policy Optimization's Heavy-tailed Gradients](https://mlsanity.com/paper/2102.10264/) (2021)
- [Can SGD Handle Heavy-Tailed Noise?](https://mlsanity.com/paper/2508.04860/) (2025)
- [Online Convex Optimization with Heavy Tails: Old Algorithms, New Regrets, and Applications](https://mlsanity.com/paper/2508.07473/) (2025)
- [Quantum Computing: Lecture Notes](https://mlsanity.com/paper/1907.09415/) (2019)
- [No-Regret Reinforcement Learning with Heavy-Tailed Rewards](https://mlsanity.com/paper/2102.12769/) (2021)
- [Tackling Heavy-Tailed Rewards in Reinforcement Learning with Function Approximation: Minimax Optimal and Instance-Dependent Regret Bounds](https://mlsanity.com/paper/2306.06836/) (2023)
- [Faster Stochastic Quasi-Newton Methods](https://mlsanity.com/paper/2004.06479/) (2020)
- [Quantum Heavy-tailed Bandits](https://mlsanity.com/paper/2301.09680/) (2023)
- [Mean Estimation in Banach Spaces Under Infinite Variance and Martingale Dependence](https://mlsanity.com/paper/2411.11271/) (2024)
- [Quantum Lower Bounds for Finding Stationary Points of Nonconvex Functions](https://mlsanity.com/paper/2212.03906/) (2022)
- [Quantum Algorithms and Lower Bounds for Finite-Sum Optimization](https://mlsanity.com/paper/2406.03006/) (2024)
- [Quantum Hamiltonian Descent for Non-smooth Optimization](https://mlsanity.com/paper/2503.15878/) (2025)
- [Quantum Speedups for Sampling and Non-convex Optimization with Stochastic Oracles](https://mlsanity.com/paper/2504.03626/) (2025)

## Abstract (arXiv)

We study stochastic optimization with heavy-tailed gradient noise. We first propose a novel quantum mean estimator for multivariate heavy-tailed random variables that achieves lower query complexity than optimal classical estimators in the low-dimensional regime. We further develop an unbiased quantum mean estimator by applying a generalized multi-level Monte Carlo technique. We prove quantum lower bounds showing that, when the dimension d of the random vector is small and can be viewed as a constant, our quantum estimators are optimal up to logarithmic factors. We further derive stronger dimension-dependent lower bounds for tail index p>4/3, showing that a nontrivial dependence on the dimension is unavoidable in the low-dimensional regime. Based on these estimators, we propose a quantum normalized stochastic gradient descent method (textttQNSGD), which finds an ε-stationary point using tildeObig(√ d,ε^-frac5p-42p-2big) queries to the quantum stochastic gradient oracle. For a convex objective function, we propose a quantum projected stochastic gradient descent method (textttQPSGD), which computes a solution with ε-optimal solution using tildeObig(√ d,ε^-frac3p-22p-2+ε-2big) queries in expectation. These sharper bounds improve upon the classical lower bounds Omegabig(ε^-frac3p-2p-1big) for nonconvex problems and Omegabig(ε^-fracpp-1big) for convex problems in the low-dimensional regimes dlesssimε^-fracpp-1 and dlesssimε^-frac2-pp-1, respectively.