PaperlayerView exact revision on arXiv

Source-linked AI summary

The Randomized Midpoint Method for Log-Concave Sampling

Ruoqi Shen, Yin Tat Lee

arXiv:1909.05503v1cs.LGcs.DSmath.PRstat.ML

TL;DR

High-dimensional log-concave sampling is important across several fields, yet existing algorithms have substantial dimension or condition-number dependencies. The paper proposes a differential-equation discretization framework and reports an improved sampling complexity bound.

  • Problem

    High-dimensional log-concave sampling is central across several fields, while existing algorithms have dimension or condition-number dependencies.

    Source: §1 · p. 1

  • Method

    The paper proposes a framework for discretizing differential equations, using fixed-point iterations to approximate solutions.

    Source: §1.1 · pp. 2, 4

  • Results

    ˜O(κ^7/6/ϵ^1/3 + κ/ϵ^2/3) steps achieve ϵ accuracy, with better dependence on κ and ϵ than previous algorithms.

    Source: §1 · p. 2

  • Takeaways & Limitations

    With suitable unbiased integral estimators, the framework may yield faster algorithms for SDEs unrelated to sampling.

    Source: §1.1 · p. 4

    The analysis assumes f is twice continuously differentiable, m-strongly convex, and has an L-Lipschitz gradient.

    Source: §3.1 · p. 5

Abstract

from arXiv · show

Sampling from log-concave distributions is a well researched problem that has many applications in statistics and machine learning. We study the distributions of the form $p^{*}\propto\exp(-f(x))$, where $f:\mathbb{R}^{d}\rightarrow\mathbb{R}$ has an $L$-Lipschitz gradient and is $m$-strongly convex. In our paper, we propose a Markov chain Monte Carlo (MCMC) algorithm based on the underdamped Langevin diffusion (ULD). It can achieve $\epsilon\cdot D$ error (in 2-Wasserstein distance) in $\tilde{O}\left(\kappa^{7/6}/\epsilon^{1/3}+\kappa/\epsilon^{2/3}\right)$ steps, where $D\overset{\mathrm{def}}{=}\sqrt{\frac{d}{m}}$ is the effective diameter of the problem and $\kappa\overset{\mathrm{def}}{=}\frac{L}{m}$ is the condition number. Our algorithm performs significantly faster than the previously best known algorithm for solving this problem, which requires $\tilde{O}\left(\kappa^{1.5}/\epsilon\right)$ steps. Moreover, our algorithm can be easily parallelized to require only $O(\kappa\log\frac{1}{\epsilon})$ parallel steps. To solve the sampling problem, we propose a new framework to discretize stochastic differential equations. We apply this framework to discretize and simulate ULD, which converges to the target distribution $p^{*}$. The framework can be used to solve not only the log-concave sampling problem, but any problem that involves simulating (stochastic) differential equations.

1 Introduction

The paper introduces a randomized midpoint approach for log-concave sampling, reporting improved iteration complexity and a framework for discretizing differential equations. Its contributions include changes to fixed-point iteration and error estimation, alongside potential applications beyond sampling.

1 Introduction

  • High-dimensional log-concave sampling is central in statistics, machine learning, and theoretical computer science, with applications including Bayesian estimation, volume computation, and bandit optimization.Source: §1 · p. 1
  • The algorithm has no dependence on d and is the first with better than 1/ϵ dependence that is neither Metropolis-adjusted nor based on extra assumptions.The cited examples of extra assumptions include high-order smoothness.Source: §1 · p. 1
  • ˜O(κ^7/6/ϵ^1/3 + κ/ϵ^2/3) steps improve dependence on κ and ϵ; in high dimensions, the κ^7/6 bound approaches the believed natural κ barrier.Previous fastest algorithms take ˜O(κ^1.5) or ˜O(d^4) steps.Source: §1 · p. 2

1.1 Contributions

  • The randomized midpoint method extends fixed-point iteration to SDEs without reducing them to ODEs [29], and uses a uniformly random time to reduce deterministic error accumulation.Source: §1.1 · p. 3
  • Two iterations of T suffice to achieve the best theoretical guarantee.Source: §1.1 · p. 3
  • The authors believe the framework can extend to other function classes and support faster algorithms for SDEs unrelated to sampling, given suitable unbiased integral estimators.Source: §1.1 · p. 4

1.2 Paper Organization

  • The paper outlines background and assumptions, presents the algorithm and main result, and places proofs and supporting analyses in appendices.Source: §1.2 · p. 4

2 Background

Log-concave sampling algorithms choose a Markov process with the target distribution as its stationary distribution, then discretize and simulate it. This paper focuses on discretizing ULD with a two-step fixed-point iteration and describes a parallel version.

2 Background

  • MCMC sampling commonly selects a process whose stationary distribution equals or approximates the target, then discretizes and simulates it until sufficiently close.Langevin diffusion and Hamiltonian Monte Carlo are among the processes discussed.Source: §2 · p. 4, §2.1 · p. 4

2.1 Choosing the Markov Process

  • ULD is the paper’s chosen process because it may be appropriate for sampling as accelerated gradient descent is for convex optimization.ULD has also been described as accelerated gradient descent for sampling [39].Source: §2.1 · pp. 4–5

2.2 Discretizing the Process

  • A two-step fixed-point iteration applied to ULD reduces discretization error compared with existing methods.The paper applies the iteration to general differential equations and uses it to simulate ULD.Source: §2.2 · p. 5
  • The algorithm can be parallelized to reduce the number of steps required.The supplied passage does not include the parallel-step bound.Source: §2.2 · p. 5
  • The paper does not combine its process with a Metropolis-Hastings step, focusing instead on dimension-independent results; its comparison assumes strong convexity and a Lipschitz gradient.The text notes that a β-warm start can depend exponentially on dimension, yielding an Ω(d^1.5) total dependence, and excludes results using bounded higher-order derivatives from the comparison.Source: §2.2 · p. 5

3 Notations and Definitions

The paper assumes a twice continuously differentiable, strongly convex function with a Lipschitz gradient. It measures sampling accuracy by the 2-Wasserstein distance to the target, relative to an effective scale D.

3 Notations and Definitions

  • ˜O(f) denotes O(f) multiplied by a polylogarithmic factor in f.The paper writes this factor as log^O(1)(f).Source: §3 · p. 5

3.1 Assumptions on f

  • The function f is twice continuously differentiable, has an L-Lipschitz gradient, and is m-strongly convex.The condition number is κ = L/m, and the algorithm accesses gradients through an oracle.Source: §3.1 · p. 5
  • Algorithm 1 initializes RandomMidpoint with (x0, v0, N, h) and samples α uniformly from [0, 1].The supplied algorithm lines also begin a Gaussian random-variable generation step.Source: §3.1 · p. 6

3.2 Wasserstein Distance

  • The sampling target is a W2 distance below ε·D between the generated-point distribution and the target distribution.D is defined in the paper context as √(d/m).Source: §3.2 · p. 6

4 Algorithms and Results

The paper uses underdamped Langevin diffusion (ULD) to target the log-concave distribution, then discretizes it with a randomized midpoint method. A generalized interval-based version supports parallel computation.

4.1 Underdamped Langevin Diffusion (ULD)

  • ULD has the target distribution as its position marginal, and its contraction bound combines with discretization-error bounds to establish algorithmic convergence.The paper studies ULD with u = 1/L.Source: §4.1 · p. 6

4.2 Randomized Midpoint Method

  • The randomized midpoint method provides a more accurate approximation than the earlier method and reduces total runtime.For twice-differentiable f, two fixed-point iterations suffice for the stated theoretical guarantee.Source: §4.2 · p. 7
  • The authors suspect that more fixed-point iterations may help when f has higher-order derivatives.The framework is presented as applicable to other SDEs.Source: §4.2 · p. 8

4.3 A More General Algorithm

  • The generalized algorithm divides the time interval into R pieces and computes the approximations in parallel, with K depending logarithmically on κ and ε.Algorithm 1 is the special case R = 1 and K = 2.Source: §4.3 · p. 9

5 Numerical Experiments

The experiments compare randomized midpoint sampling with an earlier algorithm across two datasets. The appendices also describe Brownian-motion sampling and properties used in the proofs.

5 Numerical Experiments

  • The experiments report that the ε-dependence analyses of the randomized midpoint method and [10] are both tight.The comparison uses liver-disorders and breast-cancer datasets; the authors note that the logistic function permits higher-order methods.Source: §5 · pp. 10–11

A Brownian Motion Simulation

  • Conditional on α, the Brownian-motion construction uses two independent, mean-zero Gaussian pairs that can be sampled directly.The pairs are (G1, H1) and (G2, H2).Source: A Brownian Motion Simulation · p. 15

B Properties of the ULD and the Brownian motion

B.1 Properties of the ULD

This subsection develops bounds for the ULD trajectory under a small-step assumption, supporting the discretization-error analysis.

B.1 Properties of the ULD

  • Lemma 6 states bounds for the ULD trajectory when h ≤ 1/20 and u = 1/L.The supplied passage does not expose the bound expressions.Source: §B.1 · p. 16
  • The proof bounds trajectory quantities using the definition of ULD, the L-Lipschitz gradient assumption, and inequalities including Cauchy–Schwarz.It also invokes an earlier Brownian-motion bound.Source: §B.1 · pp. 16–17
  • The proof’s final step relies on h being small.The supplied proof excerpts do not give the resulting bound values.Source: §B.1 · pp. 17–18

B.2 Properties of the Brownian Motion

This subsection uses Doob’s maximal inequality to establish bounds for Brownian motion over a short time interval.

B.2 Properties of the Brownian Motion

  • Doob’s maximal inequality is the stated tool for deriving the Brownian-motion bound in Lemma 8.The lemma assumes a short interval.Source: §B.2 · pp. 18–19
  • The proof applies Doob’s inequality to establish the lemma’s Brownian-motion bounds.The excerpt does not expose the full bound expressions.Source: §B.2 · p. 19
  • For h ≤ 1/10, the stated inequality bounds the integral of e^(4s) over [0,h] by (5/4)h, giving a linear-in-h upper bound under this condition.Source: §B.2 · p. 19

C Discretization Error of Algorithm 1

This section bounds the per-iteration discretization error of Algorithm 1. Its analysis compares an algorithm iterate with an ideal underdamped Langevin trajectory coupled through shared Brownian motion.

C Discretization Error of Algorithm 1

D Bounds on ∥∇f(x)∥and ∥v∥

This section bounds the accumulated gradient and velocity norms along Algorithm 1's iterates. It gives per-iteration lemmas under small-step conditions and uses the resulting bounds in the algorithm's guarantee.

D Bounds on ∥∇f(x)∥and ∥v∥

Proof of Theorem 3

The proof of Theorem 3 combines Lemmas 12 and 2. The excerpt also sets up a comparison with an exact underdamped Langevin diffusion and states terminal moment bounds.

Proof of Theorem 3

F Discretization Error of Algorithm 2

This section analyzes one-step discretization error for Algorithm 2. It frames comparisons between intermediate values and an ideal underdamped Langevin trajectory across substeps.

F Discretization Error of Algorithm 2

Related papers

Loading 1909.05503v1…