Speaker
Description
We study quantum mean estimation for multivariate heavy-tailed distributions. Specifically, we consider random vectors whose $p$-th central moment is bounded for some $p\in(1,2]$; this includes the bounded-variance case when $p=2$, while allowing infinite variance when $p<2$. We first propose a quantum heavy-tailed mean estimator ($\texttt{QHTME}$), for estimating the mean of random variables under this heavy-tailed assumption. In the low-dimensional regime, $\texttt{QHTME}$ achieves a lower query complexity than the optimal classical heavy-tailed mean estimator while recovering the known bounded-variance quantum query complexity when $p=2$. We further develop an unbiased quantum mean estimator, denoted by $\texttt{QUHTME}$, by combining $\texttt{QHTME}$ with a generalized multi-level Monte Carlo technique. On the quantum lower bound side, we show that, when the dimension $d$ is small and can be treated as a constant, our quantum mean estimators are optimal up to logarithmic factors. We also establish a dimension-dependent lower bound in the low-dimensional regime by introducing a new hard primitive based on bit-string recovery and search problems. Finally, we show that these quantum heavy-tailed mean estimators lead to provable quantum speedups for stochastic optimization with heavy-tailed stochastic gradient noise, suggesting a route toward quantum advantages for machine-learning-relevant optimization problems in the heavy-tailed setting.
| Topic | Quantum algorithms for machine learning applications |
|---|