Introduction : Learning with PAC-Bayes Bounds
Three Types of PAC-Bayesian Bounds
Computational Issues

PAC-Bayesian Bounds and Aggregation:
Introduction, and Algorithmic Issues
Pierre Alquier

AgroParisTech - 04/01/2016
Pierre Alquier

PAC-Bayesian Bounds and Aggregation

Introduction : Learning with PAC-Bayes Bounds
Three Types of PAC-Bayesian Bounds
Computational Issues

Learning vs. estimation
In many applications one would like to learn from a sample
without being able to write the likelihood.

Pierre Alquier

PAC-Bayesian Bounds and Aggregation

Introduction : Learning with PAC-Bayes Bounds
Three Types of PAC-Bayesian Bounds
Computational Issues

Learning vs. estimation
In many applications one would like to learn from a sample
without being able to write the likelihood.

Pierre Alquier

PAC-Bayesian Bounds and Aggregation

Introduction : Learning with PAC-Bayes Bounds
Three Types of PAC-Bayesian Bounds
Computational Issues

Typical machine learning problem
Main ingredients :Pierre Alquier

PAC-Bayesian Bounds and Aggregation

Introduction : Learning with PAC-Bayes Bounds
Three Types of PAC-Bayesian Bounds
Computational Issues

Typical machine learning problem
Main ingredients :observations object-label : (X1 , Y1 ), (X2 , Y2 ), ...

Pierre Alquier

PAC-Bayesian Bounds and Aggregation

Introduction : Learning with PAC-Bayes Bounds
Three Types of PAC-Bayesian Bounds
Computational Issues

Typical machine learning problem
Main ingredients :observations object-label : (X1 , Y1 ), (X2 , Y2 ), ...
→ either given once and for all (batch learning), once ata time (online learning), upon request...

Pierre Alquier

PAC-Bayesian Bounds and Aggregation

Introduction : Learning with PAC-Bayes Bounds
Three Types of PAC-Bayesian Bounds
Computational Issues

Typical machine learning problem
Main ingredients :observations object-label : (X1 , Y1 ), (X2 , Y2 ), ...
→ either given once and for all (batch learning), once ata time (online learning), upon request...
a restricted set of predictors (fθ , θ ∈ Θ).

Pierre Alquier

PAC-Bayesian Bounds and Aggregation

Introduction : Learning with PAC-Bayes Bounds
Three Types of PAC-Bayesian Bounds
Computational Issues

Typical machine learning problem
Main ingredients :observations object-label : (X1 , Y1 ), (X2 , Y2 ), ...
→ either given once and for all (batch learning), once ata time (online learning), upon request...
a restricted set of predictors (fθ , θ ∈ Θ).
→ fθ (X ) meant to predict Y .

Pierre Alquier

PAC-Bayesian Bounds and Aggregation

Introduction : Learning with PAC-Bayes Bounds
Three Types of PAC-Bayesian Bounds
Computational Issues

Typical machine learning problem
Main ingredients :observations object-label : (X1 , Y1 ), (X2 , Y2 ), ...
→ either given once and for all (batch learning), once ata time (online learning), upon request...
a restricted set of predictors (fθ , θ ∈ Θ).
→ fθ (X ) meant to predict Y .
a criterion of success, R(θ) :Pierre Alquier

PAC-Bayesian Bounds and Aggregation

Introduction : Learning with PAC-Bayes Bounds
Three Types of PAC-Bayesian Bounds
Computational Issues

Typical machine learning problem
Main ingredients :observations object-label : (X1 , Y1 ), (X2 , Y2 ), ...
→ either given once and for all (batch learning), once ata time (online learning), upon request...
a restricted set of predictors (fθ , θ ∈ Θ).
→ fθ (X ) meant to predict Y .
a criterion of success, R(θ) :→ for example R(θ) = P(fθ (X ) 6= Y ), R(θ) = kθ − θ0 k
where θ0 is a target parameter, ... we want R(θ) to besmall. But note that it is unknown.

Pierre Alquier

PAC-Bayesian Bounds and Aggregation

Introduction : Learning with PAC-Bayes Bounds
Three Types of PAC-Bayesian Bounds
Computational Issues

Typical machine learning problem
Main ingredients :observations object-label : (X1 , Y1 ), (X2 , Y2 ), ...
→ either given once and for all (batch learning), once ata time (online learning), upon request...
a restricted set of predictors (fθ , θ ∈ Θ).
→ fθ (X ) meant to predict Y .
a criterion of success, R(θ) :→ for example R(θ) = P(fθ (X ) 6= Y ), R(θ) = kθ − θ0 k
where θ0 is a target parameter, ... we want R(θ) to besmall. But note that it is unknown.
an empirical proxy r (θ) for this criterion of success :Pierre Alquier

PAC-Bayesian Bounds and Aggregation

Introduction : Learning with PAC-Bayes Bounds
Three Types of PAC-Bayesian Bounds
Computational Issues

Typical machine learning problem
Main ingredients :observations object-label : (X1 , Y1 ), (X2 , Y2 ), ...
→ either given once and for all (batch learning), once ata time (online learning), upon request...
a restricted set of predictors (fθ , θ ∈ Θ).
→ fθ (X ) meant to predict Y .
a criterion of success, R(θ) :→ for example R(θ) = P(fθ (X ) 6= Y ), R(θ) = kθ − θ0 k
where θ0 is a target parameter, ... we want R(θ) to besmall. But note that it is unknown.
an empirical proxy r (θ) for
Pnthis criterion of success :1→ for example r (θ) = n i=1 1(fθ (Xi ) 6= Yi ).
Pierre Alquier

PAC-Bayesian Bounds and Aggregation

Introduction : Learning with PAC-Bayes Bounds
Three Types of PAC-Bayesian Bounds
Computational Issues

PAC-Bayesian bounds
One more ingredient :Pierre Alquier

PAC-Bayesian Bounds and Aggregation

Introduction : Learning with PAC-Bayes Bounds
Three Types of PAC-Bayesian Bounds
Computational Issues

PAC-Bayesian bounds
One more ingredient :a prior π(dθ) on the parameter space.

Pierre Alquier

PAC-Bayesian Bounds and Aggregation

Introduction : Learning with PAC-Bayes Bounds
Three Types of PAC-Bayesian Bounds
Computational Issues

PAC-Bayesian bounds
One more ingredient :a prior π(dθ) on the parameter space.
The PAC-Bayesian approach usually provides a “posterior
distribution” ρ̂λ and a theoretical guarantee :ZZ
1R(θ)ρ̂λ (dθ) ≤ inf
R(θ)ρ(dθ) + K(ρ, π) + o(1).
ρλPierre Alquier

PAC-Bayesian Bounds and Aggregation

Introduction : Learning with PAC-Bayes Bounds
Three Types of PAC-Bayesian Bounds
Computational Issues

PAC-Bayesian bounds
One more ingredient :a prior π(dθ) on the parameter space.
The PAC-Bayesian approach usually provides a “posterior
distribution” ρ̂λ and a theoretical guarantee :ZZ
1R(θ)ρ̂λ (dθ) ≤ inf
R(θ)ρ(dθ) + K(ρ, π) + o(1).
ρλUsually o(1) is explicit, λ is some tuning-parameter to becalibrated (constrained to some range by theory), andρ̂λ (dθ) ∝ exp [−λr (θ)]π(dθ).
Pierre Alquier

PAC-Bayesian Bounds and Aggregation

Introduction : Learning with PAC-Bayes Bounds
Three Types of PAC-Bayesian Bounds
Computational Issues

Dalalyan-Tsybakov’s Bound
Catoni’s Bound
Audibert’s Bound for Online Learning

1st example : fixed design regression

Context :X1 , . . . , Xn deterministic ; Yi = f (Xi ) + εi andεi ∼ N (0, σ 2 ) (say).

Pierre Alquier

PAC-Bayesian Bounds and Aggregation

Introduction : Learning with PAC-Bayes Bounds
Three Types of PAC-Bayesian Bounds
Computational Issues

Dalalyan-Tsybakov’s Bound
Catoni’s Bound
Audibert’s Bound for Online Learning

1st example : fixed design regression

Context :X1 , . . . , Xn deterministic ; Yi = f (Xi ) + εi andεi ∼ N (0, σ 2 ) (say).
any (fθ (·) = hθ, g (·)i , θ ∈ Rp ).

Pierre Alquier

PAC-Bayesian Bounds and Aggregation

Introduction : Learning with PAC-Bayes Bounds
Three Types of PAC-Bayesian Bounds
Computational Issues

Dalalyan-Tsybakov’s Bound
Catoni’s Bound
Audibert’s Bound for Online Learning

1st example : fixed design regression

Context :X1 , . . . , Xn deterministic ; Yi = f (Xi ) + εi andεi ∼ N (0, σ 2 ) (say).
any (fθ (·) = hθ, g (·)i , θ ∈ Rp ).
P
R(θ) = n1 ni=1 [f (Xi ) − fθ (Xi )]2 .

Pierre Alquier

PAC-Bayesian Bounds and Aggregation

Introduction : Learning with PAC-Bayes Bounds
Three Types of PAC-Bayesian Bounds
Computational Issues

Dalalyan-Tsybakov’s Bound
Catoni’s Bound
Audibert’s Bound for Online Learning

1st example : fixed design regression

Context :X1 , . . . , Xn deterministic ; Yi = f (Xi ) + εi andεi ∼ N (0, σ 2 ) (say).
any (fθ (·) = hθ, g (·)i , θ ∈ Rp ).
P
R(θ) = n1 ni=1 [f (Xi ) − fθ (Xi )]2 .
P
rn (θ) = n1 ni=1 [Yi − fθ (Xi )]2 .

Pierre Alquier

PAC-Bayesian Bounds and Aggregation

Introduction : Learning with PAC-Bayes Bounds
Three Types of PAC-Bayesian Bounds
Computational Issues

Dalalyan-Tsybakov’s Bound
Catoni’s Bound
Audibert’s Bound for Online Learning

1st example : fixed design regression

Context :X1 , . . . , Xn deterministic ; Yi = f (Xi ) + εi andεi ∼ N (0, σ 2 ) (say).
any (fθ (·) = hθ, g (·)i , θ ∈ Rp ).
P
R(θ) = n1 ni=1 [f (Xi ) − fθ (Xi )]2 .
P
rn (θ) = n1 ni=1 [Yi − fθ (Xi )]2 .
any prior π.

Pierre Alquier

PAC-Bayesian Bounds and Aggregation

Introduction : Learning with PAC-Bayes Bounds
Three Types of PAC-Bayesian Bounds
Computational Issues

Dalalyan-Tsybakov’s Bound
Catoni’s Bound
Audibert’s Bound for Online Learning

Dalalyan and Tsybakov’s bound for EWA
TheoremDalalyan, A. & Tsybakov, A. (2008). Aggregation by Exponential Weighting, Sharp PAC-Bayesian
Bounds and Sparsity. Machine Learning.

n∀λ ≤ 2 :
4σ

 Z

E R
θρ̂λ (dθ)
Z

1
≤ inf
R(θ)ρ(dθ) + K(ρ, π)ρ
λPierre Alquier

PAC-Bayesian Bounds and Aggregation

Introduction : Learning with PAC-Bayes Bounds
Three Types of PAC-Bayesian Bounds
Computational Issues

Dalalyan-Tsybakov’s Bound
Catoni’s Bound
Audibert’s Bound for Online Learning

Dalalyan and Tsybakov’s bound for EWA
TheoremDalalyan, A. & Tsybakov, A. (2008). Aggregation by Exponential Weighting, Sharp PAC-Bayesian
Bounds and Sparsity. Machine Learning.

n∀λ ≤ 2 :
4σ

 Z

E R
θρ̂λ (dθ)
Z

1
≤ inf
R(θ)ρ(dθ) + K(ρ, π)ρλBased on previous work :Leung, G. and Barron, A. (2006). Information Theory and Mixing Least-Square Regressions. IEEE
Trans. on Information Theory.

Pierre Alquier

PAC-Bayesian Bounds and Aggregation

Introduction : Learning with PAC-Bayes Bounds
Three Types of PAC-Bayesian Bounds
Computational Issues

Dalalyan-Tsybakov’s Bound
Catoni’s Bound
Audibert’s Bound for Online Learning

Application : finite set of predictors θ1, . . . , θM
With π the uniform distribution on {θ1 , . . . , θM } we get
"Z
#
 Z

1
R(θ)ρ(dθ) + K(ρ, π)
E Rθρ̂λ (dθ)
≤ inf
ρ
λ

Pierre Alquier

PAC-Bayesian Bounds and Aggregation

Introduction : Learning with PAC-Bayes Bounds
Three Types of PAC-Bayesian Bounds
Computational Issues

Dalalyan-Tsybakov’s Bound
Catoni’s Bound
Audibert’s Bound for Online Learning

Application : finite set of predictors θ1, . . . , θM
With π the uniform distribution on {θ1 , . . . , θM } we get
"Z
#
 Z

1
R(θ)ρ(dθ) + K(ρ, π)
E Rθρ̂λ (dθ)
≤ inf
ρ
λ
"Z
#
≤ inf
R(θ)δθi (dθ) + 4σ 2 K(δθi , π)1≤i≤M

Pierre Alquier

PAC-Bayesian Bounds and Aggregation

Introduction : Learning with PAC-Bayes Bounds
Three Types of PAC-Bayesian Bounds
Computational Issues

Dalalyan-Tsybakov’s Bound
Catoni’s Bound
Audibert’s Bound for Online Learning

Application : finite set of predictors θ1, . . . , θM
With π the uniform distribution on {θ1 , . . . , θM } we get
"Z
#
 Z

1
R(θ)ρ(dθ) + K(ρ, π)
E Rθρ̂λ (dθ)
≤ inf
ρ
λ
"Z
#
≤ inf
R(θ)δθi (dθ) + 4σ 2 K(δθi , π)
1≤i≤M

"
= inf

1≤i≤M

Pierre Alquier#R(θi ) + 4σ 2 log(M) .

PAC-Bayesian Bounds and Aggregation

Introduction : Learning with PAC-Bayes Bounds
Three Types of PAC-Bayesian Bounds
Computational Issues

Dalalyan-Tsybakov’s Bound
Catoni’s Bound
Audibert’s Bound for Online Learning

Application : linear regression
With π = N (0, S 2 IM ),
 Z

E R
θρ̂λ (dθ)
≤

"Z
inf

ρ=N (θ0 ,s 2 IM )Pierre Alquier#
1
R(θ)ρ(dθ)+ K(ρ, π) .
λ

PAC-Bayesian Bounds and Aggregation

Introduction : Learning with PAC-Bayes Bounds
Three Types of PAC-Bayesian Bounds
Computational Issues

Dalalyan-Tsybakov’s Bound
Catoni’s Bound
Audibert’s Bound for Online Learning

Application : linear regression
With π = N (0, S 2 IM ),
 Z

E R
θρ̂λ (dθ)
≤

#
1
inf
R(θ)ρ(dθ)+ K(ρ, π) .
ρ=N (θ0 ,s 2 IM )λh  2 2 
ikθ0 k21s
S
As K(ρ, π) = 2 M S 2 − 1 + log s 2+ S 2 and (rough)R
calculations lead to R(θ)ρ(dθ) ≤ R(θ0 ) + M 2 kg k2∞ s 2 ,Pierre Alquier"Z

PAC-Bayesian Bounds and Aggregation

Introduction : Learning with PAC-Bayes Bounds
Three Types of PAC-Bayesian Bounds
Computational Issues

Dalalyan-Tsybakov’s Bound
Catoni’s Bound
Audibert’s Bound for Online Learning

Application : linear regression
With π = N (0, S 2 IM ),
 Z

E R
θρ̂λ (dθ)
≤

#
1
inf
R(θ)ρ(dθ)+ K(ρ, π) .
ρ=N (θ0 ,s 2 IM )λh  2 2 
ikθ0 k21s
S
As K(ρ, π) = 2 M S 2 − 1 + log s 2+ S 2 and (rough)R
calculations lead to R(θ)ρ(dθ) ≤ R(θ0 ) + M 2 kg k2∞ s 2 ,
(
 Z

 2

4Mσ 2
S Mn
E R
θρ̂λ (dθ)≤ inf R(θ0 ) +logneθ0 ∈RM)
1 kθk20 + 1++ kg k2∞ .
n
S2
Pierre Alquier"Z

PAC-Bayesian Bounds and Aggregation

Introduction : Learning with PAC-Bayes Bounds
Three Types of PAC-Bayesian Bounds
Computational Issues

Dalalyan-Tsybakov’s Bound
Catoni’s Bound
Audibert’s Bound for Online Learning

2nd example : general bound for batch learning

Context :(X1 , Y1 ), (X2 , Y2 ), ..., (Xn , Yn ) iid from P.

Pierre Alquier

PAC-Bayesian Bounds and Aggregation

Introduction : Learning with PAC-Bayes Bounds
Three Types of PAC-Bayesian Bounds
Computational Issues

Dalalyan-Tsybakov’s Bound
Catoni’s Bound
Audibert’s Bound for Online Learning

2nd example : general bound for batch learning

Context :(X1 , Y1 ), (X2 , Y2 ), ..., (Xn , Yn ) iid from P.
any (fθ , θ ∈ Θ).

Pierre Alquier

PAC-Bayesian Bounds and Aggregation

Introduction : Learning with PAC-Bayes Bounds
Three Types of PAC-Bayesian Bounds
Computational Issues

Dalalyan-Tsybakov’s Bound
Catoni’s Bound
Audibert’s Bound for Online Learning

2nd example : general bound for batch learning

Context :(X1 , Y1 ), (X2 , Y2 ), ..., (Xn , Yn ) iid from P.
any (fθ , θ ∈ Θ).
R(θ) = E(X ,Y )∼P [`(Y , fθ (X ))] for any bounded loss
function |`(·, ·)| ≤ B.

Pierre Alquier

PAC-Bayesian Bounds and Aggregation

Introduction : Learning with PAC-Bayes Bounds
Three Types of PAC-Bayesian Bounds
Computational Issues

Dalalyan-Tsybakov’s Bound
Catoni’s Bound
Audibert’s Bound for Online Learning

2nd example : general bound for batch learning

Context :(X1 , Y1 ), (X2 , Y2 ), ..., (Xn , Yn ) iid from P.
any (fθ , θ ∈ Θ).
R(θ) = E(X ,Y )∼P [`(Y , fθ (X ))] for any bounded loss
function |`(·, ·)| ≤ B.
P
rn (θ) = n1 ni=1 `(Yi , fθ (Xi )).

Pierre Alquier

PAC-Bayesian Bounds and Aggregation

Introduction : Learning with PAC-Bayes Bounds
Three Types of PAC-Bayesian Bounds
Computational Issues

Dalalyan-Tsybakov’s Bound
Catoni’s Bound
Audibert’s Bound for Online Learning

2nd example : general bound for batch learning

Context :(X1 , Y1 ), (X2 , Y2 ), ..., (Xn , Yn ) iid from P.
any (fθ , θ ∈ Θ).
R(θ) = E(X ,Y )∼P [`(Y , fθ (X ))] for any bounded loss
function |`(·, ·)| ≤ B.
P
rn (θ) = n1 ni=1 `(Yi , fθ (Xi )).
any prior π.

Pierre Alquier

PAC-Bayesian Bounds and Aggregation

Introduction : Learning with PAC-Bayes Bounds
Three Types of PAC-Bayesian Bounds
Computational Issues

Dalalyan-Tsybakov’s Bound
Catoni’s Bound
Audibert’s Bound for Online Learning

Catoni’s bound for batch learning
TheoremCatoni, O. (2007). PAC-Bayesian Supervised Classification (The Thermodynamics of Statistical
Learning), volume 56 of Lecture Notes-Monograph Series, IMS.

(Z∀λ > 0,
Z
≤ inf
ρ

P

R(θ)ρ̂λ (dθ)

 )2
2
λB
K(ρ, π) + log
R(θ)ρ(dθ) ++nλε≥ 1 − ε.

Pierre Alquier

PAC-Bayesian Bounds and Aggregation

Introduction : Learning with PAC-Bayes Bounds
Three Types of PAC-Bayesian Bounds
Computational Issues

Dalalyan-Tsybakov’s Bound
Catoni’s Bound
Audibert’s Bound for Online Learning

Catoni’s bound for batch learning
TheoremCatoni, O. (2007). PAC-Bayesian Supervised Classification (The Thermodynamics of Statistical
Learning), volume 56 of Lecture Notes-Monograph Series, IMS.

(Z∀λ > 0,
Z
≤ inf
ρ

P

R(θ)ρ̂λ (dθ)

 )2
2
λB
K(ρ, π) + log
R(θ)ρ(dθ) ++nλε≥ 1 − ε.

improving on seminal work :Shawe-Taylor, J. & Williamson, R. C. (1997). A PAC Analysis of a Bayesian Estimator. COLT’97.
McAllester, D. A. (1998). Some PAC-Bayesian Theorems. COLT’98.
Pierre Alquier

PAC-Bayesian Bounds and Aggregation

Introduction : Learning with PAC-Bayes Bounds
Three Types of PAC-Bayesian Bounds
Computational Issues

Dalalyan-Tsybakov’s Bound
Catoni’s Bound
Audibert’s Bound for Online Learning

3rd example : online learning(X1 , Y1 ), (X2 , Y2 ), ... without any other assumption than|Yi | ≤ B.

Pierre Alquier

PAC-Bayesian Bounds and Aggregation

Introduction : Learning with PAC-Bayes Bounds
Three Types of PAC-Bayesian Bounds
Computational Issues

Dalalyan-Tsybakov’s Bound
Catoni’s Bound
Audibert’s Bound for Online Learning

3rd example : online learning(X1 , Y1 ), (X2 , Y2 ), ... without any other assumption than|Yi | ≤ B.
any (fθ , θ ∈ Θ), with |f (θ)(x)| ≤ B.

Pierre Alquier

PAC-Bayesian Bounds and Aggregation

Introduction : Learning with PAC-Bayes Bounds
Three Types of PAC-Bayesian Bounds
Computational Issues

Dalalyan-Tsybakov’s Bound
Catoni’s Bound
Audibert’s Bound for Online Learning

3rd example : online learning(X1 , Y1 ), (X2 , Y2 ), ... without any other assumption than|Yi | ≤ B.
any (fθ , θ ∈ Θ), with |f (θ)(x)| ≤ B.
given (X1 , Y1 ), (X2 , Y2 ), ..., (Xt−1 , Yt−1 ) and Xt we areasked to predict Yt : by Ŷt . At some time T the gamestops and we evaluate the regret :
T
T
X
X
2
R=
(Yt − Ŷt ) − inf(Yt − fθ (Xt ))2 .
θ

t=1

Pierre Alquiert=1

PAC-Bayesian Bounds and Aggregation

Introduction : Learning with PAC-Bayes Bounds
Three Types of PAC-Bayesian Bounds
Computational Issues

Dalalyan-Tsybakov’s Bound
Catoni’s Bound
Audibert’s Bound for Online Learning

3rd example : online learning(X1 , Y1 ), (X2 , Y2 ), ... without any other assumption than|Yi | ≤ B.
any (fθ , θ ∈ Θ), with |f (θ)(x)| ≤ B.
given (X1 , Y1 ), (X2 , Y2 ), ..., (Xt−1 , Yt−1 ) and Xt we areasked to predict Yt : by Ŷt . At some time T the gamestops and we evaluate the regret :
T
T
X
X
2
R=
(Yt − Ŷt ) − inf(Yt − fθ (Xt ))2 .
θ

t=1

t=1

at time t we
can use as a proxy of the quality of θ :Pt−1
rt−1 (θ) = `=1 (Y` − fθ (X` ))2 .
Pierre Alquier

PAC-Bayesian Bounds and Aggregation

Introduction : Learning with PAC-Bayes Bounds
Three Types of PAC-Bayesian Bounds
Computational Issues

Dalalyan-Tsybakov’s Bound
Catoni’s Bound
Audibert’s Bound for Online Learning

3rd example : online learning(X1 , Y1 ), (X2 , Y2 ), ... without any other assumption than|Yi | ≤ B.
any (fθ , θ ∈ Θ), with |f (θ)(x)| ≤ B.
given (X1 , Y1 ), (X2 , Y2 ), ..., (Xt−1 , Yt−1 ) and Xt we areasked to predict Yt : by Ŷt . At some time T the gamestops and we evaluate the regret :
T
T
X
X
2
R=
(Yt − Ŷt ) − inf(Yt − fθ (Xt ))2 .
θ

t=1

t=1

at time t we
can use as a proxy of the quality of θ :Pt−1
rt−1 (θ) = `=1 (Y` − fθ (X` ))2 .
any prior π.
Pierre Alquier

PAC-Bayesian Bounds and Aggregation

Introduction : Learning with PAC-Bayes Bounds
Three Types of PAC-Bayesian Bounds
Computational Issues

Dalalyan-Tsybakov’s Bound
Catoni’s Bound
Audibert’s Bound for Online Learning

Audibert / Gerchinovitz’s bound for online learning
Fix λ ≤ 8B1 2 and define, at each time t :Zρ̂λ,t (dθ) ∝ exp[−λrt−1 (θ)]π(dθ) and Ŷt =Pierre Alquierfθ (Xt )ρ̂λ,t (dθ).

PAC-Bayesian Bounds and Aggregation

Introduction : Learning with PAC-Bayes Bounds
Three Types of PAC-Bayesian Bounds
Computational Issues

Dalalyan-Tsybakov’s Bound
Catoni’s Bound
Audibert’s Bound for Online Learning

Audibert / Gerchinovitz’s bound for online learning
Fix λ ≤ 8B1 2 and define, at each time t :Zρ̂λ,t (dθ) ∝ exp[−λrt−1 (θ)]π(dθ) and Ŷt =fθ (Xt )ρ̂λ,t (dθ).

TheoremGerchinovitz, S. (2011). Sparsity Regret Bounds for Individual Sequences in Online Linear
Regression. COLT’11.

(Z T
)
i2
Xh
1
(Yt −Ŷt )2 ≤ inf
Yt − fθ (Xt ) ρ(dθ) + K(ρ, π) .
ρ
λ
t=1
t=1

T
X

Pierre Alquier

PAC-Bayesian Bounds and Aggregation

Introduction : Learning with PAC-Bayes Bounds
Three Types of PAC-Bayesian Bounds
Computational Issues

Dalalyan-Tsybakov’s Bound
Catoni’s Bound
Audibert’s Bound for Online Learning

Audibert / Gerchinovitz’s bound for online learning
Fix λ ≤ 8B1 2 and define, at each time t :Zρ̂λ,t (dθ) ∝ exp[−λrt−1 (θ)]π(dθ) and Ŷt =fθ (Xt )ρ̂λ,t (dθ).

TheoremGerchinovitz, S. (2011). Sparsity Regret Bounds for Individual Sequences in Online Linear
Regression. COLT’11.

(Z T
)
i2
Xh
1
(Yt −Ŷt )2 ≤ inf
Yt − fθ (Xt ) ρ(dθ) + K(ρ, π) .
ρ
λ
t=1
t=1

T
X

Based on a result with general loss to be found in
Audibert, J.-Y. (2009). Fast learning Rates in Statistical Inference through Aggregation. Annalsof Statistics.
Pierre Alquier

PAC-Bayesian Bounds and Aggregation

Introduction : Learning with PAC-Bayes Bounds
Three Types of PAC-Bayesian Bounds
Computational Issues

Dalalyan-Tsybakov’s Bound
Catoni’s Bound
Audibert’s Bound for Online Learning

Bibliographical remarks (1/2)“Catoni’s type bound” : under the name “PAC-Bayesianbounds”, many authors including Langford, Seeger, Meir,
Cesa-Bianchi, Li, Jiang, Tanner, Laviolette, Guedj, sorry for
not being exhaustive, see the papers for more references !

Pierre Alquier

PAC-Bayesian Bounds and Aggregation

Introduction : Learning with PAC-Bayes Bounds
Three Types of PAC-Bayesian Bounds
Computational Issues

Dalalyan-Tsybakov’s Bound
Catoni’s Bound
Audibert’s Bound for Online Learning

Bibliographical remarks (1/2)“Catoni’s type bound” : under the name “PAC-Bayesianbounds”, many authors including Langford, Seeger, Meir,
Cesa-Bianchi, Li, Jiang, Tanner, Laviolette, Guedj, sorry for
not being exhaustive, see the papers for more references !
“Dalalyan-Tsybakov’s type” bound : under the name“Exponentially Weighted Aggregation”, Golubev, Suzuki,Montuelle, Le Pennec, Robbiano, Salmon...

Pierre Alquier

PAC-Bayesian Bounds and Aggregation

Introduction : Learning with PAC-Bayes Bounds
Three Types of PAC-Bayesian Bounds
Computational Issues

Dalalyan-Tsybakov’s Bound
Catoni’s Bound
Audibert’s Bound for Online Learning

Bibliographical remarks (1/2)“Catoni’s type bound” : under the name “PAC-Bayesianbounds”, many authors including Langford, Seeger, Meir,
Cesa-Bianchi, Li, Jiang, Tanner, Laviolette, Guedj, sorry for
not being exhaustive, see the papers for more references !
“Dalalyan-Tsybakov’s type” bound : under the name“Exponentially Weighted Aggregation”, Golubev, Suzuki,Montuelle, Le Pennec, Robbiano, Salmon...
Related to other works on aggregation : Vovk, Rissanen,
Abramovitch, Nemirovski, Yang, Rigollet, Lecué, Bellec,
Michel, Gaïffas...
Pierre Alquier

PAC-Bayesian Bounds and Aggregation

Introduction : Learning with PAC-Bayes Bounds
Three Types of PAC-Bayesian Bounds
Computational Issues

Dalalyan-Tsybakov’s Bound
Catoni’s Bound
Audibert’s Bound for Online Learning

Bibliographical remarks (2/2)ρ̂λ (dθ) ∝ exp [−λr (θ)]π(dθ).
Bayesian interpretation : exp [−λr (θ)] = “pseudo-likelihood”.

Pierre Alquier

PAC-Bayesian Bounds and Aggregation

Introduction : Learning with PAC-Bayes Bounds
Three Types of PAC-Bayesian Bounds
Computational Issues

Dalalyan-Tsybakov’s Bound
Catoni’s Bound
Audibert’s Bound for Online Learning

Bibliographical remarks (2/2)ρ̂λ (dθ) ∝ exp [−λr (θ)]π(dθ).
Bayesian interpretation : exp [−λr (θ)] = “pseudo-likelihood”.
Decision theory and Bayesian statistics : more authors
advocate the use of ρ̂λ : Miller, Dunson...
Bissiri, P., Holmes, C. and Walker, S. (2013). Fast learning Rates in Statistical Inference throughAggregation. Preprint.
Grünwald, P. D. & van Ommen, T. (2013). Inconsistency of Bayesian Inference for Misspecified
Linear Models, and a Proposal for Repairing It. Preprint.

Pierre Alquier

PAC-Bayesian Bounds and Aggregation

Introduction : Learning with PAC-Bayes Bounds
Three Types of PAC-Bayesian Bounds
Computational Issues

Dalalyan-Tsybakov’s Bound
Catoni’s Bound
Audibert’s Bound for Online Learning

Bibliographical remarks (2/2)ρ̂λ (dθ) ∝ exp [−λr (θ)]π(dθ).
Bayesian interpretation : exp [−λr (θ)] = “pseudo-likelihood”.
Decision theory and Bayesian statistics : more authors
advocate the use of ρ̂λ : Miller, Dunson...
Bissiri, P., Holmes, C. and Walker, S. (2013). Fast learning Rates in Statistical Inference throughAggregation. Preprint.
Grünwald, P. D. & van Ommen, T. (2013). Inconsistency of Bayesian Inference for Misspecified
Linear Models, and a Proposal for Repairing It. Preprint.

Asymptotic study of Bayesian estimators : Ghosh,
Ghoshal, van der Vaart, Gassiat, Rousseau, Castillo... different
from PAC-Bayes but most calculations are similar !
Pierre Alquier

PAC-Bayesian Bounds and Aggregation

Introduction : Learning with PAC-Bayes Bounds
Three Types of PAC-Bayesian Bounds
Computational Issues

Monte-Carlo
Variational Bayes Methods
PAC Analysis of Variational Bayes Approximations

Reminder : EWAρ̂λ (dθ) ∝ exp [−λr (θ)]π(dθ).

Pierre Alquier

PAC-Bayesian Bounds and Aggregation

Introduction : Learning with PAC-Bayes Bounds
Three Types of PAC-Bayesian Bounds
Computational Issues

Monte-Carlo
Variational Bayes Methods
PAC Analysis of Variational Bayes Approximations

Reminder : EWAρ̂λ (dθ) ∝ exp [−λr (θ)]π(dθ).
Depending on the setting, we have tosample from ρ̂λ ,Rcompute θρ̂λ (dθ).

Pierre Alquier

PAC-Bayesian Bounds and Aggregation

Introduction : Learning with PAC-Bayes Bounds
Three Types of PAC-Bayesian Bounds
Computational Issues

Monte-Carlo
Variational Bayes Methods
PAC Analysis of Variational Bayes Approximations

A natural idea : MCMC methods
Langevin Monte-Carlo :Dalalyan, A. and Tsybakov, A. (2011). Sparse regression learning by aggregation and LangevinMonte-Carlo. Journal of Computer and System Science.

Markov Chain Monte-Carlo :Alquier, P. & Biau, G. (2013). Sparse Single-Index Model. Journal of Machine Learning Reseach.

Pierre Alquier

PAC-Bayesian Bounds and Aggregation

Introduction : Learning with PAC-Bayes Bounds
Three Types of PAC-Bayesian Bounds
Computational Issues

Monte-Carlo
Variational Bayes Methods
PAC Analysis of Variational Bayes Approximations

A natural idea : MCMC methods
Langevin Monte-Carlo :Dalalyan, A. and Tsybakov, A. (2011). Sparse regression learning by aggregation and LangevinMonte-Carlo. Journal of Computer and System Science.

Markov Chain Monte-Carlo :Alquier, P. & Biau, G. (2013). Sparse Single-Index Model. Journal of Machine Learning Reseach.

However : very hard to prove the convergence of thealgorithm. Usually not possible to provide guarantees after afinite number of steps. See however
Joulin, A. & Ollivier, Y. (2010). Curvature, Concentration, and Error Estimates for Markov Chain
Monte Carlo. The Annals of Probability.
Dalalyan, A. (2014). Theoretical Guarantees for Approximate Sampling from a Smooth and
Log-Concave Density. Preprint.
Pierre Alquier

PAC-Bayesian Bounds and Aggregation

Introduction : Learning with PAC-Bayes Bounds
Three Types of PAC-Bayesian Bounds
Computational Issues

Monte-Carlo
Variational Bayes Methods
PAC Analysis of Variational Bayes Approximations

Variational Bayes methods
Idea from Bayesian statistics : approximate the posterior
distribution π(θ|x). We fix a convenient family of probability
distributions F and approximate the posterior by π̃(θ) :π̃ = arg min K(ρ, π(·|x)).
ρ∈F

Jordan, M. et al (1999). An Introduction to Variational Methods for Graphical Models. Machine
Learning.

Pierre Alquier

PAC-Bayesian Bounds and Aggregation

Introduction : Learning with PAC-Bayes Bounds
Three Types of PAC-Bayesian Bounds
Computational Issues

Monte-Carlo
Variational Bayes Methods
PAC Analysis of Variational Bayes Approximations

Variational Bayes methods
Idea from Bayesian statistics : approximate the posterior
distribution π(θ|x). We fix a convenient family of probability
distributions F and approximate the posterior by π̃(θ) :π̃ = arg min K(ρ, π(·|x)).
ρ∈F

Jordan, M. et al (1999). An Introduction to Variational Methods for Graphical Models. Machine
Learning.

F is either parametric or non-parametric. In the parametriccase, the problem boils down to an optimization problem :F = {ρa , a ∈ A ⊂ Rd } 99K min K(ρa , π(·|x)).
a∈A

Pierre Alquier

PAC-Bayesian Bounds and Aggregation

Introduction : Learning with PAC-Bayes Bounds
Three Types of PAC-Bayesian Bounds
Computational Issues

Monte-Carlo
Variational Bayes Methods
PAC Analysis of Variational Bayes Approximations

Variational Bayes methods
Idea from Bayesian statistics : approximate the posterior
distribution π(θ|x). We fix a convenient family of probability
distributions F and approximate the posterior by π̃(θ) :π̃ = arg min K(ρ, π(·|x)).
ρ∈F

Jordan, M. et al (1999). An Introduction to Variational Methods for Graphical Models. Machine
Learning.

F is either parametric or non-parametric. In the parametriccase, the problem boils down to an optimization problem :F = {ρa , a ∈ A ⊂ Rd } 99K min K(ρa , π(·|x)).
a∈A

Theoretical guarantees on the approximation ?
Pierre Alquier

PAC-Bayesian Bounds and Aggregation

Introduction : Learning with PAC-Bayes Bounds
Three Types of PAC-Bayesian Bounds
Computational Issues

Monte-Carlo
Variational Bayes Methods
PAC Analysis of Variational Bayes Approximations

VB in PAC-Bayesian frameworkρ̂λ (dθ) ∝ exp [−λr (θ)]π(dθ).
Then :
dρa dπK(ρa , ρ̂λ ) = logdρadπ dρ̂λZZ= λ r (θ)ρa (dθ) + K(ρa , π) + log exp[−λr ]dπ.
ZPierre Alquier

PAC-Bayesian Bounds and Aggregation

Introduction : Learning with PAC-Bayes Bounds
Three Types of PAC-Bayesian Bounds
Computational Issues

Monte-Carlo
Variational Bayes Methods
PAC Analysis of Variational Bayes Approximations

VB in PAC-Bayesian frameworkρ̂λ (dθ) ∝ exp [−λr (θ)]π(dθ).
Then :
dρa dπK(ρa , ρ̂λ ) = logdρadπ dρ̂λZZ= λ r (θ)ρa (dθ) + K(ρa , π) + log exp[−λr ]dπ.
ZWe put Zãλ = arg min λ r (θ)ρa (dθ) + K(ρa , π) and ρ̃λ = ρâλ .
a∈APierre Alquier

PAC-Bayesian Bounds and Aggregation

Introduction : Learning with PAC-Bayes Bounds
Three Types of PAC-Bayesian Bounds
Computational Issues

Monte-Carlo
Variational Bayes Methods
PAC Analysis of Variational Bayes Approximations

A PAC-Bound for VB Approximation
Theorem
Alquier, P., Ridgway, J. & Chopin, N. (2015). On the Properties of Variational Approximations ofGibbs Posteriors. Preprint.

(Z∀λ > 0,
Z
≤ inf

a∈A

P

R(θ)ρ̃λ (dθ)

 )λ 2
2R(θ)ρa (dθ) + +K(ρa , π) + log
n λε≥ 1 − ε.

Pierre Alquier

PAC-Bayesian Bounds and Aggregation

Introduction : Learning with PAC-Bayes Bounds
Three Types of PAC-Bayesian Bounds
Computational Issues

Monte-Carlo
Variational Bayes Methods
PAC Analysis of Variational Bayes Approximations

A PAC-Bound for VB Approximation
Theorem
Alquier, P., Ridgway, J. & Chopin, N. (2015). On the Properties of Variational Approximations ofGibbs Posteriors. Preprint.

(Z∀λ > 0,
Z
≤ inf

a∈A

P

R(θ)ρ̃λ (dθ)

 )λ 2
2R(θ)ρa (dθ) + +K(ρa , π) + log
n λε≥ 1 − ε.

99K if we can derive a tight oracle inequality from this bound,
we know that the VB approximation is sensible !
Pierre Alquier

PAC-Bayesian Bounds and Aggregation

Introduction : Learning with PAC-Bayes Bounds
Three Types of PAC-Bayesian Bounds
Computational Issues

Monte-Carlo
Variational Bayes Methods
PAC Analysis of Variational Bayes Approximations

Application to a linear classification problem(X1 , Y1 ), (X2 , Y2 ), ..., (Xn , Yn ) iid from P.

Pierre Alquier

PAC-Bayesian Bounds and Aggregation

Introduction : Learning with PAC-Bayes Bounds
Three Types of PAC-Bayesian Bounds
Computational Issues

Monte-Carlo
Variational Bayes Methods
PAC Analysis of Variational Bayes Approximations

Application to a linear classification problem(X1 , Y1 ), (X2 , Y2 ), ..., (Xn , Yn ) iid from P.
fθ (x) = 1(hθ, xi ≥ 0), x, θ ∈ Rd .

Pierre Alquier

PAC-Bayesian Bounds and Aggregation

Introduction : Learning with PAC-Bayes Bounds
Three Types of PAC-Bayesian Bounds
Computational Issues

Monte-Carlo
Variational Bayes Methods
PAC Analysis of Variational Bayes Approximations

Application to a linear classification problem(X1 , Y1 ), (X2 , Y2 ), ..., (Xn , Yn ) iid from P.
fθ (x) = 1(hθ, xi ≥ 0), x, θ ∈ Rd .
R(θ) = P[Y 6= fθ (X )].

Pierre Alquier

PAC-Bayesian Bounds and Aggregation

Introduction : Learning with PAC-Bayes Bounds
Three Types of PAC-Bayesian Bounds
Computational Issues

Monte-Carlo
Variational Bayes Methods
PAC Analysis of Variational Bayes Approximations

Application to a linear classification problem(X1 , Y1 ), (X2 , Y2 ), ..., (Xn , Yn ) iid from P.
fθ (x) = 1(hθ, xi ≥ 0), x, θ ∈ Rd .
R(θ) = P[Y 6= fθ (X )].
P
rn (θ) = n1 ni=1 1[Yi 6= fθ (Xi )].

Pierre Alquier

PAC-Bayesian Bounds and Aggregation

Introduction : Learning with PAC-Bayes Bounds
Three Types of PAC-Bayesian Bounds
Computational Issues

Monte-Carlo
Variational Bayes Methods
PAC Analysis of Variational Bayes Approximations

Application to a linear classification problem(X1 , Y1 ), (X2 , Y2 ), ..., (Xn , Yn ) iid from P.
fθ (x) = 1(hθ, xi ≥ 0), x, θ ∈ Rd .
R(θ) = P[Y 6= fθ (X )].
P
rn (θ) = n1 ni=1 1[Yi 6= fθ (Xi )].
Gaussian prior π = N (0, ϑI ).

Pierre Alquier

PAC-Bayesian Bounds and Aggregation

Introduction : Learning with PAC-Bayes Bounds
Three Types of PAC-Bayesian Bounds
Computational Issues

Monte-Carlo
Variational Bayes Methods
PAC Analysis of Variational Bayes Approximations

Application to a linear classification problem(X1 , Y1 ), (X2 , Y2 ), ..., (Xn , Yn ) iid from P.
fθ (x) = 1(hθ, xi ≥ 0), x, θ ∈ Rd .
R(θ) = P[Y 6= fθ (X )].
P
rn (θ) = n1 ni=1 1[Yi 6= fθ (Xi )].
Gaussian prior π = N (0, ϑI ).
Gaussian approx. of thed posterior :F = N (µ, Σ), µ ∈ R , Σ s. pos. def. .

Pierre Alquier

PAC-Bayesian Bounds and Aggregation

Introduction : Learning with PAC-Bayes Bounds
Three Types of PAC-Bayesian Bounds
Computational Issues

Monte-Carlo
Variational Bayes Methods
PAC Analysis of Variational Bayes Approximations

Application to a linear classification problem(X1 , Y1 ), (X2 , Y2 ), ..., (Xn , Yn ) iid from P.
fθ (x) = 1(hθ, xi ≥ 0), x, θ ∈ Rd .
R(θ) = P[Y 6= fθ (X )].
P
rn (θ) = n1 ni=1 1[Yi 6= fθ (Xi )].
Gaussian prior π = N (0, ϑI ).
Gaussian approx. of thed posterior :F = N (µ, Σ), µ ∈ R , Σ s. pos. def. .
Optimization criterion :
n

λX
Φ
n i=1

−Y hX , µip i i
hXi , ΣXi i!

kµk2 1
+
+
2ϑ
2




1
tr(Σ) − log |Σ|ϑusing deterministic annealing and gradient descent.
Pierre Alquier

PAC-Bayesian Bounds and Aggregation

Introduction : Learning with PAC-Bayes Bounds
Three Types of PAC-Bayesian Bounds
Computational Issues

Monte-Carlo
Variational Bayes Methods
PAC Analysis of Variational Bayes Approximations

Application of the main theorem
Corollary
Assume that, for kθk = kθ0 k = 1,√P(hθ, X√i hθ0 , X i) ≤ ckθ − θ0 k and take λ = nd andϑ = 1/ d. Then
(Z
P

r h
i
d
R(θ)ρ̃λ (dθ) ≤ inf R(θ) +log(4ne2 ) + cθn)
2 log 2ε+ √≥ 1 − ε.
nd

Pierre Alquier

PAC-Bayesian Bounds and Aggregation

Introduction : Learning with PAC-Bayes Bounds
Three Types of PAC-Bayesian Bounds
Computational Issues

Monte-Carlo
Variational Bayes Methods
PAC Analysis of Variational Bayes Approximations

Application of the main theorem
Corollary
Assume that, for kθk = kθ0 k = 1,√P(hθ, X√i hθ0 , X i) ≤ ckθ − θ0 k and take λ = nd andϑ = 1/ d. Then
(Z
P

r h
i
d
R(θ)ρ̃λ (dθ) ≤ inf R(θ) +log(4ne2 ) + cθn)
2 log 2ε+ √≥ 1 − ε.
ndN.B : under margin assumption, possible to obtain d/n rates...
Pierre Alquier

PAC-Bayesian Bounds and Aggregation

Introduction : Learning with PAC-Bayes Bounds
Three Types of PAC-Bayesian Bounds
Computational Issues

Monte-Carlo
Variational Bayes Methods
PAC Analysis of Variational Bayes Approximations

Test on real data
DatasetCovariates

VB

SMC

SVM

Pima
CreditDNA
SPECTF
Glass
IndianBreast

7
60
180
22
10
11
10

21.3
33.6
23.6
06.9
19.6
25.5
1.1

22.3
32.0
23.6
08.5
23.3
26.2
1.1

30.4
32.0
20.4
10.1
4.7
26.8
1.7

Table: Comparison of misclassification rates (%). Last column :kernel-SVM with radial kernel. The hyper-parameters λ and ϑ arechosen by cross-validation.
Pierre Alquier

PAC-Bayesian Bounds and Aggregation

Introduction : Learning with PAC-Bayes Bounds
Three Types of PAC-Bayesian Bounds
Computational Issues

Monte-Carlo
Variational Bayes Methods
PAC Analysis of Variational Bayes Approximations

Convexification of the loss
Can replace the 0/1 loss by a convex surrogate at “no” cost :Zhang, T. (2004). Statistical behavior and consistency of classification methods based on convex
risk minimization. Annals of Statistics.

Pierre Alquier

PAC-Bayesian Bounds and Aggregation

Introduction : Learning with PAC-Bayes Bounds
Three Types of PAC-Bayesian Bounds
Computational Issues

Monte-Carlo
Variational Bayes Methods
PAC Analysis of Variational Bayes Approximations

Convexification of the loss
Can replace the 0/1 loss by a convex surrogate at “no” cost :Zhang, T. (2004). Statistical behavior and consistency of classification methods based on convex
risk minimization. Annals of Statistics.

R(θ) = E[(1P − Yfθ (X ))+ ] (hinge loss).
rn (θ) = n1 ni=1 (1 − Yi fθ(Xi ))+ .
Gaussian approx. : F = N (µ, σ 2 I ), µ ∈ Rd , σ > 0 .

Pierre Alquier

PAC-Bayesian Bounds and Aggregation

Introduction : Learning with PAC-Bayes Bounds
Three Types of PAC-Bayesian Bounds
Computational Issues

Monte-Carlo
Variational Bayes Methods
PAC Analysis of Variational Bayes Approximations

Convexification of the loss
Can replace the 0/1 loss by a convex surrogate at “no” cost :Zhang, T. (2004). Statistical behavior and consistency of classification methods based on convex
risk minimization. Annals of Statistics.

R(θ) = E[(1P − Yfθ (X ))+ ] (hinge loss).
rn (θ) = n1 ni=1 (1 − Yi fθ(Xi ))+ .
Gaussian approx. : F = N (µ, σ 2 I ), µ ∈ Rd , σ > 0 .
99K the following criterion (which turns out to be convex !) :n
1X
1 − Yi hµ, Xi i
(1 − Yi hµ, Xi i) Φn i=1
σkXi k2




n
1X
1 − Yi hµ, Xi i
kµk22 d ϑ2+
σkXi kϕ++− log σ .
n i=1
σkXi k2
2ϑ 2 σ 2
Pierre Alquier

PAC-Bayesian Bounds and Aggregation

Introduction : Learning with PAC-Bayes Bounds
Three Types of PAC-Bayesian Bounds
Computational Issues

Monte-Carlo
Variational Bayes Methods
PAC Analysis of Variational Bayes Approximations

Application of the main theorem
Optimization with stochastic gradient descent on a ball ofradius M. On this ball, the objetive function is L-Lipschitz.
(k)After k step, we have the approximation ρ̃λ of the posterior.
Corollary
Assume kX k ≤ cx a.s., take λ =
(Z
P

√
√
nd and ϑ = 1/ d. Then(k)

R(θ)ρ̃λ (dθ) ≤ inf R(θ)
θ

cx
LM
+
+√
2
1+k

r

n
d
log
+
n
d

cx2 +1+ 2cx log
2cx

√
nd

2
ε

)

≥ 1 − ε.
Pierre Alquier

PAC-Bayesian Bounds and Aggregation

Introduction : Learning with PAC-Bayes Bounds
Three Types of PAC-Bayesian Bounds
Computational Issues

Monte-Carlo
Variational Bayes Methods
PAC Analysis of Variational Bayes Approximations

DatasetConvex VB

VB

SMC

SVM

Pima
CreditDNA
SPECTF
Glass
IndianBreast

21.8
27.2
4.2
19.2
26.1
26.2
0.5

21.3
33.6
23.6
06.9
19.6
25.5
1.1

22.3
32.0
23.6
08.5
23.3
26.2
1.1

30.4
32.0
20.4
10.1
4.7
26.8
1.7

Table: Comparison of misclassification rates (%), including theconvexified version of VB.

Pierre Alquier

PAC-Bayesian Bounds and Aggregation

Introduction : Learning with PAC-Bayes Bounds
Three Types of PAC-Bayesian Bounds
Computational Issues

Monte-Carlo
Variational Bayes Methods
PAC Analysis of Variational Bayes Approximations

Convergence graphs

3

Emprical Bound 95%

Emprical Bound 95%

3

2

2

1

1

0
0

25

50

75

100

Iterations

0

100

200

300

Iterations

Figure: Stochastic gradient descent, Pima and Adult datasets.

Pierre Alquier

PAC-Bayesian Bounds and Aggregation

Introduction : Learning with PAC-Bayes Bounds
Three Types of PAC-Bayesian Bounds
Computational Issues

Monte-Carlo
Variational Bayes Methods
PAC Analysis of Variational Bayes Approximations

Thanks & best wishes for 2016 !

Pierre Alquier

PAC-Bayesian Bounds and Aggregation