Research map / Learning theory and algorithms / Matrix and tensor methods
Faster Sampling from Log-Concave Densities over Polytopes via Efficient Linear Solvers
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.
Speeds up the soft-threshold Dikin walk for sampling log-concave densities over polytopes from O(md^{ω-1}) to nearly nnz(A)+d² per step, using efficient linear solvers with slowly-changing Hessians and a randomized sigmoid-series estimator for the determinant ratio.
Problem
Sampling from a log-concave distribution proportional to exp(-f) constrained to a polytope {θ: Aθ ≤ b}; prior fastest Dikin-walk implementations spend md^{ω-1} arithmetic operations per step on matrix inversion and determinant computation.
Approach
Show that the soft-threshold regularized log-barrier Hessian changes slowly in Frobenius norm w.r.t. the local norm, so an efficient inverse-maintenance linear solver can be reused across steps; estimate the Metropolis determinant ratio unbiasedly via randomized Taylor/sigmoid series expansions with two overlapping regions of convergence.
Key results
- Per-step cost reduced from md^{ω-1} to nnz(A)+d^2 (up to polylog factors), giving total runtime Õ((md + dL²R²) log(w/δ)) × (nnz(A)+d²+T_f) for L-Lipschitz f.
- Improvement over prior soft-threshold Dikin walk by at least d^{ω-2} when T_f = Ω(d²), and by d^{ω-1} when nnz(A)=O(m) and m ≥ d².
- Bayesian Lasso logistic regression example achieves Õ(d⁴) operations versus prior Õ(d^{2+ω}).
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use efficient inverse maintenance and randomized determinant estimation to implement the soft-threshold Dikin walk | Soft-threshold Dikin walk for L-Lipschitz log-concave sampling on polytopes · Log-concave sampling on polytopes, L-Lipschitz f | arithmetic operations: \tilde{O}((md + d L^2 R^2)\times (md^{\omega-1}+ T_f)) -> \tilde{O}((md + d L^2 R^2) \log(\frac{w}{\delta})) \times (\ma | Helped |
| Use efficient inverse maintenance and randomized determinant estimation to implement the soft-threshold Dikin walk | Soft-threshold Dikin walk for β-smooth log-concave sampling on polytopes · Log-concave sampling on polytopes, β-smooth f | arithmetic operations: \tilde{O}((md + d \beta R^2)\times (md^{\omega-1} + T_f) -> \tilde{O}((md + d \beta R^2) \log(\frac{w}{\delta})) \times | Helped |
| Use the proposed fast implementation | Bayesian Lasso logistic regression sampling · Bayesian Lasso logistic regression | arithmetic operations: \tilde{O}(d^{2+\omega}) -> \tilde{O}(d^{4}); d^{\omega-2} | Helped |
| Use the proposed fast implementation | Bayesian Lasso logistic regression sampling · Bayesian Lasso logistic regression | arithmetic operations: \tilde{O}(d^5) -> \tilde{O}(d^{4}); d | Helped |
| Use efficient inverse maintenance for the regularized barrier Hessian | Soft-threshold Dikin walk · Per-step computation | arithmetic operations: md^{\omega-1} -> \mathrm{nnz}(A) + d^2 | Helped |
Limitations
- The d² term in the per-step cost is not removed; authors suggest a different linear solver might remove it.
- Overall runtime remains a larger polynomial in d than fastest linear programming methods.
- Theoretical result only; no empirical experiments reported.
Experimental setup
Metrics: arithmetic operation count total variation distance
Baselines: soft-threshold Dikin walk (Chen-Dwivedi-Mishra style implementation) Dikin walk with fast linear solver for f≡0
Builds on: Dikin walk soft-threshold Dikin walk efficient inverse maintenance (Lee-Sidford-style)
Closest papers by meaning
- Log-concave Sampling from a Convex Body with a Barrier: a Robust and Unified Dikin Walk (NeurIPS 2024 · similarity 0.89)
- Chain of Log-Concave Markov Chains (ICLR 2024 · similarity 0.89)
- Faster Diffusion Sampling with Randomized Midpoints: Sequential and Parallel (ICLR 2025 · similarity 0.88)
- Parallel Simulation for Log-concave Sampling and Score-based Diffusion Models (ICML 2025 · similarity 0.87)
- Zeroth-Order Sampling Methods for Non-Log-Concave Distributions: Alleviating Metastability by Denoising Diffusion (NeurIPS 2024 · similarity 0.86)
- Langevin Monte Carlo for strongly log-concave distributions: Randomized midpoint revisited (ICLR 2024 · similarity 0.86)
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.