Skip to content
Preprint

On Complexity of Gaussian Sampling

Oct 2026 · 0 citations · 26 references
Computer Science Mathematics

TL;DR

A construction based on a hidden determinant sign is introduced and a lower bound of the $\Omega_\delta(\sqrt{\kappa}\log d)$ lower bound at constant accuracy is proved even when the spectrum of the precision matrix is known to the algorithm.

Abstract

We study the number of exact matrix-vector queries needed to sample a centered $d$-dimensional Gaussian with condition number at most $\kappa$ to total variation error $\varepsilon$. The best known algorithm uses $O(\min\{d,\sqrt{\kappa}\log(\frac{d}{\varepsilon})\})$ queries, while the known lower bounds do not grow as $\varepsilon\to0$ and match this bound only for $\kappa\le d^{1/5-\delta}$ at constant accuracy. We introduce a construction based on a hidden determinant sign and prove a lower bound of $\Omega\!\left(\min\left\{d,\sqrt{\kappa}\log\left(1+\frac{d}{\sqrt{\kappa}\,\varepsilon}\right)\right\}\right)$ uniformly for all $d\ge1$, $\kappa\ge4$, and $0<\varepsilon\le\tfrac{1}{16}$. This bound matches the known upper bound up to constant factors whenever $\kappa\le d^{2-\delta}$ for fixed $\delta\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 $\kappa=2$ to $2\le\kappa\le d^{1-\delta}$, for any fixed $\delta\in(0,1)$. This gives an $\Omega_\delta(\sqrt{\kappa}\log d)$ lower bound at constant accuracy that holds even when the spectrum of the precision matrix is known to the algorithm.

View source

Similar papers

Preprint Oct 2026

Stable and Online Algorithms for Random Matrix Discrepancy

We study the average-case matrix discrepancy problem: given independent normalized $d\times d$ Gaussian orthogonal ensemble matrices $A_1,\dots,A_N$ and a fixed margin $\kappa>0$, find signs $\sigma_1,\dots,\sigma_N\in\{-1,1\}$ such that the operator norm of $\sum_{i=1}^N \sigma_i A_i$ is at most $\kappa\sqrt{N}$. Focu...

Eren C. Kızıldağ, Shuang-Ping Li · 2 citations
#machine learning Preprint Oct 2026

Approximating the Euclidean Ball by Polytopes: Surprising Rates in High Dimensions

We provide sharp estimates on the number of vertices needed to approximate the Euclidean unit ball $B_d\subset\mathbb R^d$ with relative symmetric-difference volume error at most $\varepsilon\in(0,1)$. We show that the minimum vertex budget $N_\varepsilon(d)$ satisfies $$\log N_\varepsilon(d)\asymp d\log\left(1+\frac1{...

Yegor Gorodzha, Steven Hoehner, Gil Kur · 0 citations
Preprint Oct 2026

Fourier dimension for exactly approximable matrices

We determine the Fourier dimension of exactly approximation set for all dimensions. More precisely, let $m,n\ge1$, $\boldsymbol\theta\in\mathbb R^m$, and $\psi:\mathbb N\to \mathbb R^+$ be a non-increasing approximate function. Denote by $\textrm{Exact}_{m,n}(\psi,\boldsymbol\theta)$ the set of $m\times n$ matrices whi...

Yu-Bin He, Bi-Xuan Li, Bao-Wei Wang · 0 citations
Preprint Nov 2026

Fourier Entropy Bounds via Approximations

We establish upper bounds on the Shannon entropy $\mathbb H(\widehat f^{\,2})$ of the Fourier distribution of Boolean functions. We prove that $$ \mathbb H(\widehat f^{\,2}) =O\!\left(\log\bigl(1+\|\widehat f\|_{1,1/3}\bigr)\right), $$ where $\|\widehat f\|_{1,1/3}$ denotes the minimum spectral norm of a pointwise $1/3...

Manaswi Paraashar, N. Saurabh · 0 citations
#machine learning Preprint Oct 2026

Near-Optimal Complexity of Finite-Sum Nonconvex-Strongly-Concave Minimax Optimization

We characterize, up to logarithmic factors, the minimax expected query complexity of finite-sum nonconvex-strongly-concave optimization under mean-squared averaged smoothness. For randomized zero-respecting incremental first-order algorithms, the complexity is $\tilde{\Theta}(n+\min\{\sqrt{n}\,\kappa,n^{3/4}\sqrt{\kapp...

Qi-Hao Zhou · 3 citations · ⚡2
Preprint Sep 2026

Near-Optimal Exact-Value Zeroth-Order Complexity for Smooth Strongly Convex Optimization

We study deterministic adaptive optimization of globally $\beta$-smooth, $\mu$-strongly convex functions using exact scalar function values. Queries and outputs lie in $B_2^d(R)$, and the minimizer lies in $B_2^d(R/2)$. Set $\kappa=\beta/\mu$, $Q=\beta R^2/\epsilon$, and $D_d=(d/\log(ed))^{1/3}$. For sufficiently large...

Wen-Dao Wu, Hai-Han Zhang, Chen-Heng Zhang et al. · 0 citations

We use cookies to run the site and, with your consent, for analytics and to show ads. See our Cookie Policy.