We propose an algorithm to sample from composite log-concave distributions over Rd, i.e., densities of the form π∝e−f−g, assuming access to gradient evaluations of f and a restricted Gaussian oracle (RGO) for g. The latter requirement means that we can easily sample from the density RGOg,h,y(x)∝exp(−g(x)−2h1∣∣y−x∣∣2), which is the sampling analogue of the proximal operator for g. If f+g is α-strongly convex and f is β-smooth, our sampler achieves ε error in total variation distance in O(κdlog4(1/ε)) iterations where κ:=β/α, which matches prior state-of-the-art results for the case g=0. We further extend our results to cases where (1) π is non-log-concave but satisfies a Poincaré or log-Sobolev inequality, and (2) f is non-smooth but Lipschitz.
We study the query complexity of obtaining a relative Fisher information guarantee for sampling from a log-smooth non-log-concave distribution; this is a sampling analog of finding an approximate stationary point in optimization. Our algorithm is based on the proximal sampler, which is an implicit discretization of the Langevin diffusion, and requires an implementation of the backward step known as the restricted Gaussian oracle (RGO). We show that by leveraging the recent results for log-concave sampling with high-accuracy guarantees in Rényi divergence, we can obtain an approximate RGO implementation that -- when used with the proximal sampler -- yields a complexity guarantee in relative Fisher information that inherits the same dimension dependence as log-concave sampling, and improves upon prior work for non-log-concave sampling. We also show a converse reduction that any improvement in the dimension dependence in relative Fisher information for non-log-concave sampling will yield an improved dimension dependence for high-accuracy log-concave sampling.
We investigate the stochastic-gradient query complexity of sampling smooth strongly log-concave distributions in any fixed Euclidean dimension. The potential is μ-strongly convex and L-smooth, with an unknown mode in the ball of radius μ−1/2 about the origin. We have access to unbiased stochastic oracles with the variance at most σ2. For every σ2≥0 and total variation (TV) accuracy 0<ε≤1/10, we prove that the tight complexity of sampling a distribution within ϵ-TV distance from the target distribution is
NTV⋆=Θ(log(1+κ)+μϵσ2),
where κ:=μL is the condition number. Note that this complexity bound is simultaneously tight for the condition number κ and accuracy ϵ. Besides, our tight complexity bound is adaptive to noiseless setting σ=0, which is NTV⋆=Θ(log(1+κ)).
We give a simple, unified, and nearly tight bound for sampling arbitrary logconcave distributions from a warm start using the In-and-Out algorithm along with exponential lifting. The main new ingredient in the analysis is an improved bound on the Poincaré constant of a lifted distribution. As a consequence, the resulting convergence rate is nearly tight for both constrained settings (e.g., Gaussian restricted to a convex body) and well-conditioned settings (e.g., strongly logconcave and smooth densities).