Quantum Speedups for Stochastic Optimization with Heavy-Tailed Noise

arXiv:2607.25492v1 Announce Type: new Abstract: 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 (exttt{QNSGD}), which finds an epsilon-stationary point using ilde{O}ig(sqrt d,epsilon^{-frac{5p-4}{2p-2}}ig) queries to the quantum stochastic gradient oracle. For a convex objective function, we propose a quantum projected stochastic gradient descent method (exttt{QPSGD}), which computes a solution with epsilon-optimal solution using ilde{O}ig(sqrt d,epsilon^{-frac{3p-2}{2p-2}}+epsilon^{-2}ig) queries in expectation. These sharper bounds improve upon the classical lower bounds Omegaig(epsilon^{-frac{3p-2}{p-1}}ig) for nonconvex problems and Omegaig(epsilon^{-frac{p}{p-1}}ig) for convex problems in the low-dimensional regimes dlesssimepsilon^{-frac{p}{p-1}} and dlesssimepsilon^{-frac{2-p}{p-1}}, respectively.

Source: arXiv cs.LG | 2026-07-29