Lecture

Convergence of Langevin Monte Carlo: Tail Growth and Smoothness

Graph Chat

Chat with Graph Search

Ask any question about EPFL courses, lectures, exercises, research, news, etc. or try the example questions below.

DISCLAIMER: The Graph Chatbot is not programmed to provide explicit or categorical answers to your questions. Rather, it transforms your questions into API requests that are distributed across the various IT services officially administered by EPFL. Its purpose is solely to collect and recommend relevant references to content that you can explore to help you answer your questions.

Description

This lecture by the instructor explores the convergence properties of Langevin Monte Carlo (LMC) algorithms, focusing on the interplay between tail growth and smoothness of the target distribution. The lecture covers topics such as the sampling from Gibbs measures, the transition from discrete algorithms to continuous diffusion, and the convergence analysis of LMC under different growth rates. It also delves into the theoretical guarantees for LMC, the role of degenerately convex potentials, and the modified Log-Sobolev inequality. The main theorem presented in the lecture establishes the conditions under which LMC achieves fast convergence rates for a wide class of potentials, including non-convex and non-smooth functions.

Official source

Related concepts (31)

Numerical stability

In the mathematical subfield of numerical analysis, numerical stability is a generally desirable property of numerical algorithms. The precise definition of stability depends on the context. One is numerical linear algebra and the other is algorithms for solving ordinary and partial differential equations by discrete approximation. In numerical linear algebra, the principal concern is instabilities caused by proximity to singularities of various kinds, such as very small or nearly colliding eigenvalues.

Numerical analysis

Numerical analysis is the study of algorithms that use numerical approximation (as opposed to symbolic manipulations) for the problems of mathematical analysis (as distinguished from discrete mathematics). It is the study of numerical methods that attempt at finding approximate solutions of problems rather than the exact ones. Numerical analysis finds application in all fields of engineering and the physical sciences, and in the 21st century also the life and social sciences, medicine, business and even the arts.

Numerical methods for ordinary differential equations

Numerical methods for ordinary differential equations are methods used to find numerical approximations to the solutions of ordinary differential equations (ODEs). Their use is also known as "numerical integration", although this term can also refer to the computation of integrals. Many differential equations cannot be solved exactly. For practical purposes, however – such as in engineering – a numeric approximation to the solution is often sufficient. The algorithms studied here can be used to compute such an approximation.

Diffusion

Diffusion is the net movement of anything (for example, atoms, ions, molecules, energy) generally from a region of higher concentration to a region of lower concentration. Diffusion is driven by a gradient in Gibbs free energy or chemical potential. It is possible to diffuse "uphill" from a region of lower concentration to a region of higher concentration, like in spinodal decomposition. Diffusion is a stochastic process due to the inherent randomness of the diffusing entity and can be used to model many real-life stochastic scenarios.

Monte Carlo method

Monte Carlo methods, or Monte Carlo experiments, are a broad class of computational algorithms that rely on repeated random sampling to obtain numerical results. The underlying concept is to use randomness to solve problems that might be deterministic in principle. They are often used in physical and mathematical problems and are most useful when it is difficult or impossible to use other approaches. Monte Carlo methods are mainly used in three problem classes: optimization, numerical integration, and generating draws from a probability distribution.

Related lectures (64)

Explicit Stabilised Methods: Applications to Bayesian Inverse Problems

Explores explicit stabilised Runge-Kutta methods and their application to Bayesian inverse problems, covering optimization, sampling, and numerical experiments.

Nonlinear Equations: Fixed Point Method Convergence

Covers the convergence of fixed point methods for nonlinear equations, including global and local convergence theorems and the order of convergence.

Efficient Stochastic Numerical Methods

Explores efficient stochastic numerical methods for modeling and learning, covering topics like the Analytical Engine and kinase inhibitors.

Numerics: semester project

Covers the semester project on numerics, focusing on adaptive algorithms and multistep methods.

Implicit Schemes in Numerical Analysis