非凸分布采样新算法：超越对数凹性的近端采样复杂度分析
Subpolynomial-Query Proximal Sampling Beyond Log-Concavity
理论向的文章：作者改进了近端采样器在非凸密度下的查询复杂度，LSI 条件下得到次多项式查询上界，还证明了 PI 情形的 oracle 下界。做采样理论的朋友可以看看证明思路。
论文研究从密度 π(x)∝e^{-V(x)} 采样的梯度查询复杂度，其中 V 只需满足 β-Lipschitz 梯度而不必凸。方法采用近端采样器（proximal sampler），交替进行高斯扰动与基于噪声观测的条件采样，并用 [OpenAI 2026] 的高阶噪声条件采样器实现观测链。若 π 满足常数 α 的对数 Sobolev 不等式（LSI），算法在总变差距离 ε 内返回样本，查询次数上界为 C_ν·κ(d+κ+ε^{-1}+‖∇V(x_0)‖²/β)^ν，其中 κ=β/α。论文还给出 Poincaré 不等式（PI）条件下的暖启动保证，并证明在 PI 下仅有驻点信息不够，需给出 oracle 下界。
Subpolynomial-Query Proximal Sampling Beyond Log-Concavity
We study the gradient query complexity of sampling from a density $π(x)\propto\mathrm{e}^{-V(x)}$ on $\mathbb{R}^d$, where $V$ has a $β$-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 $π$ satisfies a log-Sobolev inequality (LSI) with constant $α$, then for every fixed $ν>0$, there is a finite constant $C_ν$ depending only on $ν$ such that the algorithm returns a sample within total-variation distance $\varepsilon$ using at most $C_νκ(d+κ+\varepsilon^{-1}+\|\nabla V(x_0)\|^2/β)^ν$ queries, where $κ=β/α$ 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.