1 of 34

Kirill Neklyudov

Langevin Dynamics

for sampling and

global optimization

2 of 34

Goals of this talk

  • Introduction to the Langevin dynamics
  • Derive basics (1st half)
  • Outline some important results (2nd half)
  • Recommend some literature

3 of 34

Langevin Equation

Ito Stochastic Differential Equation (SDE):

Force

Random fluctuations

Discrete approximation:

4 of 34

1-d simulation

Langevin equation

Fokker-Planck equation

5 of 34

Derivation of the Fokker-Planck equation

Langevin equation:

Increments of the Brownian motion:

Consider a small increment of :

6 of 34

Derivation of the Fokker-Planck equation

Using the change of variables formula, we obtain:

Density of particle distribution:

Unknown density!

7 of 34

Changing variables

The change of variables:

We can’t invert this

8 of 34

Changing variables

9 of 34

Changing variables

From the previous slide:

Equation for the increment

(Langevin equation)

Note that

since

10 of 34

Changing variables

Finally!

With a little more efforts (homework):

Reminder:

11 of 34

Derivation of the Fokker-Planck equation

Change of variables

Increment of the density

???

12 of 34

Derivation of the Fokker-Planck equation

0th order:

1st order:

2nd order:

13 of 34

Taking the expectation

0th order:

1st order:

14 of 34

Taking the expectation (2nd order)

15 of 34

Derivation of the Fokker-Planck equation

Increment of the density

Taylor series

0

16 of 34

5 min break

17 of 34

Fokker-Planck equation

18 of 34

Stationary distribution of the Langevin dynamics

With a little efforts (homework), we obtain:

when

(density does not change anymore)

Let

Gibbs distribution

19 of 34

Sampling via the Langevin dynamics

Particles have the stationary distribution:

Gibbs distribution

Langevin equation

We want to sample from

Note!

20 of 34

Sampling via the Langevin dynamics

Stochastic Differential Equation for sampling:

Discrete approximation:

More popular way:

21 of 34

Langevin dynamics for the Bayesian inference

Predictive distribution

We need samples

Langevin equation

Discrete approximation

???

???

22 of 34

Borkar, Mitter, 1999

Consider a SDE:

Theorem

Discrete approximation:

Stationary distribution

Stationary distribution

23 of 34

Sketch of the proof

Lemma

24 of 34

What happened to the noise?

Lemma says

Original dynamics

The same but integrated

Our approximation

Free speed-up?

25 of 34

What happened to the noise?

Computational efforts are hidden here

26 of 34

Sketch of the proof

Lemma 1

Stationary distribution

Theorem

Stationary distribution

Lemma 2

27 of 34

Global optimization

28 of 34

Temperature annealing

Langevin equation

Particles have the stationary distribution:

Gibbs distribution

Concentrates on the global minima

29 of 34

Annealing example

30 of 34

Distribution of particles

Langevin equation

???

Annealing schedule

Theorem:

31 of 34

Distribution of particles

Annealing schedule

Theorem:

32 of 34

Continuous process

Discrete approximation

Stationary distribution

Discretization error

Convergence speed

33 of 34

Further reading

34 of 34

The end