Complexity of Non-Log-Concave Sampling in Fisher Information
For researchers in sampling and optimization, this work provides a theoretical advance in non-log-concave sampling complexity, though it is incremental as it builds on existing proximal sampler and log-concave results.
The paper presents a sampling algorithm for non-log-concave distributions that achieves a relative Fisher information guarantee with dimension dependence matching log-concave sampling, improving over prior work. It also shows that any further improvement would imply better dimension dependence for high-accuracy log-concave sampling.
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.