# Algorithmic Theory of ODEs and Sampling from Well-conditioned Logconcave Densities

arXiv: https://arxiv.org/abs/1812.06243 · HTML: https://mlsanity.com/paper/1812.06243/

## Key facts

- Cited by 8 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 15 Dec 2018.

## Built on by (most cited first, 8 of 8)

- [Private Convex Optimization via Exponential Mechanism](https://mlsanity.com/paper/2203.00263/) (2022)
- [When is the Convergence Time of Langevin Algorithms Dimension Independent? A Composite Optimization Viewpoint](https://mlsanity.com/paper/2110.01827/) (2021)
- [Unadjusted Hamiltonian MCMC with Stratified Monte Carlo Time Integration](https://mlsanity.com/paper/2211.11003/) (2022)
- [High-accuracy and dimension-free sampling with diffusions](https://mlsanity.com/paper/2601.10708/) (2026)
- [Faster Sampling via Stochastic Gradient Proximal Sampler](https://mlsanity.com/paper/2405.16734/) (2024)
- [Algorithmic warm starts for Hamiltonian Monte Carlo](https://mlsanity.com/paper/2603.22741/) (2026)
- [Truncated Log-concave Sampling with Reflective Hamiltonian Monte Carlo](https://mlsanity.com/paper/2102.13068/) (2021)
- [Sampling from multi-modal distributions on Riemannian manifolds with training-free stochastic interpolants](https://mlsanity.com/paper/2602.00641/) (2026)

## Abstract (arXiv)

Sampling logconcave functions arising in statistics and machine learning has been a subject of intensive study. Recent developments include analyses for Langevin dynamics and Hamiltonian Monte Carlo (HMC). While both approaches have dimension-independent bounds for the underlying mathitcontinuous processes under sufficiently strong smoothness conditions, the resulting discrete algorithms have complexity and number of function evaluations growing with the dimension. Motivated by this problem, in this paper, we give a general algorithm for solving multivariate ordinary differential equations whose solution is close to the span of a known basis of functions (e.g., polynomials or piecewise polynomials). The resulting algorithm has polylogarithmic depth and essentially tight runtime - it is nearly linear in the size of the representation of the solution. We apply this to the sampling problem to obtain a nearly linear implementation of HMC for a broad class of smooth, strongly logconcave densities, with the number of iterations (parallel depth) and gradient evaluations being mathitpolylogarithmic in the dimension (rather than polynomial as in previous work). This class includes the widely-used loss function for logistic regression with incoherent weight matrices and has been subject of much study recently. We also give a faster algorithm with  mathitpolylogarithmic~depth for the more general and standard class of strongly convex functions with Lipschitz gradient. These results are based on (1) an improved contraction bound for the exact HMC process and (2) logarithmic bounds on the degree of polynomials that approximate solutions of the differential equations arising in implementing HMC.