Quantum Speedups for Stochastic Optimization with Heavy-Tailed Noise

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 ($\text{QNSGD}$), which finds an $\hat{I}\mu$-stationary point using $\tilde{\mathcal{O}}\left(\sqrt{d}\hat{I}{\mu }^{-\frac{5p-4}{2p-2}}\right)$ queries to the quantum stochastic gradient oracle. For a convex objective function, we propose a quantum projected stochastic gradient descent method ($\text{QPSGD}$), which computes a solution with $\hat{I}\mu$-optimal solution using $\tilde{\mathcal{O}}(\sqrt{d}\hat{I}{\mu }^{-\frac{3p-2}{2p-2}}+\hat{I}{\mu }^{-2})$ queries in expectation. These sharper bounds improve upon the classical lower bounds $\hat{I}\text{c◯}\left(\hat{I}{\mu }^{-\frac{3p-2}{p-1}}\right)$ for nonconvex problems and $\hat{I}\text{c◯}\left(\hat{I}{\mu }^{-\frac{p}{p-1}}\right)$ for convex problems in the low-dimensional regimes $d\lesssim \hat{I}{\mu }^{-\frac{p}{p-1}}$ and $d\lesssim \hat{I}{\mu }^{-\frac{2-p}{p-1}}$, respectively.

56 pages

Topics & keywords