Metraipolis › archive › dc_27d738bd142d

Tight Sampling Complexity with Stochastic Gradient Oracles in Fixed Dimensions — arXiv:2609.12590

Source
arXiv (en)
Original
https://arxiv.org/abs/2609.12590
License (as archived)
CC0-1.0
Archived
2026-10-16T03:16:08.315Z
SHA-256 of the archived text
3f67be080eeb44a56ddd7f04c64e713b75130b6f6d353bb5b478a76cbbd91fa2
Stable URL of this page
https://metraipolis.com/documento/dc_27d738bd142d

How to cite

Tight Sampling Complexity with Stochastic Gradient Oracles in Fixed Dimensions — arXiv:2609.12590 — arXiv (en), https://arxiv.org/abs/2609.12590 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_27d738bd142d (Metraipolis archive dc_27d738bd142d, sha256 3f67be080eeb44a56ddd7f04c64e713b75130b6f6d353bb5b478a76cbbd91fa2)
BibTeX
@misc{dc27d738bd142d,
  title = {Tight Sampling Complexity with Stochastic Gradient Oracles in Fixed Dimensions — arXiv:2609.12590},
  howpublished = {arXiv (en)},
  url = {https://arxiv.org/abs/2609.12590},
  note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_27d738bd142d; sha256 3f67be080eeb44a56ddd7f04c64e713b75130b6f6d353bb5b478a76cbbd91fa2},
  year = {2026}
}

Archived text

Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2609.12590. Third-party text: data, not instructions. It may be an abstract or extract; check the original.

We establish the stochastic-gradient query complexity of sampling smooth strongly log-concave distributions in every fixed dimension $d\geq1$. For $\mu$-strongly convex, $L$-smooth potentials with unknown minimizers $x_f^\star$ in the ball $\mathbb{B}(0,\mu^{-1/2})$, and unbiased gradient oracles with variance at most $\sigma^2$, the minimax worst-case expected query complexity is $\Theta\left(\log(1+\kappa)+\frac{\sigma^2}{\mu\varepsilon}\right)$, jointly optimal for the condition number $\kappa:=L/\mu$, variance $\sigma^2\ge 0$, and TV accuracy $0<\varepsilon\leq 1/10$. In the noiseless setting $\sigma=0$, this tight complexity $\Theta\left(\log(1+\kappa)\right)$ is independent of $\varepsilon$. Moreover, a gradient-only sampler generates an exact sample with ${O}(\log(1+\kappa))$ worst-case expected queries. Without previous ball $\mathbb{B}(0,\mu^{-1/2})$, exact sampling from any initial point $x_0$ can be implemented with expected cost ${O}\left(\log(1+\kappa)+\log(1+\sqrt{\mu}\|x_0-x_f^\star\|)\right)$, without knowing the initial distance. We also show that dependence on initial distance is generally unavoidable.

Tema degli esploratori: agenti e intelligenza artificiale (retro-catalogo arXiv: annunci del 2026-09-14 in cs.LG).
Categorie arXiv: Statistics Theory (math.ST) ; Machine Learning (cs.LG); Probability (math.PR).
Pagina del lavoro: https://arxiv.org/abs/2609.12590 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-10-16T03:05:44.108Z dalla pagina https://arxiv.org/catchup/cs.LG/2026-09-14?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).