Gaussian Cooling and Dikin Walks: The Interior-Point Method for Logconcave Sampling
This work provides a general framework for efficient sampling in structured domains, advancing computational statistics and optimization, though it builds incrementally on prior methods like the Dikin walk.
The authors tackled the problem of developing an interior-point method (IPM) analog for structured logconcave sampling, generalizing the Dikin walk with IPM machinery to achieve efficient warm starts and handle non-uniform distributions and nonlinear constraints, resulting in the fastest algorithms for sampling uniform, exponential, or Gaussian distributions on a truncated PSD cone.
The connections between (convex) optimization and (logconcave) sampling have been considerably enriched in the past decade with many conceptual and mathematical analogies. For instance, the Langevin algorithm can be viewed as a sampling analogue of gradient descent and has condition-number-dependent guarantees on its performance. In the early 1990s, Nesterov and Nemirovski developed the Interior-Point Method (IPM) for convex optimization based on self-concordant barriers, providing efficient algorithms for structured convex optimization, often faster than the general method. This raises the following question: can we develop an analogous IPM for structured sampling problems? In 2012, Kannan and Narayanan proposed the Dikin walk for uniformly sampling polytopes, and an improved analysis was given in 2020 by Laddha-Lee-Vempala. The Dikin walk uses a local metric defined by a self-concordant barrier for linear constraints. Here we generalize this approach by developing and adapting IPM machinery together with the Dikin walk for poly-time sampling algorithms. Our IPM-based sampling framework provides an efficient warm start and goes beyond uniform distributions and linear constraints. We illustrate the approach on important special cases, in particular giving the fastest algorithms to sample uniform, exponential, or Gaussian distributions on a truncated PSD cone. The framework is general and can be applied to other sampling algorithms.