[Submitted on 12 May 2026 (v1), last revised 15 Oct 2026 (this version, v3)]
Abstract:We propose an algorithm to sample from composite log-concave distributions over $mathbb{R}^d$, i.e., densities of the form $pipropto e^{-f-g}$, assuming access to gradient evaluations of $alpha_f$-convex $f$ and a restricted Gaussian oracle (RGO) for $alpha_g$-convex $g$, where $alpha_g ge 0$. The latter requirement means that we can easily sample from the density $text{RGO}_{g,h,y}(x) propto exp(-g(x) -frac{1}{2h}||y-x||^2)$, which is the sampling analogue of the proximal operator for $g$. If $f + g$ is $alpha$-convex and $f$ is $beta$-smooth, our sampler achieves $varepsilon$ error in total variation distance using $widetilde{mathcal O}(kappa sqrt d log^4(1/varepsilon))$ oracle calls where $kappa := 1 vee beta/alpha$, with $0le alpha_g le beta$ and $alpha := alpha_f + alpha_g > 0$, which matches prior state-of-the-art results for the case $g=0$. We further extend our results to cases where (1) $pi$ is non-log-concave but satisfies a Poincaré or log-Sobolev inequality, and (2) $f$ is non-smooth but Lipschitz.
Submission history
From: Linghai Liu [view email]
[v1] Tue, 12 May 2026 17:48:09 UTC (121 KB)
[v2] Wed, 14 Oct 2026 09:23:20 UTC (124 KB)
[v3] Thu, 15 Oct 2026 04:23:14 UTC (124 KB)