Introduction : algorithms for Bayesian inference
Noisy MCMC
Variational approximations

Approximate Bayesian Inference
Study of a few algorithms

Pierre Alquier

Università degli Studi di Padova, May 10, 2019
Pierre AlquierApproximate Bayesian InferenceIntroduction : algorithms for Bayesian inference
Noisy MCMC
Variational approximations

Notations
Assume that we observe X1 , . . . , Xn i.i.d from Pθ0 in a modelθ{Pθ , θ ∈ Θ} dominated by Q : dP
= pθ . Prior π on Θ.
dQ

Pierre AlquierApproximate Bayesian InferenceIntroduction : algorithms for Bayesian inference
Noisy MCMC
Variational approximations

Notations
Assume that we observe X1 , . . . , Xn i.i.d from Pθ0 in a modelθ{Pθ , θ ∈ Θ} dominated by Q : dP
= pθ . Prior π on Θ.
dQ
The likelihood
Ln (θ) =nYpθ (Xi )

i=1

Pierre AlquierApproximate Bayesian InferenceIntroduction : algorithms for Bayesian inference
Noisy MCMC
Variational approximations

Notations
Assume that we observe X1 , . . . , Xn i.i.d from Pθ0 in a modelθ{Pθ , θ ∈ Θ} dominated by Q : dP
= pθ . Prior π on Θ.
dQ
The likelihood
Ln (θ) =nYpθ (Xi )i=1

The posterior
πn (dθ) ∝ Ln (θ)π(dθ).

Pierre AlquierApproximate Bayesian InferenceIntroduction : algorithms for Bayesian inference
Noisy MCMC
Variational approximations

Notations
Assume that we observe X1 , . . . , Xn i.i.d from Pθ0 in a modelθ{Pθ , θ ∈ Θ} dominated by Q : dP
= pθ . Prior π on Θ.
dQ
The likelihood
Ln (θ) =nYpθ (Xi )i=1

The posterior
πn (dθ) ∝ Ln (θ)π(dθ).
The tempered posterior - 0 < α < 1πn,α (dθ) ∝ [Ln (θ)]α π(dθ).
Pierre AlquierApproximate Bayesian InferenceIntroduction : algorithms for Bayesian inference
Noisy MCMC
Variational approximations

Various reasons to use a tempered posteriormore robust to model misspecification (at least
empirically)
P. Grünwald. The Safe Bayesian : Learning the Learning Rate via the Mixability Gap ALT 2012.

Pierre AlquierApproximate Bayesian InferenceIntroduction : algorithms for Bayesian inference
Noisy MCMC
Variational approximations

Various reasons to use a tempered posteriormore robust to model misspecification (at least
empirically)
P. Grünwald. The Safe Bayesian : Learning the Learning Rate via the Mixability Gap ALT 2012.

theoretical analysis easier
A. Bhattacharya, D. Pati & Y. Yang. Bayesian fractional posteriors. The Annals of Statistics,
2019.

Pierre AlquierApproximate Bayesian InferenceIntroduction : algorithms for Bayesian inference
Noisy MCMC
Variational approximations

Computation of the posterior
explicit form (conjugate models),

Pierre AlquierApproximate Bayesian InferenceIntroduction : algorithms for Bayesian inference
Noisy MCMC
Variational approximations

Computation of the posterior
explicit form (conjugate models),
MCMC algorithms.

Pierre AlquierApproximate Bayesian InferenceIntroduction : algorithms for Bayesian inference
Noisy MCMC
Variational approximations

Computation of the posterior
explicit form (conjugate models),
MCMC algorithms. Example : Metropolis-Hastings.
Metropolis-Hastings Algorithm (MH)arbitraty θ0 ,given θn ,1
2

draw tn+1
 ∼ q(·|θn ),tn+1 with probability a(θn , tn+1 )θn+1 =
θn otherwise.


πn,α (t)q(θ|t)
a(θ, t) = min,1 .
πn,α (θ)q(t|θ)
Pierre AlquierApproximate Bayesian InferenceIntroduction : algorithms for Bayesian inference
Noisy MCMC
Variational approximations

But...
when the dimension is large, the convergence of MCMC
can be extremely slow,

Pierre AlquierApproximate Bayesian InferenceIntroduction : algorithms for Bayesian inference
Noisy MCMC
Variational approximations

But...
when the dimension is large, the convergence of MCMC
can be extremely slow,
when the model is complex, each evaluation of πn,α (θ)
can be expensive,

Pierre AlquierApproximate Bayesian InferenceIntroduction : algorithms for Bayesian inference
Noisy MCMC
Variational approximations

But...
when the dimension is large, the convergence of MCMC
can be extremely slow,
when the model is complex, each evaluation of πn,α (θ)
can be expensive,also, when the sample size is large, each evaluation of
πn,α (θ) can be expensive even in simple models.
For these reasons, in the past 20 years, many methods
targeting an approximation of πn,α became popular : ABC, EP
algorithm, variational inference, approximate MCMC ...

Pierre AlquierApproximate Bayesian InferenceIntroduction : algorithms for Bayesian inference
Noisy MCMC
Variational approximations

Outline of the talk1

Introduction : algorithms for Bayesian inference2

Noisy MCMC
Noisy MCMC : definition, and motivating example
Convergence study of noisy MCMC
Subsampling in MCMC

3

Variational approximations
Variational approximations : definition
Consistency of variational approximations
Applications

Pierre AlquierApproximate Bayesian InferenceIntroduction : algorithms for Bayesian inference
Noisy MCMC
Variational approximations

Noisy MCMC : definition, and motivating example
Convergence study of noisy MCMC
Subsampling in MCMC

Outline of the talk1

Introduction : algorithms for Bayesian inference2

Noisy MCMC
Noisy MCMC : definition, and motivating example
Convergence study of noisy MCMC
Subsampling in MCMC

3

Variational approximations
Variational approximations : definition
Consistency of variational approximations
Applications

Pierre AlquierApproximate Bayesian InferenceIntroduction : algorithms for Bayesian inference
Noisy MCMC
Variational approximations

Noisy MCMC : definition, and motivating example
Convergence study of noisy MCMC
Subsampling in MCMC

Co-authors on this project

Nial FrielFlorian Maire

Aidan Boland

Richard Everitt

Pierre AlquierApproximate Bayesian InferenceIntroduction : algorithms for Bayesian inference
Noisy MCMC
Variational approximations

Noisy MCMC : definition, and motivating example
Convergence study of noisy MCMC
Subsampling in MCMC

Noisy Metropolis-Hastings
Metropolis-Hastings Algorithm
arbitraty θ0 ,given θn ,1
2

draw tn+1
 ∼ q(·|θn ),tn+1 with probability a(θn , tn+1 )θn+1 =
θn otherwise,

Pierre AlquierApproximate Bayesian InferenceIntroduction : algorithms for Bayesian inference
Noisy MCMC
Variational approximations

Noisy MCMC : definition, and motivating example
Convergence study of noisy MCMC
Subsampling in MCMC

Noisy Metropolis-Hastings
Noisy Metropolis-Hastings Algorithm
arbitraty θ0 ,given θn ,1
2

draw tn+1
 ∼ q(·|θn ),tn+1 with probability â(θn , tn+1 , Sn )
θn+1 =
θn otherwise,

where â(θ, t, S) is a numerical approximation ofπn,α (t)q(θ|t)
a(θ, t) = min,1πn,α (θ)q(t|θ)
that can be based (or not !) on some simulated r.v. S.
Pierre AlquierApproximate Bayesian InferenceIntroduction : algorithms for Bayesian inference
Noisy MCMC
Variational approximations

Noisy MCMC : definition, and motivating example
Convergence study of noisy MCMC
Subsampling in MCMC

A motivating example
Example : Exponential Random Graph Model (ERGM)
Given a set of nodes {1, . . . , n}, and x a graph on these nodes
represented by the adjacency matrix xi,j = 1 ⇔ “i and j areconnected”, and s(x) be a vector of statistics. We define :exp(θT s(x))
exp(θT s(x))
pθ (x) = P
=
.
T
Z (θ)
y exp(θ s(x))

Pierre AlquierApproximate Bayesian InferenceIntroduction : algorithms for Bayesian inference
Noisy MCMC
Variational approximations

Noisy MCMC : definition, and motivating example
Convergence study of noisy MCMC
Subsampling in MCMC

A motivating example
Example : Exponential Random Graph Model (ERGM)
Given a set of nodes {1, . . . , n}, and x a graph on these nodes
represented by the adjacency matrix xi,j = 1 ⇔ “i and j areconnected”, and s(x) be a vector of statistics. We define :exp(θT s(x))
exp(θT s(x))
pθ (x) = P
=
.
T
Z (θ)
y exp(θ s(x))
Then
#

α
π(t) exp(t T s(x))Z (θ) q(θ|t)
a(θ, t) = min,1 .
π(θ) [exp(θT s(x))Z (t)]α q(t|θ)"

Pierre AlquierApproximate Bayesian InferenceIntroduction : algorithms for Bayesian inference
Noisy MCMC
Variational approximations

Noisy MCMC : definition, and motivating example
Convergence study of noisy MCMC
Subsampling in MCMC

Approximation of a(·, ·) in ERGM#απ(t) exp(t T s(x))Z (θ) q(θ|t)
a(θ, t) = min,1 .
π(θ) [exp(θT s(x))Z (t)]α q(t|θ)"

and we cannot compute Z .

Pierre AlquierApproximate Bayesian InferenceIntroduction : algorithms for Bayesian inference
Noisy MCMC
Variational approximations

Noisy MCMC : definition, and motivating example
Convergence study of noisy MCMC
Subsampling in MCMC

Approximation of a(·, ·) in ERGM#απ(t) exp(t T s(x))Z (θ) q(θ|t)
a(θ, t) = min,1 .
π(θ) [exp(θT s(x))Z (t)]α q(t|θ)"

and we cannot compute Z . However, X
exp(θT s(x)) exp(t T s(x))
exp(θT s(x))
Z (θ)
=
Ex∼Pt
=
T
T
exp(t s(x))
exp(t s(x))
Z (t)
Z (t)
x

Pierre AlquierApproximate Bayesian InferenceIntroduction : algorithms for Bayesian inference
Noisy MCMC
Variational approximations

Noisy MCMC : definition, and motivating example
Convergence study of noisy MCMC
Subsampling in MCMC

Approximation of a(·, ·) in ERGM#απ(t) exp(t T s(x))Z (θ) q(θ|t)
a(θ, t) = min,1 .
π(θ) [exp(θT s(x))Z (t)]α q(t|θ)"

and we cannot compute Z . However, X
exp(θT s(x)) exp(t T s(x))
exp(θT s(x))
Z (θ)
=
Ex∼Pt
=
T
T
exp(t s(x))
exp(t s(x))
Z (t)
Z (t)
x
so we can draw SN = (x1 , . . . , xN ) iid from Pt (feasible) andâ(θ, t, SN )"!α #Nπ(t) exp(αt T s(x))q(θ) 1 X exp(θT s(xi ))
= min
,1 .
π(θ) exp(αθT s(x))q(t) N i=1 exp(t T s(xi ))Pierre AlquierApproximate Bayesian InferenceIntroduction : algorithms for Bayesian inference
Noisy MCMC
Variational approximations

Noisy MCMC : definition, and motivating example
Convergence study of noisy MCMC
Subsampling in MCMC

Theoretical study of noisy MCMC
Note that noisy MCMC produces a Markov chain, but there is
no reason for πn,α to be invariant for this chain.

Pierre AlquierApproximate Bayesian InferenceIntroduction : algorithms for Bayesian inference
Noisy MCMC
Variational approximations

Noisy MCMC : definition, and motivating example
Convergence study of noisy MCMC
Subsampling in MCMC

Theoretical study of noisy MCMC
Note that noisy MCMC produces a Markov chain, but there is
no reason for πn,α to be invariant for this chain. However :TheoremAssume :ES |a(θ, t) − â(θ, t, S)| ≤ δ(θ, t).
The kernel P associated with a(θ, t) is uniformly ergodic :kδθ0 P M − πn,α kTV ≤ C ρM .
Z
M
MThen kδθ0 P − δθ0 P̂ kTV ≤ 2K (C , ρ) sup q(dt|θ)δ(θ, t)
∀θ0 ,

θ

where P̂ is the kernel of noisy MCMC, K (C , ρ) is known.
Pierre AlquierApproximate Bayesian InferenceIntroduction : algorithms for Bayesian inference
Noisy MCMC
Variational approximations

Noisy MCMC : definition, and motivating example
Convergence study of noisy MCMC
Subsampling in MCMC

Noisy MCMC for ERGM
Corollary for ERGM
Assume thatthe parameter space is bounded : supθ∈Θ kθk = T < ∞,there is a c > 0 such that c ≤ π(θ), q(θ|t) ≤ 1/c.
C(T , c, s)√
Then : kδθ0 P M − δθ0 P̂ M kTV ≤.
N
P. Alquier, N. Friel, R. G. Everitt & A. Boland. Noisy Monte-Carlo : Convergence of Markov
Chains with Approximate Transition Kernels. Statistics and Computing, 2016.

Pierre AlquierApproximate Bayesian InferenceIntroduction : algorithms for Bayesian inference
Noisy MCMC
Variational approximations

Noisy MCMC : definition, and motivating example
Convergence study of noisy MCMC
Subsampling in MCMC

Noisy MCMC for ERGM
Corollary for ERGM
Assume thatthe parameter space is bounded : supθ∈Θ kθk = T < ∞,there is a c > 0 such that c ≤ π(θ), q(θ|t) ≤ 1/c.
C(T , c, s)√
Then : kδθ0 P M − δθ0 P̂ M kTV ≤.
N
P. Alquier, N. Friel, R. G. Everitt & A. Boland. Noisy Monte-Carlo : Convergence of Markov
Chains with Approximate Transition Kernels. Statistics and Computing, 2016.

Important generalization to the geometrically ergodic P, using
the Wasserstein distance rather than total variation :D. Rudolf & N. Schweizer. Perturbation theory for Markov chains via Wasserstein distance.
Bernoulli, 2018.
Pierre AlquierApproximate Bayesian InferenceIntroduction : algorithms for Bayesian inference
Noisy MCMC
Variational approximations

Noisy MCMC : definition, and motivating example
Convergence study of noisy MCMC
Subsampling in MCMC

Simulations : Florentine Family Business Dataset

Pierre AlquierApproximate Bayesian InferenceIntroduction : algorithms for Bayesian inference
Noisy MCMC
Variational approximations

Noisy MCMC : definition, and motivating example
Convergence study of noisy MCMC
Subsampling in MCMC

Simulations : Florentine Family Business Datasets(x) = (s1 (x), s2 (x))
s1 (x) number of edges,s2 (x) number of 2-stars.

Pierre AlquierApproximate Bayesian InferenceIntroduction : algorithms for Bayesian inference
Noisy MCMC
Variational approximations

Noisy MCMC : definition, and motivating example
Convergence study of noisy MCMC
Subsampling in MCMC

Numerical Results

MethodBERGM
Exchange
Noisy Exchange
Noisy Langevin
MALA Exchange
Noisy MALA

Edge
Mean
-2.675-2.573-2.686-2.281-2.518-2.584

SD
0.647
0.568
0.526
0.513
0.62
0.498

2-star
Mean
0.188
0.146
0.167
0.081
0.136
0.144

SD
0.155
0.133
0.122
0.119
0.128
0.113

Table – Posterior means and standard deviations.

Pierre AlquierApproximate Bayesian InferenceIntroduction : algorithms for Bayesian inference
Noisy MCMC
Variational approximations

Noisy MCMC : definition, and motivating example
Convergence study of noisy MCMC
Subsampling in MCMC

Chains, density and ACF plot for the edge statistic.

0 20006000

Iteration

10000

0 20006000

Iteration

10000

0
−1
−5
0

2000

6000

2000

6000

Iteration

1.0
0.2

0

1

Pierre Alquier

−0.2

−1
Edge

●
●
●
●●
●
●●●
●●
●●
●●
●●●●●
●
●●●
● ●●●●
●●●
●
●●●●●
●●●●
● ●●●●●●● ●● ● ●● ●● ●● ●● ● ●● ●●●●● ● ●●● ●●● ● ●● ●● ●● ●● ● ●● ●●● ●● ● ●●● ●● ●●● ●● ●●●● ● ●● ●●●● ●● ●● ●
● ●●
●
●
●
● ● ●
●
●
● ●
●
●
● ●
● ●● ●●
●
●●
● ●
●
●●
● ●●
●
●●
● ●●
●
●
● ●
●●
●
●
● ●●●
●●
●
● ●●
●●
●
● ●●●●●●●●●●●● ●●●●●
●
●●
●●
●
●
●●
● ●●
●
●
●●
● ●●
●
●●
●
● ●●
●
●●
●
● ●●
●
●●
●
●
●
●●
●● ●●●●
●
●
●●
●●●
●
●
●●
●●
●
●●●
●●
●●
●
●●● ●●●●
●●
●●
●●●
●
●● ●●●●●● ●●●●
●●
●
●●
●
●●
●●
●● ●●●●●●● ●●●
●●
●●●●
●●
●●
●
●●
●●●●
●●● ●●●●●●●●●●●●● ●●●●●●●●●●●●● ●●●●●●●●●
●●
●●
●●●●●
●●
●● ●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●
●●●
●●
●●
●●
●●●●●●●●
●●●
●●
●●
●●●●●
●●●●●●●●●●●●●●●●●●●●●
●●●●
●●
●●●
●●●●●●●●●●●●●●●●●●●●●●●●●● ●●●●●●●●●●●●●●●●●●●● ●●●
●●●●
●●●●
●●
●●●● ●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●
●●●●●
●●
●●●
●●●●●●●
●●●●●
●●
●●●●
●●●●●●●●
●●●●●
●●
●●●
●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●● ●●●●●●●●●●●●●●● ●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●● ●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●● ●●●●●●●
●●
●●●
●●
●●●●●●●●●● ●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●● ●●●●●●●●●● ●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●
●●
●●
●●
●●
●●
●●●
●●●●
●●
●●
●●●●●●●
●●●●
●●●●
●●●
●●
●●●●●●●●●●●●●●●●●●●●●
●●●●
●●
●●●●
●●
●●●
●●●●●●
●●
●●
●●●●
●●●●●
●●●●●
●●
●●●
●●●●●
●●●
●●●●●●●●●●●●●●●●●
●●●●●
●●●
●●●●
●●●●●●
●●●
●●●●
●●●●
●●●● ●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●● ●●●●●●●●●●●●●●●●●●●●●●●●●●●●●● ●●●●●●●●●●●●●●●●●●●●●●●● ●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●
●
●
●
●
●
●
●
●●●●●
●
●
●●●●●●●●●●●●●●●●●●●●●●●●●●●●● ●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●● ●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●● ●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●● ●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●
●●●●
●●●●●
●●

Exchange
Noisy Exch
Noisy Lang
● MALA Exch
● Noisy MALA Exch
●
●
●

0.6

0.0 0.2 0.4 0.6 0.8

ACF Edge
BERGM
Exchange
Noisy Exch
Noisy Lang
MALA Exch
Noisy MALA

−30

Iteration

Edge

−5

Noisy MALA Exch

−3

−1
−3
−5

−3

−1

0

MALA Exchange

0Langevin

−5

−5

−3

−1

0

Noisy Exchange

0

50

150
Lag

250

Approximate Bayesian InferenceIntroduction : algorithms for Bayesian inference
Noisy MCMC
Variational approximations

Noisy MCMC : definition, and motivating example
Convergence study of noisy MCMC
Subsampling in MCMC

Chains, density and ACF plot for the 2-star stat.

4000 8000

Iteration

14000

6000

Iteration

10000

0 20006000

Iteration

10000

0

2000

1.0
0.2

Pierre Alquier

−0.2

1

1.0

Exchange
Noisy Exch
Noisy Lang
MALA Exch● Noisy MALA Exch
●
●

0

50

150
Lag

250

Approximate Bayesian Inference

6000

Iteration

●
●
●
●●
●
●●
●●
●
●●
●
●●●
●
●
●●●
●
● ●
●●●
●
●●
●● ●
●
●●●
●
● ●●●
●●●
● ●●●
●
●●●●
● ●●●
●
●
●
● ●● ●●●● ●●● ●● ●●●● ●●● ●● ●●●●● ●●● ●
●
●● ●
●
●
●
●● ●●
●
●● ●
●
●● ●
●●
●
●● ●●
●
●● ●●
●
●
●●● ●●●● ● ●●●● ● ●●●●● ● ●●●●● ● ●●●● ● ●●●● ● ●●●●●●●●●● ●●●●●●●●●● ●●●●●●●●●●● ●●●●●●●●●●● ●●●
●●
●
●●
●● ●●
●
●●
●● ●●
●●●
●
●● ●●●
●
●● ●●
●●●●
●
●●
●● ●●
●●
● ●●
●●● ●●●●● ●●●●●● ●●●●● ●●●
● ●●●
●●
●● ●●
●● ●●●●●●● ●●●●●● ●●●●
●● ●●
●●
●● ●●
●● ●●
●● ●●●
●●
●● ●●
●● ●●
●●
●● ●●
●● ●●●●●●● ●●●●●●●●● ●●●●●●●●●●●●●●●●●●●●●●
●●●
●●●
●● ●●
●●●●●●●●●●●●●●●●●●●● ●●●●●●●●●●●●●●●●●●●●●●●●●●●●● ●●●●●●●●●●●●●●●●●●●●● ●●●●●●●●●●●●●●●● ●●●●●●●●●●●●●●●●● ●●●●●●●●●●●●●●●●●●
●●
●●
●
●●●
●●●●●●●●●●● ●●●●●●●●●●●●●●● ●●●
●●●
●●●
●●●
●●●●●●●●●
●●●
●●●
●●●
●●
●●
●●
●●●
●●●●
●●●
●●●
●●●●●
●●●●
●●●●
●●
●●●
●●●●
●●
●●●●●●
●●●●
●●
●●●●●
●●● ●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●● ●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●● ●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●
●●●●●
●●●●●
●●
●●●●●●●●●●●●●●●●●
●●●
●●
●●●●●
●●●
●●●
●●●●●●●●●●●●●●●●●●●●●●●●
●●●
●●●●
●●●●
●●●
●●●●●
●●●
●●●●●
●●●
●●●
●●●●●●●●●●●●●
●●●●
●●
●●●
●●●●●●●●●
●●●
●●●
●●●
●●
●●●●
●●●●●●
●●●●
●●●●
●●
●●●
●●●
●●●
●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●
●●
●●
●●
●●●●●
●●●
●●●
●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●● ●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●● ●●●●●●●●●●● ●●●●●●●●●●●●●●● ●●●●●●●●●●●●●●●●● ●●●●●●●●●●● ●●●●●● ●●●●● ●●●●●●●●●●●●●●●● ●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●
●●●●●
●●
●●
●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●● ●●●
●●
●●●
●●●
●●●●
●●
●●●●
●●●●●●●●●●●●●●●●●●●●●●●●●●●●●● ●●●●●●●●●● ●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●
●●●
●●●●

●

0.6

4

6000

Iteration

●

2

3

2000

ACF 2star
BERGM
Exchange
Noisy Exch
Noisy Lang
MALA Exch
Noisy MALA

0.0
2star

0.8
0.0
−0.4

0

2star

−1.0

Noisy MALA Exch
0.4

0.8
0.4
−0.4

0.0

0.4

0.8

MALA Exchange

0.0
0 200000Langevin

−0.4

0.0
−0.4

−0.4

0.0

0.4

0.8

Noisy Exchange

0.4

0.8

Exchange

Introduction : algorithms for Bayesian inference
Noisy MCMC
Variational approximations

Noisy MCMC : definition, and motivating example
Convergence study of noisy MCMC
Subsampling in MCMC

Subsampling in MCMC
Idea to approximate â when the sample size n is too large :evaluate â on a subsample of the data.
time
3 minsM–H

noisy MCMC

15 mins
30 mins
60 mins

Pierre AlquierApproximate Bayesian InferenceIntroduction : algorithms for Bayesian inference
Noisy MCMC
Variational approximations

Noisy MCMC : definition, and motivating example
Convergence study of noisy MCMC
Subsampling in MCMC

Subsampling in MCMC
Idea to approximate â when the sample size n is too large :evaluate â on a subsample of the data.
time
3 minsM–H

noisy MCMC

15 mins
30 mins
60 mins
F. Maire, N. Friel, P. Alquier, Informed Sub-Sampling MCMC : Approximate Bayesian Inference
for Large Datasets. Statistics and Computing, 2019.
Pierre AlquierApproximate Bayesian InferenceIntroduction : algorithms for Bayesian inference
Noisy MCMC
Variational approximations

Variational approximations : definition
Consistency of variational approximations
Applications

Outline of the talk1

Introduction : algorithms for Bayesian inference2

Noisy MCMC
Noisy MCMC : definition, and motivating example
Convergence study of noisy MCMC
Subsampling in MCMC

3

Variational approximations
Variational approximations : definition
Consistency of variational approximations
Applications

Pierre AlquierApproximate Bayesian InferenceIntroduction : algorithms for Bayesian inference
Noisy MCMC
Variational approximations

Variational approximations : definition
Consistency of variational approximations
Applications

Co-authors on this projectJames Ridgway

Pierre Alquier

Nicolas Chopin

Approximate Bayesian InferenceIntroduction : algorithms for Bayesian inference
Noisy MCMC
Variational approximations

Variational approximations : definition
Consistency of variational approximations
Applications

Co-authors on this projectJames Ridgway

Nicolas Chopin

Idea of VB : chose a family F of probability distributions on Θ
and approximate πn,α by a distribution in F :Pierre AlquierApproximate Bayesian InferenceIntroduction : algorithms for Bayesian inference
Noisy MCMC
Variational approximations

Variational approximations : definition
Consistency of variational approximations
Applications

Co-authors on this projectJames Ridgway

Nicolas Chopin

Idea of VB : chose a family F of probability distributions on Θ
and approximate πn,α by a distribution in F :π̃n,α := arg min K(ρ, πn,α ).
ρ∈F

Pierre AlquierApproximate Bayesian InferenceIntroduction : algorithms for Bayesian inference
Noisy MCMC
Variational approximations

Variational approximations : definition
Consistency of variational approximations
Applications

Variational approximations
π̃n,α = arg min K(ρ, πn,α )
ρ∈F
)
(
Z
n
1X
log pθ (Xi )ρ(dθ) + K(ρ, π) .
= arg min −α
ρ∈F
n i=1
|
{z
}
−ELBO(ρ)

Examples :Pierre AlquierApproximate Bayesian InferenceIntroduction : algorithms for Bayesian inference
Noisy MCMC
Variational approximations

Variational approximations : definition
Consistency of variational approximations
Applications

Variational approximations
π̃n,α = arg min K(ρ, πn,α )
ρ∈F
)
(
Z
n
1X
log pθ (Xi )ρ(dθ) + K(ρ, π) .
= arg min −α
ρ∈F
n i=1
|
{z
}
−ELBO(ρ)

Examples :parametric approximation

F = N (µ, Σ) : µ ∈ Rd , Σ ∈ Sd+ .

Pierre AlquierApproximate Bayesian InferenceIntroduction : algorithms for Bayesian inference
Noisy MCMC
Variational approximations

Variational approximations : definition
Consistency of variational approximations
Applications

Variational approximations
π̃n,α = arg min K(ρ, πn,α )
ρ∈F
)
(
Z
n
1X
log pθ (Xi )ρ(dθ) + K(ρ, π) .
= arg min −α
ρ∈F
n i=1
|
{z
}
−ELBO(ρ)

Examples :parametric approximation

F = N (µ, Σ) : µ ∈ Rd , Σ ∈ Sd+ .
mean-field approximation, Θ = Θ1 × Θ2 andF : {ρ : ρ(dθ) = ρ1 (dθ1 ) × ρ2 (dθ2 )} .
Pierre AlquierApproximate Bayesian InferenceIntroduction : algorithms for Bayesian inference
Noisy MCMC
Variational approximations

Variational approximations : definition
Consistency of variational approximations
Applications

Tools for the consistency of VB
The α-Rényi divergence for α ∈ (0, 1)Z1Dα (P, R) =log (dP)α (dR)1−α .
α−1Pierre AlquierApproximate Bayesian InferenceIntroduction : algorithms for Bayesian inference
Noisy MCMC
Variational approximations

Variational approximations : definition
Consistency of variational approximations
Applications

Tools for the consistency of VB
The α-Rényi divergence for α ∈ (0, 1)Z1Dα (P, R) =log (dP)α (dR)1−α .
α−1All the properties derived in :T. Van Erven & P. Harremos. Rényi divergence and Kullback-Leibler divergence. IEEE
Transactions on Information Theory, 2014.

Among others, for 1/2 ≤ α, link with Hellinger and Kullback :H2 (P, R) ≤ Dα (P, R) −−→ K(P, R).
α%1

Pierre AlquierApproximate Bayesian InferenceIntroduction : algorithms for Bayesian inference
Noisy MCMC
Variational approximations

Variational approximations : definition
Consistency of variational approximations
Applications

What do we know about πn,α ?
B(r ) = {θ ∈ Θ : K(Pθ0 , Pθ ) ≤ r } .
Theorem, variant of (Bhattacharya, Pati & Yang)
For any sequence (rn ) such that− log π[B(rn )] ≤ nrn
we haveZE1+αDα (Pθ , Pθ0 )πn,α (dθ) ≤
rn .
1−α

A. Bhattacharya, D. Pati & Y. Yang. Bayesian fractional posteriors. The Annals of Statistics,
2019.

Pierre AlquierApproximate Bayesian InferenceIntroduction : algorithms for Bayesian inference
Noisy MCMC
Variational approximations

Variational approximations : definition
Consistency of variational approximations
Applications

Extension of previous result to VB
Theorem (A. & Ridgway)
If there is ρn ∈ F and (rn ) such that
 R
 K(Pθ0 , Pθ )ρn (dθ) ≤ rn ,andK(ρn , π) ≤ nrn ,then, for any α ∈ (0, 1),Z
1+αDα (Pθ , Pθ0 )π̃n,α (dθ) ≤
E
rn .
1−α

Pierre AlquierApproximate Bayesian InferenceIntroduction : algorithms for Bayesian inference
Noisy MCMC
Variational approximations

Variational approximations : definition
Consistency of variational approximations
Applications

Extension of previous result to VB
Theorem (A. & Ridgway)
If there is ρn ∈ F and (rn ) such that
 R
 K(Pθ0 , Pθ )ρn (dθ) ≤ rn ,andK(ρn , π) ≤ nrn ,then, for any α ∈ (0, 1),Z
1+αDα (Pθ , Pθ0 )π̃n,α (dθ) ≤
E
rn .
1−α
P. Alquier & J. Ridgway. Concentration of tempered posteriors and of their variational
approximations. The Annals of Statistics, to appear.
Pierre AlquierApproximate Bayesian InferenceIntroduction : algorithms for Bayesian inference
Noisy MCMC
Variational approximations

Variational approximations : definition
Consistency of variational approximations
Applications

Misspecified case
Assume now that X1 , . . . , Xn i.i.d ∼ Q ∈/ {Pθ , θ ∈ Θ}. Put :θ∗ := arg min K(Q, Pθ ).
θ∈Θ

Theorem (A. and Ridgway)
Assume that there is ρn ∈ F such that

Z 
dPθ∗
E log
ρn (dθ) ≤ rn and K(ρn , π) ≤ nrn ,dPθthen, for any α ∈ (0, 1),ZE
Dα (Pθ , Q)π̃n,α (dθ) ≤Pierre Alquier1+ααK(Q, Pθ∗ ) +
rn .
1−α
1−α
Approximate Bayesian InferenceIntroduction : algorithms for Bayesian inference
Noisy MCMC
Variational approximations

Variational approximations : definition
Consistency of variational approximations
Applications

Example 1 : Gaussian VB
Let Θ = Rp .

Pierre AlquierApproximate Bayesian InferenceIntroduction : algorithms for Bayesian inference
Noisy MCMC
Variational approximations

Variational approximations : definition
Consistency of variational approximations
Applications

Example 1 : Gaussian VB
Let Θ = Rp .
We start with the family of approximations
FGΦ := Φ(dθ; m, Σ), m ∈ Rd , Σ ∈ G ⊂ S+d (R) ,Pierre AlquierApproximate Bayesian InferenceIntroduction : algorithms for Bayesian inference
Noisy MCMC
Variational approximations

Variational approximations : definition
Consistency of variational approximations
Applications

Example 1 : Gaussian VB
Let Θ = Rp .
We start with the family of approximations
FGΦ := Φ(dθ; m, Σ), m ∈ Rd , Σ ∈ G ⊂ S+d (R) ,We assume that for a model {pθ , θ ∈ Θ} there exists a
measurable real valued function M(·) such that|log pθ (X1 ) − log pθ0 (X1 )| ≤ M(X1 ) kθ − θ0 k2
Furthermore we assume that
EM(X1 ) =: B1 , EM 2 (X1 ) =: B2 < ∞.
Pierre AlquierApproximate Bayesian InferenceIntroduction : algorithms for Bayesian inference
Noisy MCMC
Variational approximations

Variational approximations : definition
Consistency of variational approximations
Applications

Application of the result
Theorem
Let the family of approximation be F with FσΦ2 I ⊂ F as
defined above. We put
rn =

B1 B2
d
∨ 2 ∨ C log nnnnThen for any α ∈ (0, 1),

Z
1+α
n
E
Dα (Pθ , Pθ0 )π̃n,α (dθ|X1 ) ≤
rn .
1−α

Pierre AlquierApproximate Bayesian InferenceIntroduction : algorithms for Bayesian inference
Noisy MCMC
Variational approximations

Variational approximations : definition
Consistency of variational approximations
Applications

Stochastic Variational Bayes
To implement the idea we writeFBΦ = Φ(dθ; m, CC t ), (m, C ) ∈ B ∩ Rd × S+d .
F : x = (m, C ) ∈ Rd × Rd×d 7→ E [f (x, ξ)] = K(ρm,C , πn )where ξ ∼ N (0, Id )Pierre AlquierApproximate Bayesian InferenceIntroduction : algorithms for Bayesian inference
Noisy MCMC
Variational approximations

Variational approximations : definition
Consistency of variational approximations
Applications

Stochastic Variational Bayes
To implement the idea we writeFBΦ = Φ(dθ; m, CC t ), (m, C ) ∈ B ∩ Rd × S+d .
F : x = (m, C ) ∈ Rd × Rd×d 7→ E [f (x, ξ)] = K(ρm,C , πn )where ξ ∼ N (0, Id )The optimization problem can be writtenmindx∈B∩Rd ×S+

E [f (x, ξ)] ,where
f ((m, C ), ξ) := log pm+C ξ (Y1n ) + log
Pierre AlquierdΦm,CC t(m + C ξ)dπApproximate Bayesian InferenceIntroduction : algorithms for Bayesian inference
Noisy MCMC
Variational approximations

Variational approximations : definition
Consistency of variational approximations
Applications

We can use stochastic gradient descent
Algorithm 1 Stochastic VB
Input : x0 , X1n , γT
For i ∈ {1, · · · , T },a. Sample ξt ∼ N (0, Id )b. Updatext ← PB (xt−1 − γT ∇f (xt−1 , ξt ))End For .
P
Output : x̄T = T1 Tt=1 xt
where ∇f is the gradient of the integrand in the objectivefunction
Pierre AlquierApproximate Bayesian InferenceIntroduction : algorithms for Bayesian inference
Noisy MCMC
Variational approximations

Variational approximations : definition
Consistency of variational approximations
Applications

Assume that f is convex in its first component x and thatit has L-Lipschitz gradients.
kDefine π̃n,α(dθ|X1n ) to be the k-th iterate of the algorithm
Theorem
For some C ,
B1 B2
rn =
∨ 2 ∨
n
n


 


d 1
1
kθ0 k2d2 2log ϑ n C + 2 +
−
n 2
nϑ
nϑ2
2n

with γk = L√B2k , we get
Z
E



1+α
1
k
Dα (Pθ , Pθ0 )π̃n,α(dθ|X1n ) ≤
rn +
1−α
1−α
Pierre AlquierApproximate Bayesian Inference

r

2BL
.
k

Introduction : algorithms for Bayesian inference
Noisy MCMC
Variational approximations

Variational approximations : definition
Consistency of variational approximations
Applications

Example 2 : nonparametric regression
Nonparametric regression
Yi = f (Xi ) + ξi ,Pierre AlquierApproximate Bayesian InferenceIntroduction : algorithms for Bayesian inference
Noisy MCMC
Variational approximations

Variational approximations : definition
Consistency of variational approximations
Applications

Example 2 : nonparametric regression
Nonparametric regression
Yi = f (Xi ) + ξi ,ξi ∼ N (0, σ 2 ),Pierre AlquierApproximate Bayesian InferenceIntroduction : algorithms for Bayesian inference
Noisy MCMC
Variational approximations

Variational approximations : definition
Consistency of variational approximations
Applications

Example 2 : nonparametric regression
Nonparametric regression
Yi = f (Xi ) + ξi ,ξi ∼ N (0, σ 2 ),f is s-smooth with s unknown,

Pierre AlquierApproximate Bayesian InferenceIntroduction : algorithms for Bayesian inference
Noisy MCMC
Variational approximations

Variational approximations : definition
Consistency of variational approximations
Applications

Example 2 : nonparametric regression
Nonparametric regression
Yi = f (Xi ) + ξi ,ξi ∼ N (0, σ 2 ),f is s-smooth with s unknown,Pprior : f (·) = Kj=1 βj φj (·), random K and βj ’s, (ϕj )basis...

Pierre AlquierApproximate Bayesian InferenceIntroduction : algorithms for Bayesian inference
Noisy MCMC
Variational approximations

Variational approximations : definition
Consistency of variational approximations
Applications

Example 2 : nonparametric regression
Nonparametric regression
Yi = f (Xi ) + ξi ,ξi ∼ N (0, σ 2 ),f is s-smooth with s unknown,Pprior : f (·) = Kj=1 βj φj (·), random K and βj ’s, (ϕj )basis...
variational approx : βj mutually independent...
2s 2s+1
Under suitable assumptions, rn ∼ log(n).
nPierre AlquierApproximate Bayesian InferenceIntroduction : algorithms for Bayesian inference
Noisy MCMC
Variational approximations

Variational approximations : definition
Consistency of variational approximations
Applications

Example 3 : matrix completion

In
P. Alquier, J. Ridgway , N. Chopin. On the Properties of Variational Approximations of Gibbs
Posteriors. JMLR, 2016.

we proved that the variational approximations used in thematrix completion problem do not change the rate ofconvergence.

Pierre AlquierApproximate Bayesian InferenceIntroduction : algorithms for Bayesian inference
Noisy MCMC
Variational approximations

Variational approximations : definition
Consistency of variational approximations
Applications

Example 4 : model selectionkAssume that we have K models, define π̃n,αa variational
approximation of the tempered posterior in model k, and rnk its
convergence rate if model k is correct. Put :kk̂ = arg max ELBO(π̃n,α).
kPierre AlquierApproximate Bayesian InferenceIntroduction : algorithms for Bayesian inference
Noisy MCMC
Variational approximations

Variational approximations : definition
Consistency of variational approximations
Applications

Example 4 : model selectionkAssume that we have K models, define π̃n,αa variational
approximation of the tempered posterior in model k, and rnk its
convergence rate if model k is correct. Put :kk̂ = arg max ELBO(π̃n,α).
kTheoremIf the true model is actually k0 ,Z
1 + α k0log(K )0nk̂EDα (Pθ , P )π̃n,α (dθ|X1 ) ≤
rn +
.
1−α
n(1 − α)Pierre AlquierApproximate Bayesian InferenceIntroduction : algorithms for Bayesian inference
Noisy MCMC
Variational approximations

Variational approximations : definition
Consistency of variational approximations
Applications

Example 4 : model selection
TheoremIf the true model is actually k0 ,Z

1 + α k0log(K )0k̂nEDα (Pθ , P )π̃n,α (dθ|X1 ) ≤
rn +
.
1−α
n(1 − α)This result is actually due
to my PhD student BadrEddine Chérief-Abdellatif.
B.-E. Chérief-Abdellatif. Consistency of
ELBO maximization for model
selection. AABI 2018.

Pierre AlquierApproximate Bayesian InferenceIntroduction : algorithms for Bayesian inference
Noisy MCMC
Variational approximations

Variational approximations : definition
Consistency of variational approximations
Applications

Example 5 : mixture models
VB for mixtures
P
Pp,θ = Ki=1 pi qθi ,Pierre AlquierApproximate Bayesian InferenceIntroduction : algorithms for Bayesian inference
Noisy MCMC
Variational approximations

Variational approximations : definition
Consistency of variational approximations
Applications

Example 5 : mixture models
VB for mixtures
P
Pp,θ = Ki=1 pi qθi ,VB approximation : the θi ’s are mutually independent andindependent from (p1 , . . . , pK ).

Pierre AlquierApproximate Bayesian InferenceIntroduction : algorithms for Bayesian inference
Noisy MCMC
Variational approximations

Variational approximations : definition
Consistency of variational approximations
Applications

Example 5 : mixture models
VB for mixtures
P
Pp,θ = Ki=1 pi qθi ,VB approximation : the θi ’s are mutually independent andindependent from (p1 , . . . , pK ).
.
Under suitable assumptions, rn ∼ K log(n)nPierre AlquierApproximate Bayesian InferenceIntroduction : algorithms for Bayesian inference
Noisy MCMC
Variational approximations

Variational approximations : definition
Consistency of variational approximations
Applications

Example 5 : mixture models
VB for mixtures
P
Pp,θ = Ki=1 pi qθi ,VB approximation : the θi ’s are mutually independent andindependent from (p1 , . . . , pK ).
.
Under suitable assumptions, rn ∼ K log(n)nB.-E. Chérief-Abdellatif, P. Alquier. Consistency of Variational Bayes Inference for Estimation andModel Selection in Mixtures. Electronic Journal of Statistics, 2018.

Pierre AlquierApproximate Bayesian InferenceIntroduction : algorithms for Bayesian inference
Noisy MCMC
Variational approximations

Variational approximations : definition
Consistency of variational approximations
Applications

What’s next ?
Case α = 1[L(θ)]α π(dθ) = L(θ)π(dθ)
F. Zhang & C. Gao (2017). Convergence Rates of Variational Posterior Distributions. Preprint
arxiv :1712.02519.

Pierre AlquierApproximate Bayesian InferenceIntroduction : algorithms for Bayesian inference
Noisy MCMC
Variational approximations

Variational approximations : definition
Consistency of variational approximations
Applications

What’s next ?
Case α = 1[L(θ)]α π(dθ) = L(θ)π(dθ)
F. Zhang & C. Gao (2017). Convergence Rates of Variational Posterior Distributions. Preprint
arxiv :1712.02519.

we only proved pointwise convergence. What would be
conditions ensuring that credible intervals given by thevariational approximation are correct ?

Pierre AlquierApproximate Bayesian InferenceIntroduction : algorithms for Bayesian inference
Noisy MCMC
Variational approximations

Variational approximations : definition
Consistency of variational approximations
Applications

What’s next ?
Case α = 1[L(θ)]α π(dθ) = L(θ)π(dθ)
F. Zhang & C. Gao (2017). Convergence Rates of Variational Posterior Distributions. Preprint
arxiv :1712.02519.

we only proved pointwise convergence. What would be
conditions ensuring that credible intervals given by thevariational approximation are correct ?
many recent papers study approximations based on otherdivergences or distances than K : Rényi, Wasserstein, ...

Pierre AlquierApproximate Bayesian InferenceIntroduction : algorithms for Bayesian inference
Noisy MCMC
Variational approximations

Variational approximations : definition
Consistency of variational approximations
Applications

What’s next ?
Case α = 1[L(θ)]α π(dθ) = L(θ)π(dθ)
F. Zhang & C. Gao (2017). Convergence Rates of Variational Posterior Distributions. Preprint
arxiv :1712.02519.

we only proved pointwise convergence. What would be
conditions ensuring that credible intervals given by thevariational approximation are correct ?
many recent papers study approximations based on otherdivergences or distances than K : Rényi, Wasserstein, ...
analysis of online variational inference (work in progresswith Emti Khan and Badr-Eddine Chérief-Abdellatif)...
Pierre AlquierApproximate Bayesian InferenceIntroduction : algorithms for Bayesian inference
Noisy MCMC
Variational approximations

Variational approximations : definition
Consistency of variational approximations
Applications

Thank you !

Pierre AlquierApproximate Bayesian Inference