Faster Sampling from Log-Concave Densities over Polytopes via Efficient Linear Solvers
Authors: Oren Mangoubi, Nisheeth K. Vishnoi
ICLR 2024 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | We consider the problem of sampling from a log-concave distribution π(θ) e f(θ) constrained to a polytope K := {θ Rd : Aθ b}, where A Rm d and b Rm. The fastest-known algorithm Mangoubi & Vishnoi (2022) for the setting when f is O(1)-Lipschitz or O(1)-smooth runs in roughly O(md mdω 1) arithmetic operations... We present a nearly-optimal implementation of this Markov chain with per-step complexity which is roughly the number of non-zero entries of A while the number of Markov chain steps remains the same. The key technical ingredients are 1) to show that the matrices that arise in this Dikin walk change slowly, 2) to deploy efficient linear solvers that can leverage this slow change to speed up matrix inversion by using information computed in previous steps, and 3) to speed up the computation of the determinantal term in the Metropolis filter step via a randomized Taylor series-based estimator. This result directly improves the runtime for applications that involve sampling from Gibbs distributions constrained to polytopes that arise in Bayesian statistics and private optimization. |
| Researcher Affiliation | Academia | Oren Mangoubi Worcester Polytechnic Institute Nisheeth K. Vishnoi Yale University |
| Pseudocode | Yes | Section 3 is titled "Algorithm" and includes "Algorithm 1: Fast implementation of soft-threshold Dikin walk" which provides structured pseudocode. |
| Open Source Code | No | The paper does not include any statement about making its code open source or providing a link to a code repository. |
| Open Datasets | No | The paper mentions applications and examples such as "Bayesian Lasso logistic regression" but does not describe the use of any specific public dataset for experimental evaluation within the paper itself. It is a theoretical paper. |
| Dataset Splits | No | The paper focuses on theoretical algorithm development and analysis, not empirical experiments. Therefore, it does not provide dataset split information for training, validation, or testing. |
| Hardware Specification | No | The paper focuses on theoretical algorithmic improvements and complexity analysis. It does not describe any empirical experiments, and therefore, no hardware specifications are mentioned. |
| Software Dependencies | No | The paper focuses on theoretical algorithmic improvements and complexity analysis. It does not describe any empirical experiments, and therefore, no software dependencies with specific version numbers are mentioned. |
| Experiment Setup | No | The paper is theoretical and focuses on algorithm design and analysis. It does not describe an experimental setup with specific hyperparameters or training configurations for empirical validation. |