Montreal, November 2002

Annealed Feynman-Kac models

Pierre DEL MORAL LSP-C.N.R.S, Univ. Paul Sabatier, F-Toulouse.

↪ Annealed Feynman-Kac Models, join work with Laurent Miclo, Communications in Mathematical Physics (2003)

Notations (E, E) measurable space

P(E) = {μ probability on E }
B_{b}(E) = {f : E → ℝ bounded + E-measurable }

• (μ, f) ∈ P(E) × B_{b}(E) ⟶ μ(f) = ∫ f(x)μ(dx)

• M(x, dx′) Markov kernel on E

μM(dx′) = ∫ μ(dx)M(x, dx′) and M(f)(x) = ∫ M(x, dx′)f(x′)

• ⌊a⌋ = integer part of a ∈ ℝ Annealed Feynman-Kac models

• Markov X_{n} ∈ E, M(x, dx′), η_{0} ∈ P(E).

• Potential G_{α} : E → (0, ∞) s.t. lim_{α→∞} G_{α} = G : E → [0, ∞).

• α(n) → ∞, (ex.: G_{α(n)} = e^{−α(n)V} → 1_{V^{−1}(0)} )

η_{n}(f) = γ_{n}(f)/γ_{n}(1) and η̂_{n}(f) = γ̂_{n}(f)/γ̂_{n}(1)

with

γ_{n}(f) = 𝔼_{η_{0}}(f(X_{n}) ∏_{p=0}^{n−1} G_{α(p)}(X_{p})) and γ̂_{n}(f) = γ_{n}(fG_{α(n)})

Concentration Find α(n) ↑ ∞ and A ∈ E s.t. lim_{n→∞} η̂_{n}(A) = 1 + decays rates Annealed FK and Interacting particle systems Nonlinear m.v.p.:

η_{n+1} = Φ_{α(n)}(η_{n}) or η̂_{n} = Φ̂_{α(n)} (η̂_{n−1}) ∈ P(E)

η_{n} \underrightarrow{updating} η̂_{n} = Ψ_{α(n)}(η_{n}) = \frac{1}{η_{n}(G_{α(n)})} G_{α(n)} dη_{n} \underrightarrow{prediction} η_{n+1} = η̂_{n}M

N-IPS: ξ_{n} ∈ E^{N} Markov

ξ_{n} \underrightarrow{selection} ξ̂_{n} \underrightarrow{mutation} ξ_{n+1}

• ξ_{n} → ξ̂_{n} = (ξ̂_{n}^{1}, …, ξ̂_{n}^{N}) “iid” Ψ_{α(n)}(\frac{1}{N} ∑_{i=1}^{N} δ_{ξ_{n}^{i}}) = ∑_{i=1}^{N} \frac{G_{α(n)}(ξ_{n}^{i})}{∑_{j=1}^{N} G_{α(n)}(ξ_{n}^{j})} δ_{ξ_{n}^{i}}

• ξ̂_{n}^{i} → ξ_{n}^{i} ∼ M(ξ̂_{n}^{i},.)

5

Ex.1: physics [trapping analysis], G_{α} = e^{−αV}, c = cemetery state.

X_{n}^{c} \underrightarrow{absorbtion} X̂_{n}^{c} \underrightarrow{exploration} X_{n+1}^{c}

• ℙ(X̂_{n}^{c} ∈ dx | X_{n}^{c}) = e^{−α(n)V (X_{n}^{c})} δ_{X_{n}^{c}} + (1 − e^{−α(n)V (X_{n}^{c})} ) δ_{c}.

• ℙ(X_{n+1}^{c} ∈ dx | X̂_{n}^{c}) = M(X̂_{n}^{c}, dx) if X̂_{n}^{c} ≠ c (otherwise X_{n+1}^{c} = c).

γ̂_{n} = ℙ(X̂_{n}^{c} ∈., T^{c} > n), γ̂_{n}(1) = ℙ(T^{c} > n) ⇒ η̂_{n} = ℙ(X̂_{n}^{c} ∈. | T^{c} > n) Note : (Guionnet-DM, IHP (01))

(α(n) = α) + M mixing ⟹ ∃! μ_{α} = Φ̂_{α} (μ_{α}) ∈ P(E)

Ex.2: statistics, MCMC [Feynman-Kac-Metropolis] Target Gibbs’:

π_{α}(dy) = \frac{1}{ν(e^{−αV})} e^{−αV (y)} ν(dy) ∈ P(S) with ν reversible w.r.t. K(y, dy′)

FK-model:

• X_{n} = (Y_{n}, Y_{n+1} ) ∈ E = (S × S), with Y_{n} Markov K and Y_{0} = y_{0}.

• G_{α}(y, y′) = e^{−α(V (y′)−V (y))} (×e^{−αosc (V)})

⟹^{α(n)=α}  \begin{aligned}η̂_{n}(d(y, y′)) & = ℙ_{π_{α}}((Y_{1}, Y_{0}) ∈ d(y, y′) | Y_{n+1} = y_{0}) \\ & → π_{α}(dy′)K(y′, dy) = (π_{α} × K)_{2}(d(y, y′)) \end{aligned}

Note : (Doucet-DM, Interacting Metropolis models, Séminaire Probab. (03)) K mixing ⟹ (π_{α} × K)_{2} = Φ̂_{α} ((π_{α} × K)_{2}) unique .../...

Concentration analysis • Contraction of nonlinear Feynman-Kac semi-groups.

• Fixed point oscillations α → μ_{α} = Φ̂_{α} (μ_{α})

Def. annealed FK-models α′(n) ↑ ∞, and Δ(α) ↑ ∞ • Time mesh t(n + 1) = t(n) + Δ′(n), with Δ′(n) = Δ(α′(n))

• Cooling schedule α(p) = α′(n) for all t(n) < p ≤ t(n + 1)

t(n) < p ≤ t(n + 1) ⟶ η̂_{p} = Φ̂_{α′(n)} (η̂_{p−1})

Key decomposition [contraction (Φ̂_{α}^{n} = Φ̂_{α}^{n−1} ∘ Φ̂_{α} ) +oscillations (α → μ_{α})]

η̂_{t(n+1)} − μ_{α′(n+1)} = [Φ̂_{α′(n)}^{Δ′(n)} (η̂_{t(n)}) − Φ̂_{α′(n)}^{Δ′(n)} (μ_{α′(n)})] + [μ_{α′(n)} − μ_{α′(n+1)} ]

Feynman-Kac-Metropolis model Gibbs’ target π_{α}(dy) ∝ e^{−αV (y)} ν(dy) − (ν K − rev. ) ⟶ μ_{α} = Φ̂_{α} (μ_{α}) = (π_{α} × K)_{2} Mixing hyp. (K)_{m} ∃(m, ϵ(K)) : K^{m}(y,.) ≥ ϵ(K) K^{m}(y′,.) Prop.1 If Δ(α) = (m + 1) (2 + ⌊a (b + α osc (V))⌋), with (a, b) ∼ ϵ(K). Then

• ∥Φ̂_{α}^{Δ(α)} (η_{1}) − Φ̂_{α}^{Δ(α)} (η_{2})∥_{tv} ≤ \frac{1}{e} ∥η_{1} − η_{2}∥_{tv}

• ∥(π_{α_{1}} × K)_{2} − (π_{α_{2}} × K)_{2}∥_{tv} ≤ \frac{1}{2} |α_{1} − α_{2}| osc (V)

Th.1

• lim_{n→∞}[α′(n + 1) − α′(n)] = 0 ⟹ lim_{n→∞} ∥η̂_{t_{n}} − (π_{α′(n)} × K)_{2}∥_{tv} = 0

• If α′(n) = (n + 1)^{a}, a ∈ (0, 1), then t(n) = O(n^{1+a} ) and

(n + 1)^{1−a} ∥η̂_{t_{n}} − (π_{α′(n)} × K)_{2}∥_{tv} ≤ 4 (1 + a osc (V))

Notes : • If V_{ν} = essinf _{ν}(V) then ∀ϵ > 0, lim_{α→∞} π_{α}({V ≥ V_{ν} + ϵ}) = 0.

• Non linear FK-simulated annealing with “sub-linear” cooling schedule.

Annealed FK model [(Markov kernel,potential)=(M, e^{−αV})] Mixing hyp. (M)_{m} ∃(m, ϵ(M)) : M^{m}(x,.) ≥ ϵ(M) M^{m}(x′,.) Prop.2 If Δ(α) = m (1 + ⌊a e^{α δ(m)}(b + α δ(m))⌋), with (a, b) ∼ ϵ(M) and δ(m) = (m − 1) osc (V), then

• ∥Φ̂_{α}^{Δ(α)} (η_{1}) − Φ̂_{α}^{Δ(α)} (η_{2})∥_{tv} ≤ \frac{1}{e} ∥η_{1} − η_{2}∥_{tv}

• ∥μ_{α_{1}} − μ_{α_{2}}∥_{tv} ≤ osc (V) |α_{1} − α_{2}| Δ(α_{1} ∧ α_{2}) Note : (M)_{m=1} ⟹ Δ(α) = 1 + ⌊ab⌋ Th.2

• (M)_{m=1}

– lim_{n→∞}[α′(n + 1) − α′(n)] = 0 ⟹ lim_{n→∞} ∥η̂_{t_{n}} − μ_{α′(n)}∥_{tv} = 0

– If α′(n) = (n + 1)^{a}, a ∈ (0, 1), then t(n) = O(n^{1+a} ) and

∥η̂_{t_{n}} − μ_{α′(n)}∥_{tv} ≤ c(a)/(n + 1)^{1−a}

• (M)_{m>1} If α′(n) = α′(0) log (n + e) with b = δ(m)α′(0) < 1 Then t(n) = O(n^{1+b} log n) and

∥η̂_{t_{n}} − μ_{α′(n)}∥_{tv} ≤ c(b) log (n + e) /(n + 1)^{1−b}

Pb : • Find asymptotic concentration levels (V_{ν} = essinf _{ν}(V)).

• Conjecture: lim_{α→∞} μ_{α}({V ≥ V_{ν} + ϵ}) = 0?→ in general false when m > 1 Hyp. (M)_{m=1}

μ_{α}(f) = Φ̂_{α} (μ_{α})(f) = \frac{μ_{α}Q_{α}(f)}{μ_{α}Q_{α}(1)} with Q_{α}(f) = M(e^{−αV} f)

For any f ≥ 0

ϵ(M) \frac{ν(e^{−αV} f)}{ν(e^{−αV})} ≤ μ_{α}(f) ≤ \frac{1}{ϵ(M)} \frac{ν(e^{−αV} f)}{ν(e^{−αV})}

⟹ concentration level = V_{ν} Large deviation analysis (M)_{m}

• ∃! ν = νM and μ_{α} = Φ̂_{α} (μ_{α}).

• L_{n} = \frac{1}{n} ∑_{p=1}^{n} δ_{X_{p}} LDP I(μ) = inf_{K:μK=μ} \{∫ μ(dx) Ent (K(x,.)|M(x,.))\}.

• Varadhan’s FK-representation (∀μ) → log-Lyapunov exp. s.g. Q_{α}

Λ(−αV) = lim_{n→∞} \frac{1}{n} log 𝔼_{μ}(e^{nL_{n}(−αV)}) = sup_{η} (η(−αV) − I(η))

Lemma [Variational pb.]

\frac{1}{α} log μ_{α}(e^{αV}) = inf_{μ} (μ(V) + \frac{1}{α}I(μ)) ⟶ V_{I} = inf_{I(μ)<∞} μ(V) ≥ V_{ν}

Note :

⟹ lim_{α→∞} \frac{1}{α} log μ_{α}(V ≥ V_{I} + ϵ) ≤ −ϵ Concentration levels

V_{I} = − lim_{α→+∞} \frac{1}{α} lim_{n→∞} \frac{1}{n} log \underbrace{𝔼_{x}[exp (−α ∑_{p=1}^{n}V (X_{p}))]}_{≥M(x,x)^{n} exp (−nαV (x))}

Prop.1: V_{I} ≤ V_{M} = inf {V (x) ; x ∈ E , M(x, x) > 0} Note: [diagonal mutations] (∀x ∈ E , M(x, x) > 0) ⟹ V_{I} = V_{ν} Finite state space |E| < ∞ M-path energy: V : P = (x_{1}, …, x_{n}) ↦ V (P) = \frac{1}{n} ∑_{p=1}^{n} V (x_{p}) M-cycles = M-path with x_{i} ≠ x_{i+1} , i < n with x_{1} = x_{n} and M(x_{n}, x_{1}) > 0 Prop.2: V_{I} = V_{C} =_{def.} inf_{C∈C} V (C) with C = M − cycles Note: V_{I} = V_{ν} ⟺ V^{−1}(V_{ν}) ∩ C ≠ ∅ Bellman-equations

−\frac{1}{α} log μ_{α}(.) \overrightarrow{α → ∞} accumulation pt. U

Prop.3 [Bellman-fixed points]

• U(y) = inf_{x∈E} (U(x) + nV^{(n)}(x, y)) − nV_{I} with V^{(n)}(x, y) = min_{P ∈P^{(n)}(x,y)} V (P).

• U^{−1}(0) ⊂ (V ≤ V_{I}) and ∂_{M}U^{−1}(0) ⊂ (V > V_{I})

with M-boundary of A

∂_{M}(A) = {y ∈ E − A ; ∃x ∈ A M(x, y) > 0} E = {0, 1, 2},

V (0) > \frac{V (0)+V (1)+V (2)}{3} > V (2) > V (1) = 0 and M = ( \begin{matrix}p & 1 − p & 0 \\ 0 & 0 & 1 \\ 1 & 0 & 0 \end{matrix} )

ν = νM = (1, 1 − p, 1 − p)/(3 − 2p), V_{ν} = V (1) < V_{I} = \frac{V (0)+V (1)+V (2)}{3} Bellman-eq. (n = 1)

\{ \begin{matrix}U(0) & = & min \{U(0), U(2)\} + V (0) − V_{I} \\ U(1) & = & U(0) + V (1) − V_{I} \\ U(2) & = & U(1) + V (2) − V_{I} \end{matrix}

⟹ U = (V (0) − V_{I}, V_{I} − V (2), 0) ⇒ lim_{α→∞} μ_{α}(2) = 1