Related papers: Tight Sampling Complexity with stochastic gradient oracles in Fixed Dimensions

Tight Sampling Complexity with stochastic gradient oracles in Fixed Dimensions

URL: http://arxiv.org/abs/2609.12590v1
Date: Fri, 11 Sep 2026 08:44:06 GMT
Title: Tight Sampling Complexity with stochastic gradient oracles in Fixed Dimensions
Abstract summary: The potential is $$-strongly convex and $L$-smooth, with an unknown mode in the ball of radius $-1/2$ about the origin.<n>We prove that the tight complexity of sampling a distribution within $$-TV distance from the target distribution is [ Nstar_textTV=!left(log(1+)+ frac2right), ] where $:=frac L$ is the condition number.
Score: 5.603202398374589
License: http://creativecommons.org/licenses/by/4.0/
Abstract: We investigate the stochastic-gradient query complexity of sampling smooth strongly log-concave distributions in any fixed Euclidean dimension. The potential is $μ$-strongly convex and $L$-smooth, with an unknown mode in the ball of radius $μ^{-1/2}$ about the origin. We have access to unbiased stochastic oracles with the variance at most $σ^2$. For every $σ^2\ge0$ and total variation (TV) accuracy $0<\varepsilon\le1/10$, we prove that the tight complexity of sampling a distribution within $ε$-TV distance from the target distribution is \[ N^\star_{\text{TV}}=Θ\!\left(\log(1+κ)+ \frac{σ^2}{με}\right), \] where $κ:=\frac Lμ$ is the condition number. Note that this complexity bound is simultaneously tight for the condition number $κ$ and accuracy $ε$. Besides, our tight complexity bound is adaptive to noiseless setting $σ=0$, which is $ N^\star_{\text{TV}}=Θ\!\left(\log(1+κ)\right)$.

Related papers

A Near-optimal SQ Lower Bound for Smoothed Agnostic Learning of Boolean Halfspaces [0.0]
We study the complexity of smoothed learning of halfspaces on $pm 1n$ under uniform marginals in the model ofciteKM25.
arXiv Detail & Related papers (2026-05-04T08:53:40Z)
High-accuracy sampling for diffusion models and log-concave distributions [70.90863485771405]
We present algorithms for diffusion model sampling which obtain $$-error in $mathrmpolylog (1/)$ steps.<n>Our approach also yields the first $mathrmpolylog (1/)$ complexity sampler for general log-concave distributions.
arXiv Detail & Related papers (2026-02-01T17:05:31Z)
Information-Computation Tradeoffs for Noiseless Linear Regression with Oblivious Contamination [65.37519531362157]
We show that any efficient Statistical Query algorithm for this task requires VSTAT complexity at least $tildeOmega(d1/2/alpha2)$.
arXiv Detail & Related papers (2025-10-12T15:42:44Z)
Improved sampling algorithms and Poincaré inequalities for non-log-concave distributions [2.959331374750817]
We show that the query complexity of sampling from $mu$ can be $mathrmpoly(L,d)cdot left(fracLMdepsilon2right)mathcalO(L+1)$, which is in $d$ and $frac1epsilon$ when $L=mathcalO(1)$ and $M=mathrmpoly(d)$.
arXiv Detail & Related papers (2025-07-15T12:06:11Z)
On the query complexity of sampling from non-log-concave distributions [2.4253233571593547]
We study the problem of sampling from a $d$-dimensional distribution with density $p(x)propto e-f(x)$, which does not necessarily satisfy good isoperimetric conditions.<n>We show that for a wide range of parameters, sampling is strictly easier than optimization by a super-exponential factor in the dimension $d$.
arXiv Detail & Related papers (2025-02-10T06:54:16Z)
Dimension-free Private Mean Estimation for Anisotropic Distributions [55.86374912608193]
Previous private estimators on distributions over $mathRd suffer from a curse of dimensionality. We present an algorithm whose sample complexity has improved dependence on dimension.
arXiv Detail & Related papers (2024-11-01T17:59:53Z)
Measuring quantum relative entropy with finite-size effect [53.64687146666141]
We study the estimation of relative entropy $D(rho|sigma)$ when $sigma$ is known.<n>Our estimator attains the Cram'er-Rao type bound when the dimension $d$ is fixed.
arXiv Detail & Related papers (2024-06-25T06:07:20Z)
Testing Closeness of Multivariate Distributions via Ramsey Theory [40.926523210945064]
We investigate the statistical task of closeness (or equivalence) testing for multidimensional distributions. Specifically, given sample access to two unknown distributions $mathbf p, mathbf q$ on $mathbb Rd$, we want to distinguish between the case that $mathbf p=mathbf q$ versus $|mathbf p-mathbf q|_A_k > epsilon$. Our main result is the first closeness tester for this problem with em sub-learning sample complexity in any fixed dimension.
arXiv Detail & Related papers (2023-11-22T04:34:09Z)
The Sample Complexity of Robust Covariance Testing [56.98280399449707]
We are given i.i.d. samples from a distribution of the form $Z = (1-epsilon) X + epsilon B$, where $X$ is a zero-mean and unknown covariance Gaussian $mathcalN(0, Sigma)$. In the absence of contamination, prior work gave a simple tester for this hypothesis testing task that uses $O(d)$ samples. We prove a sample complexity lower bound of $Omega(d2)$ for $epsilon$ an arbitrarily small constant and $gamma
arXiv Detail & Related papers (2020-12-31T18:24:41Z)
Learning Mixtures of Spherical Gaussians via Fourier Analysis [0.5381004207943596]
We find that a bound on the sample and computational complexity was previously unknown when $omega(1) leq d leq O(log k)$. These authors also show that the sample of complexity of a random mixture of gaussians in a ball of radius $d$ in $d$ dimensions, when $d$ is $Theta(sqrtd)$ in $d$ dimensions, when $d$ is at least $poly(k, frac1delta)$.
arXiv Detail & Related papers (2020-04-13T08:06:29Z)
Curse of Dimensionality on Randomized Smoothing for Certifiable Robustness [151.67113334248464]
We show that extending the smoothing technique to defend against other attack models can be challenging. We present experimental results on CIFAR to validate our theory.
arXiv Detail & Related papers (2020-02-08T22:02:14Z)

This list is automatically generated from the titles and abstracts of the papers in this site.