Lower bounds established for exact Gaussian sampling complexity
On Complexity of Gaussian Sampling
Computational Complexity
Summary
Sampling from a Gaussian distribution is a common task in many fields like statistics and machine learning. The authors study how many times you need to multiply a matrix by a vector to get a sample that is very close to the true Gaussian. They prove new limits showing that any algorithm requires at least a certain number of these multiplications, depending on the size and shape of the Gaussian. These results match or improve what was known before, especially when the Gaussian has certain properties or when high accuracy is needed.
What this means in practice
- •For machine learning engineers: Determine minimal computational steps needed for exact Gaussian sampling algorithms to meet precision requirements in high-dimensional models.
- •For statistical software developers: Guide design of sampling routines for Gaussian models ensuring efficiency limits are respected based on problem size and condition number.
A theory result. No direct application yet.
Authors
Huanjian Zhou, Taiji Suzuki
Abstract
We study the number of exact matrix-vector queries needed to sample a centered $d$-dimensional Gaussian with condition number at most $κ$ to total variation error $\varepsilon$. The best known algorithm uses $O(\min\{d,\sqrtκ\log(\frac{d}{\varepsilon})\})$ queries, while the known lower bounds do not grow as $\varepsilon\to0$ and match this bound only for $κ\le d^{1/5-δ}$ at constant accuracy. We introduce a construction based on a hidden determinant sign and prove a lower bound of $Ω\!\left(\min\left\{d,\sqrtκ\log\left(1+\frac{d}{\sqrtκ\,\varepsilon}\right)\right\}\right)$ uniformly for all $d\ge1$, $κ\ge4$, and $0<\varepsilon\le\tfrac{1}{16}$. This bound matches the known upper bound up to constant factors whenever $κ\le d^{2-δ}$ for fixed $δ\in(0,2)$, or $\varepsilon\le d^{-c}$ for fixed $c>0$. We also extend a recent fixed-spectrum construction with a hidden eigenbasis from $κ=2$ to $2\leκ\le d^{1-δ}$, for any fixed $δ\in(0,1)$. This gives an $Ω_δ(\sqrtκ\log d)$ lower bound at constant accuracy that holds even when the spectrum of the precision matrix is known to the algorithm.