Introduction : tempered posteriors & variational approx.
Main results
Applications

Concentration of tempered posteriors andof their variational approximations
Pierre AlquierWorkshop “Approximating high dimensional functions”
Dec. 19, 2017
Pierre AlquierConcentration of variational approximations

Introduction : tempered posteriors & variational approx.
Main results
Applications

Talk based on the preprint :P. Alquier & J. Ridgway (2017). Concentration of tempered posteriors and of their variational
approximations. Preprint arxiv :1706.09293.

Pierre AlquierConcentration of variational approximations

Introduction : tempered posteriors & variational approx.
Main results
Applications

Outline of the talk1

Introduction : tempered posteriors & variational approx.
Tempered posteriors
Variational approximations

2

Main results
Concentration of the tempered posterior
A result in expectation
The misspecified case3

Applications
Gaussian VB
Matrix completion

Pierre AlquierConcentration of variational approximations

Introduction : tempered posteriors & variational approx.
Main results
Applications

Tempered posteriors
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 AlquierConcentration of variational approximations

Introduction : tempered posteriors & variational approx.
Main results
Applications

Tempered posteriors
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 AlquierConcentration of variational approximations

Introduction : tempered posteriors & variational approx.
Main results
Applications

Tempered posteriors
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 AlquierConcentration of variational approximations

Introduction : tempered posteriors & variational approx.
Main results
Applications

Tempered posteriors
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 AlquierConcentration of variational approximations

Introduction : tempered posteriors & variational approx.
Main results
Applications

Tempered posteriors
Variational approximations

Various reasons to use a tempered posterioreasier to sample fromG. Behrens, N. Friel & M. Hurn. (2012). Tuning tempered transitions. Statistics and Computing.

Pierre AlquierConcentration of variational approximations

Introduction : tempered posteriors & variational approx.
Main results
Applications

Tempered posteriors
Variational approximations

Various reasons to use a tempered posterioreasier to sample fromG. Behrens, N. Friel & M. Hurn. (2012). Tuning tempered transitions. Statistics and Computing.

robust to model misspecification
P. Grünwald and T. van Ommen (2017). Inconsistency of Bayesian Inference for Misspecified
Linear Models, and a Proposal for Repairing It. Bayesian Analysis.

Pierre AlquierConcentration of variational approximations

Introduction : tempered posteriors & variational approx.
Main results
Applications

Tempered posteriors
Variational approximations

Various reasons to use a tempered posterioreasier to sample fromG. Behrens, N. Friel & M. Hurn. (2012). Tuning tempered transitions. Statistics and Computing.

robust to model misspecification
P. Grünwald and T. van Ommen (2017). Inconsistency of Bayesian Inference for Misspecified
Linear Models, and a Proposal for Repairing It. Bayesian Analysis.

theoretical analysis easier
A. Bhattacharya, D. Pati & Y. Yang (2016). Bayesian fractional posteriors. Preprint
arxiv :1611.01125.

Pierre AlquierConcentration of variational approximations

Introduction : tempered posteriors & variational approx.
Main results
Applications

Tempered posteriors
Variational approximations

Bhattacharya, Pati & Yang’s approach (1/2)
The α-Rényi divergence for α ∈ (0, 1)
 1
R dP α−1log
dP if P  R
α−1dR
Dα (P, R) =+∞ otherwise.

Pierre AlquierConcentration of variational approximations

Introduction : tempered posteriors & variational approx.
Main results
Applications

Tempered posteriors
Variational approximations

Bhattacharya, Pati & Yang’s approach (1/2)
The α-Rényi divergence for α ∈ (0, 1)
 1
R dP α−1log
dP if P  R
α−1dR
Dα (P, R) =+∞ otherwise.
All the properties derived in :T. Van Erven & P. Harremos (2014). Rényi divergence and Kullback-Leibler divergence. IEEE
Transactions on Information Theory.

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

Pierre AlquierConcentration of variational approximations

Introduction : tempered posteriors & variational approx.
Main results
Applications

Tempered posteriors
Variational approximations

Bhattacharya, Pati & Yang’s approach (2/2)

B(r ) =pθ (Xi )θ ∈ Θ : K(Pθ0 , Pθ ) ≤ r and Var log≤ r.
pθ0 (Xi )Theorem (Bhattacharya, Pati & Yang)
For any sequence (rn ) such that− log π[B(rn )] ≤ nrn
we haveZ2(1 + α)2P
Dα (Pθ , Pθ0 )πn,α (dθ) ≤rn ≥ 1 −.
1−αnrn
Pierre AlquierConcentration of variational approximations

Introduction : tempered posteriors & variational approx.
Main results
Applications

Tempered posteriors
Variational approximations

Computational issues
Popular methods to compute / sample from the (tempered)posterior :Pierre AlquierConcentration of variational approximations

Introduction : tempered posteriors & variational approx.
Main results
Applications

Tempered posteriors
Variational approximations

Computational issues
Popular methods to compute / sample from the (tempered)posterior :Monte-Carlo methods : MCMC (Gibbs Sampler,
Metropolis-Hastings), SMC, Langevin Monte-Carlo etc.

Pierre AlquierConcentration of variational approximations

Introduction : tempered posteriors & variational approx.
Main results
Applications

Tempered posteriors
Variational approximations

Computational issues
Popular methods to compute / sample from the (tempered)posterior :Monte-Carlo methods : MCMC (Gibbs Sampler,
Metropolis-Hastings), SMC, Langevin Monte-Carlo etc.
optimization methods : variational Bayes (VB) and
expectation-propagation (EP).

Pierre AlquierConcentration of variational approximations

Introduction : tempered posteriors & variational approx.
Main results
Applications

Tempered posteriors
Variational approximations

Computational issues
Popular methods to compute / sample from the (tempered)posterior :Monte-Carlo methods : MCMC (Gibbs Sampler,
Metropolis-Hastings), SMC, Langevin Monte-Carlo etc.
optimization methods : variational Bayes (VB) and
expectation-propagation (EP).
Principle of VB : chose a family F of probability distributions
on Θ and approximate πn,α by a distribution in F :Pierre AlquierConcentration of variational approximations

Introduction : tempered posteriors & variational approx.
Main results
Applications

Tempered posteriors
Variational approximations

Computational issues
Popular methods to compute / sample from the (tempered)posterior :Monte-Carlo methods : MCMC (Gibbs Sampler,
Metropolis-Hastings), SMC, Langevin Monte-Carlo etc.
optimization methods : variational Bayes (VB) and
expectation-propagation (EP).
Principle 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 AlquierConcentration of variational approximations

Introduction : tempered posteriors & variational approx.
Main results
Applications

Tempered posteriors
Variational approximations

Variational approximations
π̃n,α = arg min K(ρ, πn,α )
ρ∈F
(
)
Z
n
1X
= arg min −αlog pθ (Xi )ρ(dθ) + K(ρ, π) .
ρ∈F
n i=1
Examples :Pierre AlquierConcentration of variational approximations

Introduction : tempered posteriors & variational approx.
Main results
Applications

Tempered posteriors
Variational approximations

Variational approximations
π̃n,α = arg min K(ρ, πn,α )
ρ∈F
(
)
Z
n
1X
= arg min −αlog pθ (Xi )ρ(dθ) + K(ρ, π) .
ρ∈F
n i=1
Examples :parametric approximation

F = N (µ, Σ) : µ ∈ Rd , Σ ∈ Sd+ .

Pierre AlquierConcentration of variational approximations

Introduction : tempered posteriors & variational approx.
Main results
Applications

Tempered posteriors
Variational approximations

Variational approximations
π̃n,α = arg min K(ρ, πn,α )
ρ∈F
(
)
Z
n
1X
= arg min −αlog pθ (Xi )ρ(dθ) + K(ρ, π) .
ρ∈F
n i=1
Examples :parametric approximation

F = N (µ, Σ) : µ ∈ Rd , Σ ∈ Sd+ .
mean-field approximation, Θ = Θ1 × Θ2 andF : {ρ : ρ(dθ) = ρ1 (dθ1 ) × ρ2 (dθ2 )} .
Pierre AlquierConcentration of variational approximations

Introduction : tempered posteriors & variational approx.
Main results
Applications

Concentration of the tempered posterior
A result in expectation
The misspecified case

Extension of previous result to VB
TheoremAssume that (rn ) is such that there is a distribution ρn ∈ F
with


Z
Z 
pθ (Xi )2ρn (dθ) ≤ rn
K(Pθ0 , Pθ )ρn (dθ) ≤ rn ,E logpθ0 (Xi )andK(ρn , π) ≤ nrn .
Then, for any α ∈ (0, 1),Z2(α + 1)
2P
Dα (Pθ , Pθ0 )π̃n,α (dθ) ≤rn ≥ 1 −.
1−αnrn
Pierre AlquierConcentration of variational approximations

Introduction : tempered posteriors & variational approx.
Main results
Applications

Concentration of the tempered posterior
A result in expectation
The misspecified case

A simpler result in expectation
TheoremIf we only require that there is ρn ∈ F such thatZ
K(Pθ0 , Pθ )ρn (dθ) ≤ rn
andK(ρn , π) ≤ nrn ,then, for any α ∈ (0, 1),
Z

1+α
rn .
E
Dα (Pθ , Pθ0 )π̃n,α (dθ) ≤1−αPierre AlquierConcentration of variational approximations

Introduction : tempered posteriors & variational approx.
Main results
Applications

Concentration of the tempered posterior
A result in expectation
The misspecified case

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

TheoremAssume 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 Alquierα1+αK(Q, Pθ∗ ) +
rn .
1−α
1−α
Concentration of variational approximations

Introduction : tempered posteriors & variational approx.
Main results
Applications

Gaussian VB
Matrix completion

1

Introduction : tempered posteriors & variational approx.
Tempered posteriors
Variational approximations

2

Main results
Concentration of the tempered posterior
A result in expectation
The misspecified case3

Applications
Gaussian VB
Matrix completion

Pierre AlquierConcentration of variational approximations

Introduction : tempered posteriors & variational approx.
Main results
Applications

Gaussian VB
Matrix completion

Gaussian VB
Let Θ = Rp .

Pierre AlquierConcentration of variational approximations

Introduction : tempered posteriors & variational approx.
Main results
Applications

Gaussian VB
Matrix completion

Gaussian VB
Let Θ = Rp .
We start with the family of approximations
FGΦ := Φ(dθ; m, Σ), m ∈ Rd , Σ ∈ G ⊂ S+d (R) ,Pierre AlquierConcentration of variational approximations

Introduction : tempered posteriors & variational approx.
Main results
Applications

Gaussian VB
Matrix completion

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(·) and p ∈ N? ∪ { 21 }2p|log pθ (X1 ) − log pθ0 (X1 )| ≤ M(X1 ) kθ − θ0 k2
Furthermore we assume that
EM(X1 ) =: B1 , EM 2 (X1 ) =: B2 < ∞.
Pierre AlquierConcentration of variational approximations

Introduction : tempered posteriors & variational approx.
Main results
Applications

Gaussian VB
Matrix completion

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 AlquierConcentration of variational approximations

Introduction : tempered posteriors & variational approx.
Main results
Applications

Gaussian VB
Matrix completion

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 AlquierConcentration of variational approximations

Introduction : tempered posteriors & variational approx.
Main results
Applications

Gaussian VB
Matrix completion

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πConcentration of variational approximations

Introduction : tempered posteriors & variational approx.
Main results
Applications

Gaussian VB
Matrix completion

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 AlquierConcentration of variational approximations

Introduction : tempered posteriors & variational approx.
Main results
Applications

Gaussian VB
Matrix completion

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

r

1
+
α
1
2BL
k
Dα (Pθ , Pθ0 )π̃n,α(dθ|X1n ) ≤
rn +
.
1−α
n(1 − α)k
Pierre AlquierConcentration of variational approximations

Introduction : tempered posteriors & variational approx.
Main results
Applications

Gaussian VB
Matrix completion

Matrix completion : notations
The parameter θ is a matrix M 0 ∈ Rm×p , with m, p ≥ 1.
Under PM , the observations are random entries of this matrix
with possible noise :Yi = Mi0k ,jk + εkwhere the (ik , jk ) are i.i.d U({1, . . . , m} × {1, . . . , p}). Assume
that the εk are i.i.d N (0, σ 2 ), σ 2 known. We havempkM − Nk2F
1 X X (Mi,j − Ni,j )2=.
K(PM , PN ) =mp i=1 j=1
2σ 2
2σ 2 mp

Pierre AlquierConcentration of variational approximations

Introduction : tempered posteriors & variational approx.
Main results
Applications

Gaussian VB
Matrix completion

Matrix completion : notations
The parameter θ is a matrix M 0 ∈ Rm×p , with m, p ≥ 1.
Under PM , the observations are random entries of this matrix
with possible noise :Yi = Mi0k ,jk + εkwhere the (ik , jk ) are i.i.d U({1, . . . , m} × {1, . . . , p}). Assume
that the εk are i.i.d N (0, σ 2 ), σ 2 known. We havempkM − Nk2F
1 X X (Mi,j − Ni,j )2=.
K(PM , PN ) =mp i=1 j=1
2σ 2
2σ 2 mp
Usual assumption : M 0 is low-rank.
Pierre AlquierConcentration of variational approximations

Introduction : tempered posteriors & variational approx.
Main results
Applications

Gaussian VB
Matrix completion

Prior specification - main idea
Define :M = |{z}U |{z}
VT .
|{z}
p×m

Pierre Alquierp×k k×m

Concentration of variational approximations

Introduction : tempered posteriors & variational approx.
Main results
Applications

Gaussian VB
Matrix completion

Prior specification - main idea
Define :M = |{z}U |{z}
VT .
|{z}
p×m

p×k k×m

Let U·,` ∼ N (0, γI ) denote the `-th column of M, we have :M=

kXU·,` (V·,` )T⇒rank(M) ≤ k.

`=1

Pierre AlquierConcentration of variational approximations

Introduction : tempered posteriors & variational approx.
Main results
Applications

Gaussian VB
Matrix completion

Prior specification - adaptation
R. Salakhutdinov & A. Mnih (2008). Bayesian probabilistic matrix factorization using MCMC.
Proceedings of ICML’08.

Pierre AlquierConcentration of variational approximations

Introduction : tempered posteriors & variational approx.
Main results
Applications

Gaussian VB
Matrix completion

Prior specification - adaptation
R. Salakhutdinov & A. Mnih (2008). Bayesian probabilistic matrix factorization using MCMC.
Proceedings of ICML’08.

M=

k
X

U·,` (V·,` )T`=1with k large - e.g. k = min(p, m).

Pierre AlquierConcentration of variational approximations

Introduction : tempered posteriors & variational approx.
Main results
Applications

Gaussian VB
Matrix completion

Prior specification - adaptation
R. Salakhutdinov & A. Mnih (2008). Bayesian probabilistic matrix factorization using MCMC.
Proceedings of ICML’08.

M=

k
X

U·,` (V·,` )T`=1with k large - e.g. k = min(p, m).
Definition of π :U·,` , V·,` ∼ N (0, γ` I ),γ` is itself random, such that most of the γ` ' 0
1∼ Gamma(a, b).
γ`
Pierre AlquierConcentration of variational approximations

Introduction : tempered posteriors & variational approx.
Main results
Applications

Gaussian VB
Matrix completion

Known results
T. Suzuki (2015). Convergence rate of Bayesian tensor estimator and its minimax optimality.
ICML.
(truncation of the support of π : remove large values of Mi,j ).

Pierre AlquierConcentration of variational approximations

Introduction : tempered posteriors & variational approx.
Main results
Applications

Gaussian VB
Matrix completion

Known results
T. Suzuki (2015). Convergence rate of Bayesian tensor estimator and its minimax optimality.
ICML.
(truncation of the support of π : remove large values of Mi,j ).

T. T. Mai & P. Alquier (2014). A Bayesian Approach for Noisy Matrix Completion : Optimal
Rate under General Sampling Distribution. Electronic Journal of Statistics.
(truncation of the support of π : remove large values of Ui,k and Vj,k ).

Pierre AlquierConcentration of variational approximations

Introduction : tempered posteriors & variational approx.
Main results
Applications

Gaussian VB
Matrix completion

Known results
T. Suzuki (2015). Convergence rate of Bayesian tensor estimator and its minimax optimality.
ICML.
(truncation of the support of π : remove large values of Mi,j ).

T. T. Mai & P. Alquier (2014). A Bayesian Approach for Noisy Matrix Completion : Optimal
Rate under General Sampling Distribution. Electronic Journal of Statistics.
(truncation of the support of π : remove large values of Ui,k and Vj,k ).

In both cases, (in expectation or with large probability),Z
kM − M 0 k2F
rank(M 0 ) max(m, p) log(. . . )
π̂
(dM)
.
.
n,α
2σ 2 mpn

Pierre AlquierConcentration of variational approximations

Introduction : tempered posteriors & variational approx.
Main results
Applications

Gaussian VB
Matrix completion

Variational approximation
Y. J. Lim & Y. W. Teh (2007). Variational Bayesian approach to movie rating prediction.
Proceedings of KDD cup and workshop.

Mean-field approximation, F given by :ρ(dU, dV , dγ) =mOρUi (dUi,· )i=1Pierre Alquier

p
O
j=1

ρVj (dVj,· )KOργk (γk ).

k=1

Concentration of variational approximations

Introduction : tempered posteriors & variational approx.
Main results
Applications

Gaussian VB
Matrix completion

Variational approximation
Y. J. Lim & Y. W. Teh (2007). Variational Bayesian approach to movie rating prediction.
Proceedings of KDD cup and workshop.

Mean-field approximation, F given by :ρ(dU, dV , dγ) =mOρUi (dUi,· )

i=1

p
O
j=1

ρVj (dVj,· )KOργk (γk ).

k=1

It can be shown that1
ρUi is N (mTi,· , Vi ),2
ρVj is N (nTj,· , Wj ),3
ργk is Γ(a + (m1 + m2 )/2, βk ),for some m × K matrix m whose rows are denoted by mi,· ,some p × K matrix n and some vector β = (β1 , . . . , βK ).
Pierre AlquierConcentration of variational approximations

Introduction : tempered posteriors & variational approx.
Main results
Applications

Gaussian VB
Matrix completion

The VB algorithm
The parameters are updated iteratively through the formulae
1

moments of U :2αTmi,· :=

−1

Vi

:=

n

Vi

X

T
k

Yi ,j nj ,·k k

k:ik =ii m1 + m2
2α X hT−1
Wj + nj ,· nj ,· + a +diag(β)kkk
n k:i =i2k2moments of V :Tnj,· :=

−1

Wj

:=

2α
n

Wj

X

T
k

Yi ,j mi ,·k k

k:jk =ji 
2α X hm1 + m2
T−1
Vi + mi ,· mi ,· + a +diag(β)kkk
n k:j =j2
k3

moments of γ :

βk :=

1
2





m1 
m2 

 X
X
2
2
mi,k + (Vi )k,k +nj,k + (Vj )k,k  .
i=1

Pierre Alquierj=1

Concentration of variational approximations

Introduction : tempered posteriors & variational approx.
Main results
Applications

Gaussian VB
Matrix completion

Application of our theorem
TheoremAssume M = Ū V̄ T whereŪ = (Ū1,· | . . . |Ūr ,· |0| . . . |0) and V̄ = (V̄1,· | . . . |V̄r ,· |0| . . . |0)and supi,k |Ui,k |, supj,k |Vj,k | ≤ B. Take a > 0 as any constant2
and b = 512(nmp)B4 [(m∨p)K ]2 . ThenZP2(α + 1)
2
Dα (PM , PM 0 )π̃n,α (dM) ≤rn ≥ 1 −1−αnrn
where rn =C(a, σ 2 , B)r max(m, p) log(nmp).
nPierre AlquierConcentration of variational approximations

Introduction : tempered posteriors & variational approx.
Main results
Applications

Gaussian VB
Matrix completion

Thank you !

Pierre AlquierConcentration of variational approximations