Feynman Kac models 0.3cm Stability & discretization 0.6cm ...mcqmc2018.inria.fr/wp-content/uploads/2018/07/pres_MCQMC-Ferre… · Feynman–Kacmodels Stability & discretization MCQMC2018

Feynman–Kac modelsStability & discretization

MCQMC 2018

Grégoire Ferré∗? Mathias Rousset† Gabriel Stoltz∗

∗ École des Ponts ParisTech & INRIA Paris? Labex Bézout

† INRIA Rennes & IRMAR

Wednesday July 4th, 2018

Motivation Ergodicity for Markov chains Ergodicity for Feynman–Kac dynamics A word on discretization Conclusion

SituationIf this meeting is about

x −Monte Carlo

with

x ∈{Quasi,Markov Chain, Sequential,Quantum,Hamiltonian,

Multilevel,Diffusion,Langevin,Multifidelity...},

Grégoire Ferré Feynman–Kac models


SituationIf this meeting is about

x −Monte Carlo

with

x ∈{Quasi,Markov Chain, Sequential,Quantum,Hamiltonian,

Multilevel,Diffusion,Langevin,Multifidelity...},

then this talk would be on

x −Monte Carlo,

withx ∈

{Sequential,Quantum,Diffusion

},

summarized as Feynman–Kac models (also known as splitting,genealogical, branching models, etc).



Motivation

Ergodicity for Markov chains

Ergodicity for Feynman–Kac dynamics

A word on discretization

Conclusion



A rare event problem

• Consider a dynamics over X ⊂ Rd :

dXt = b(Xt)dt + σ(Xt)dBt ,

with invariant measure µ and generator L.

• Ergodicity: for a test function f

1t

∫ t

0f (Xs)ds

t→+∞−−−−→∫Xf (x)µ(dx).



A rare event problem

• Consider a dynamics over X ⊂ Rd :

dXt = b(Xt)dt + σ(Xt)dBt ,

with invariant measure µ and generator L.

• Ergodicity: for a test function f

1t

∫ t

0f (Xs)ds

t→+∞−−−−→∫Xf (x)µ(dx).

• Idea of large deviations:

P[1t

∫ t

0f (Xs)ds = a

]� e−tI (a),

where I is the rate function, or generalized entropy creation.Grégoire Ferré Feynman–Kac models


Duality and importance sampling

• Donsker-Varadhan duality [70’s]: in many cases it holds

I (a) = supk∈R

{ka− λf (k)

},

whereλf (k) = lim

t→∞

1tlogE

[ek

∫ t0 f (Xs)ds

].



Duality and importance sampling

• Donsker-Varadhan duality [70’s]: in many cases it holds

I (a) = supk∈R

{ka− λf (k)

},

whereλf (k) = lim

t→∞

1tlogE

[ek

∫ t0 f (Xs)ds

].

• Similar to study, for an observable ϕ,

Θt(µ)(ϕ) =Eµ[ϕ(Xt) e

∫ t0 f (Xs)ds

]Eµ[e∫ t0 f (Xs)ds

] .

• This procedure weights the trajectories depending on f .



Natural questions

One may wonder:

• for which class of functions f does λf exists?

• under which conditions Θt admits a long time limit?

• how can we discretize in time for numerical purposes?

• how to sample efficiently the expectations?



Natural questions

One may wonder:

• for which class of functions f does λf exists?

• under which condition Θt admits a long time limit?

• how can we discretize in time for numerical purposes?

• how to sample efficiently the expectations?



Link with filtering & Sequential Monte Carlo

In Sequential Monte Carlo/filtering, we generally consider theweighted path measure

Qn(dx0:n) =1Ln

{G0(x0)

t∏k=1

Gk(xk−1, xk)}M0(dx0)

n∏k=1

Mk(xk−1, xk).

Analogies:

• Gk(xk−1, xk)↔ ef (xk−1) with «potential» f ,

• Mk ↔ Q(x , ·) = E[xk ∈ ·

∣∣ xk−1 = x]homogeneous transition

kernel,

• Ln ↔ (efQ)n1 = E[e∑n−1

k=0 f (xk )]accumulated weight up to

time n (sometimes written γn(1)).



Numerics – Sequential Monte Carlo

• Dynamics (xn+1, yn+1) = (xn, yn)− 0.1(xn, yn) + Gn ∈ R2,• Weight function f (x , y) = x .

-1

-0.5

0

0.5

1

-0.5 0 0.5 1 1.5

y

x

The weight

wnm = exp

(n−1∑k=0

f (xmk )

).

of particle m at time n is usedfor resampling(renormalization).





-1

-0.5

0

0.5

1

-0.5 0 0.5 1 1.5

y

x

The weight

wnm = exp

(n−1∑k=0

f (xmk )

).






-1

-0.5

0

0.5

1

-0.5 0 0.5 1 1.5

y

x

The weight

wnm = exp

(n−1∑k=0

f (xmk )

).






-1

-0.5

0

0.5

1

-0.5 0 0.5 1 1.5

y

x

The weight

wnm = exp

(n−1∑k=0

f (xmk )

).






-1

-0.5

0

0.5

1

-0.5 0 0.5 1 1.5

y

x

The weight

wnm = exp

(n−1∑k=0

f (xmk )

).






-1

-0.5

0

0.5

1

-0.5 0 0.5 1 1.5

y

x

The weight

wnm = exp

(n−1∑k=0

f (xmk )

).


Conclusion: the particles areselected towards the right.



Motivation




Conclusion



Markov chains and ergodicity

A homogeneous Markov chain (xn)n∈N is defined through itsevolution operator Q:

Qϕ(x) := E[ϕ(x1) | x0 = x ] =

∫Xϕ(y)Q(x , dy).

A measure µ∗ ∈ P(X ) is invariant if ∀A ⊂ X :

µ∗Q(A) :=

∫Xµ∗(dx)Q(x ,A) = µ(A).

The process is ergodic when, for any initial distribution µ,

µQn n→+∞−−−−→ µ∗.



Big picture I

b

b

bb

b

Trajectory of the Markov chain

Measurable set A

Probability µQn(A)



An ergodic theorem

Theorem [M. Hairer & J. Mattingly]

Assume there exist W : X → R+, γ ∈ (0, 1) and C > 0 suchthat

(L) PW ≤ γW + C ,

and α > 0, η ∈ P(X ) such that

(M) infx∈C

P(x , ·) ≥ αη(·),

for C a large enough level set of W . Then, there exist a uniqueµ∗ ∈ P(X ), C > 0 and α ∈ (0, 1) such that for any µ ∈ P(X )

‖Pnµ− µ∗‖W ≤ C αn‖µ− µ∗‖W .

Here: ‖f ‖ = supx∈X

|f (x)|1 + W (x)

, ‖µ−ν‖W = sup‖ϕ‖≤1

∫Xϕ(x)(µ−ν)(dx).



Motivation




Conclusion



Feynman–Kac models

We consider:• a kernel operator Q f with Q f 6= 1;• a dynamics Φn : P(X )→ P(X ) defined by, for testsfunctions ϕ

Φn(µ)(φ) =µ((Q f )nϕ

)µ((Q f )n1

) = (Φn)(µ)(ϕ) with Φ(µ)(ϕ) =µ(Q f ϕ

)µ(Q f 1

) .



Feynman–Kac models

We consider:• a kernel operator Q f with Q f 6= 1;• a dynamics Φn : P(X )→ P(X ) defined by, for testsfunctions ϕ

Φn(µ)(φ) =µ((Q f )nϕ

)µ((Q f )n1

) = (Φn)(µ)(ϕ) with Φ(µ)(ϕ) =µ(Q f ϕ

)µ(Q f 1

) .Typically• Q f = efQ, where Q defines a Markov chain (xn)n∈N;• then

Φn(µ)(φ) =Eµ[ϕ(xn) e

∑n−1k=0 f (xk )

]Eµ[e∑n−1

k=0 f (xk )] .




Theorem [G.F., M. Rousset & G. Stoltz, yesterday]Assumptions:

• Lyapunov condition: there exist W : X → [1,+∞), γn∞−→ 0,

bn ≥ 0 and compact sets Kn s.t.

(L) Q fW (x) ≤ γnW (x) + bn1Kn ;

• Minorization condition: ∀ n ≥ 1, there exist αn > 0, ηn ∈ P(X )s.t.

(M) ∀ x ∈ Kn, Q f (x , ·) ≥ αnηn(·);

• X is Polish and Q f is «locally strong Feller».

Then, there exist a unique µ∗f and α ∈ (0, 1) such that for any µ ∈P(X ), ∃Cµ > 0 for which

‖Φn(µ)− µ∗f ‖W ≤ Cµαn, and Φ(µ∗f ) = µ∗f .



Big picture II

b

b

bb

b

A trajectory of the Markov chain

Measurable set A

Probability Φn(µ)(A)

bb

b

b

b

Another trajectory

Measurable set B

Probability Φn(µ)(B)



Sketch of proof

The steps of the proof are as follows:

• Q f is quasi-compact in L∞W (X ) = {ϕ : sup |ϕ|/W < +∞};

• the spectral radius Λ is an eigenvalue with «positive»eigenvector h:

Q f h = Λh ;



Sketch of proof




Q f h = Λh;

• define the Markovian kernel Qh = Λh−1Q f h;

• Φn is rewritten

Φn(µ)(φ) =µ(h(Qh)nh−1ϕ

)µ(h(Qh)nh−1

) ;

• the kernel Qh = Λh−1Q f h satifies the conditions of Hairer andMattingly’s theorem.



Sketch of proof




Q f h = Λh;

• define the Markovian kernel Qh = Λh−1Q f h;

• Φn is rewritten

Φn(µ)(φ) =µ(h(Qh)nh−1ϕ

)µ(h(Qh)nh−1

) ;

• the kernel Qh = Λh−1Q f h satifies the conditions of Hairer andMattingly’s theorem.



Toy model application

Consider the following Markov chain in Rd :

xn+1 = ρxn + σGn,

with ρ ∈ (−1, 1), (Gn)n∈N standard Gaussian r.v.



Toy model application

Consider the following Markov chain in Rd :

xn+1 = ρxn + σGn,

with ρ ∈ (−1, 1), (Gn)n∈N standard Gaussian r.v.

Then, the Feynman–Kac dynamics is stable if

f (x) ≤ a|x |p + c ,

with a > 0, c ∈ R, and 0 ≤ p < 2. The Lyapunov function is

W (x) = eβx2, with 0 < β <

1− ρ2

2σ2 .



Back to O.U. process

• Dynamics (xn+1, yn+1) = (xn, yn)− 0.1(xn, yn) + Gn ∈ R2,• Weight function f (x , y) = a|x |α, a > 0.

-1

-0.5

0

0.5

1

-0.5 0 0.5 1 1.5

y

x





-1

-0.5

0

0.5

1

-0.5 0 0.5 1 1.5

y

x





-1

-0.5

0

0.5

1

-0.5 0 0.5 1 1.5

y

x

Conclusion: for α > 2, thealgorithm blows up!





-1

-0.5

0

0.5

1

-0.5 0 0.5 1 1.5

y

x


For α = 2 there is a limitvalue a∗.





-1

-0.5

0

0.5

1

-0.5 0 0.5 1 1.5

y

x







-1

-0.5

0

0.5

1

-0.5 0 0.5 1 1.5

y

x





Motivation




Conclusion



DiscretizationGoal: discretize in time the quantity


∫ t0 f (Xs)ds


] .



DiscretizationGoal: discretize in time the quantity


∫ t0 f (Xs)ds


] .

Idea: discretize (Xt) into xn ≈ Xn∆t , and consider e.g.

Φn,∆t(µ)(φ) =Eµ[ϕ(xn) e

∑n−1k=0 f (xk )∆t

]Eµ[e∑n−1

k=0 f (xk )∆t] .

Other possible choice:

Φn,∆t(µ)(φ) =Eµ[ϕ(xn) e

∑n−1k=0

f (xk )+f (xk+1)

2 ∆t]

Eµ[e∑n−1

k=0f (xk )+f (xk+1)

2 ∆t] .



DiscretizationUnder verifiable conditions and if X is bounded, the followingtheorem holds.

Theorem: error estimate on the invariant measure [G.F.,G. Stoltz, 2017]

There exist µ∗f , µ∗f ,∆t ∈ P(X ) such that ∀µ ∈ P(X )

Θt(µ)t→+∞−−−−→ µ∗f , Φn(µ)

n→+∞−−−−→ µ∗f ,∆t .

Moreover, there exist p ≥ 1 and ψ solution to a Poisson equationsuch that∫Xϕ dµ∗f ,∆t =

∫Xϕ dµ∗f + ∆tp

∫Xϕψ dµ∗f + O(∆tp+1).



Application

Overdamped Langevin dynamics on a one dimensional torus.

1.254

1.256

1.258

1.26

1.262

0 0.005 0.01 0.015 0.02 0.025 0.03 0.035

Avera

ge

∆t

MC 1st-order

MC hybrid

MC 2nd-order

Galerkin 1st-order

Galerkin 2nd-order

Average estimate for:

• dXt = (−V ′(Xt) + 1)dt + dBt ,

• V (x) = 0.02 cos(2πx),

• f = |V |2,

• ϕ = ef

• Euler-Maruyama scheme and2nd order modified scheme,

• comparison to Galerkindiscretization.



Conclusion

Take home message:

• new results on the ergodicity of Feynman–Kac dynamics;

• easily verifiable conditions;

• natural extension of the theory for Markov chains;

• numerical analysis for discretizations of SDE’s;

• possible directions: applications to SPDE’s, link with largedeviations theory, application to systems of interactingparticles...



References

Pierre Del Moral and Alice Guionnet.On the stability of interacting processes with applications to filteringand genetic algorithms.Annales de l’IHP Probabilités et statistiques, 37(2):155–194, 2001.

G. F., Mathias Rousset, and Gabriel Stoltz.More on the stability of Feynman–Kac semigroups.arXiv:1807.00390, 2018.

G. F. and Gabriel Stoltz.Error estimates on ergodic properties of Feynman–Kac semigroups.arXiv:1712.04013, 2017.

Martin Hairer and Jonathan C. Mattingly.Yet another look at Harris’ ergodic theorem for Markov chains.In Seminar on Stochastic Analysis, Random Fields and ApplicationsVI, pages 109–117. Springer, 2011.

Luc Rey-Bellet.Ergodic properties of Markov processes.In Open Quantum Systems II, pages 1–39. Springer, 2006.



Spectrum of quasi-compact operators

Spectral radius Λ

Essential spectral radius θ

b

b

b

b

b

b

b b

b

b

b

b

b

Discrete spectrum

C

Essential spectrum


Documents

Feynman Kac models 0.3cm Stability & discretization 0.6cm ...mcqmc2018.inria.fr/wp-content/uploads/2018/07/pres_MCQMC-Ferre… · Feynman–Kacmodels Stability & discretization MCQMC2018