aiqbench analysis
Composing insight from the full article — this may take a moment.
Subpolynomial-Query Proximal Sampling Beyond Log-Concavity
arXiv:2611.03442v1 Announce Type: cross Abstract: 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\'e inequality (PI), we obtain a corresponding guarantee from a warm start with a known bound on its R\'enyi divergence. An oracle lower bound shows that a stationary point alone, which suffices under LSI, is insufficient under PI.
Abstract: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.
Machine Learning (stat.ML); Computational Complexity (cs.CC); Machine Learning (cs.LG); Statistics Theory (math.ST)
arXiv:2611.03442 [stat.ML]
(or arXiv:2611.03442v1 [stat.ML] for this version)
https://doi.org/10.48550/arXiv.2611.03442 Focus to learn more arXiv-issued DOI via DataCite (pending registration)
arXivLabs is a framework that allows collaborators to develop and share new arXiv features directly on our website.
Both individuals and organizations that work with arXivLabs have embraced and accepted our values of openness, community, excellence, and user data privacy. arXiv is committed to these values and only works with partners that adhere to them.
Have an idea for a project that will add value for arXiv's community? Learn more about arXivLabs.
Full text under the publisher's open licence · 280 words