Fast and Efficient Parallel Sampling Using Higher Order Langevin Dynamics
Fuente:
arXiv
Saved in:
| Main Authors: | , , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866911659786764288 |
|---|---|
| author | Mahajan, Jaideep Zhang, Kaihong Liang, Feng Liu, Jingbo |
| author_facet | Mahajan, Jaideep Zhang, Kaihong Liang, Feng Liu, Jingbo |
| contents | We study parallel sampling from high-dimensional strongly log-concave distributions. Langevin-based samplers converge rapidly in continuous time, but their discretizations are typically sequential and often require polynomially many steps in the dimension $d$, the target accuracy $\varepsilon^{-1}$, or both. Picard-based parallel sampling methods reduce this sequential depth to polylogarithmic scale by solving for many time-discretization points in parallel; however, existing guarantees often require a polynomial number of processors, leading to substantial memory and gradient-evaluation costs in high dimensions.
We show that higher-order Langevin structure can reduce this parallel resource burden while preserving polylogarithmic sequential depth. Our method combines arbitrary-order Langevin dynamics with blockwise Lagrange polynomial interpolation. This sharper discretization reduces the number of parallel points required to achieve a target accuracy. Our results cover both higher-order smooth potentials and ridge-separable potentials, including models such as Bayesian logistic regression and two-layer neural networks, and improve upon the space complexity of the current literature on parallel log-concave sampling. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2510_18242 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Fast and Efficient Parallel Sampling Using Higher Order Langevin Dynamics Mahajan, Jaideep Zhang, Kaihong Liang, Feng Liu, Jingbo Statistics Theory Methodology Machine Learning We study parallel sampling from high-dimensional strongly log-concave distributions. Langevin-based samplers converge rapidly in continuous time, but their discretizations are typically sequential and often require polynomially many steps in the dimension $d$, the target accuracy $\varepsilon^{-1}$, or both. Picard-based parallel sampling methods reduce this sequential depth to polylogarithmic scale by solving for many time-discretization points in parallel; however, existing guarantees often require a polynomial number of processors, leading to substantial memory and gradient-evaluation costs in high dimensions. We show that higher-order Langevin structure can reduce this parallel resource burden while preserving polylogarithmic sequential depth. Our method combines arbitrary-order Langevin dynamics with blockwise Lagrange polynomial interpolation. This sharper discretization reduces the number of parallel points required to achieve a target accuracy. Our results cover both higher-order smooth potentials and ridge-separable potentials, including models such as Bayesian logistic regression and two-layer neural networks, and improve upon the space complexity of the current literature on parallel log-concave sampling. |
| title | Fast and Efficient Parallel Sampling Using Higher Order Langevin Dynamics |
| topic | Statistics Theory Methodology Machine Learning |
| url | https://arxiv.org/abs/2510.18242 |