Nonasymptotic bounds for sampling algorithms without log-concavity

Mateusz B. Majka, Aleksandar Mijatović, Łukasz SzpruchThe Annals of Applied Probability 2020 · DOI

TL;DR

This paper develops new theoretical tools to analyze sampling algorithms for high-dimensional probability distributions, specifically focusing on Euler schemes for stochastic differential equations (SDEs). The key innovation is relaxing the common assumption of log-concavity, which is often too restrictive, and instead introducing a "log-concavity at infinity" condition. This allows for non-asymptotic convergence guarantees for a broader class of problems, including those with randomized or inaccurate drift functions, and has implications for efficient multi-level Monte Carlo methods.

What Problem Does This Paper Address?

Sampling from complex, high-dimensional probability distributions is a fundamental problem in many scientific fields, from machine learning to statistical physics. A common approach is to use algorithms based on discretizing stochastic differential equations (SDEs), such as the Euler scheme. Analyzing the convergence of these algorithms, particularly how quickly they approach the true target distribution (non-asymptotic analysis), is crucial for understanding their performance.

Traditionally, much of this analysis has relied on the assumption that the target distribution is "log-concave." While powerful, this assumption is often too strict and doesn't apply to many interesting distributions (e.g., those arising from double-well potentials). This paper addresses the challenge of providing rigorous convergence guarantees for these sampling algorithms without the log-concavity assumption. Specifically, they aim to derive non-asymptotic bounds on the distance between the distribution generated by the discrete-time algorithm and the true invariant distribution of the continuous-time SDE, even when the drift function is not globally well-behaved or when the drift is estimated with some noise.

Methods

The core of the paper's contribution lies in developing novel mathematical techniques to overcome the limitations of existing methods.

  • Relaxing Log-Concavity: The authors replace the strict log-concavity assumption with a weaker condition called "contractivity at infinity." This condition ensures that the drift function becomes contractive as the state space grows large, which is sufficient for certain types of convergence.
  • Novel Coupling Construction: A key technical innovation is a new method for constructing "couplings" of Markov chains. Couplings are a way to compare two random processes by defining them on the same probability space. The authors introduce a hybrid coupling that combines a synchronous coupling (for when the processes are close) with a "mirror coupling" (for when they are far apart and the drift is not contractive). This allows them to control both $L^1$ and $L^2$ Wasserstein distances simultaneously.
  • Pseudo-Distance Functions: To analyze the coupled processes, they define and utilize specialized "Wasserstein-type pseudo-distances" based on carefully constructed concave and convex functions. These functions are tailored to the specific properties of the drift and the coupling.
  • Perturbation Inequalities: The paper derives new perturbation inequalities that quantify how the distance between the algorithm's output and the true distribution changes when the drift function is slightly modified (e.g., due to inaccurate estimation).
  • Multi-level Monte Carlo (MLMC) Analysis: The developed tools are applied to analyze MLMC estimators, which are designed to reduce variance by using multiple levels of discretization.

Datasets

Not discussed in the paper. The paper is theoretical and focuses on the mathematical properties of algorithms rather than empirical evaluation on specific datasets.

Key Insights and Ideas

  • Log-concavity is not always necessary: The paper demonstrates that rigorous convergence guarantees can be achieved for sampling algorithms even when the target distribution is not log-concave, by focusing on behavior at infinity. This significantly broadens the applicability of theoretical analysis.
  • A clever coupling is key: The novel hybrid coupling strategy is central to the paper's success. It elegantly handles different regimes of the drift function, allowing for simultaneous control of $L^1$ and $L^2$ distances, which is a significant technical advance.
  • Randomized drifts don't necessarily hurt weak convergence rate: Surprisingly, the paper shows that the variance of a randomized drift does not influence the rate of weak convergence of the Euler scheme to the SDE. This is an important theoretical finding for algorithms that use noisy gradient estimates.
  • Bridging theory and practice: The work provides a solid theoretical foundation for algorithms used in practice, such as those employing randomized gradients or multi-level Monte Carlo methods, by offering non-asymptotic bounds.

Key Results

  • Novel non-asymptotic $L^2$ convergence rates: The paper provides explicit convergence rates for Euler schemes under the "contractivity at infinity" condition, expressed in terms of problem parameters.
  • Bounds for randomized drifts: Non-asymptotic bounds are derived for the distance between Euler schemes and invariant laws of SDEs, even when the drift is randomized or inaccurate.
  • Analysis of Multi-level Monte Carlo (MLMC): The framework is used to obtain bounds for MLMC estimators, suggesting potential improvements in computational complexity.
  • Weak convergence analysis: The paper provides a weak convergence analysis that covers both standard and randomized drift cases, revealing the independence of the convergence rate from the variance of the randomized drift.

Limitations and Future Work

  • Optimality of constants: While the paper provides precise convergence rates, it remains an open question whether the constants in these bounds are truly optimal, especially given the more general contractivity assumption.
  • Trade-off analysis for MLMC: The paper mentions that the choice of parameters for MLMC involves a trade-off between variance reduction and convergence speed, and a precise analysis of this trade-off is left for future work.
  • Generalization to other algorithms: The techniques developed are primarily for Euler schemes. Extending them to other discretization schemes or sampling methods could be a fruitful direction.
  • Practical implementation of coupling: While the coupling is theoretically powerful, its practical implementation and computational cost in high dimensions might require further investigation.

Summary updated

Abstract

Discrete time analogues of ergodic stochastic differential equations (SDEs) are one of the most popular and flexible tools for sampling high-dimensional probability measures. Non-asymptotic analysis in the $L^2$ Wasserstein distance of sampling algorithms based on Euler discretisations of SDEs has been recently developed by several authors for log-concave probability distributions. In this work we replace the log-concavity assumption with a log-concavity at infinity condition. We provide novel $L^2$ convergence rates for Euler schemes, expressed explicitly in terms of problem parameters. From there we derive non-asymptotic bounds on the distance between the laws induced by Euler schemes and the invariant laws of SDEs, both for schemes with standard and with randomised (inaccurate) drifts. We also obtain bounds for the hierarchy of discretisation, which enables us to deploy a multi-level Monte Carlo estimator. Our proof relies on a novel construction of a coupling for the Markov chains that can be used to control both the $L^1$ and $L^2$ Wasserstein distances simultaneously. Finally, we provide a weak convergence analysis that covers both the standard and the randomised (inaccurate) drift case. In particular, we reveal that the variance of the randomised drift does not influence the rate of weak convergence of the Euler scheme to the SDE.
BibTeX
@article{majka2020nonasymptotic,
  author = {Mateusz B. Majka and Aleksandar Mijatović and Łukasz Szpruch},
  title = {{Nonasymptotic bounds for sampling algorithms without log-concavity}},
  journal = {The Annals of Applied Probability},
  year = {2020},
  doi = {10.1214/19-aap1535},
}
Figure