PAC-Bayes bounds : introduction
PAC-Bayes and Mutual Information bounds

PAC-Bayes bounds
Pierre Alquier

Machine Learning Summer School
Okinawa Institute of Science and Technology, March 2024

Pierre Alquier, ESSEC Business School

PAC-Bayes

PAC-Bayes bounds : introduction
PAC-Bayes and Mutual Information bounds

Singapore

Cergy (near Paris)

Kamelia
DAUDEL

JeroenROMBOUTS

Olga KLOPP

Vincenzo
ESPOSITO VINZIMarie KRATZ
Guillaume
CHEVILLON
Roberto RENO

Mohamed NDAOUD
Guillaume LECUE

Jeremy HENG

Pierre JACOB

Pierre ALQUIERPierre Alquier, ESSEC Business School

PAC-Bayes

PAC-Bayes bounds : introduction
PAC-Bayes and Mutual Information bounds

Information :contact : alquier@essec.edu
webpage : https ://pierrealquier.github.io/
This lecture will be based on :Alquier, P. (2024). User-friendly Introduction to PAC-Bayes bounds. Foundations and Trends©
in Machine Learning.

(link to preliminary arXiv version + slides on my webpage).

Many thanks to Richard Cariño III who helped with the drawings !

Pierre Alquier, ESSEC Business School

PAC-Bayes

PAC-Bayes bounds : introduction
PAC-Bayes and Mutual Information bounds

1

PAC-Bayes bounds : introduction
Generalization bounds and PAC-Bayes
Minimization of the PAC-Bayes boundA zoo of PAC-Bayes bounds

2

PAC-Bayes and Mutual Information bounds
Excess risk bounds
Fast rates
Mutual information bounds

Pierre Alquier, ESSEC Business School

PAC-Bayes

PAC-Bayes bounds : introduction
PAC-Bayes and Mutual Information bounds

Generalization bounds and PAC-Bayes
Minimization of the PAC-Bayes boundA zoo of PAC-Bayes bounds

Objects x ∈ X , labels y ∈ Y.
Predictor : function fθ : X → Y indexed by θ ∈ Θ.

dog
shark
heron
cat
...

Pierre Alquier, ESSEC Business School

PAC-Bayes

PAC-Bayes bounds : introduction
PAC-Bayes and Mutual Information bounds

Generalization bounds and PAC-Bayes
Minimization of the PAC-Bayes boundA zoo of PAC-Bayes bounds

Prediction error measured through loss function ℓ :ℓ y , fθ (x) .
Risk :h 
iR(θ) := E(X ,Y )∼P ℓ Y , fθ (X ) .

where P is the probability distribution of pairs
object-label we want to learn to classify.
Objective :R ∗ = inf R(θ).
θ∈Θ

Data (X1 , Y1 ), . . . , (Xn , Yn ) i.i.d. from P. Empirical risk :n
1X Rn (θ) =ℓ Yi , fθ (Xi ) .
n i=1
Pierre Alquier, ESSEC Business School

PAC-Bayes

PAC-Bayes bounds : introduction
PAC-Bayes and Mutual Information bounds

Generalization bounds and PAC-Bayes
Minimization of the PAC-Bayes boundA zoo of PAC-Bayes bounds

Toy example :X uniform on [0, 1],
Y = |2X − 1| + ϵ.

Pierre Alquier, ESSEC Business School

PAC-Bayes

PAC-Bayes bounds : introduction
PAC-Bayes and Mutual Information bounds

Generalization bounds and PAC-Bayes
Minimization of the PAC-Bayes boundA zoo of PAC-Bayes bounds

Prediction by regular histogram with k-bins.
ℓ(y , fθ (x)) = (y − fθ (x))2 .
That is,θ1 if x ∈ [0, 1/k), θ2 if x ∈ [1/k, 2/k),fθ (x) =..
.
 θ if x ∈ [(k − 1)/k, 1].
kPierre Alquier, ESSEC Business School

PAC-Bayes

PAC-Bayes bounds : introduction
PAC-Bayes and Mutual Information bounds

Generalization bounds and PAC-Bayes
Minimization of the PAC-Bayes boundA zoo of PAC-Bayes bounds

Prediction by regular histogram with k-bins.
ℓ(y , fθ (x)) = (y − fθ (x))2 .

Pierre Alquier, ESSEC Business School

PAC-Bayes

PAC-Bayes bounds : introduction
PAC-Bayes and Mutual Information bounds

Generalization bounds and PAC-Bayes
Minimization of the PAC-Bayes boundA zoo of PAC-Bayes bounds

Prediction by regular histogram with k-bins.
ℓ(y , fθ (x)) = (y − fθ (x))2 .

Pierre Alquier, ESSEC Business School

PAC-Bayes

PAC-Bayes bounds : introduction
PAC-Bayes and Mutual Information bounds

Generalization bounds and PAC-Bayes
Minimization of the PAC-Bayes boundA zoo of PAC-Bayes bounds

Prediction by regular histogram with k-bins.
ℓ(y , fθ (x)) = (y − fθ (x))2 .

Pierre Alquier, ESSEC Business School

PAC-Bayes

PAC-Bayes bounds : introduction
PAC-Bayes and Mutual Information bounds

Pierre Alquier, ESSEC Business School

Generalization bounds and PAC-Bayes
Minimization of the PAC-Bayes boundA zoo of PAC-Bayes bounds

PAC-Bayes

PAC-Bayes bounds : introduction
PAC-Bayes and Mutual Information bounds

Generalization bounds and PAC-Bayes
Minimization of the PAC-Bayes boundA zoo of PAC-Bayes bounds

Law of large numbers : for a fixed θ,n
1X ℓ Yi , fθ (Xi ) −−−→ R(θ).
Rn (θ) =n→∞n i=1

But θ̂ = θ̂((X1 , Y1 ), . . . , (Xn , Yn )) = θ̂(S) learnt from data.
Can we quantify R(θ̂) − Rn (θ̂) when θ̂ is learnt ?
Various approaches :Vapnik-Chervonenkis theory,algorithmic stability,
information bounds : MDL, PAC-Bayes, etc.
Pierre Alquier, ESSEC Business School

PAC-Bayes

PAC-Bayes bounds : introduction
PAC-Bayes and Mutual Information bounds

Generalization bounds and PAC-Bayes
Minimization of the PAC-Bayes boundA zoo of PAC-Bayes bounds

Information we can get from these theories :1“generalization bound”
R(θ̂) ≤ Rn (θ̂) + data-dependent terms.
2“excess risk bound”
R(θ̂) ≤ R ∗ + rate of convergence.

Pierre Alquier, ESSEC Business School

PAC-Bayes

PAC-Bayes bounds : introduction
PAC-Bayes and Mutual Information bounds

Generalization bounds and PAC-Bayes
Minimization of the PAC-Bayes boundA zoo of PAC-Bayes bounds

Assumption for whole lecture
Unless specified otherwise, 0 ≤ ℓ ≤ 1 and data is i.i.d. from P.
Vapnik-Chervonenkis – classification (Y = {0, 1})
With probability at least 1 − δ on the data, for any θ̂ learnt
from the data,s
8d log 2en+ 8 log 4δdR(θ̂) ≤ Rn (θ̂) +nwhere d : the VC-dimension of the set of classifiers (fθ , θ ∈ Θ).

Pierre Alquier, ESSEC Business School

PAC-Bayes

PAC-Bayes bounds : introduction
PAC-Bayes and Mutual Information bounds

Generalization bounds and PAC-Bayes
Minimization of the PAC-Bayes boundA zoo of PAC-Bayes bounds

Statistical estimation / ERM etc.
data

estimator(X × Y)nΘSθ̂ = θ̂(S)Randomized estimators :(X × Y)nM(Θ)

Sρ̂ = ρ̂(S)Pierre Alquier, ESSEC Business School

PAC-Bayes

Θ
θ∼ρ̂

θ

PAC-Bayes bounds : introduction
PAC-Bayes and Mutual Information bounds

Generalization bounds and PAC-Bayes
Minimization of the PAC-Bayes boundA zoo of PAC-Bayes bounds

Randomized estimator inspired by Bayesian statistics, but
it is a more general notion.
For each new pair object-label (x, y ) ∼ P, we can draw a
predictor θ ∼ ρ̂. We incur a loss ℓ(y , fθ (x)).
If we repeat this for each new object to classify, ouraverage loss will converge toEθ∼ρ̂ E(x,y )∼P ℓ(y , fθ (x)) = Eθ∼ρ̂ [R(θ)].

Pierre Alquier, ESSEC Business School

PAC-Bayes

PAC-Bayes bounds : introduction
PAC-Bayes and Mutual Information bounds

Generalization bounds and PAC-Bayes
Minimization of the PAC-Bayes boundA zoo of PAC-Bayes bounds

McAllester’s PAC-Bayes boundFix a prior distribution π ∈ M(Θ). With probability at least
1 − δ on the data S, for any probability distribution ρ learnt
on the data,
v
 √ 
u
u KL(ρ∥π) + log 2 ntδEθ∼ρ [R(θ)] ≤ Eθ∼ρ [Rn (θ)] +.
2nKL(ρ∥π) = Küllback-Leibler divergence between ρ and πρ can be learnt on the data, so if we have a randomized
estimator ρ̂ in mind, we can apply the bound to ρ = ρ̂.
we will see later that the bound is helpful to define good
randomized estimators ρ̂.
Pierre Alquier, ESSEC Business School

PAC-Bayes

PAC-Bayes bounds : introduction
PAC-Bayes and Mutual Information bounds

Generalization bounds and PAC-Bayes
Minimization of the PAC-Bayes boundA zoo of PAC-Bayes bounds

KL(ρ∥π) = Küllback-Leibler divergence between ρ and π
discrete case :KL(ρ∥π) =Xρ(θ) log

θ∈Θ

ρ(θ)
π(θ)

and KL(ρ∥π) = ∞ if for some θ, π(θ) = 0 and ρ(θ) > 0.
general casedρKL(ρ∥π) = Eθ∼ρ log
(θ)
dπ
dρ
and KL(ρ∥π) = ∞ is ρ has no density dπ
w.r.t. π...

KL(ρ∥π) ≥ 0 and KL(ρ∥π) = 0 ⇔ ρ = π.
Pierre Alquier, ESSEC Business School

PAC-Bayes

PAC-Bayes bounds : introduction
PAC-Bayes and Mutual Information bounds

Generalization bounds and PAC-Bayes
Minimization of the PAC-Bayes boundA zoo of PAC-Bayes bounds

Intuition on KL :π uniform on A
π(θ) =

1A (θ)V(A)ρ uniform on B
ρ(θ) =dρ
not defined here.
dπ
B ⊈ A ⇒ KL(ρ∥π) = +∞.
Pierre Alquier, ESSEC Business School

PAC-Bayes

1B (θ)
V(B)PAC-Bayes bounds : introduction
PAC-Bayes and Mutual Information bounds

Generalization bounds and PAC-Bayes
Minimization of the PAC-Bayes boundA zoo of PAC-Bayes bounds

Intuition on KL :π uniform on A
π(θ) =

1A (θ)V(A)ρ uniform on B
ρ(θ) =

1B (θ)
V(B)dρ
V(A)1B (θ)
(θ) =
dπ
V(B)


dρ
V(A)
KL(ρ∥π) = Eθ∼ρ log(θ) = log
.
dπ
V(B)
B ⊆A⇒

Pierre Alquier, ESSEC Business School

PAC-Bayes

PAC-Bayes bounds : introduction
PAC-Bayes and Mutual Information bounds

Generalization bounds and PAC-Bayes
Minimization of the PAC-Bayes boundA zoo of PAC-Bayes bounds

Intuition on KL :Bd (x, r ) ball centered on x, with radius r in Rdd

V(Bd (x, r )) =rdπ 2
Γ( d2 + 1)

π uniform on A = Bd (0, C )ρ uniform on B = Bd (θ0 , ϵ)KL(ρ∥π) = log

Pierre Alquier, ESSEC Business SchoolV(A)C= d log .
V(B)ϵPAC-Bayes

Generalization bounds and PAC-Bayes
Minimization of the PAC-Bayes boundA zoo of PAC-Bayes bounds

PAC-Bayes bounds : introduction
PAC-Bayes and Mutual Information bounds

McAllester’s PAC-Bayes boundEθ∼ρ [R(θ)] ≤ Eθ∼ρ [Rn (θ)] +

v
 √ 
u
u KL(ρ∥π) + log 2 n
t
δ
2n

.

π uniform on Θ = Bd (0, C )ρ = ρ̂ uniform on Bd (θ̂, ϵ)Eθ∼ρ̂ [R(θ)] ≤ Eθ∼ρ̂ [Rn (θ)] +Pierre Alquier, ESSEC Business School

v
 √ 
u
u d log C + log 2 ntϵδ

PAC-Bayes

2n.

PAC-Bayes bounds : introduction
PAC-Bayes and Mutual Information bounds

Generalization bounds and PAC-Bayes
Minimization of the PAC-Bayes boundA zoo of PAC-Bayes bounds

Toy classification example :Xi ∈ [−1, 1],classifiers (fθ )θ∈[−1,1] given by
0 if x ≤ θfθ (x) =1 if x > θ.
Yi = fθ∗ (Xi ).

Pierre Alquier, ESSEC Business School

PAC-Bayes

PAC-Bayes bounds : introduction
PAC-Bayes and Mutual Information bounds

Generalization bounds and PAC-Bayes
Minimization of the PAC-Bayes boundA zoo of PAC-Bayes bounds

Vapnik-type bound :sR(θ̂) ≤

8 log (2en) + 8 lognPierre Alquier, ESSEC Business School

PAC-Bayes

4δPAC-Bayes bounds : introduction
PAC-Bayes and Mutual Information bounds

Generalization bounds and PAC-Bayes
Minimization of the PAC-Bayes boundA zoo of PAC-Bayes bounds

PAC-Bayes :π uniform on [−1, 1],ρ̂ uniform on [a, b].

Eθ∼ρ̂ [R(θ)] ≤

v
 √ 
u
u log 2 + log 2 ntb−aδPierre Alquier, ESSEC Business School

2n

PAC-Bayes.

PAC-Bayes bounds : introduction
PAC-Bayes and Mutual Information bounds

Pierre Alquier, ESSEC Business School

Generalization bounds and PAC-Bayes
Minimization of the PAC-Bayes boundA zoo of PAC-Bayes bounds

PAC-Bayes

PAC-Bayes bounds : introduction
PAC-Bayes and Mutual Information bounds

Generalization bounds and PAC-Bayes
Minimization of the PAC-Bayes boundA zoo of PAC-Bayes bounds

Vapnik-type bound :sR(θ̂) ≤

8 log (2en) + 8 lognPierre Alquier, ESSEC Business School

PAC-Bayes

4δPAC-Bayes bounds : introduction
PAC-Bayes and Mutual Information bounds

Generalization bounds and PAC-Bayes
Minimization of the PAC-Bayes boundA zoo of PAC-Bayes bounds

PAC-Bayes :π uniform on [−1, 1],ρ̂ uniform on [a, b].

Eθ∼ρ̂ [R(θ)] ≤

v
 √ 
u
u log 2 + log 2 ntb−aδPierre Alquier, ESSEC Business School

2n

PAC-Bayes.

PAC-Bayes bounds : introduction
PAC-Bayes and Mutual Information bounds

Pierre Alquier, ESSEC Business School

Generalization bounds and PAC-Bayes
Minimization of the PAC-Bayes boundA zoo of PAC-Bayes bounds

PAC-Bayes

PAC-Bayes bounds : introduction
PAC-Bayes and Mutual Information bounds

Pierre Alquier, ESSEC Business School

Generalization bounds and PAC-Bayes
Minimization of the PAC-Bayes boundA zoo of PAC-Bayes bounds

PAC-Bayes

PAC-Bayes bounds : introduction
PAC-Bayes and Mutual Information bounds

Generalization bounds and PAC-Bayes
Minimization of the PAC-Bayes boundA zoo of PAC-Bayes bounds

1

PAC-Bayes bounds : introduction
Generalization bounds and PAC-Bayes
Minimization of the PAC-Bayes boundA zoo of PAC-Bayes bounds

2

PAC-Bayes and Mutual Information bounds
Excess risk bounds
Fast rates
Mutual information bounds

Pierre Alquier, ESSEC Business School

PAC-Bayes

Generalization bounds and PAC-Bayes
Minimization of the PAC-Bayes boundA zoo of PAC-Bayes bounds

PAC-Bayes bounds : introduction
PAC-Bayes and Mutual Information bounds

McAllester’s PAC-Bayes boundFix prior π ∈ M(Θ). With proba. at least 1 − δ, ∀ρ ∈ M(Θ),
v
 √ 
u
u KL(ρ∥π) + log 2 ntδEθ∼ρ [R(θ)] ≤ Eθ∼ρ [Rn (θ)] +
.
2n
r

a
= inf
b λ>0

Eθ∼ρ [R(θ)] ≤ Eθ∼ρ [Rn (θ)]
(



a
λ
+
λ 4b

.

KL(ρ∥π) + log

+ inf

λ

λ>0

Pierre Alquier, ESSEC Business School

PAC-Bayes

 √ 
2 n
δ

)
λ
+
.
8n

PAC-Bayes bounds : introduction
PAC-Bayes and Mutual Information bounds

Generalization bounds and PAC-Bayes
Minimization of the PAC-Bayes boundA zoo of PAC-Bayes bounds∀λ > 0, Eθ∼ρ [R(θ)] ≤ Eθ∼ρ [Rn (θ)]
KL(ρ∥π) + log
+

 √ 
2 n
δ

λ

Definition - Gibbs posteriorπ̂λ (dθ) =exp(−λRn (θ))π(dθ).
Eϑ∼π [exp(−λRn (ϑ))]

TheoremKL(ρ∥π)π̂λ = arg min Eθ∼ρ [Rn (θ)] +λρ∈M(Θ)
Pierre Alquier, ESSEC Business School

PAC-Bayes


.

+

λ
.
8n

PAC-Bayes bounds : introduction
PAC-Bayes and Mutual Information bounds

Generalization bounds and PAC-Bayes
Minimization of the PAC-Bayes boundA zoo of PAC-Bayes bounds

Proof :
0 ≤ KL(ρ∥π̂λ )dρ= Eθ∼ρ log
(θ)
dπ̂λ


dπ̂λ
dρ
(θ) − log(θ)= Eθ∼ρ log
dπ
dπ


dρ
= Eθ∼ρ log(θ) + λRn (θ) + log Eϑ∼π [exp(−λRn (ϑ)]
dπ= KL(ρ∥π) + λEθ∼ρ [Rn (θ)] + log Eϑ∼π [exp(−λRn (ϑ)].

Pierre Alquier, ESSEC Business School

PAC-Bayes

PAC-Bayes bounds : introduction
PAC-Bayes and Mutual Information bounds

Generalization bounds and PAC-Bayes
Minimization of the PAC-Bayes boundA zoo of PAC-Bayes bounds

Consequence of the PAC-Bayes boundFix prior π ∈ M(Θ). With proba. at least 1 − δ, ∀λ > 0,Eθ∼π̂λ [R(θ)] ≤− log Eϑ∼π [exp(−λRn (ϑ))] + log
λ

 √ 
2 n
δ

+

in simple cases, we can sample from π̂λ by standard
Monte Carlo / MCMC techniques,
the minimization in λ can be tricky.

Pierre Alquier, ESSEC Business School

PAC-Bayes

λ.
8nPAC-Bayes bounds : introduction
PAC-Bayes and Mutual Information bounds

Generalization bounds and PAC-Bayes
Minimization of the PAC-Bayes boundA zoo of PAC-Bayes bounds

Approximate minimization of the PAC-Bayes bound.

Pierre Alquier, ESSEC Business School

PAC-Bayes

PAC-Bayes bounds : introduction
PAC-Bayes and Mutual Information bounds

Generalization bounds and PAC-Bayes
Minimization of the PAC-Bayes boundA zoo of PAC-Bayes bounds∀λ > 0, Eθ∼ρ [R(θ)] ≤ Eθ∼ρ [Rn (θ)]
KL(ρ∥π) + log
+

λ

 √ 
2 n
δ

+

λ
.
8n

Alternative approach : optimize ρ in a smaller set F ⊊ M(Θ).
Definition - variational approximation of Gibbs posterior
KL(ρ∥π)ρ̃λ = arg min Eθ∼ρ [Rn (θ)] +.
λρ∈FExample : ρ = N (µ, Σ), optimize (µ, Σ).

Pierre Alquier, ESSEC Business School

PAC-Bayes

PAC-Bayes bounds : introduction
PAC-Bayes and Mutual Information bounds

Generalization bounds and PAC-Bayes
Minimization of the PAC-Bayes boundA zoo of PAC-Bayes bounds

Example : Gaussian prior π, and we optimize a Gaussian
posterior ρ :π = N (µ0 , Σ0 ) and ρ = N (µ1 , Σ1 ) in Rd .

"1
KL(ρ∥π) =tr(Σ1 Σ0 −1 ) − d
2
#
detΣ
0
+ (µ1 − µ0 )T Σ0 −1 (µ1 − µ0 ) + log.
detΣ1

Pierre Alquier, ESSEC Business School

PAC-Bayes

PAC-Bayes bounds : introduction
PAC-Bayes and Mutual Information bounds

Generalization bounds and PAC-Bayes
Minimization of the PAC-Bayes boundA zoo of PAC-Bayes bounds

π = N (µ0 , Σ0 ) and ρ = N (µ1 , Σ1 ) in R.

"#(µ0 − µ1 )2Σ0
1 Σ1KL(ρ∥π) =
−1+
+ log
.
2 Σ0
Σ0
Σ1
Pierre Alquier, ESSEC Business School

PAC-Bayes

PAC-Bayes bounds : introduction
PAC-Bayes and Mutual Information bounds

Generalization bounds and PAC-Bayes
Minimization of the PAC-Bayes boundA zoo of PAC-Bayes bounds

If µ1 goes far away from µ0 to ∞,KL(ρ∥π) ∼(µ0 − µ1 )2
→ ∞.
2Σ0

Pierre Alquier, ESSEC Business School

PAC-Bayes

PAC-Bayes bounds : introduction
PAC-Bayes and Mutual Information bounds

If Σ1 → 0,KL(ρ∥π) ∼Pierre Alquier, ESSEC Business School

Generalization bounds and PAC-Bayes
Minimization of the PAC-Bayes boundA zoo of PAC-Bayes bounds

1
Σ0
log
→ ∞.
2
Σ1
PAC-Bayes

PAC-Bayes bounds : introduction
PAC-Bayes and Mutual Information bounds

Generalization bounds and PAC-Bayes
Minimization of the PAC-Bayes boundA zoo of PAC-Bayes bounds

With a sharp minimum, to keep
Eθ∼N (θ̂,Σ1 ) [Rn (θ)] ∼ Rn (θ̂),Σ1 should be small, and thus KL(ρ∥π) will be large.
Pierre Alquier, ESSEC Business School

PAC-Bayes

PAC-Bayes bounds : introduction
PAC-Bayes and Mutual Information bounds

Generalization bounds and PAC-Bayes
Minimization of the PAC-Bayes boundA zoo of PAC-Bayes bounds

With a flat minimum,
Eθ∼N (θ̂,Σ1 ) [Rn (θ)] ∼ Rn (θ̂)
for Σ1 “not so small”, thus KL(ρ∥π) does not have to be large.
Pierre Alquier, ESSEC Business School

PAC-Bayes

PAC-Bayes bounds : introduction
PAC-Bayes and Mutual Information bounds

Generalization bounds and PAC-Bayes
Minimization of the PAC-Bayes boundA zoo of PAC-Bayes boundsρ = ρµ1 ,Σ1 = N (µ1 , Σ1 ) = N (µ1 , UU T ).


KL(ρ∥π).
min Eθ∼N (µ1 ,UU T ) [Rn (θ)] +µ1 ,UλEθ∼N (µ1 ,UU T ) [Rn (θ)] = Eξ∼N (0,I ) [Rn (µ1 + Uξ)].
Stochastic Gradient Algorithm
Random initialization of µ1 and U, then iterate :sample ξ ∼ N (0, I ),updateµ1 ← µ1 − η ∂µ∂ 1 [Rn (µ1 + Uξ) + KL(ρµ1 ,Σ1 ∥π)]∂U ← U − η ∂U
[Rn (µ1 + Uξ) + KL(ρµ1 ,Σ1 ∥π)]
Pierre Alquier, ESSEC Business School

PAC-Bayes

PAC-Bayes bounds : introduction
PAC-Bayes and Mutual Information bounds

Generalization bounds and PAC-Bayes
Minimization of the PAC-Bayes boundA zoo of PAC-Bayes bounds

Application : generalization bounds for deep learning.

Pierre Alquier, ESSEC Business School

PAC-Bayes

PAC-Bayes bounds : introduction
PAC-Bayes and Mutual Information bounds

Generalization bounds and PAC-Bayes
Minimization of the PAC-Bayes boundA zoo of PAC-Bayes bounds

Train a neural network forclassification (0-1 loss).
Vapnik-type bound usuallylead to something larger
than 1, for example :R(θ̂) ≤ 35.4
As R(θ̂) = P(Y ̸= fθ̂ (X )),the bound brings no information (vacuous).

Pierre Alquier, ESSEC Business School

PAC-Bayes

PAC-Bayes bounds : introduction
PAC-Bayes and Mutual Information bounds

Pierre Alquier, ESSEC Business School

Generalization bounds and PAC-Bayes
Minimization of the PAC-Bayes boundA zoo of PAC-Bayes bounds

PAC-Bayes

PAC-Bayes bounds : introduction
PAC-Bayes and Mutual Information bounds

Generalization bounds and PAC-Bayes
Minimization of the PAC-Bayes boundA zoo of PAC-Bayes bounds

Combine many ideas to get tighter bounds :prior centered at the (random) initialization of SGD, θinit .
“multi-scale” prior :Xπ=p(σ)N (θinit , σ 2 I ).
σ∈Sreplace Rn (θ) by convex surrogate.
...

Pierre Alquier, ESSEC Business School

PAC-Bayes

PAC-Bayes bounds : introduction
PAC-Bayes and Mutual Information bounds

Generalization bounds and PAC-Bayes
Minimization of the PAC-Bayes boundA zoo of PAC-Bayes bounds

Results taken from :Dzuigaite, G. K. and Roy, D. M. (2017). Computing Nonvacuous Generalization Bounds for Deep
(Stochastic) Neural Networks with Many More Parameters than Training Data. UAI.

Pierre Alquier, ESSEC Business School

PAC-Bayes

PAC-Bayes bounds : introduction
PAC-Bayes and Mutual Information bounds

Generalization bounds and PAC-Bayes
Minimization of the PAC-Bayes boundA zoo of PAC-Bayes bounds

More recent results (among others !) :Pérez-Ortiz, M., Rivasplata, O., Shawe-Taylor, J. and Szepesvári, C. (2021). Tighter riskcertificates for neural networks. Journal of Machine Learning Research.
Clerico, E., Farghly, T., Deligiannidis, G., Guedj, B. and Doucet, A. (2022). Generalisation under
gradient descent via deterministic PAC-Bayes. ArXiv preprint arXiv :2209.02525.

Pierre Alquier, ESSEC Business School

PAC-Bayes

PAC-Bayes bounds : introduction
PAC-Bayes and Mutual Information bounds

Generalization bounds and PAC-Bayes
Minimization of the PAC-Bayes boundA zoo of PAC-Bayes bounds

1

PAC-Bayes bounds : introduction
Generalization bounds and PAC-Bayes
Minimization of the PAC-Bayes boundA zoo of PAC-Bayes bounds

2

PAC-Bayes and Mutual Information bounds
Excess risk bounds
Fast rates
Mutual information bounds

Pierre Alquier, ESSEC Business School

PAC-Bayes

PAC-Bayes bounds : introduction
PAC-Bayes and Mutual Information bounds

Generalization bounds and PAC-Bayes
Minimization of the PAC-Bayes boundA zoo of PAC-Bayes bounds

Seminalpaper,
that
contains the bound statedearlier today.
Since then, various bounds
published :tighter,with less assumptions(i.i.d, bounded loss),easier to optimize,...

Pierre Alquier, ESSEC Business School

PAC-Bayes

PAC-Bayes bounds : introduction
PAC-Bayes and Mutual Information bounds

Generalization bounds and PAC-Bayes
Minimization of the PAC-Bayes boundA zoo of PAC-Bayes bounds

Catoni’s PAC-Bayes bound, 2003
Fix λ > 0 and π. With proba. at least 1 − δ on S, for any ρ̂,KL(ρ̂∥π) + log 1δλEθ∼ρ̂ [R(θ)] ≤ Eθ∼ρ̂ [Rn (θ)] ++ .
λ8n“De-randomized” PAC-Bayes bound, 2003
Fix λ > 0, π and a randomized estimator ρ̂.
Sample θ̂ ∼ ρ̂(S).
With probability at least 1 − δ on (S, θ̂),dρ̂(θ̂) + log 1δ
log dπλR(θ̂) ≤ Rn (θ̂) +
+ .
λ
8n

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

Pierre Alquier, ESSEC Business School

PAC-Bayes

PAC-Bayes bounds : introduction
PAC-Bayes and Mutual Information bounds

Generalization bounds and PAC-Bayes
Minimization of the PAC-Bayes boundA zoo of PAC-Bayes bounds

Classical references :Connections with information theory
and MDL.
Pierre Alquier, ESSEC Business School

Very tight bounds, applications to
Support Vector Machines.

PAC-Bayes

PAC-Bayes bounds : introduction
PAC-Bayes and Mutual Information bounds

Generalization bounds and PAC-Bayes
Minimization of the PAC-Bayes boundA zoo of PAC-Bayes bounds

Seeger, M. (2002). PAC-Bayesian generalisation error bounds for Gaussian process classification.
Journal of Machine Learning Research.
Maurer, A. (2004). A note on the PAC-Bayesian theorem. Arxiv preprint arXiv :cs/0411099.
Tolstikhin, I. and Seldin, Y. (2013). PAC-Bayes-empirical-Bernstein inequality. NeurIPS.

Tolstikhin and Seldin’s PAC-Bayes bound, 2013
With proba. at least 1 − δ, for any ρ,Eθ∼ρ [R(θ)] ≤ Eθ∼ρ [Rn (θ)]
s+√

KL(ρ∥π) + log 2 δ n
2Eθ∼ρ [Rn (θ)]
n√

KL(ρ∥π) + log 2 δ n+2.
n
Pierre Alquier, ESSEC Business School

PAC-Bayes

PAC-Bayes bounds : introduction
PAC-Bayes and Mutual Information bounds

Generalization bounds and PAC-Bayes
Minimization of the PAC-Bayes boundA zoo of PAC-Bayes bounds

Consequence : if Eθ∼ρ [Rn (θ)] = 0,Eθ∼ρ [R(θ)] ≤ 
Eθ∼ρ
[Rn
(θ)]

s



2√n + logKL(ρ∥π)δ+ 2Eθ∼ρ[R
n (θ)]
n

√KL(ρ∥π) + log 2 δ n+2.
n

Pierre Alquier, ESSEC Business School

PAC-Bayes

PAC-Bayes bounds : introduction
PAC-Bayes and Mutual Information bounds

Generalization bounds and PAC-Bayes
Minimization of the PAC-Bayes boundA zoo of PAC-Bayes bounds

v
 √

u
2n
u log 2 + logtb−a 
δ
Eθ∼ρ [R(θ)] ≤ 
.
2n
 √ 
2
+ log 2 δ nlog b−aEθ∼ρ [R(θ)] ≤ 2.
nPierre Alquier, ESSEC Business School

PAC-Bayes

PAC-Bayes bounds : introduction
PAC-Bayes and Mutual Information bounds

Generalization bounds and PAC-Bayes
Minimization of the PAC-Bayes boundA zoo of PAC-Bayes bounds

Bound in expectation → bound on the weighted majority
vote :
Germain, P., Lacasse, A., Laviolette, F., Marchand, M. and Roy, J.-F. (2015). Risk bounds for the
majority vote : from a PAC-Bayesian analysis to a learning algorithm Journal of Machine Learning
Research.

Tight bound that allows to recover all the above, and more :Germain, P., Lacasse, A., Laviolette, F. and Marchand, M. (2009). PAC-Bayesian learning of
linear classifiers. ICML.

François Laviolette (1962-2021).

Pierre Alquier, ESSEC Business School

PAC-Bayes

PAC-Bayes bounds : introduction
PAC-Bayes and Mutual Information bounds

Generalization bounds and PAC-Bayes
Minimization of the PAC-Bayes boundA zoo of PAC-Bayes bounds

Tutorials :McAllester, D. (2013). A PAC-Bayesian tutorial with a dropout bound. ArXiv preprint
arXiv :1307.2118.
Van Erven, T. (2014). PAC-Bayes mini-tutorial : a continuous union bound. ArXiv preprint
arXiv :1405.1580.
Guedj, B. (2019). A primer on PAC-Bayesian learning. ArXiv preprint arXiv :1901.05353.

Pierre Alquier, ESSEC Business School

PAC-Bayes

PAC-Bayes bounds : introduction
PAC-Bayes and Mutual Information bounds

Excess risk bounds
Fast rates
Mutual information bounds

1

PAC-Bayes bounds : introduction
Generalization bounds and PAC-Bayes
Minimization of the PAC-Bayes boundA zoo of PAC-Bayes bounds

2

PAC-Bayes and Mutual Information bounds
Excess risk bounds
Fast rates
Mutual information bounds

Pierre Alquier, ESSEC Business School

PAC-Bayes

PAC-Bayes bounds : introduction
PAC-Bayes and Mutual Information bounds

Excess risk bounds
Fast rates
Mutual information bounds

Recap :
Data : S = ((X1 , Y1 ), . . h. , (Xn , Yn )). i
Risk : R(θ) := E(X ,Y )∼P ℓ Y , fθ (X ).

Oracle risk : R ∗ = inf θ∈Θ R(θ). Pn
1
Empirical risk : Rn (θ) = n i=1 ℓ Yi , fθ (Xi ) .
“Randomized estimators”
data

proba. distributionSρ̂ = ρ̂(S)parameterθ∼ρ̂θ

Today, we study “excess-risk bounds”, that is :Eθ∼ρ̂ [R(θ)] ≤ R ∗ + . . . (rate of convergence).
Pierre Alquier, ESSEC Business School

PAC-Bayes

PAC-Bayes bounds : introduction
PAC-Bayes and Mutual Information bounds

Excess risk bounds
Fast rates
Mutual information bounds

Catoni’s PAC-Bayes bound, 2003
Fix λ > 0 and π. With proba. at least 1 − δ on S, for any ρ̂,KL(ρ̂∥π) + log 1δλ+ .
Eθ∼ρ̂ [R(θ)] ≤ Eθ∼ρ̂ [Rn (θ)] +λ8n“De-randomized” PAC-Bayes bound, 2003
Fix λ > 0, π and a randomized estimator ρ̂.
Sample θ̂ ∼ ρ̂(S).
With probability at least 1 − δ on (S, θ̂),R(θ̂) ≤ Rn (θ̂) +dρ̂
log dπ(θ̂) + log 1δ
λ
+ .
λ
8n

Pierre Alquier, ESSEC Business School

PAC-Bayes

PAC-Bayes bounds : introduction
PAC-Bayes and Mutual Information bounds

Excess risk bounds
Fast rates
Mutual information bounds

Catoni’s PAC-Bayes bound in expectation, 2003
Fix λ > 0, π and a randomized estimator ρ̂.
#
"
h
i
λ
KL(ρ̂∥π).
ES Eθ∼ρ̂ [R(θ)] ≤ ES Eθ∼ρ̂ [Rn (θ)] ++λ8nCatoni, O. (2003). A PAC-Bayesian approach to adaptive classification. Preprint LPMA 840.
Zhang, T. (2006). Information-theoretic upper and lower bounds for statistical estimation IEEE
Transactions on Information Theory.

Note : sometimes refered to as “MAC-Bayes” for “MeanApproximately Correct”...

Pierre Alquier, ESSEC Business School

PAC-Bayes

PAC-Bayes bounds : introduction
PAC-Bayes and Mutual Information bounds

Excess risk bounds
Fast rates
Mutual information bounds

Reminder – Gibbs posterior
KL(ρ∥π)π̂λ = arg min Eθ∼ρ [Rn (θ)] +λρ∈M(Θ)π̂λ (dθ) =exp(−λRn (θ))π(dθ).
Eϑ∼π [exp(−λRn (ϑ)]

Consequence of PAC-Bayes bound in expectation :"#iKL(π̂λ ∥π)
λES Eθ∼π̂λ [R(θ)] ≤ ES Eθ∼π̂λ [Rn (θ)] +
+
λ
8n
"
#
KL(ρ∥π)λ= ES inf Eρ [Rn (θ)] +
+
ρ
λ
8n
"
#
KL(ρ∥π)λ≤ inf ES Eρ [Rn (θ)] +
+
.
ρ
λ
8n
h

Pierre Alquier, ESSEC Business School

PAC-Bayes

PAC-Bayes bounds : introduction
PAC-Bayes and Mutual Information bounds

Excess risk bounds
Fast rates
Mutual information bounds"#hiKL(ρ∥π)λ
ES Eθ∼π̂λ [R(θ)] ≤ inf ES Eρ [Rn (θ)] +
+
.
ρ
λ
8n
ES Eρ [Rn (θ)] = Eρ [ES Rn (θ)] (Fubini-Tonelli)= Eρ [R(θ)].

Catoni’s PAC-Bayes oracle bound, 2003
Fix λ > 0, π, and let π̂λ be the Gibbs posterior.
"#hiKL(ρ∥π)λ
ES Eθ∼π̂λ [R(θ)] ≤ inf Eθ∼ρ [R(θ)] ++.
ρ∈M(Θ)
λ8n
In this result, we use π̂λ as our randomized estimator.
But to explicit the right-hand side, we can substituteanything to ρ in the infimum...
Pierre Alquier, ESSEC Business School

PAC-Bayes

PAC-Bayes bounds : introduction
PAC-Bayes and Mutual Information bounds

Excess risk bounds
Fast rates
Mutual information bounds

Illustration :π uniform on Θ = Bd (0, C )ρ uniform on Bd (θ∗ , ϵ) whereR(θ∗ ) = R ∗ .
KL(ρ∥π) = d logC.
ϵAssume θ 7→ ℓ(y , fθ (x)) is L-Lipschitz around θ∗ , that is :|ℓ(y , fθ (x)) − ℓ(y , fθ∗ (x))| ≤ L∥θ − θ∗ ∥.
By taking expectations :R(θ) − R ∗ = R(θ) − R(θ∗ ) ≤ L∥θ − θ∗ ∥.
Thus Eθ∼ρ [R(θ)] ≤ R ∗ + Lϵ.
Pierre Alquier, ESSEC Business School

PAC-Bayes

PAC-Bayes bounds : introduction
PAC-Bayes and Mutual Information bounds

Excess risk bounds
Fast rates
Mutual information bounds

"
#
C
i
d
log
λ
ϵ
.
ES Eθ∼π̂λ [R(θ)] ≤ inf R ∗ + ϵ +
+
ϵ>0
λ
8n
h

The bound is exactly minimized for ϵ = d/λ :


h
i
Cλ
λ
d
∗
ES Eθ∼π̂λ [R(θ)] ≤ R +1 + log+ .
λd8n
In thispcase, we can calibrate the Gibbs posterior with
λ = n/d which leads to
!
r
i
d
n
ES Eθ∼π̂λ [R(θ)] ≤ R ∗ + O
log
.
n
d
h

Pierre Alquier, ESSEC Business School

PAC-Bayes

PAC-Bayes bounds : introduction
PAC-Bayes and Mutual Information bounds

Excess risk bounds
Fast rates
Mutual information bounds

Reminder : Catoni’s PAC-Bayes oracle boundhi
ES Eθ∼π̂λ [R(θ)] ≤"#KL(ρ∥π)λinf Eθ∼ρ [R(θ)] ++.
ρ∈M(Θ)
λ8nRecap on the previous example :π uniform on Bd (0, C ),
ρ uniform on Bd (θ∗ , ϵ),L-Lipschitz loss function.
⇒ Eθ∼ρ [R(θ)] ≤ R ∗ + Lϵ.
More generally, we can consider in the PAC-Bayes oracle
bound :
ρ = πδ := restriction of π to {θ : R(θ) ≤ R ∗ + δ}.
Pierre Alquier, ESSEC Business School

PAC-Bayes

PAC-Bayes bounds : introduction
PAC-Bayes and Mutual Information bounds

Excess risk bounds
Fast rates
Mutual information bounds

ρ = πδ := restriction of π to {θ : R(θ) ≤ R ∗ + δ}.

Pierre Alquier, ESSEC Business School

PAC-Bayes

PAC-Bayes bounds : introduction
PAC-Bayes and Mutual Information bounds

Excess risk bounds
Fast rates
Mutual information bounds"#iKL(πδ ∥π)λ
ES Eθ∼π̂λ [R(θ)] ≤ inf Eθ∼πδ [R(θ)] +
+
δ>0
λ
8n
#
"
1
log π{θ:R(θ)≤R
∗ +δ}
λ
+
.
≤ inf R ∗ + δ +
δ>0
λ
8n
h

In the previous example,
1
C≤ d log∗π{θ : R(θ) ≤ R + δ}δpand we obtained a bound in d/n log(n/d).
log

Definition : the prior mass condition is satisfied if there are
C , D > 0 such that, for any δ > 0 small enough,log

1C≤ D log .
∗π{θ : R(θ) ≤ R + δ}δ

Pierre Alquier, ESSEC Business School

PAC-Bayes

PAC-Bayes bounds : introduction
PAC-Bayes and Mutual Information bounds

Excess risk bounds
Fast rates
Mutual information bounds

Theorem - excess risk boundAssume the prior mass condition with C , D > 0.
p
Fix λ = n/D log(D/n), and let π̂λ be the Gibbs
posterior.
!
r
h
i
D
n
ES Eθ∼π̂λ [R(θ)] ≤ R ∗ + O
log
.
n
D

Pierre Alquier, ESSEC Business School

PAC-Bayes

PAC-Bayes bounds : introduction
PAC-Bayes and Mutual Information bounds

Excess risk bounds
Fast rates
Mutual information bounds

1

PAC-Bayes bounds : introduction
Generalization bounds and PAC-Bayes
Minimization of the PAC-Bayes boundA zoo of PAC-Bayes bounds

2

PAC-Bayes and Mutual Information bounds
Excess risk bounds
Fast rates
Mutual information bounds

Pierre Alquier, ESSEC Business School

PAC-Bayes

PAC-Bayes bounds : introduction
PAC-Bayes and Mutual Information bounds

Excess risk bounds
Fast rates
Mutual information bounds

Reminder – Tolstikhin and Seldin’s PAC-Bayes bound, 2013
With proba. at least 1 − δ, for any ρ,Eθ∼ρ [R(θ)] ≤ Eθ∼ρ [Rn (θ)]
s+√

KL(ρ∥π) + log 2 δ n
2Eθ∼ρ [Rn (θ)]
n√

KL(ρ∥π) + log 2 δ n+2.
n→ if there is a perfect predictor θ∗ , Rn (θ∗ ) = R(θ∗ ) = 0, thenusing the previous approach (prior mass condition) :


D
n
∗
Eθ∼ρ [R(θ)] ≤ |{z}
R +O
log
.
n
D
=0

This can happen beyond the case Rn (θ∗ ) = R(θ∗ ) = 0 !
Pierre Alquier, ESSEC Business School

PAC-Bayes

PAC-Bayes bounds : introduction
PAC-Bayes and Mutual Information bounds

Excess risk bounds
Fast rates
Mutual information bounds

Example 1 : classification, ℓ(y , fθ (x)) = 1y ̸=fθ (x) .
Recall :η(x) = P(Y = 1|X = x),
the “Bayes classifier” f ∗ (x) = 1η(x)≥1/2 .
Mammen and Tsybakov margin assumption :P(|η(X ) − 1/2| < τ ) = 0 for some small enough τ > 0.
there is θ∗ such that f ∗ = fθ∗ .
Mammen, E. and Tsybakov, A. B. (1999). Smooth discrimination analysis. The Annals of
Statistics.
Tsybakov, A. B. (2003). Optimal rates of aggregation. COLT.

Under the margin assumption, they prove fast rates in n1 forvarious predictors.
Pierre Alquier, ESSEC Business School

PAC-Bayes

PAC-Bayes bounds : introduction
PAC-Bayes and Mutual Information bounds

Excess risk bounds
Fast rates
Mutual information bounds

P(|η(X ) − 1/2| < τ ) = 0 for some small enough τ > 0.

Pierre Alquier, ESSEC Business School

PAC-Bayes

PAC-Bayes bounds : introduction
PAC-Bayes and Mutual Information bounds

Excess risk bounds
Fast rates
Mutual information bounds

Example 2 : “strongly convex, Lipschitz loss”.
For short, put g (θ) = gx,y (θ) = ℓ(y , fθ (x)).
Assume there are L, α > 0 such that, for any x, y , there is aδ(·, ·) = δx,y (·, ·) ≥ 0 withg (θ) + g (θ∗ )θ + θ∗1 2∀θ,≥−g
δ (θ, θ∗ ),222α
and g (θ) − g (θ∗ ) ≤ Lδ(θ, θ∗ ).
Bartlett, P. L., Jordan, M. I. and McAuliffe, J. D. (2003). Convexity, classification, and riskbounds. Journal of the American Statistical Association.

→ fast rates also in this case.
Pierre Alquier, ESSEC Business School

PAC-Bayes

PAC-Bayes bounds : introduction
PAC-Bayes and Mutual Information bounds

Excess risk bounds
Fast rates
Mutual information bounds

Definition – Bernstein condition
Bernstein condition is satisfied with constant K ifh
2 i
E ℓ(Y , fθ (X )) − ℓ(Y , fθ∗ (X ))hi≤ K E ℓ(Y , fθ (X )) − ℓ(Y , fθ∗ (X )) .
|{z}
=R(θ)−R ∗Mammen & Tsybakov margin assumption

Bernstein condition

Bartlett et al. convexity condition

Pierre Alquier, ESSEC Business School

PAC-Bayes

fast rates

PAC-Bayes bounds : introduction
PAC-Bayes and Mutual Information bounds

Excess risk bounds
Fast rates
Mutual information bounds

Intuition : for a fixed θ ∈ Θ we have

2 
= Var
E Rn (θ) − R(θ)!
n1Xℓ(Yi , fθ (Xi ))
n
i=1

=

n
1 X



Var
ℓ(Y
,
f
(X
))
.
i
i
θ
n2
{z
}
i=1 |
=:v (θ)By Jensen,h

E Rn (θ) − R(θ)

i

s 
r

2 
v (θ)
=
.
≤ E Rn (θ) − R(θ)
n

If θ and θ′ have the same empirical risk Rn (θ) = Rn (θ′ ), their risks√
might differ by 1/ n !
Pierre Alquier, ESSEC Business School

PAC-Bayes

PAC-Bayes bounds : introduction
PAC-Bayes and Mutual Information bounds

E

Excess risk bounds
Fast rates
Mutual information bounds

2 Rn (θ) − Rn (θ ) − (R(θ) − R )
∗

= Var

∗

n
i
1 Xh
ℓ(Yi , fθ (Xi )) − ℓ(Yi , fθ∗ (Xi ))
n

!

i=1

=

n
1 X

n2



Var ℓ(Yi , fθ (Xi )) − ℓ(Yi , fθ∗ (Xi ))

i=1

2
1 h
≤ E ℓ(Y , fθ (X )) − ℓ(Y , fθ∗ (X )) ]nK
≤ [R(θ) − R ∗ ] (using Bernstein condition).
n
If θ and θ∗ have the same empirical risk Rn (θ) = Rn (θ∗ ),
2 KKR(θ) − R ∗ ≤ [R(θ) − R ∗ ] ⇒ R(θ) − R ∗ ≤ .
nnPierre Alquier, ESSEC Business School

PAC-Bayes

PAC-Bayes bounds : introduction
PAC-Bayes and Mutual Information bounds

Excess risk bounds
Fast rates
Mutual information bounds

PAC-Bayes oracle inequality under Bernstein condition
Assume Bernstein condition is satisfied with constant K .
Put λ = n/ max(2K , 1),hES Eθ∼π̂λ [R(θ)] − R
"

∗

i

#
max(2K,
1)KL(ρ∥π).
≤ 2 inf Eθ∼ρ [R(θ)] − R ∗ +ρ∈M(Θ)nAssume moreover the prior mass condition with C , D > 0.
hi 2 max(2K , 1)DeCn∗
ES Eθ∼π̂λ [R(θ)] − R ≤
log
.
n
D
Pierre Alquier, ESSEC Business School

PAC-Bayes

PAC-Bayes bounds : introduction
PAC-Bayes and Mutual Information bounds

Excess risk bounds
Fast rates
Mutual information bounds

Reminder – Bernstein conditionh2 i
E ℓ(Y , fθ (X )) − ℓ(Y , fθ∗ (X ))hi≤ K E ℓ(Y , fθ (X )) − ℓ(Y , fθ∗ (X )) .
|{z}
=R(θ)−R ∗Mammen & Tsybakov margin assumption

Bernstein condition

Bartlett et al. convexity condition

Pierre Alquier, ESSEC Business School

PAC-Bayes

fast rates

PAC-Bayes bounds : introduction
PAC-Bayes and Mutual Information bounds

Excess risk bounds
Fast rates
Mutual information boundsh2 i
E ℓ(Y , fθ (X )) − ℓ(Y , fθ∗ (X ))hi= E ℓ(Y , fθ (X )) − ℓ(Y , fθ∗ (X )) ℓ(Y , fθ (X )) − ℓ(Y , fθ∗ (X ))
|
{z
}
≤1

i
i h
h
≤ E ℓ(Y , fθ (X )) − ℓ(Y , fθ∗ (X )) ≮E ℓ(Y , fθ (X )) − ℓ(Y , fθ∗ (X )) .

If we assume that there is a “uniformly best” θ∗ , that is, withprobability 1 on (X , Y ),ℓ(Y , fθ∗ (X )) ≤ ℓ(Y , fθ (X ))thenh we obtain
2 i
E ℓ(Y , fθ (X )) − ℓ(Y , fθ∗ (X ))hi≤ E ℓ(Y , fθ (X )) − ℓ(Y , fθ∗ (X )) = R(θ) − R ∗ .
This is the case if R ∗ = 0 ⇒ ℓ(Y , fθ∗ (X )) = 0 with proba. 1.
Pierre Alquier, ESSEC Business School

PAC-Bayes

PAC-Bayes bounds : introduction
PAC-Bayes and Mutual Information bounds

Excess risk bounds
Fast rates
Mutual information bounds

Reminder – Bernstein conditionh2 i≤ K [R(θ) − R ∗ ].
E ℓ(Y , fθ (X )) − ℓ(Y , fθ∗ (X ))Mammen & Tsybakov margin assumptionR∗ = 0

uniformly best θ ∗Bernstein condition

Bartlett et al. convexity condition

Pierre Alquier, ESSEC Business School

PAC-Bayes

fast rates

PAC-Bayes bounds : introduction
PAC-Bayes and Mutual Information bounds

Excess risk bounds
Fast rates
Mutual information bounds

Van Erven, T., Grünwald, P.,
Mehta, N., Reid, M. andWilliamson, R. (2015). Fast
Rates in Statistical andOnline Learning. JMLR.

Pierre Alquier, ESSEC Business School

PAC-Bayes

PAC-Bayes bounds : introduction
PAC-Bayes and Mutual Information bounds

Excess risk bounds
Fast rates
Mutual information bounds

Example : linear regression with quadratic loss,fθ (x) = ⟨θ, x⟩ℓ(y , fθ (x)) = (y − ⟨θ, x⟩)2 .
We have to impose boundedness conditions on Y ⊂ R and X , Θ ⊂ Rd to get
0 ≤ ℓ ≤ 1.
We can check Bartlett et al condition with δ(θ, θ∗ ) = | ⟨x, θ − θ∗ ⟩ |.



h
i
n
d
∗
ES Eθ∼π̂λ [R(θ)] ≤ R + O
log
.
n
d
Note that it is actually possible to get rid of some boundedness conditions, aswell as to get rid of the log terms.

Catoni, O. (2004). Statistical learning theory and Stochastic optimization. Saint-Flour summer
school on Probability Theory, Springer Lecture Notes in Mathematics.
Pierre Alquier, ESSEC Business School

PAC-Bayes

PAC-Bayes bounds : introduction
PAC-Bayes and Mutual Information bounds

Excess risk bounds
Fast rates
Mutual information bounds

Example : high-dimensional sparse linear regression withquadratic loss. That is, d > n but θ∗ has d0 ≪ d non-zerocomponents.
Sparsity inducing prior : under π,= 0 with probability p,θj∼ U[a, b] with probability 1 − p.


h
i
d0
∗
ES Eθ∼π̂λ [R(θ)] ≤ R + O
log(d) .
n
Dalalyan, A. and Tsybakov, A. B. (2008). Aggregation by exponential weighting, sharp
PAC-Bayesian bounds and sparsity. Machine Learning.
Alquier, P. and Lounici, K. (2011). PAC-Bayesian bounds for sparse regression estimation withexponential weights. Electronic Journal of Statistics.
Pierre Alquier, ESSEC Business School

PAC-Bayes

PAC-Bayes bounds : introduction
PAC-Bayes and Mutual Information bounds

Excess risk bounds
Fast rates
Mutual information bounds

More examples :low-rank tensor estimation :Suzuki, T. (2015). Convergence rate of Bayesian tensor estimator and its minimax optimality.
ICML.

deep learning :Chérief-Abdellatif, B.-E. (2020). Convergence Rates of Variational Inference in Sparse Deep
Learning. ICML.
Steffen, M. F. and Trabs, M. (2022). PAC-Bayes training for neural networks : sparsity anduncertainty quantification. ArXiv preprint arXiv :2204.12392.

quantum tomography (reconstructing the quantum stateof a system from measurements) :Mai, T. T. and Alquier, P. (2017). Pseudo-Bayesian quantum tomography with rank-adaptation.
Journal of Statistical Planning and Inference.

...
Pierre Alquier, ESSEC Business School

PAC-Bayes

PAC-Bayes bounds : introduction
PAC-Bayes and Mutual Information bounds

Excess risk bounds
Fast rates
Mutual information bounds(General) Bernstein condition
For K > 0 and γ ∈ [0, 1],h2 i∗≤ K [R(θ) − R ∗ ]γ .
E ℓ(Y , fθ (X )) − ℓ(Y , fθ (X ))So far, we studied γ = 1.
Always satisfied for γ = 0 (bounded loss).
In the general case,!
1  2−γihDNES Eθ∼π̂λ [R(θ)] − R ∗ ≤ O
log
.
N
D
Mammen and Tsybakov proved a sufficient margin
condition for 0 < γ < 1 : 1 
P(|η(X ) − 1/2| < τ ) = O τ 1−γ for τ → 0.
Pierre Alquier, ESSEC Business School

PAC-Bayes

PAC-Bayes bounds : introduction
PAC-Bayes and Mutual Information bounds

Excess risk bounds
Fast rates
Mutual information bounds

1

PAC-Bayes bounds : introduction
Generalization bounds and PAC-Bayes
Minimization of the PAC-Bayes boundA zoo of PAC-Bayes bounds

2

PAC-Bayes and Mutual Information bounds
Excess risk bounds
Fast rates
Mutual information bounds

Pierre Alquier, ESSEC Business School

PAC-Bayes

PAC-Bayes bounds : introduction
PAC-Bayes and Mutual Information bounds

Excess risk bounds
Fast rates
Mutual information bounds

Reminder – Catoni’s PAC-Bayes bound, 2003
Fix λ > 0 and π. With proba. at least 1 − δ on S, for any
randomized estimator ρ̂,KL(ρ̂∥π) + log 1δλEθ∼ρ̂ [R(θ)] ≤ Eθ∼ρ̂ [Rn (θ)] ++ .
λ8nFor λ and π are fixed, this motivated the introduction of the
Gibbs posterior ρ̂ = π̂λ , that minimizes the r.h.s. Then, weapplied the bound in expectation to derive rates of
convergence :"#hiKL(π̂λ ∥π)
λES Eθ∼π̂λ [R(θ)] ≤ ES Eθ∼π̂λ [Rn (θ)] ++.
λ8nBut... why did we keep the same λ and π ?
Pierre Alquier, ESSEC Business School

PAC-Bayes

PAC-Bayes bounds : introduction
PAC-Bayes and Mutual Information bounds

Excess risk bounds
Fast rates
Mutual information bounds

PAC-Bayes bound in expectation – v2.0
Fix Λ > 0, Π and the randomized estimator ρ̂ (forexample ρ̂ = π̂λ ).
#
"
h
i
Λ
KL(ρ̂∥Π)ES Eθ∼ρ̂ [R(θ)] ≤ ES Eθ∼ρ̂ [Rn (θ)] +
+
.
Λ
8n
Thus,
h

ES Eθ∼ρ̂ [R(θ)]

i"#
KL(ρ̂∥Π)Λ≤ inf inf ES Eθ∼ρ̂ [Rn (θ)] ++Λ>0 Π∈M(Θ)
Λ
8n
"
#
h
i
KL(ρ̂∥Π)Λ+.
= ES Eθ∼ρ̂ [Rn (θ)] + inf inf ES
Λ>0 Π∈M(Θ)Λ
8nPierre Alquier, ESSEC Business School

PAC-Bayes

PAC-Bayes bounds : introduction
PAC-Bayes and Mutual Information boundshExcess risk bounds
Fast rates
Mutual information bounds"i

ES Eθ∼ρ̂ [Rn (θ)] + inf

inf ES

Λ>0 Π∈M(Θ)#
KL(ρ̂∥Π)
Λ
,
+
Λ
8n

the infimum is reached, as shown by :Catoni, O. (2007). PAC-Bayesian supervised learning : the thermodynamics of statistical learning.
IMS lecture notes – monograph series.

ES KL(ρ̂∥Π) = ES KL(ρ̂∥ES ρ̂) + KL(ES ρ̂∥Π) .
|{z}=0 if Π=ES ρ̂

ES ρ̂ ∈ M(Θ) defined by [ES ρ̂](E ) = ES [ρ̂(E )].
the first term in the r.h.s. has a nice interpretation...

Pierre Alquier, ESSEC Business School

PAC-Bayes

PAC-Bayes bounds : introduction
PAC-Bayes and Mutual Information bounds

Excess risk bounds
Fast rates
Mutual information bounds

Let (U, V ) ∼ P. Let PU and PV denote their marginals. If U
and V were independent, P = PU ⊗ PV .
Mutual information between two random variables
I(U, V ) := KL(P∥PU ⊗ PV ).
Note : I(U, V ) depends on the distribution P of (U, V ), not on (U, V ). This isconfusing... remember that E(U) is not a function of U !

Propositionhi
I(U, V ) = EU KL(PV |U ∥PV ) .
Thus,
ES KL(ρ̂∥Π) = ES KL(ρ̂∥ES ρ̂) + KL(ES ρ̂∥Π) .
|
{z
} |
{z
}
=:I(θ,S)

Pierre Alquier, ESSEC Business School

PAC-Bayes=0 if Π=ES ρ̂PAC-Bayes bounds : introduction
PAC-Bayes and Mutual Information bounds

Excess risk bounds
Fast rates
Mutual information boundshi
ES Eθ∼ρ̂ [R(θ)]"Λ
KL(ρ̂∥Π)+≤ ES Eθ∼ρ̂ [Rn (θ)] + inf inf ES
Λ>0 Π∈M(Θ)
Λ
8n
#
"
h
i
Λ
I(θ, S).
= ES Eθ∼ρ̂ [Rn (θ)] + inf
+
Λ>0
Λ
8n
h

i

#

Mutual information bound
r
h
i
h
i
I(θ, S)
ES Eθ∼ρ̂ [R(θ)] ≤ ES Eθ∼ρ̂ [Rn (θ)] +.
2nRusso, D. and Zou, J. (2019). How much does your data exploration overfit ? controlling bias via
information usage. IEEE Transactions on Information Theory.
Pierre Alquier, ESSEC Business School

PAC-Bayes

PAC-Bayes bounds : introduction
PAC-Bayes and Mutual Information bounds

Excess risk bounds
Fast rates
Mutual information bounds

Mutual information bound
r
h
i
h
i
I(θ, S)
ES Eθ∼ρ̂ [R(θ)] ≤ ES Eθ∼ρ̂ [Rn (θ)] +.
2nI(θ, S) = ES KL(ρ̂∥ES ρ̂) ≤ ES KL(ρ̂∥π)

.

qMI :

PAC-Bayes:q

I(θ,S)..
2n

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

Pierre Alquier, ESSEC Business School

PAC-Bayes

PAC-Bayes bounds : introduction
PAC-Bayes and Mutual Information bounds

Excess risk bounds
Fast rates
Mutual information bounds

Let us illustrate the improvements of MI over PAC-Bayes on asimple example :finite parameter set Θ = {θ1 , . . . , θM }.
ρ̂ = δθ̂ the point mass on the ERM θ̂.
sI(θ̂, S)
ES [R(θ̂)] ≤ ES [Rn (θ̂)] +.
2nES [Rn (θ̂)] = ES [ inf Rn (θ)] ≤ inf ES [Rn (θ)] = inf R(θ) = R ∗ .
θ∈Θ

θ∈Θ

θ∈Θ

MI bound for the ERMs
ES [R(θ̂)] ≤ R ∗ +Pierre Alquier, ESSEC Business SchoolI(θ̂, S).
2n

PAC-Bayes

PAC-Bayes bounds : introduction
PAC-Bayes and Mutual Information bounds

Excess risk bounds
Fast rates
Mutual information bounds

Reminder – MI bound for the ERMs
ES [R(θ̂)] ≤ R ∗ +I(θ̂, S).
2n

PAC-Bayes : let π be uniform on Θ,I(θ̂, S) ≤ ES KL(δθ̂ ∥π)= log(M).
r
ES [R(θ̂)] ≤ R ∗ +Pierre Alquier, ESSEC Business Schoollog(M).
2n

PAC-Bayes

Excess risk bounds
Fast rates
Mutual information bounds

PAC-Bayes bounds : introduction
PAC-Bayes and Mutual Information bounds

Reminder – MI bound for the ERMs
ES [R(θ̂)] ≤ R ∗ +I(θ̂, S).
2nwhere ∆(θ) = R(θ) − R ∗ ,Catoni : π(θ) = P exp(−α∆(θ))
exp(−α∆(θ))
θ∈Θ

"

#

I(θ̂, S) ≤ ES KL(δθ̂ ∥π) = ES α∆(θ̂) + log

X

exp(−α∆(θ))θ∈Θ

Put ζ = logPθ∈Θ exp(−α∆(θ)), we obtain the inequation :s
ES [∆(θ̂)] ≤Pierre Alquier, ESSEC Business School

αES [∆(θ̂)] + ζ.
2nPAC-Bayes

PAC-Bayes bounds : introduction
PAC-Bayes and Mutual Information bounds

Excess risk bounds
Fast rates
Mutual information boundssES [∆(θ̂)] ≤αES [∆(θ̂)] + ζ
.
2n

s 

α
1 1 α2
ES [∆(θ̂)] ≤++ 2ζ .
4n 2 n 4n
ζ = logXexp(−α∆(θ)) ≤ log(M)θ∈Θ"ζ = log 1 +#Xexp(−α∆(θ)) ≤ M exp −α min∗ ∆(θ) .
θ̸=θ

θ̸=θ∗

√
Take α = 2 n.
Pierre Alquier, ESSEC Business School

PAC-Bayes

PAC-Bayes bounds : introduction
PAC-Bayes and Mutual Information bounds

Excess risk bounds
Fast rates
Mutual information bounds

Recap : MI bound for the ERM on a finite Θ
Assume Θ = {θ1 , . . . , θM } and put ∆ = minθ̸=θ∗ [R(θ) − R ∗ ].
Then
v
h
i
u
u 1 + min M exp(−∆√2n), log(M)t2
1ES [R(θ̂)] ≤ R ∗ +
+ .
2n
2n

Pierre Alquier, ESSEC Business School

PAC-Bayes

PAC-Bayes bounds : introduction
PAC-Bayes and Mutual Information bounds

Excess risk bounds
Fast rates
Mutual information bounds

Starting from the PAC-Bayes bound in expectation, we can
combine the improvements due to Bernstein assumption to the
optimization with respect to the prior.
MI bound with Bernstein condition
Assume Bernstein condition is satisfied with constant K .
Fix λ = n/ max(2K , 1), and ρ̂, then
ES Eθ∼ρ̂ [R(θ) − R ∗ ]≤ 2ES Eθ∼ρ̂ [Rn (θ) − R ∗ ] +Pierre Alquier, ESSEC Business School

PAC-Bayesmax(2K , 1)I(θ, S).
n

PAC-Bayes bounds : introduction
PAC-Bayes and Mutual Information bounds

Excess risk bounds
Fast rates
Mutual information bounds

A recent survey/tutorials that covers MI bounds in depth, andtheir relation to PAC-Bayes bounds :Hellström, F., Durisi, G., Guedj, B. and Raginsky, M. (2023). Generalization bounds :Perspectives from information theory and PAC-Bayes. Arxiv preprint arXiv :2309.04381.

Pierre Alquier, ESSEC Business School

PAC-Bayes

PAC-Bayes bounds : introduction
PAC-Bayes and Mutual Information bounds

Excess risk bounds
Fast rates
Mutual information bounds

Review of topics not covered in these slides.
Unbounded losses :Haddouche, M. and Guedj, B. (2023). PAC-Bayes Generalisation Bounds for Heavy-Tailed Losses
through Supermartingales. Transactions on Machine Learning Research.
Rodríguez-Gálvez, B., Thobaben, R. and Skoglund, M. (2023). More PAC-Bayes bounds : Frombounded losses, to losses with general tail behaviors, to anytime-validity. ArXiv preprint
arXiv :2306.12214

Non i.i.d., time series...
Alquier, P. and Wintenberger, O. (2012). Model selection for weakly dependent time series
forecasting. Bernoulli.
Alquier, P., Li. X. and Wintenberger, O. (2013). Prediction of time series by statistical learning :general losses and fast rates. Dependence Modeling.
Banerjee, I., Rao, V. A. and Honnappa, H. (2021). PAC-Bayes bounds on variational tempered
posteriors for Markov models. Entropy.

Pierre Alquier, ESSEC Business School

PAC-Bayes

PAC-Bayes bounds : introduction
PAC-Bayes and Mutual Information bounds

Excess risk bounds
Fast rates
Mutual information bounds

Robust estimator (not Bayesian) studied by adding a random
perturbation, and then using PAC-Bayes bounds.
Catoni, O. (2012). Challenging the empirical mean and empirical variance : a deviation study.
Annales de l’IHP.
Catoni, O. and Giulini, I. (2017). Dimension free PAC-Bayesian bounds for the estimation of themean of a random vector. NeurIPS 2017 Workshop : (Almost) 50 Shades of Bayesian Learning :PAC-Bayesian trends and insights.
Zhivotovskiy, N. (2024). Dimension-free bounds for sums of independent matrices and simple
tensors via the variational principle. Electronic Journal of Probability.

Meta-learning.
Rothfuss, J., Fortuin, V., Josifoski, M. and Krause, A. (2021). PACOH : Bayes-optimal
meta-learning with PAC-guarantees. ICML.
Riou, C., Alquier, P. and Chérief-Abdellatif, B.-E. (2023). Bayes meets Bernstein at the Meta
Level : an Analysis of Fast Rates in Meta-Learning with PAC-Bayes. Arxiv preprint
arXiv :2302.11709.

Pierre Alquier, ESSEC Business School

PAC-Bayes

PAC-Bayes bounds : introduction
PAC-Bayes and Mutual Information bounds

Excess risk bounds
Fast rates
Mutual information bounds

PAC-Bayes or MI bounds where KL(ρ∥π) is replaced byanother D(ρ, π).
Alquier, P. and Guedj, B. (2018). Simpler PAC-Bayesian bounds for hostile data. Machine
Learning.
Neu, G. and Lugosi, G. (2022). Generalization Bounds via Convex Analysis. ICML.

In particular, Wasserstein distance studied in :Rodríguez-Gálvez, B., Bassi, G., Thobaben, R. and Skoglund, M. (2021). Tighter expected
generalization error bounds via Wasserstein distance NeurIPS.
Clerico, E., Shidani, A., Deligiannidis, G. and Doucet, A. (2022). Chained Generalisation Bounds.
COLT.
Viallard, P., Haddouche, M., Simsekli, U. and Guedj, B. (2023). Learning via Wasserstein-based
high probability generalisation bounds. NeurIPS.
Neu, G. and Lugosi, G. (2023). Online-to-PAC Conversions : Generalization Bounds via Regret
Analysis. Arxiv preprint arXiv :2305.19674.

Pierre Alquier, ESSEC Business School

PAC-Bayes

PAC-Bayes bounds : introduction
PAC-Bayes and Mutual Information bounds

Excess risk bounds
Fast rates
Mutual information bounds

終わりC’est la fin.
The end.
t = +∞.

Thank you !
ありがとう ございました。

Pierre Alquier, ESSEC Business School

PAC-Bayes