Research map / Learning theory and algorithms / Sample complexity
Fast MCMC Sampling Algorithms on Polytopes
Yuansi Chen, Raaz Dwivedi, Martin J. Wainwright, Bin Yu
Read the paperCheck your idea against 137,217 papers
AI-extracted. The measured effects below were read by AI from the paper's full text (no summary yet). Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| use Vaidya walk instead of Dikin walk on hypercube with n = 2d^3 constraints | Dikin walk · Hypercube [-1,1]^d, n = 2d^3 | exponent of d in approximate mixing time: 3.84 -> 2.75 | Improved |
| use Vaidya walk instead of Dikin walk on hypercube with n = 2d^2 constraints | Dikin walk · Hypercube [-1,1]^d, n = 2d^2 | exponent of d in approximate mixing time: 2.80 -> 2.48 | Improved |
| use Vaidya walk instead of Dikin walk on hypercube with n = 2d constraints | Dikin walk · Hypercube [-1,1]^d, n = 2d | exponent of d in approximate mixing time: 1.58 -> 1.72 | Hurt |
| use Vaidya walk instead of Dikin walk as number of repeated constraints n grows | Dikin walk · Square [-1,1]^2 with repeated constraints | log-log slope of approx. mixing time vs n: 0.88 -> 0.45 | Improved |
| use Vaidya walk instead of Dikin walk on randomly generated symmetric polytopes in R^2 with n = 64 | Dikin walk · Random symmetric polytopes in R^2, n = 64 | empirical distribution uniformity | No clear effect |
| use Vaidya walk instead of Dikin walk on random symmetric polytopes with 2048 constraints | Dikin walk · Random symmetric polytopes in R^2, n = 2048 | empirical distribution uniformity | Improved |
| use Vaidya walk instead of Dikin walk on hypercube d = 50 and d = 10 (other than n = 5120) | Dikin walk · Hypercube d = 10, 50, 1-D projection trace | sequential plot jaggedness | No clear effect |
Closest papers by meaning
- Faster Sampling from Log-Concave Densities over Polytopes via Efficient Linear Solvers (ICLR 2024 · similarity 0.90)
- Log-concave Sampling from a Convex Body with a Barrier: a Robust and Unified Dikin Walk (NeurIPS 2024 · similarity 0.89)
- Sampling from Structured Log-Concave Distributions via a Soft-Threshold Dikin Walk (NeurIPS 2023 · similarity 0.88)
- Log-concave sampling: Metropolis-Hastings algorithms are fast (JMLR 2019 · similarity 0.88)
- Faster Diffusion Sampling with Randomized Midpoints: Sequential and Parallel (ICLR 2025 · similarity 0.86)
- Chain of Log-Concave Markov Chains (ICLR 2024 · 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.
