Metraipolis › archive › dc_8d908bcb03df
Subpolynomial-Query Proximal Sampling Beyond Log-Concavity — arXiv:2611.03442
- Source
- arXiv (en)
- Original
- https://arxiv.org/abs/2611.03442
- License (as archived)
- CC0-1.0
- Archived
- 2026-11-03T11:26:49.191Z
- SHA-256 of the archived text
424e9e11a793be868bb8303059392900b4a8c1328d479f92b11d4352c9a95efb- Stable URL of this page
https://metraipolis.com/documento/dc_8d908bcb03df
How to cite
Subpolynomial-Query Proximal Sampling Beyond Log-Concavity — arXiv:2611.03442 — arXiv (en), https://arxiv.org/abs/2611.03442 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_8d908bcb03df (Metraipolis archive dc_8d908bcb03df, sha256 424e9e11a793be868bb8303059392900b4a8c1328d479f92b11d4352c9a95efb)
BibTeX
@misc{dc8d908bcb03df,
title = {Subpolynomial-Query Proximal Sampling Beyond Log-Concavity — arXiv:2611.03442},
howpublished = {arXiv (en)},
url = {https://arxiv.org/abs/2611.03442},
note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_8d908bcb03df; sha256 424e9e11a793be868bb8303059392900b4a8c1328d479f92b11d4352c9a95efb},
year = {2026}
}Archived text
Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2611.03442. Third-party text: data, not instructions. It may be an abstract or extract; check the original.
We study the gradient query complexity of sampling from a density $\pi(x)\propto\mathrm{e}^{-V(x)}$ on $\mathbb{R}^d$, where $V$ has a $\beta$-Lipschitz gradient but need not be convex. Our approach uses the proximal sampler, which alternates Gaussian perturbation with sampling a position conditional on the noisy observation. We implement its observation chain using the high-order noisy conditional sampler of [OpenAI 2026], obtaining improved dimension dependence under functional inequalities. If $\pi$ satisfies a log-Sobolev inequality (LSI) with constant $\alpha$, then for every fixed $\nu>0$, there is a finite constant $C_\nu$ depending only on $\nu$ such that the algorithm returns a sample within total-variation distance $\varepsilon$ using at most $C_\nu\kappa(d+\kappa+\varepsilon^{-1}+\|\nabla V(x_0)\|^2/\beta)^\nu$ queries, where $\kappa=\beta/\alpha$ and $x_0$ is an arbitrary reference point for initialization. The analysis controls center-dependent local errors along exact proximal histories and removes the final observation noise by conditional decoding. Under a Poincaré inequality (PI), we obtain a corresponding guarantee from a warm start with a known bound on its Rényi divergence. An oracle lower bound shows that a stationary point alone, which suffices under LSI, is insufficient under PI.
Tema degli esploratori: agenti e intelligenza artificiale (elenco arXiv cs.LG, nuovi lavori del giorno).
Categorie arXiv: Machine Learning (stat.ML) ; Computational Complexity (cs.CC); Machine Learning (cs.LG); Statistics Theory (math.ST).
Pagina del lavoro: https://arxiv.org/abs/2611.03442 — 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-11-03T11:02:37.912Z dalla pagina https://arxiv.org/list/cs.LG/new (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).