Introduction
Optimizing the prior
Tight generalization certificates

What to expect from
PAC-Bayes bounds?
Pierre Alquier

AABI 2022

Pierre Alquier, RIKEN AIPPAC-Bayes bounds

Introduction
Optimizing the prior
Tight generalization certificates

François Laviolette
1962–2021

Pierre Alquier, RIKEN AIPPAC-Bayes bounds

Introduction
Optimizing the prior
Tight generalization certificates

PAC-Bayes bounds
Finding the best classifier

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

generalization riskh i
R(f ) = E(X ,Y )∼P ` f (X ), Y
randomized prediction / ensemble / ... : f ∼ ρ,compare Ef ∼ρ [R(f )] and Ef ∼ρ [r (f )].
In this talk : `(u, v ) ∈ [0, 1].
Pierre Alquier, RIKEN AIPPAC-Bayes bounds

Introduction
Optimizing the prior
Tight generalization certificates

PAC-Bayes bounds
Finding the best classifier

A generic PAC-Bayes bound
Let S denote the sample S = [(Xi , Yi )]ni=1 .
Theorem
Let D : [0, 1]2 → R be any convex function. For any ε > 0,"PS ∀ρ, D Ef ∼ρ [r (f )], Ef ∼ρ [R(f )]nD(r (f ),R(f ))KL(ρkπ) + log ES Ef ∼π e ε≤n#≤ ε.

Germain, P., Lacasse, A., Laviolette, F. and Marchand, M. (2009). PAC-Bayesian Learning ofLinear Classifiers. ICML.

Pierre Alquier, RIKEN AIPPAC-Bayes bounds

Introduction
Optimizing the prior
Tight generalization certificates

PAC-Bayes bounds
Finding the best classifier

A more explicit bound
For D(u, v ) = 2(u − v )2 we obtain :hi2 KL(ρkπ) + log 3ε2 Ef ∼ρ [R(f )] − Ef ∼ρ [r (f )] ≤nsEf ∼ρ [R(f )] ≤ Ef ∼ρ [r (f )] +KL(ρkπ) + log 3ε2n

McAllester, D. (2003). PAC-Bayesian Learning of Linear Classifiers. Machine learning.

Pierre Alquier, RIKEN AIPPAC-Bayes bounds

Introduction
Optimizing the prior
Tight generalization certificates

PAC-Bayes bounds
Finding the best classifier

A bound in expectation

Theorem
For any (data-dependent) ρ,rES Ef ∼ρ [R(f )] ≤ ES Ef ∼ρ [r (f )] +2ES KL(ρkπ)
nImportant ! This bound does not give a generalization
certificate.

Pierre Alquier, RIKEN AIPPAC-Bayes boundsIntroduction
Optimizing the prior
Tight generalization certificates

PAC-Bayes bounds
Finding the best classifier

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 bounds

Introduction
Optimizing the prior
Tight generalization certificates

PAC-Bayes bounds
Finding the best classifier

PAC-Bayes bound for classifier selectionMore generally, M classifiers f1 , . . . , fM :Puniform 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 bounds

Introduction
Optimizing the prior
Tight generalization certificates

PAC-Bayes bounds
Finding the best classifier

Ask an undergrad student in statistics
Say R(f1 ) < R(f2 ),hiˆ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]f
and r (f2 ) − r (f1 )N ∆R, vn sor  exp − n[∆R]2v
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 boundsIntroduction
Optimizing the prior
Tight generalization certificates

PAC-Bayes bounds
Finding the best classifier

Which is the largest ?

Pierre Alquier, RIKEN AIPPAC-Bayes bounds

Introduction
Optimizing the prior
Tight generalization certificates

PAC-Bayes bounds
Finding the best classifier

Objective of this talk

PAC-Bayes bounds (basic version) can be suboptimal inmany ways.
we will see that in the example above, the uniform priorleads to the catastrophe.
we will discuss “prior improvement” ideas in theory andpractice.

Pierre Alquier, RIKEN AIPPAC-Bayes bounds

IntroductionOptimizing the prior
Tight generalization certificates

PAC-Bayes bounds
Finding the best classifier

Contents
1

Introduction
PAC-Bayes bounds
Finding the best classifier

2

Optimizing the prior
Optimization with respect to the priorConsequences

3

Tight generalization certificatesSome ideas
How far can we go ?

Pierre Alquier, RIKEN AIPPAC-Bayes bounds

Introduction
Optimizing the prior
Tight generalization certificates

Optimization with respect to the priorConsequences

Contents
1

Introduction
PAC-Bayes bounds
Finding the best classifier

2

Optimizing the prior
Optimization with respect to the priorConsequences

3

Tight generalization certificatesSome ideas
How far can we go ?

Pierre Alquier, RIKEN AIPPAC-Bayes bounds

Introduction
Optimizing the prior
Tight generalization certificates

Optimization with respect to the priorConsequences

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 bounds

Introduction
Optimizing the prior
Tight generalization certificates

Optimization with respect to the priorConsequences

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 bounds

Introduction
Optimizing the prior
Tight generalization certificates

Optimization with respect to the priorConsequences

PAC-Bayes and MI bounds

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

q MI :

PAC-Bayes:
q2I(ρ,S)..
n

2ES KL(ρkπ)
nCatoni :optimize w.r.t. π

Pierre Alquier, RIKEN AIPPAC-Bayes bounds

Introduction
Optimizing the prior
Tight generalization certificates

Optimization with respect to the priorConsequences

Classifier selectionr (f1 ) = 0.15

Pierre Alquier, RIKEN AIPr (f2 ) = 0.01

PAC-Bayes bounds

Introduction
Optimizing the prior
Tight generalization certificates

Optimization with respect to the priorConsequences

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∆Rlog2v1−α≤ min R(f ) +fnn∆R
Take α = exp −Φ...
2v
Pierre Alquier, RIKEN AIPPAC-Bayes bounds

Introduction
Optimizing the prior
Tight generalization certificates

Optimization with respect to the priorConsequences

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n∆216log 1 + Me− 32fn∆p√
For ∆ ' 1 n we recover the log(M)/n rate...
ES R(fˆ) ≤ min R(f ) +Alquier, P. (2021). User-friendly introduction to PAC-Bayes bounds. Preprint arXiv.

Pierre Alquier, RIKEN AIPPAC-Bayes bounds

Introduction
Optimizing the prior
Tight generalization certificates

Optimization with respect to the priorConsequences

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(Θ) = duniformpriorqdlog dnndlog dnn

localizedq priordndn(MA) = margin assumption, includes noiseless classification
Alquier, P. (2021). User-friendly introduction to PAC-Bayes bounds. Preprint arXiv.

Pierre Alquier, RIKEN AIPPAC-Bayes bounds

Introduction
Optimizing the prior
Tight generalization certificatesSome ideas
How far can we go ?

Contents
1

Introduction
PAC-Bayes bounds
Finding the best classifier

2

Optimizing the prior
Optimization with respect to the priorConsequences

3

Tight generalization certificatesSome ideas
How far can we go ?

Pierre Alquier, RIKEN AIPPAC-Bayes bounds

Introduction
Optimizing the prior
Tight generalization certificatesSome ideas
How far can we go ?

Towards tighter generalization certificatesdefine an architecture : {fw , w ∈ W}.
minimize (in ρ) a PAC-Bayes bound on Ew ∼ρ [R(fw )].
outcome :the posterior ρ,a numerical certificate for Ew ∼ρ [R(fw )].
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. (2020). Tighter riskcertificates for neural networks. Preprint arXiv.

(standard) PAC-Bayes bounds lead to vacuous certificates,
propose many improvements to obtain tighter bounds.
Pierre Alquier, RIKEN AIPPAC-Bayes bounds

Introduction
Optimizing the prior
Tight generalization certificatesSome ideas
How far can we go ?

Some ideas

Prior on the weights : w ∼ N (w0 , σI ).
w0 chosen randomly = the initialization of the SGD,
σ = c exp(−j/b), j ∈ N (with union bound).
other option : sample splitting. Learn a prior on the firsthalf, learn ρ via minimizing a PAC-Bayes bound on thesecond half only.
etc.

Pierre Alquier, RIKEN AIPPAC-Bayes bounds

Introduction
Optimizing the prior
Tight generalization certificatesSome ideas
How far can we go ?

Empirical bound with a localized prior
TheoremPut
π−βr (f ) ∝ exp(−βr (f ))p(f ).
Fix λ ∈ [0, n] and ξ ∈ [0, 1). For any ε > 0,PS ∀ρ, Ef ∼ρ [R(f )]≤(1 − ξ)Ef ∼ρ [r (f )] + KL (ρkπ−ξλr ) + (1 + ξ) log 2ε2(1 − ξ)λ + (1 + ξ) λn!
≥1−εCatoni, O. (2003). A PAC-Bayesian approach to adaptive classification. Preprint LPMA.

Pierre Alquier, RIKEN AIPPAC-Bayes bounds

Introduction
Optimizing the prior
Tight generalization certificatesSome ideas
How far can we go ?

Pros and cons of Catoni’s localized bounds
π−βr (f ) ∝ exp(−βr (f ))p(f ).
ppros : we recover the rates in d/n and d/n above...
cons :KL (ρkπ−ξλr )= KL(ρkp) + βEf ∼ρ [r (f )] + log Ef ∼p [exp(−βr (f ))]Should be tried in practice.

Pierre Alquier, RIKEN AIPPAC-Bayes bounds

Introduction
Optimizing the prior
Tight generalization certificatesSome ideas
How far can we go ?

Future objective
On the “theoretical bounds” side, most issues with PAC-Bayesand MI bounds are solved in
Grünwald, P., Steinke, T. and Zakynthinou, L. (2021). MAC-Bayes and Conditional Mutual
Information : Fast rate bounds that handle general VC classes. Preprint arXiv.

How much can we improve the numerical certificate via
data-dependent priors ? Besides Catoni’s bound we mentioned
earlier, more recent works :Parrado-Hernández, E., Ambroladze, A., Shawe-Taylor, J. and Sun., S. (2012). PAC-Bayesbounds with data dependent priors. JMLR.
Dziugaite, G. K. and Roy, D. M. (2018). Data-dependent PAC-Bayes priors via differential
privacy. NeurIPS.

Pierre Alquier, RIKEN AIPPAC-Bayes bounds