Research map / Learning theory and algorithms / Sample complexity
Log-concave Sampling from a Convex Body with a Barrier: a Robust and Unified Dikin Walk
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 a robust soft-threshold Dikin walk for log-concave sampling over polytopes (Lee-Sidford barrier) and spectrahedra (log-barrier) that tolerates approximate Hessians via approximate-acceptance-probability correction, with mixing times of order d^2 and nd respectively.
Problem
Sampling from a log-concave density over a convex body given by a self-concordant barrier is expensive per step because the barrier Hessian must be computed exactly, and prior Dikin walks either have slow mixing (depending on n) or cannot tolerate Hessian approximation without losing stationarity.
Approach
A barrier-based (rather than polytope-based) analysis of a soft-threshold Dikin walk that uses spectral approximations of the barrier Hessian for proposals, while computing the Metropolis acceptance with the approximate proposal densities so the approximate chain remains reversible with the exact target. Conditions (nu-bar symmetry, convexity of log det(H+I), bounded local norm) give mixing in O(n
Key results
- For polytopes with n constraints, the Lee-Sidford-barrier walk mixes in O~(d^2 + dL^2R^2) steps with per-step cost O~(n d^{omega-1}), improving on O~(nd + dL^2R^2) for prior log-barrier walks.
- For spectrahedra, the walk mixes in O~(nd + dL^2R^2) steps with per-iteration cost O~(n^omega + n^2 d^{3omega-5}), improving the mixing bound of Narayanan-Rakhlin's O~(n^2d^3 + n^2dL^2R^2).
- Approximate Hessians with spectral error 1/d suffice: the walk's stationary distribution remains exactly the target because acceptance uses approximate proposal densities.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use the Lee-Sidford barrier instead of the prior polytope Dikin-walk approach | Robust Dikin walk · Polytopes | mixing time: \widetilde O(nd+dL^2R^2) -> \widetilde O((d^2+dL^2R^2)\log(w/\delta)) | Helped |
| Use the robust spectral-approximation framework for the spectrahedron log-barrier Hessian | Dikin walk for spectrahedra · Spectrahedra | mixing time: \widetilde O((n^2d^3+n^2dL^2R^2)\log(w/\delta)) -> \widetilde O((nd+dL^2R^2)\log(w/\delta)) | Helped |
| Approximate the log-barrier Hessian with tensor-based sketching rather than computing it exactly | Dikin walk for spectrahedra · Spectrahedra | per-iteration cost: O(dn^\omega+n^2d^{\omega-1}) -> \widetilde O(n^\omega+n^2d^{3\omega-5}) | Helped |
Limitations
- Mixing time depends polynomially on the radius R of the enclosing ball, which the authors call unsatisfactory.
- Requires log-Lipschitz target density rather than Lipschitz f in the main results.
- For spectrahedra, the per-step cost bound is slow when n is not much larger than d because spectral error must be O(1/d).
Experimental setup
Metrics: mixing time (steps to TV distance delta) per-iteration cost
Baselines: hit-and-run Narayanan-Rakhlin Dikin walk Mangoubi-Vishnoi soft-threshold Dikin walk Kook-Vempala log-barrier walk
Builds on: Dikin walk soft-threshold Dikin walk Lee-Sidford barrier Kannan-Narayanan Dikin walk for log-concave sampling Narayanan-Rakhlin spectrahedron Dikin walk
Closest papers by meaning
- Sampling from Structured Log-Concave Distributions via a Soft-Threshold Dikin Walk (NeurIPS 2023 · similarity 0.92)
- Faster Sampling from Log-Concave Densities over Polytopes via Efficient Linear Solvers (ICLR 2024 · similarity 0.89)
- In-and-Out: Algorithmic Diffusion for Sampling Convex Bodies (NeurIPS 2024 · similarity 0.88)
- Faster Diffusion Sampling with Randomized Midpoints: Sequential and Parallel (ICLR 2025 · similarity 0.85)
- Fast Non-Log-Concave Sampling under Nonconvex Equality and Inequality Constraints with Landing (NeurIPS 2025 · similarity 0.84)
- Langevin Monte Carlo for strongly log-concave distributions: Randomized midpoint revisited (ICLR 2024 · similarity 0.84)
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.