Double Randomized Underdamped Langevin with Dimension-Independent Convergence Guarantee
Authors: Yuanshi Liu, Cong Fang, Tong Zhang
NeurIPS 2023 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | This paper focuses on the high-dimensional sampling of log-concave distributions with composite structures: p (dx) exp( g(x) f(x))dx. We develop a double randomization technique, which leads to a fast underdamped Langevin algorithm with a dimension-independent convergence guarantee. We prove that the algorithm enjoys an overall e O (tr(H))1/3 ϵ2/3 iteration complexity to reach an ϵ-tolerated sample whose distribution p admits W2(p, p ) ϵ. Here, H is an upper bound of the Hessian matrices for f and does not explicitly depend on dimension d. For the posterior sampling over linear models with normalized data, we show a clear superiority of convergence rate which is dimension-free and outperforms the previous best-known results by a d1/3 factor. The analysis to achieve a faster convergence rate brings new insights into high-dimensional sampling. |
| Researcher Affiliation | Academia | School of Intelligence Science and Technology, Peking University Department of Computer Science & Engineering, the Hong Kong University of Science and Technology {liu_yuanshi, fangcong}@pku.edu.cn, tongzhang@tongzhang-ml.org |
| Pseudocode | Yes | Algorithm 1 Double-Randomized Underdamped Langevin (DRUL) |
| Open Source Code | No | The paper does not provide any statement or link regarding the availability of open-source code for the described methodology. |
| Open Datasets | Yes | As shown in Figure 1(a), the Gram matrix of the MNIST dataset, which is also the Hessian of Bayesian ridge linear regression, has rapidly decreasing eigenvalues. |
| Dataset Splits | No | The paper is theoretical and discusses convergence rates and complexities. It does not describe an experimental setup with training, validation, and test dataset splits. |
| Hardware Specification | No | The paper is theoretical and focuses on algorithm design and convergence analysis. It does not describe specific experimental setups or hardware used to obtain empirical results. |
| Software Dependencies | No | The paper focuses on theoretical contributions and does not provide details on specific software dependencies with version numbers for reproducibility. |
| Experiment Setup | No | The paper is theoretical and focuses on algorithm design and convergence analysis. It does not provide specific details about an experimental setup, such as hyperparameters or training configurations. |