Fast Algorithms for Multivariate ODEs arising in Sampling and Learning
summary
Proposes a practical algorithm that solves the multivariate ODEs behind Hamiltonian Monte Carlo by approximating trajectories with low‑degree polynomials and running a collocation method whose iterations are O(log 1/ε) and each iteration costs d function evaluations for degree d. Proves polynomial approximability via complex-analytic derivative bounds and directional-derivative calculus, and reports a concrete cost for logistic regression sampling: linear in n and κ^{1.5} (up to polylog factors).
AI-written summary · about
chapters (20)
- 0:00Intro
- 0:36Ordinary Differential Equations
- 3:23Focus application: Sampling
- 3:57Sampling via diffusion
- 6:10Hamiltonian Monte Carlo
- 9:46Known guarantees for sampling
- 12:04An improved contraction bound
- 17:54Proof of contraction HMC ODE
- 19:26Proof of contraction: distance stays bounded
- 22:37ODE algorithms
- 23:33Back to first-order ODE
- 26:50Proof of P-L lemma
- 28:12Collocation method
- 29:12Collocation algorithm
- 29:36First-order ODE guarantee
- 30:17Implementing HMC
- 30:42Polynomial approximations
- 31:13Derivatives of high dimensional functions? Idea reduce estimating derivatives of general functions to one-variable functions.
- 32:12Guarantee for logistic loss
- 32:39Features of collocation
related talks
12mIterative Methods and High-Dimensional Statistics
01h 10mAn Introduction to Hamiltonian Monte Carlo Method for Sampling
31mThe Convergence of Hamiltonian Monte Carlo
01h 07mStochastic Second Order Optimization Methods I
01h 07mOptimization Crash Course (continued)
01h 18mOptimization I
01h 03mSampling for Linear Algebra, Statistics, and Optimization I
32mMonte Carlo Sampling Approach to Solving Stochastic Multistage Programs