In-and-Out: Algorithmic Diffusion for Sampling Convex Bodies

2024/05/02 by Kook, Yunbum, Vempala, Santosh S., Zhang, Matthew S. · 2 citations
#Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #FOS: Mathematics #Machine Learning (cs.LG) #Machine Learning (stat.ML) #Statistics Theory (math.ST)

paper · doi:10.48550/arxiv.2405.01425

Abstract

We present a new random walk for uniformly sampling high-dimensional convex bodies. It achieves state-of-the-art runtime complexity with stronger guarantees on the output than previously known, namely in Rényi divergence (which implies TV, W₂, KL, χ²). The proof departs from known approaches for polytime algorithms for the problem -- we utilize a stochastic diffusion perspective to show contraction to the target distribution with the rate of convergence determined by functional isoperimetric constants of the target distribution.

Cited by

• Oracle-based Uniform Sampling from Convex Bodies
• On the complexity of standard and waste-free SMC samplers

Related

• Randomized Interior Point methods for Sampling and Optimization
• Gaussian Cooling and Dikin Walks: The Interior-Point Method for Logconcave Sampling
• Hit-and-run mixing via localization schemes
• Sampling and Integration of Logconcave Functions by Algorithmic Diffusion
• Gibbs/Metropolis algorithms on a convex polytope