Informed Subsampling MCMC:
Approximate Bayesian Inference for Large Datasets

Pierre Alquier

Bayesian Statistics in the Big Data Era

Pierre Alquier

Informed Subsampling MCMC

F. Maire, N. Friel, P. Alquier, Informed Sub-Sampling MCMC : Approximate Bayesian Inference
for Large Datasets. To appear in Statistics and Computing.

Pierre Alquier

Informed Subsampling MCMC

F. Maire, N. Friel, P. Alquier, Informed Sub-Sampling MCMC : Approximate Bayesian Inference
for Large Datasets. To appear in Statistics and Computing.

Pierre Alquier

Informed Subsampling MCMC

F. Maire, N. Friel, P. Alquier, Informed Sub-Sampling MCMC : Approximate Bayesian Inference
for Large Datasets. To appear in Statistics and Computing.

Pierre Alquier

Informed Subsampling MCMC

Metropolis-Hastings algorithm
Consider the posterior distribution
π(θ|Y ) = π(θ | Y1 , . . . , YN ) ∝ f (Y1 , . . . , YN | θ)π(θ)

Pierre Alquier

Informed Subsampling MCMC

Metropolis-Hastings algorithm
Consider the posterior distribution
π(θ|Y ) = π(θ | Y1 , . . . , YN ) ∝ f (Y1 , . . . , YN | θ)π(θ)
Metropolis-Hastings, transitioning from θk → θk+1 :1
2

draw θ̃ ∼ Q(θk , ·)set θk+1 = θ̃ with probabilityA(θk , θ̃) = 1 ∧π(θ̃ |Y )Q(θ̃, θk )π(θk |Y )Q(θk , θ̃)and θk+1 = θk w.p. 1 − A(θk , θ̃).

Pierre Alquier

Informed Subsampling MCMC

Metropolis-Hastings algorithm
Consider the posterior distribution
π(θ|Y ) = π(θ | Y1 , . . . , YN ) ∝ f (Y1 , . . . , YN | θ)π(θ)
Metropolis-Hastings, transitioning from θk → θk+1 :1
2

draw θ̃ ∼ Q(θk , ·)set θk+1 = θ̃ with probabilityA(θk , θ̃) = 1 ∧π(θ̃ |Y )Q(θ̃, θk )π(θk |Y )Q(θk , θ̃)and θk+1 = θk w.p. 1 − A(θk , θ̃).

Is it possible to usefully employ MH without computingπ(θ̃ | Y1 , . . . , YN ), to accept/reject θ̃ based on a subset
of n  N data ?
Pierre Alquier

Informed Subsampling MCMC

Austerity in MCMC-Land
A. Korattikara, Y. Chen, M. Welling, Austerity in MCMC land : Cutting the Metropolis-Hastingsbudget. ICML (2014).

Pierre Alquier

Informed Subsampling MCMC

Austerity in MCMC-Land
A. Korattikara, Y. Chen, M. Welling, Austerity in MCMC land : Cutting the Metropolis-Hastingsbudget. ICML (2014).

Idea : θk+1 = θ̃ iffU≤

π(θ̃ |Y )Q(θ̃, θk )where U ∼ U[0, 1].
π(θk |Y )Q(θk , θ̃)

Pierre Alquier

Informed Subsampling MCMC

Austerity in MCMC-Land
A. Korattikara, Y. Chen, M. Welling, Austerity in MCMC land : Cutting the Metropolis-Hastingsbudget. ICML (2014).

Idea : θk+1 = θ̃ iffπ(θ̃ |Y )Q(θ̃, θk )where U ∼ U[0, 1].
π(θk |Y )Q(θk , θ̃)
QIn the i.i.d case f (Y1 , . . . , YN | θ) = Ni=1 f (Yi | θ),
!
"
#
N
1
f (Yi |θ̃)
π(θk )Q(θk , θ̃)1 X≥ s := log U
log
N i=1
f (Yi |θk )Nπ(θ̃)Q(θ̃, θk )U≤

Pierre Alquier

Informed Subsampling MCMC

Austerity in MCMC-Land
A. Korattikara, Y. Chen, M. Welling, Austerity in MCMC land : Cutting the Metropolis-Hastingsbudget. ICML (2014).

Q
In the i.i.d case f (Y1 , . . . , YN | θ) = Ni=1 f (Yi | θ),!
"#Nf (Yi |θ̃)
1
1 X
π(θk )Q(θk , θ̃)log≥ s := log U
N i=1
f (Yi |θk )Nπ(θ̃)Q(θ̃, θk )Based on a random subsample of size n, test!
N
1 X
f (Yi |θ̃)
H0 :
≥ s.
log
N i=1
f (Yi |θk )Austerity in MCMC-Land
A. Korattikara, Y. Chen, M. Welling, Austerity in MCMC land : Cutting the Metropolis-Hastingsbudget. ICML (2014).

Q
In the i.i.d case f (Y1 , . . . , YN | θ) = Ni=1 f (Yi | θ),!
"#Nf (Yi |θ̃)
1
1 X
π(θk )Q(θk , θ̃)log≥ s := log U
N i=1
f (Yi |θk )Nπ(θ̃)Q(θ̃, θk )Based on a random subsample of size n, test!
N
1 X
f (Yi |θ̃)
H0 :
≥ s.
log
N i=1
f (Yi |θk )If the power of the test is not large enough :increase n and start again.
Pierre Alquier

Informed Subsampling MCMC

Theoretical analysis
R. Bardenet, A. Doucet, C. Holmes, Towards scaling up Markov chain Monte Carlo : an adaptive
subsampling approach. ICML (2014).

Pierre Alquier

Informed Subsampling MCMC

Theoretical analysis
R. Bardenet, A. Doucet, C. Holmes, Towards scaling up Markov chain Monte Carlo : an adaptive
subsampling approach. ICML (2014).

Designed an explicit test with probability of mistake ≤ δ.

Pierre Alquier

Informed Subsampling MCMC

Theoretical analysis
R. Bardenet, A. Doucet, C. Holmes, Towards scaling up Markov chain Monte Carlo : an adaptive
subsampling approach. ICML (2014).

Designed an explicit test with probability of mistake ≤ δ.
Theoretical analysis :Theorem (' BDH 2014)
Assume that the transition kernel P(·, ·) of the (regular) MH
algorithm is uniformly geometrically ergodic, that is∃ρ < 1, ∀θ,P k (θ, ·) − π(·|Y ) TV ≤ C ρk .

Pierre Alquier

Informed Subsampling MCMC

Theoretical analysis
R. Bardenet, A. Doucet, C. Holmes, Towards scaling up Markov chain Monte Carlo : an adaptive
subsampling approach. ICML (2014).

Designed an explicit test with probability of mistake ≤ δ.
Theoretical analysis :Theorem (' BDH 2014)
Assume that the transition kernel P(·, ·) of the (regular) MH
algorithm is uniformly geometrically ergodic, that is∃ρ < 1, ∀θ,P k (θ, ·) − π(·|Y ) TV ≤ C ρk .

Then the kernel P̃(·, ·) of the subsampling MH satisfies∀θ,P̃ k (θ, ·) − P k (θ, ·)≤ C̃ δ.
TV

Pierre Alquier

Informed Subsampling MCMC

Generalization : Noisy MCMC
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 Alquier

Informed Subsampling MCMC

Generalization : Noisy MCMC
P. Alquier, N. Friel, R. G. Everitt & A. Boland. Noisy Monte-Carlo : Convergence of Markov
Chains with Approximate Transition Kernels. Statistics and Computing, 2016.

Noisy MCMC :12draw θ̃ ∼ Q(θk , ·)set θk+1 = θ̃ with probability Â(θk , θ̃, X ).

Â(θ, θ0 , X ) : approximation of the acceptance ratioA(θ, θ0 ) that might be based on the drawing of an
auxiliary random variable X .

Pierre Alquier

Informed Subsampling MCMC

Generalization : Noisy MCMC
P. Alquier, N. Friel, R. G. Everitt & A. Boland. Noisy Monte-Carlo : Convergence of Markov
Chains with Approximate Transition Kernels. Statistics and Computing, 2016.

Noisy MCMC :12draw θ̃ ∼ Q(θk , ·)set θk+1 = θ̃ with probability Â(θk , θ̃, X ).

Â(θ, θ0 , X ) : approximation of the acceptance ratioA(θ, θ0 ) that might be based on the drawing of an
auxiliary random variable X .
Defineδ(θ, θ0 ) = EX |Â(θ, θ0 , X ) − A(θ, θ0 )|Z
δ = sup Q(θ, dθ0 )δ(θ, θ0 ).
θ
Pierre Alquier

Informed Subsampling MCMC

Theoretical study of Noisy MCMC
Theorem (AFEB 2016)
Assume that the transition kernel P(·, ·) of MH algorithm isuniformly geometrically ergodic with (C , ρ). Then the kernelP̃(·, ·) of noisy MCMC satisfies∀θ,P̃ k (θ, ·) − P k (θ, ·)≤ C̃ δ.
TV

Pierre Alquier

Informed Subsampling MCMC

Theoretical study of Noisy MCMC
Theorem (AFEB 2016)
Assume that the transition kernel P(·, ·) of MH algorithm isuniformly geometrically ergodic with (C , ρ). Then the kernelP̃(·, ·) of noisy MCMC satisfies∀θ,P̃ k (θ, ·) − P k (θ, ·)≤ C̃ δ.
TV

Finally,
D. Rudolf, N. Schweizer. Perturbation theory for Markov chains via Wasserstein distance.
Bernoulli, 2018.

extended considerably the generality of the results :(non-uniformly) geometrically erdogic Markov chains.
Pierre Alquier

Informed Subsampling MCMC

A problem with the “austerity” approachremind that in order to reach a proba. of mistake ≤ δ,
one might have to increase the size of the subsample n,depending on the values of θk and θ̃.

Pierre Alquier

Informed Subsampling MCMC

A problem with the “austerity” approachremind that in order to reach a proba. of mistake ≤ δ,
one might have to increase the size of the subsample n,depending on the values of θk and θ̃.
Bardenet, Doucet & Holmes actually show that in thestationary regime, one hasn∝N
for some constant N.

Pierre Alquier

Informed Subsampling MCMC

A problem with the “austerity” approachremind that in order to reach a proba. of mistake ≤ δ,
one might have to increase the size of the subsample n,depending on the values of θk and θ̃.
Bardenet, Doucet & Holmes actually show that in thestationary regime, one hasn∝N
for some constant N.
But one would like n  N.

Pierre Alquier

Informed Subsampling MCMC

Firefly MCMC
D., Maclaurin, R., Adams. Firefly Monte Carlo : Exact MCMC with Subsets of Data. IJCAI, 2014.

Pierre Alquier

Informed Subsampling MCMC

Firefly MCMC
D., Maclaurin, R., Adams. Firefly Monte Carlo : Exact MCMC with Subsets of Data. IJCAI, 2014.


Aux. variables Zi =1 if Yi included in the subsample,
0 otherwise.

Adapting acceptance ratio → exact sampling,

Pierre Alquier

Informed Subsampling MCMC

Firefly MCMC
D., Maclaurin, R., Adams. Firefly Monte Carlo : Exact MCMC with Subsets of Data. IJCAI, 2014.


Aux. variables Zi =1 if Yi included in the subsample,
0 otherwise.

Adapting acceptance ratio → exact sampling, but one has toknow an easily computable lower-bound 0 < Bi (θ) < f (Yi |θ).

Pierre Alquier

Informed Subsampling MCMC

Firefly MCMC
D., Maclaurin, R., Adams. Firefly Monte Carlo : Exact MCMC with Subsets of Data. IJCAI, 2014.


Aux. variables Zi =1 if Yi included in the subsample,
0 otherwise.

Adapting acceptance ratio → exact sampling, but one has toknow an easily computable lower-bound 0 < Bi (θ) < f (Yi |θ).
If the lower-bound B is not tight, one ends up withn=N
X

Zi ' N.

i=1

Pierre Alquier

Informed Subsampling MCMC

Subposteriors

Definition
Let YU be a subset of Y1:N of size n, we define the “scaled
subposteriors” π̄n by
# Nn

"
N
n

π̄n (θ | YU ) ∝ f (YU | θ) π(θ) =Yf (Yi |θ)i∈U

Pierre Alquier

Informed Subsampling MCMC

π(θ)

Motivating example : exponential family
Assume that f belongs to the exponential familyf (y | θ) ∝ ψ(θ) exp{φ(θ)T S(y )} .

Pierre Alquier

Informed Subsampling MCMC

Motivating example : exponential family
Assume that f belongs to the exponential familyf (y | θ) ∝ ψ(θ) exp{φ(θ)T S(y )} .

Definition
For any U ∈ Un , the set of all possible subset of {1, . . . , N} ofsize n, define the vector of sufficient statistics between thewhole dataset and the sub-sample YU as :
N
X
k=1

NX
S(yk ).
n k∈U

Pierre Alquier

Informed Subsampling MCMC∆n (U) =S(yk ) −Exponential family : an optimality result
Proposition
For any U ∈ Un , the following inequality holds :KL(π(·|Y ), π̄n (·|YU )) ≤ B(Y , U) , wherenoB(Y , U) = k∆n (U)k log Eπ exp kφ(θ) − Eπ (φ(θ))k .

Pierre Alquier

Informed Subsampling MCMC

Exponential family : an optimality result
Proposition
For any U ∈ Un , the following inequality holds :KL(π(·|Y ), π̄n (·|YU )) ≤ B(Y , U) , wherenoB(Y , U) = k∆n (U)k log Eπ exp kφ(θ) − Eπ (φ(θ))k .
As a consequence,
1
If there is a “perfect” U, that isN
1 X
1X
S(yk ) =S(yk ),
N k=1
n k∈U

then π̄n (·|YU ) = π(·|Y ).
2k∆n (U1 )k ≤ k∆n (U2 )k ⇒ B(Y , U1 ) ≤ B(Y , U2 ).
Pierre Alquier

Informed Subsampling MCMC

Toy example : Bernoulli model
Simulate N = 10, 000 observations Y1 , . . . , YN ∼ Be(p). ThenPN

k=1 Ykπ(θ |Y ) ∝ π(θ)(1 − p)N P

π̄n (θ | YU ) ∝ π(θ)(1 − p) n

Pierre Alquierp N−

k∈U YkPN

k=1 YkN P

p N− nk∈U YkInformed Subsampling MCMC

Toy example : Bernoulli model
Simulate N = 10, 000 observations Y1 , . . . , YN ∼ Be(p). ThenPN

k=1 Ykπ(θ |Y ) ∝ π(θ)(1 − p)N P

π̄n (θ | YU ) ∝ π(θ)(1 − p) n

p N−k∈U YkPN

k=1 YkN P

p N− nk∈U YkHere the sufficient statistics difference is|∆n (U)| =

N
X
k=1

Pierre Alquier

Yk −

NX
Yk .
n k∈U

Informed Subsampling MCMC

Bernoulli model, n = 100

n=100
30
π
π̃n , k∆n (U )k = 4425π̃n , k∆n (U )k = 56
π̃n , k∆n (U )k = 25620π̃n , k∆n (U )k = 644

15

10

5

0
0.6

0.7

0.8

Pierre Alquier

0.9
θ

1

1.1

Informed Subsampling MCMC

1.2

Bernoulli model, n = 1000

n=1,00030ππ̃n , k∆n (U )k = 425π̃n , k∆n (U )k = 14π̃n , k∆n (U )k = 2620π̃n , k∆n (U )k = 34

15

10

5

0
0.9

0.92

0.94

0.96

0.98

Pierre Alquier

1
θ

1.02

1.04

1.06

Informed Subsampling MCMC

1.08

1.1

From sufficient statistics to summary statistics
We no longer assume that we are in an exponential model, nori.i.d.

Pierre Alquier

Informed Subsampling MCMC

From sufficient statistics to summary statistics
We no longer assume that we are in an exponential model, nori.i.d.
Let S be a mapping of summary statistics.
∆n (U) = S(Y1 , . . . , YN ) − Nn S(YU ).

Pierre Alquier

Informed Subsampling MCMC

From sufficient statistics to summary statistics
We no longer assume that we are in an exponential model, nori.i.d.
Let S be a mapping of summary statistics.
∆n (U) = S(Y1 , . . . , YN ) − Nn S(YU ).

For each U ∈ Un , a weight νn, (U) is assigned to the subset ofdata YUνn, (U) ∝ exp −k∆n (U)k2 .
 → 0 : all the subsets have the same weight.
 → ∞ : the mass is concentrated on the mostrepresentative subset.
Pierre Alquier

Informed Subsampling MCMCISS-MCMC
Based on the analysis of exponential models, we propose
ISS-MCMC (for Informed Sub-Sampling). It produces a chain{θk , Uk }k . A single iteration of this algorithm is as follows :ISS-MCMC
Based on the analysis of exponential models, we propose
ISS-MCMC (for Informed Sub-Sampling). It produces a chain{θk , Uk }k . A single iteration of this algorithm is as follows :1

Update the subset :1
2

propose U 0 ∼ R(Uk , ·)set Uk+1 with probability
1 ∧ exp { (k∆n (Uk )k − k∆n (U 0 )k)}ISS-MCMC
Based on the analysis of exponential models, we propose
ISS-MCMC (for Informed Sub-Sampling). It produces a chain{θk , Uk }k . A single iteration of this algorithm is as follows :1

Update the subset :1
2

2

propose U 0 ∼ R(Uk , ·)set Uk+1 with probability
1 ∧ exp { (k∆n (Uk )k − k∆n (U 0 )k)}Update the parameter :1
2

propose θ0 ∼ Q(θk , ·)set θk+1 = θ0 with probability1∧

f (θ0 | YUk+1 )π(θ0 )Q(θ0 , θk ).
f (θk | YUk+1 )π(θk )Q(θk , θ0 )Pierre Alquier

Informed Subsampling MCMC

Assumptions for the analysis of ISS-MCMC
By construction, ISS-MCMC samples a Markov chain on an
extended state space {(θi , Ui ), i ∈ N}. Here we study the
distribution of the marginal chain (θi ).

Pierre Alquier

Informed Subsampling MCMC

Assumptions for the analysis of ISS-MCMC
By construction, ISS-MCMC samples a Markov chain on an
extended state space {(θi , Ui ), i ∈ N}. Here we study the
distribution of the marginal chain (θi ).
Some assumptions :Pierre Alquier

Informed Subsampling MCMC

Assumptions for the analysis of ISS-MCMC
By construction, ISS-MCMC samples a Markov chain on an
extended state space {(θi , Ui ), i ∈ N}. Here we study the
distribution of the marginal chain (θi ).
Some assumptions :1
We assume that the MH transition kernel K targetting π
is either uniformly ergodic or geometrically ergodic.

Pierre Alquier

Informed Subsampling MCMC

Assumptions for the analysis of ISS-MCMC
By construction, ISS-MCMC samples a Markov chain on an
extended state space {(θi , Ui ), i ∈ N}. Here we study the
distribution of the marginal chain (θi ).
Some assumptions :1
We assume that the MH transition kernel K targetting π
is either uniformly ergodic or geometrically ergodic.
2
The subsets U1 , U2 , . . . are independent and identically
distributed under νn, .

Pierre Alquier

Informed Subsampling MCMC

Assumptions for the analysis of ISS-MCMC
By construction, ISS-MCMC samples a Markov chain on an
extended state space {(θi , Ui ), i ∈ N}. Here we study the
distribution of the marginal chain (θi ).
Some assumptions :1
We assume that the MH transition kernel K targetting π
is either uniformly ergodic or geometrically ergodic.
2
The subsets U1 , U2 , . . . are independent and identically
distributed under νn, .
3
There exists a constant γn < ∞, such that for all(θ, U) ∈ Θ × Un|log f (Y | θ) − (N/n) log f (YU | θ)| ≤ γn NkS(Y )−S(YU )k .

Pierre Alquier

Informed Subsampling MCMC

Theoretical analysis of ISS-MCMC

Theorem 1
When the chain produced by the (regular) Metropolis-Hastings
algorithm is geometrically ergodic, then so is (θ̃i ).

Pierre Alquier

Informed Subsampling MCMC

Theoretical analysis of ISS-MCMC
Theorem 2
When the chain produced by MH is uniformly ergodic, then sois (θ̃i ), and its asymptotic distribution π̃n, satisfies, for someκ > 0,kπ̃n, − π(·|Y )kTV ≤ κδn,εwhere δn,ε is provided by the Noisy-MCMC analysis :Z
ΦU (θ0 )δn,ε = sup EU∼νn, 1 −Q(θ, dθ0 ),ΦU (θ)
θ
where ΦU (θ) =Pierre Alquierf (Y |θ)N

f (YU |θ) n.

Informed Subsampling MCMC

Choice of summary statistics
1

Clearly, this approach was initially motivated by the ABC
methodPierre Alquier

Informed Subsampling MCMC

Choice of summary statistics
1

2

Clearly, this approach was initially motivated by the ABC
methodIdeally the choice of S should guarantee that subsamples
YU having a very small likelihood f (YU | θ) are assigned
to a weight νn, (U) ≈ 0 to limit their contribution. In
other words, S should be specified in a way that preventsf (YU | θ) to go to 0 faster than νn, (U). This is ensured if
Assumption 3 holds.

Pierre Alquier

Informed Subsampling MCMC

Choice of summary statistics
1

2

3

Clearly, this approach was initially motivated by the ABC
methodIdeally the choice of S should guarantee that subsamples
YU having a very small likelihood f (YU | θ) are assigned
to a weight νn, (U) ≈ 0 to limit their contribution. In
other words, S should be specified in a way that preventsf (YU | θ) to go to 0 faster than νn, (U). This is ensured if
Assumption 3 holds.
In situations where the maximum likelihood estimatorθ∗ (Y1:n ) is easy and quick to evaluate numerically, we
recommend setting S(Y1:n ) = θ∗ (Y1:n ). In the case of
independent observations, setting the summary statistics
as the maximum likelihood estimate is justified since it ispossible to prove that this implies that Assumption 3
holds.
Pierre Alquier

Informed Subsampling MCMC

Implementing ISS-MCMC
Subset size n : This choice is essentially related to thecomputational budget available to the user. In thefollowing examples we have used n ∝ N 1/2 which achieves
a substantial computational gain at a price of a negligible
asymptotic bias.
Bandwidth parameter  : In practice,  needs to be verylarge and could potentially cause the algorithm to getstuck in a very small number of subsets. To avoid such asituation, we suggest monitoring the refresh rate of
subsamples that should occur with probability of at least
1%.

Pierre Alquier

Informed Subsampling MCMCExample 1 : estimation of template shapes
Data are of handwritten digits (MNIST database)

Figure – example of data

The dataset contains N = 10, 000 images of size 16x16
Each image belongs to a class Ik ∈ {1, . . . , 5} assumed tobe known
The model can be written as :Ik = i,Yk = φ(θi ) + σ 2 εk ,Pierre Alquierεk ∼ N (0, 1) .

Informed Subsampling MCMCExample 1 : estimation of template shapes
n = 100 digits,P = 105 and S(U) = (S1 (U), . . . , S5 (U))
with Si (U) = k∈U Ik
τMH = 41.2 secs and τISS-MCMC = 0.7 secs (60 × faster)time
3 mins

M–H

ISS–MCMC

15 mins
30 mins
60 mins

Pierre Alquier

Informed Subsampling MCMCExample 1 : estimation of template shapes
P
PL(t)
1
Consider the metric d(t) = 5i=1 θi∗ − L(t)`=1 θi,` ,where :
L(t) is the number of iterations completed at time t
θi∗ is the map of model i (estimated from stochastic EM)

Pierre Alquier

Informed Subsampling MCMCExample 1 : estimation of template shapes
θ1

θ5

25
MH
informedSubsampling−MCMC

14

12

20

10
15
8

6

10

4
5
2

0
0.54

0.56

0.58

0.6

0.62

0.64

0.66

0.68

0.7

0
0.65

0.7

0.75

0.8

0.85

0.9

0.95

1

1.05

Figure – Comparing the true and approximate marginal distributionof one parameter of θ1 (left) and one parameter of θ5 (right).

Pierre Alquier

Informed Subsampling MCMCExample 2 : Auto regressive model
An AR(2) model, parameterized by θ = (θ1 θ2 , θ3 )yt = θ1 yt−1 + θ2 yt−2 + ζt ,

ζt ∼ N (0, θ32 ) .

An AR(2) time-series was simulated with N = 106
observations.
Approximate inference with n ∈ {102 , 103 }.
Summary statistics : auto-correlation function, or θ
estimated by Yule-Walker ?
Different  were used.
Note : Sampling from π( · | y ) via MH was a laborious task !
Pierre Alquier

Informed Subsampling MCMCExample 2 : Auto regressive model
Case where S is defined as the estimated ACF (first 5
coefficients).
n=1,000, ǫ = 5.0 106 , unvalidated summary statistics

5

1

x 10

600

log f (Y | θ) − (N/n) log f (YU | θ)

0.8

π(θ3 )
Informed Subsampling chains

500

0.6
0.4

400

0.2
0

300

−0.2
200

−0.4
−0.6

100

−0.8
−1

0

0.02

0.04
0.06
kS̄(Y ) − S̄(YU )k

0.08

0.1

0
0.95

0.96

0.97

0.98

0.99

1

θ3

Here S is not useful, φU (θ) is unstable yielding poor
approximate posterior inference.
Pierre Alquier

Informed Subsampling MCMC

1.01

1.02

Example 2 : Auto regressive model
Second case is where S is defined as the Yule Walker coefs.
4

6

x 10

log f (Y | θ) − (N/n) log f (YU | θ)

4

2

0

−2

−4

−6

0

0.01

0.02

0.03

0.04
0.05
0.06
kS̄(Y ) − S̄(YU )k

0.07

0.08

0.09

0.1

⇒ S is appropriate since the log ratio does not grow fasterthan linearly in kS(Y ) − (N/n)S(YU )k.
Pierre Alquier

Informed Subsampling MCMCExample 2 : Auto regressive model
n=1,000, ǫ = 5.0 106
600
π(θ3 )
Informed Subsampling chains
500

400

300

200

100

0
0.997

0.998

0.999

1
θ3

1.001

1.002

1.003

Marginal distribution of θ3 for 4 independent ISS-MCMC.
Pierre Alquier

Informed Subsampling MCMCExample 2 : Auto regressive model
n=1,000
1
0.9

ε=0
ε=1

0.8

ε=5 10MH

6

Average TV distance

0.7
0.6
0.5
0.4
0.3
0.2
0.1
0
−4
10

−3

10

−2

10

−1

0

10

10

1

10

time (s)Pierre Alquier

Informed Subsampling MCMC

2

10

3

10

Conclusions

Our Informed Subsampling MCMC scheme :Allows one to control deterministically the MH transition
complexity.
Subsamples according to their fidelity to this full dataset,through summary statistics.
Allows to control only asymptotically the distance
between the chain distribution and the true posterior.

Pierre Alquier

Informed Subsampling MCMC

A recent paper

M. Quiroz, R. Kohn, M. Villani, M. Tran,. Speeding up MCMC by efficient data subsampling.
JASA, to appear.

Pierre Alquier

Informed Subsampling MCMC

A recent paper

M. Quiroz, R. Kohn, M. Villani, M. Tran,. Speeding up MCMC by efficient data subsampling.
JASA, to appear.

Pushed further the analysis of subsampling in
Metropolis-Hastings with explicit rates. However, as far as I
understand, the analysis only covers the  = 0 case.

Pierre Alquier

Informed Subsampling MCMC

A recent paper

M. Quiroz, R. Kohn, M. Villani, M. Tran,. Speeding up MCMC by efficient data subsampling.
JASA, to appear.

Pushed further the analysis of subsampling in
Metropolis-Hastings with explicit rates. However, as far as I
understand, the analysis only covers the  = 0 case.
The website of the conference says that one of the authors
should be here. I’d be happy to talk with you !

Pierre Alquier

Informed Subsampling MCMC

A word on Lanvegin-Monte-Carlo
Langevin-Monte Carlo approach can also be approximated bysubsampling.
M. Welling, Y. W. Teh. Bayesian learning via stochastic gradient Langevin dynamics. ICML, 2011.

Pierre Alquier

Informed Subsampling MCMC

A word on Lanvegin-Monte-Carlo
Langevin-Monte Carlo approach can also be approximated bysubsampling.
M. Welling, Y. W. Teh. Bayesian learning via stochastic gradient Langevin dynamics. ICML, 2011.

However, one has now two levels of approximation :discretization + subsampling. See the nice analysis
A. Dalalyan. Further and stronger analogy between sampling and optimization : Langevin Monte
Carlo and gradient descent. COLT, 2017.

(requires strong assumptions on the distribution though).

Pierre Alquier

Informed Subsampling MCMC

A word on variational approximations
When one wants to get really faster, replacing sampling by
optimization (Variational Bayes or EP) becomes unavoidable.
Stochastic optimization then allows subsampling :T. Broderick, N. Boyd, A. Wibisono, A. Wilson, M. Jordan. Streaming variational Bayes. NIPS,
2013.
M. Khan, D. Nielsen. Fast yet Simple Natural-Gradient Descent for Variational Inference inComplex Models. ISITA, 2018.

Pierre Alquier

Informed Subsampling MCMC

A word on variational approximations
When one wants to get really faster, replacing sampling by
optimization (Variational Bayes or EP) becomes unavoidable.
Stochastic optimization then allows subsampling :T. Broderick, N. Boyd, A. Wibisono, A. Wilson, M. Jordan. Streaming variational Bayes. NIPS,
2013.
M. Khan, D. Nielsen. Fast yet Simple Natural-Gradient Descent for Variational Inference inComplex Models. ISITA, 2018.

The approximate posteriors were recently proven to beconsistent (despite a possible deformation)
P. Alquier, J. Ridgway, N. Chopin. On the properties of variational approximations of Gibbs
posteriors. Journal of Machine Learning Research, 2016.
P. Alquier, J. Ridgway. Concentration of tempered posteriors and of their variational
approximations. preprint arXiv, 2017.
B.-E. Chérief-Abdellatif, P. Alquier. Consistency of Variational Bayes Inference for Estimation andModel Selection in Mixtures Electronic Journal of Statistics, 2018.
B.-E. Chérief-Abdellatif. Consistency of ELBO maximization for model selection. AABI, 2018.
Pierre Alquier

Informed Subsampling MCMC

Thank you !

Pierre Alquier

Informed Subsampling MCMC