In-and-Out: Algorithmic Diffusion for Sampling Convex Bodies
Authors: Yunbum Kook, Santosh Vempala, Matthew Zhang
NeurIPS 2024 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | The contribution of this paper is primarily theoretical, and the paper does not contain any experimental results. 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, W2, KL, χ2). 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 stationary density. |
| Researcher Affiliation | Academia | Yunbum Kook School of Computer Science Georgia Institute of Technology yb.kook@gatech.edu Santosh S. Vempala School of Computer Science Georgia Institute of Technology vempala@gatech.edu Matthew S. Zhang Department of Computer Science, University of Toronto, matthew.zhang@mail.utoronto.ca |
| Pseudocode | Yes | Algorithm 1 In-and-Out |
| Open Source Code | No | The paper does not contain experiments and therefore does not require data or code. |
| Open Datasets | No | The paper does not contain experiments. |
| Dataset Splits | No | The paper does not contain experiments. |
| Hardware Specification | No | The paper does not contain experiments. |
| Software Dependencies | No | The paper does not contain experiments. |
| Experiment Setup | No | The paper does not contain experiments. |