Research map / Optimization / Nonconvex and smooth optimization
In-and-Out: Algorithmic Diffusion for Sampling Convex Bodies
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proposes In-and-Out, a Gibbs-style proximal/diffusion sampler (alternating Gaussian step and truncated-Gaussian step) for uniform sampling of convex bodies, with convergence guarantees in Rényi divergence governed by Poincaré/log-Sobolev constants.
Problem
Uniform sampling from high-dimensional convex bodies with strong output guarantees (beyond total variation) at state-of-the-art query complexity.
Approach
Interpret an alternating Gaussian step and membership-filtered truncated-Gaussian step as forward and backward heat flows (proximal sampler), so contraction in Rényi/chi-squared divergence follows directly from the Poincaré or log-Sobolev constant of the uniform distribution, avoiding projection oracles and laziness.
Key results
- Achieves Rényi-q divergence guarantees with e-O(q d^2 Λ log^2(M/ηε)) proper steps and e-O(q M d^2 Λ log^6(1/ηε)) expected membership queries, matching the Ball walk's TV complexity.
- Gives W2, TV, KL, and chi-squared guarantees as corollaries of the Rényi bound.
- Shows that for near-isotropic bodies the mixing bound depends only on Poincaré/log-Sobolev constants and holds for non-convex bodies for the number of proper steps.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| use In-and-Out instead of prior uniform samplers | Uniform sampling from convex bodies · Uniform sampling from convex bodies | output divergence guarantee | Helped |
| use In-and-Out instead of Ball walk | Uniform sampling from convex bodies · Uniform sampling from convex bodies | asymptotic runtime complexity | No clear effect |
| use In-and-Out instead of Hit-and-Run | Uniform sampling from convex bodies · Uniform sampling from convex bodies | asymptotic runtime complexity | Mixed |
Surprising findings
- The sampler does not need laziness (the lazy step used by Ball walk) to converge to the target stationary distribution.
Limitations
- Requires an M-warm initial distribution, and warm-start generation adds e-O(d^3) cost for well-rounded bodies.
- Relies on convexity for bounding the expected number of rejection trials; general non-log-concave sampling remains open.
Experimental setup
Metrics: Rényi divergence query complexity number of proper steps membership queries
Baselines: Ball walk Speedy walk Hit-and-Run Riemannian Hamiltonian Monte Carlo Dikin walk
Builds on: proximal sampler Ball walk Speedy walk restricted Gaussian oracle Gaussian Cooling
Closest papers by meaning
- Log-concave Sampling from a Convex Body with a Barrier: a Robust and Unified Dikin Walk (NeurIPS 2024 · similarity 0.88)
- Faster Diffusion Sampling with Randomized Midpoints: Sequential and Parallel (ICLR 2025 · similarity 0.86)
- The Sample Complexity of Gradient Descent in Stochastic Convex Optimization (NeurIPS 2024 · similarity 0.85)
- Query Lower Bounds for Diffusion Sampling (NeurIPS 2026 · similarity 0.85)
- Parallel Simulation for Log-concave Sampling and Score-based Diffusion Models (ICML 2025 · similarity 0.85)
- From stability of Langevin diffusion to convergence of proximal MCMC for non-log-concave sampling (NeurIPS 2025 · similarity 0.85)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.