Introduction
PAC-Bayes point of view on contraction (and vice-versa)

PAC-Bayes and contraction of theposterior
Pierre AlquierThe (International) Bayes Club – Apr. 21, 2022

Pierre Alquier, RIKEN AIPPAC-Bayes and contraction of the posterior

Introduction
PAC-Bayes point of view on contraction (and vice-versa)

Two worlds

Pierre Alquier, RIKEN AIPPAC-Bayes and contraction of the posterior

Introduction
PAC-Bayes point of view on contraction (and vice-versa)

Contents

1

Introduction
Contraction of the posterior
PAC-Bayes bounds

2

PAC-Bayes point of view on contraction (and vice-versa)
An empirical point of view on the prior mass condition
Variational approximations

Pierre Alquier, RIKEN AIPPAC-Bayes and contraction of the posterior

Introduction
PAC-Bayes point of view on contraction (and vice-versa)

Contraction of the posterior
PAC-Bayes bounds

Contents

1

Introduction
Contraction of the posterior
PAC-Bayes bounds

2

PAC-Bayes point of view on contraction (and vice-versa)
An empirical point of view on the prior mass condition
Variational approximations

Pierre Alquier, RIKEN AIPPAC-Bayes and contraction of the posterior

Introduction
PAC-Bayes point of view on contraction (and vice-versa)

Contraction of the posterior
PAC-Bayes bounds

Notations and setting
X1 , . . . , Xn i.i.d. from P0 ,(Pθ , θ ∈ Θ) model, densities pθ (x),prior π on Θ,posteriornYπ(dθ|S) ∝!
pθ (Xi ) π(dθ).

i=1Question : if P0 = Pθ0 , do we have
ES Pθ∼π(·|S) [d(θ, θ0 ) ≤ rn ] −−−→ 1n→∞for some
rn −−−→ 0 ?
n→∞Pierre Alquier, RIKEN AIPPAC-Bayes and contraction of the posterior

Introduction
PAC-Bayes point of view on contraction (and vice-versa)

Contraction of the posterior
PAC-Bayes bounds

Conditions for contraction
This can be proven under the following 2 assumptions :pθ (Xi )B(r ) = θ ∈ Θ : KL(Pθ0 , Pθ ) ≤ r and Var log≤r .
pθ0 (Xi )Prior mass condition
The sequence (rn ) satisfies
π[B(rn )] ≥ e−dnrn that is log π[B(rn )] ≥ −dnrn .
Test condition
There is a sequence of tests φn = φn (S) ∈ [0, 1] such thatES φn −−−→ 0, andn→∞

supd(θ,θ0 )>rnES∼Pθn [1 − φn ] = o e−(d+2)nrn .

Pierre Alquier, RIKEN AIPPAC-Bayes and contraction of the posterior

Introduction
PAC-Bayes point of view on contraction (and vice-versa)

Contraction of the posterior
PAC-Bayes bounds

Tempered posteriors - 0 < α < 1π̂α (dθ) ∝nY!αpθ (Xi )π(dθ).

i=1π̂α is more robust than π(·|S) to misspecifitation.
Grünwald, P. & Van Ommen, T. (2017). Inconsistency of Bayesian inference for misspecified
linear models, and a proposal for repairing it. Bayesian analysis.

The α-Rényi divergence
1log
Dα (P, R) =α−1

Z(dP)α (dR)1−α .

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

Pierre Alquier, RIKEN AIPPAC-Bayes and contraction of the posterior

Introduction
PAC-Bayes point of view on contraction (and vice-versa)

Contraction of the posterior
PAC-Bayes bounds

Contraction of tempered posteriors

Theorem
For any rn with nrn → ∞ satisfying the prior mass condition
only, there is a known C (d) such thatC (d)rn−−−→ 1.
ES Pθ∼π̂α Dα (Pθ , Pθ0 ) ≤n→∞1−αBhattacharya, A., Pati, D. & Yang, Y. (2019). Bayesian fractional posteriors. Annals of Statistics.

Pierre Alquier, RIKEN AIPPAC-Bayes and contraction of the posterior

Introduction
PAC-Bayes point of view on contraction (and vice-versa)

Contraction of the posterior
PAC-Bayes bounds

Contents

1

Introduction
Contraction of the posterior
PAC-Bayes bounds

2

PAC-Bayes point of view on contraction (and vice-versa)
An empirical point of view on the prior mass condition
Variational approximations

Pierre Alquier, RIKEN AIPPAC-Bayes and contraction of the posterior

Introduction
PAC-Bayes point of view on contraction (and vice-versa)

Contraction of the posterior
PAC-Bayes bounds

Objective of PAC-Bayes bounds
empirical riskn
1X r (f ) =` f (Xi ), Yi
n i=1

generalization riskh 
iR(f ) = E(X ,Y )∼P ` f (X ), Y
randomized prediction / ensemble / ... : f ∼ ρ,
compare Ef ∼ρ [R(f )] and Ef ∼ρ [r (f )].
In a first time, we only consider bounded losses `(u, v ) ∈ [0, 1].
Pierre Alquier, RIKEN AIPPAC-Bayes and contraction of the posterior

Introduction
PAC-Bayes point of view on contraction (and vice-versa)

Contraction of the posterior
PAC-Bayes bounds

A generic PAC-Bayes bound
Let S denote the sample S = [(Xi , Yi )]ni=1 .
Theorem
For any ε > 0, for any λ > 0,"PS ∀ρ, Ef ∼ρ [R(f )]KL(ρkπ) + log 1ελ≤ Ef ∼ρ [r (f )] ++2nλ#≥ 1 − ε.

Catoni, O. (2003). A PAC-Bayesian approach to adaptive classification. Preprint.

Pierre Alquier, RIKEN AIPPAC-Bayes and contraction of the posterior

Introduction
PAC-Bayes point of view on contraction (and vice-versa)

Contraction of the posterior
PAC-Bayes bounds

Minimization of PAC-Bayes bounds

KL(ρkπ) + log 1ελEf ∼ρ [R(f )] ≤ Ef ∼ρ [r (f )] ++2nλThis motivates the introduction ofKL(ρkπ)ρ̂λ = arg min Ef ∼ρ [r (f )] +.
λρ⇒ ρ̂(df ) ∝ exp(−λr (f ))π(df ).
Question : how small can the bound be ?

Pierre Alquier, RIKEN AIPPAC-Bayes and contraction of the posterior

Introduction
PAC-Bayes point of view on contraction (and vice-versa)

Contraction of the posterior
PAC-Bayes bounds

A bound in expectation
Theorem
For any (data-dependent) ρ and for any λ,λKL(ρkπ)
ES Ef ∼ρ [R(f )] ≤ ES Ef ∼ρ [r (f )] ++2nλand λ = ES KL(ρkπ)/2n leads tor
ES Ef ∼ρ [R(f )] ≤ ES Ef ∼ρ [r (f )] +2ES KL(ρkπ)
nImportant ! This it does not give a generalization certificate.
But necessary to study the statistical properties of ρ̂λ .
Pierre Alquier, RIKEN AIPPAC-Bayes and contraction of the posterior

Introduction
PAC-Bayes point of view on contraction (and vice-versa)

Contraction of the posterior
PAC-Bayes bounds

Generalization under ρ̂λKL(ρkπ)λ+ES Ef ∼ρ̂λ [R(f )] ≤ ES min Ef ∼ρ [r (f )] +ρ2nλλKL(ρkπ)≤ min Ef ∼ρ [R(f )] ++ρ2nλand take ρ as π restricted to {f : R(f ) − inf R ≤ s} :1log π{f :R(f )−inf R≤s}λ+.
2nλPrior mass condition : log π{f : R(f ) − inf R ≤ s} ≥ d log(s),ES Ef ∼ρ̂λ [R(f )] ≤ inf R + s +ES Ef ∼ρ̂λ [R(f )] ≤ inf R + s +d log 1sλ+.
2nλOptimize in s and λ :rES Ef ∼ρ̂λ [R(f )] ≤ inf R +Pierre Alquier, RIKEN AIP

2dnlog .
nd

PAC-Bayes and contraction of the posterior

Introduction
PAC-Bayes point of view on contraction (and vice-versa)

Contraction of the posterior
PAC-Bayes bounds

PAC-Bayes : other topics

unbounded losses : many important works, see referencesat the end.
let’s discuss briefly the optimality of the rates.

Pierre Alquier, RIKEN AIPPAC-Bayes and contraction of the posterior

Introduction
PAC-Bayes point of view on contraction (and vice-versa)

Contraction of the posterior
PAC-Bayes bounds

An easy problem : find the best neural network
You have one data set S that you will use as a test set, andtwo classifiers.

r (f1 ) = 0.15
R(f1 ) =?
Pierre Alquier, RIKEN AIPr (f2 ) = 0.01
R(f2 ) =?
PAC-Bayes and contraction of the posterior

Introduction
PAC-Bayes point of view on contraction (and vice-versa)

Contraction of the posterior
PAC-Bayes bounds

PAC-Bayes bound for classifier selectionMore generally, M classifiers f1 , . . . , fM :P
uniform prior : π = M1 M
i=1 δfifˆ = arg minf r (f ) and ρ = δ ˆfr

2ES KL(ρkπ)
ES Ef ∼ρ [R(f )] ≤ ES Ef ∼ρ [r (f )] +nr
2 log(M)
ES R(fˆ) ≤ ES [min r (f )] +fnr
ES R(fˆ) ≤ min R(f ) +fPierre Alquier, RIKEN AIP

2 log(M)n

PAC-Bayes and contraction of the posterior

Introduction
PAC-Bayes point of view on contraction (and vice-versa)

Contraction of the posterior
PAC-Bayes bounds

Ask an undergrad student in statistics
Say R(f1 ) < R(f2 ),ih
ES R(fˆ) = ES R(f1 )1fˆ=f1 + R(f2 )1fˆ=f2hi≤ ES R(f1 ) + 1fˆ=f2= min R(f ) + PS [r (f2 ) − r (f1 ) < 0]fand r (f2 ) − r (f1 )N ∆R, vn sor  exp − n[∆R]2v
np n ,PS [r (f2 ) − r (f1 ) < 0] ∼ Φ ∆R∼v
∆R 2π v

∆R = R(f2 ) − R(f1 ) and v = R(f2 )[1 − R(f2 )] + R(f1 )[1 − R(f1 )] − 2P(f1 (X ) = f2 (X ) 6= Y ).

Pierre Alquier, RIKEN AIPPAC-Bayes and contraction of the posterior

Introduction
PAC-Bayes point of view on contraction (and vice-versa)

Contraction of the posterior
PAC-Bayes bounds

Which is the largest ?

Pierre Alquier, RIKEN AIPPAC-Bayes and contraction of the posterior

Introduction
PAC-Bayes point of view on contraction (and vice-versa)

Contraction of the posterior
PAC-Bayes bounds

Optimizing with respect to the prior
In practice, popular choices :ρ = δθ̂ ,ρ(f ) ∝ exp(−λr (f ))p(f )...
Once ρ is fixed, why not optimize with respect to π ?
r2ES KL(ρkπ)
ES Ef ∼ρ [R(f )] ≤ ES Ef ∼ρ [r (f )] +nES KL(ρkπ) = ES KL(ρkES ρ) + KL(ES ρkπ)|{z} | {z }=:I(ρ,S)=0 if π=ES ρ

Catoni, O. (2007). PAC-Bayesian supervised learning : the thermodynamics of statistical learning.
IMS lecture notes – monograph series.
Pierre Alquier, RIKEN AIPPAC-Bayes and contraction of the posterior

Introduction
PAC-Bayes point of view on contraction (and vice-versa)

Contraction of the posterior
PAC-Bayes bounds

Mutual information boundThe corresponding bound was re-discovered (independently).
Mutual information boundrES Ef ∼ρ [R(f )] ≤ ES Ef ∼ρ [r (f )] +2I(ρ, S)
nRusso, D. and Zou, J. (2019). How much does your data exploration overfit ? controlling bias via
information usage. IEEE Transactions on Information Theory.

Pierre Alquier, RIKEN AIPPAC-Bayes and contraction of the posterior

Introduction
PAC-Bayes point of view on contraction (and vice-versa)

Contraction of the posterior
PAC-Bayes bounds

PAC-Bayes and MI bounds

I(ρ, S) = ES KL(ρkES ρ) ≤ ES KL(ρkπ).

q MI :

PAC-Bayes:
q2I(ρ,S)..
n2ES KL(ρkπ)
nCatoni :optimize w.r.t. π

Pierre Alquier, RIKEN AIPPAC-Bayes and contraction of the posterior

Introduction
PAC-Bayes point of view on contraction (and vice-versa)

Contraction of the posterior
PAC-Bayes bounds

Classifier selectionr (f1 ) = 0.15

Pierre Alquier, RIKEN AIPr (f2 ) = 0.01

PAC-Bayes and contraction of the posterior

Introduction
PAC-Bayes point of view on contraction (and vice-versa)

Contraction of the posterior
PAC-Bayes bounds

Application in the selection problem
Prior πα (f ) = αδf1 + (1 − α)δf2 .
Say R(f1 ) < R(f2 ). For any α,r2ES KL(ρkπα )ES R(fˆ) ≤ min R(f ) +fns

12ES 1fˆ=f1 log α1 + 1fˆ=f2 log 1−α= min R(f ) +fns 12 log α1 + Φ n∆Rlog
2v
1−α≤ min R(f ) +fn
n∆R
Take α = exp −Φ...
2v
Pierre Alquier, RIKEN AIPPAC-Bayes and contraction of the posterior

Introduction
PAC-Bayes point of view on contraction (and vice-versa)

Contraction of the posterior
PAC-Bayes bounds

Application in the selection problem
TheoremIn the case of M functions f1 , . . . , fM , put∆=

mini:R(fi )6=minf R(f )R(fi ) − min R(f ).

Then
2
16− n∆
ˆ32
ES R(f ) ≤ min R(f ) +log 1 + Me
fn∆p√
For ∆ ' 1 n we recover the log(M)/n rate...

Pierre Alquier, RIKEN AIPPAC-Bayes and contraction of the posterior

Introduction
PAC-Bayes point of view on contraction (and vice-versa)

Contraction of the posterior
PAC-Bayes bounds

Optimization of the prior : more cases
When ρ(f ) ∝ exp(−λr (f ))p(f ), Catoni suggests to use the(almost optimal) “localized prior”
π−βR (f ) ∝ exp(−βR(f ))p(f ).

situation
dim(Θ) = d(MA) + dim(Θ) = duniform
prior
qdlog dnndlog dnn

localized
q priordndn(MA) = margin assumption, includes noiseless classification
Pierre Alquier, RIKEN AIPPAC-Bayes and contraction of the posterior

Introduction
PAC-Bayes point of view on contraction (and vice-versa)

Contraction of the posterior
PAC-Bayes bounds

Additional references
Arguments for generalized posteriors :Bissiri, P. G., Holmes, C. C. & Walker, S. G. (2016). A general framework for updating belief
distributions. JRSS-B.
Knoblauch, J., Jewson, J. & Damoulas, T. (2022). An Optimization-centric View on Bayes’
Rule : Reviewing and Generalizing Variational Inference. JMLR (to appear).

Also note that the connection between contraction andPAC-Bayes was already used by many authors to study
generalized posteriors :Grünwald, P. D. & Mehta, N. A. (2020). Fast Rates for General Unbounded Loss Functions :From ERM to Generalized Bayes. JMLR.
Syring, N. & Martin, R. (2020). Gibbs posterior concentration rates under sub-exponential typelosses. Preprint arXiv :2012.04505.

Pierre Alquier, RIKEN AIPPAC-Bayes and contraction of the posterior

Introduction
PAC-Bayes point of view on contraction (and vice-versa)

An empirical point of view on the prior mass condition
Variational approximations

Contents

1

Introduction
Contraction of the posterior
PAC-Bayes bounds

2

PAC-Bayes point of view on contraction (and vice-versa)
An empirical point of view on the prior mass condition
Variational approximations

Pierre Alquier, RIKEN AIPPAC-Bayes and contraction of the posterior

Introduction
PAC-Bayes point of view on contraction (and vice-versa)

An empirical point of view on the prior mass condition
Variational approximations

Bayesian deep learning
Deep neural networks :amazing practical performances,theory not yet complete.
Contraction of the posterior for Bayesian deep networks :Polson, N. G. & Ročková, V. (2018). Posterior concentration for sparse deep learning. NeurIPS.
Chérief-Abdellatif, B. E. (2020). Convergence rates of variational inference in sparse deeplearning. ICML.

beautiful results but do not really match the algorithm used inpractice...

Pierre Alquier, RIKEN AIPPAC-Bayes and contraction of the posterior

Introduction
PAC-Bayes point of view on contraction (and vice-versa)

An empirical point of view on the prior mass condition
Variational approximations

Empirical prior mass
Among practitioners, consensus : “flat minima” lead to good
generalization in deep learning. Tentative interpretation :r (f ∗ ) “flat” ↔ {f : r (f ) − r (f ∗ ) ≤ s} is large↔ π({f : r (f ) − r (f ∗ ) ≤ s}) is not too small.
"KL(ρkπ) + log 1ελEf ∼ρ̂ [R(f )] ≤ min Ef ∼ρ [r (f )] ++ρ2nλ#take ρ as π restricted to {f : r (f ) − r (f ∗ ) ≤ s},
11log+log∗λεπ({f :r (f )−r (f )≤s}).
Ef ∼ρ̂ [R(f )] ≤ min r (f ∗ ) +s ++s| {z }2nλ=0Pierre Alquier, RIKEN AIPPAC-Bayes and contraction of the posterior

Introduction
PAC-Bayes point of view on contraction (and vice-versa)

An empirical point of view on the prior mass condition
Variational approximations

PAC-Bayes and deep learning
In recent papers : minimization of PAC-Bayes bounds to train
a neural network, leading to tight generalization certificates.
Dziugaite, G. K. and Roy, D. M. (2017). Computing nonvacuous generalization bounds for deep
(stochastic) neural networks with many more parameters than training data. UAI.
Pérez-Ortiz, M., Rivasplata, O., Shawe-Taylor, J. and Szepesvári, C. (2021). Tighter riskcertificates for neural networks. JMLR.

Pierre Alquier, RIKEN AIPPAC-Bayes and contraction of the posterior

Introduction
PAC-Bayes point of view on contraction (and vice-versa)

An empirical point of view on the prior mass condition
Variational approximations

Contents

1

Introduction
Contraction of the posterior
PAC-Bayes bounds

2

PAC-Bayes point of view on contraction (and vice-versa)
An empirical point of view on the prior mass condition
Variational approximations

Pierre Alquier, RIKEN AIPPAC-Bayes and contraction of the posterior

Introduction
PAC-Bayes point of view on contraction (and vice-versa)

An empirical point of view on the prior mass condition
Variational approximations

Variational approximations
Reminder :X1 , . . . , Xn i.i.d. from P0 ,(Pθ , θ ∈ Θ) model, densities pθ (x),prior π on Θ,Qαtempered posterior π̂α (dθ) ∝ ( ni=1 pθ (Xi )) π(dθ).
Variational approximations
Let F be a set of (tractable) distributions,π̃α = arg min K(ρ, πα )ρ∈F(Z= arg min −αρ∈F)
n1Xlog pθ (Xi )ρ(dθ) + K(ρ, π) .
n i=1Pierre Alquier, RIKEN AIPPAC-Bayes and contraction of the posterior

Introduction
PAC-Bayes point of view on contraction (and vice-versa)

An empirical point of view on the prior mass condition
Variational approximations

PAC-Bayes bound for tempered posteriors
TheoremAlquier, P. & Ridgway, J. (2020). Concentration of tempered posteriors and of their variationalapproximations. The Annals of Statistics.

ES Eθ∼π̃α Dα (Pθ , Pθ0 )
αKL(ρ, π).
≤ infEθ∼ρ KL(Pθ , Pθ0 ) +ρ∈F 1 − αn(1 − α)Assume that for any n, there is a ρn ∈ F such thatEθ∼ρn KL(Pθ , Pθ0 ) ≤ rnKL(ρn , π) ≤ nrn ,then2αrnES Eθ∼π̃α Dα (Pθ , Pθ0 ) ≤.
1−αPierre Alquier, RIKEN AIPPAC-Bayes and contraction of the posterior

Introduction
PAC-Bayes point of view on contraction (and vice-versa)

An empirical point of view on the prior mass condition
Variational approximations

Further references :Application to mixture models, application to Markov chains :Chérief-Abdellatif, B.-E. & Alquier, P. (2018). Consistency of variational Bayes inference forestimation and model selection in mixtures. Electronic Journal of Statistics.
Banerjee, I., Rao, V. A. & Honnappa, H. (2021). PAC-Bayes Bounds on Variational Tempered
Posteriors for Markov Models. Entropy.

Allowing α = 1 :Y. Yang, D. Pati & A. Bhattacharya (2020). α-Variational Inference with Statistical Guarantees.
The Annals of Statistics.
F. Zhang & C. Gao (2020). Convergence Rates of Variational Posterior Distributions. The Annalsof Statistics.
Ohn, I. & Lin, L. (2021). Adaptive variational Bayes : Optimality, computation and applications.
Preprint arXiv :2109.03204.

Pierre Alquier, RIKEN AIPPAC-Bayes and contraction of the posterior

Introduction
PAC-Bayes point of view on contraction (and vice-versa)

An empirical point of view on the prior mass conditionVariational approximations

Advertisement

Alquier, P. (2021). User-friendly
introduction to PAC-Bayes bounds.
Preprint arXiv.

Discusses the topics above andunbounded losses,
non i.i.d. observations,...
and provides references.

Pierre Alquier, RIKEN AIPPAC-Bayes and contraction of the posterior

Introduction
PAC-Bayes point of view on contraction (and vice-versa)

An empirical point of view on the prior mass condition
Variational approximations

La fin終わり
ありがとう ございます。

Pierre Alquier, RIKEN AIPPAC-Bayes and contraction of the posterior