Composite Logconcave Sampling with a Restricted Gaussian Oracle
This addresses sampling challenges in high-dimensional statistics and machine learning for models with non-smooth constraints, offering a more efficient and general method than prior approaches.
The paper tackles the problem of sampling from composite log-concave densities with non-smooth convex terms by introducing an algorithm that uses a restricted Gaussian oracle, achieving a runtime of O(κ² d log²(κd/ε)) iterations to reach total variation distance ε. It shows experimental improvements over hit-and-run for sampling Gaussian restrictions to the positive orthant.
We consider sampling from composite densities on $\mathbb{R}^d$ of the form $dπ(x) \propto \exp(-f(x) - g(x))dx$ for well-conditioned $f$ and convex (but possibly non-smooth) $g$, a family generalizing restrictions to a convex set, through the abstraction of a restricted Gaussian oracle. For $f$ with condition number $κ$, our algorithm runs in $O \left(κ^2 d \log^2\tfrac{κd}ε\right)$ iterations, each querying a gradient of $f$ and a restricted Gaussian oracle, to achieve total variation distance $ε$. The restricted Gaussian oracle, which draws samples from a distribution whose negative log-likelihood sums a quadratic and $g$, has been previously studied and is a natural extension of the proximal oracle used in composite optimization. Our algorithm is conceptually simple and obtains stronger provable guarantees and greater generality than existing methods for composite sampling. We conduct experiments showing our algorithm vastly improves upon the hit-and-run algorithm for sampling the restriction of a (non-diagonal) Gaussian to the positive orthant.