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

Yin Tat Lee, Zhao Song, Santosh S. VempalaarXiv 2018 · arXiv

Introduction: The Challenge of High-Dimensional Sampling

In fields ranging from statistics to machine learning, sampling from high-dimensional "logconcave" distributions is a fundamental task. While the continuous mathematical processes underlying popular methods like Hamiltonian Monte Carlo (HMC) are incredibly efficient—often independent of the dimension ($d$)—the discrete algorithms implemented on computers frequently suffer from the "curse of dimensionality."

To prevent discretization errors from accumulating, traditional solvers must take very small steps, causing the number of function evaluations to grow polynomially with $d$ (e.g., $d^{0.5}$ or $d^1$). This paper introduces a nearly linear-time algorithm for solving multivariate Ordinary Differential Equations (ODEs) and applies it to revolutionize high-dimensional sampling, achieving the first sampling algorithm with polylogarithmic parallel depth.

Methodology: From ODEs to Efficient Sampling

The paper attacks the discretization gap from two primary angles: a general theory for ODEs and a specific improvement to the HMC process.

1. The Collocation Method

The authors adapt the "collocation method," a classical numerical technique. The core insight is that if an ODE's solution remains close to the span of a known basis (such as polynomials), the entire trajectory can be solved rapidly. They prove that for a wide class of ODEs, the complexity of solving the equation is nearly equivalent to the complexity of representing the solution itself.

2. Polynomial Approximation and HMC

They demonstrate that the specific ODEs arising in HMC—which describe the path a sample takes—can be approximated by piecewise low-degree polynomials. This allows the collocation method to solve HMC steps in parallel with polylogarithmic depth. Additionally, the authors provide a new contraction bound for HMC, showing that the process converges at a rate of $\kappa^{1.5}$ (where $\kappa$ is the condition number), an improvement over the previous benchmark of $\kappa^2$.

The Hamiltonian Monte Carlo (HMC) Algorithm analyzed in this work.

Key Insights: Representation as Complexity

The most profound insight of this work is that the bottleneck for solving an ODE is not necessarily the mathematical difficulty, but the complexity of describing the solution. If the solution is smooth enough to be represented as a low-degree polynomial, it can be solved in nearly linear time.

Furthermore, because the collocation method solves for the entire path simultaneously rather than stepping through time sequentially, it is highly parallelizable. This leads to "polylogarithmic depth," meaning that increasing the number of dimensions has a minimal impact on the computational "thickness" of the process.

Results: Breaking the Curse of Dimensionality

The paper's results represent a significant leap in complexity bounds for sampling from smooth, strongly logconcave densities:

  • Dimension Independence: The number of iterations (parallel depth) and gradient evaluations is polylogarithmic in the dimension $d$. Previous state-of-the-art methods required $d^{0.25}$ to $d^{0.5}$ iterations.
  • Total Runtime: The algorithm achieves nearly linear total runtime relative to the size of the representation.
  • HMC Efficiency: The authors achieve a sampling complexity of $\tilde{O}(\kappa^{1.5} d)$ for strongly convex functions with Lipschitz gradients, significantly faster than previous $\kappa^2 \sqrt{d}$ benchmarks.

Limitations and Future Work

While the results are groundbreaking, they come with specific requirements. The most impressive "polylogarithmic" results require the target density to be highly smooth (possessing many bounded derivatives). For functions that are only twice-differentiable, the gains remain significant but are less "dimension-free."

Additionally, the specific application to logistic regression relies on an "incoherence" assumption for weight matrices. Future work may explore "decomposable" functions—where the loss is a sum of many terms—by incorporating stochastic optimization techniques to further enhance efficiency.

Summary updated

Abstract

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 $\mathit{continuous}$ 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 $\mathit{polylogarithmic}$ 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 $ \mathit{polylogarithmic~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.
BibTeX
@misc{lee2018algorithmic,
  author = {Yin Tat Lee and Zhao Song and Santosh S. Vempala},
  title = {{Algorithmic Theory of ODEs and Sampling from Well-conditioned Logconcave Densities}},
  year = {2018},
  eprint = {1812.06243},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1812.06243},
}
Figure