Quantum Speedups for Stochastic Optimization with Heavy-Tailed Noise

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; while for the high-dimensional regime, no quantum speedup is available compared to optimal classical mean estimators. Based on these estimators, we propose a quantum normalized stochastic gradient descent method ($\text{QNSGD}$), which finds an $ϵ$-stationary point of a nonconvex objective using $\tilde{\mathcal{O}}\left(d^{\frac{p}{4(p-1)}}{ϵ}^{-\frac{5p-4}{2p-2}}\right)$ queries to the stochastic gradient, where $p\in (1,2]$ is the tail index. For a convex objective function, we propose a quantum projected stochastic gradient descent method ($\text{QPSGD}$), which computes an $ϵ$-optimal solution with query complexity $\tilde{\mathcal{O}}\left(d^{\frac{p}{4(p-1)}}{ϵ}^{-\frac{3p-2}{2p-2}}\right)$. Our results improve upon the classical lower bounds $\Omega \left({ϵ}^{-\frac{3p-2}{p-1}}\right)$ for nonconvex problems and $\Omega \left({ϵ}^{-\frac{p}{p-1}}\right)$ for convex problems, demonstrating a quantum speedup when $d$ is relatively small.