Introduction : Bayesian learning and meta-learning
Overview of our results
More detailed view of our results

Rates of convergence inBayesian meta-learning
Pierre Alquier12th Workshop on High Dimensional Data Analysis
ESSEC and University Mohamed V
Rabat, Morocco
Pierre Alquier, ESSEC

Bayesian meta-learning

Introduction : Bayesian learning and meta-learning
Overview of our results
More detailed view of our results

Charles RIOU

Badr-Eddine CHÉRIEF-ABDELLATIF

University of Tokyo,

CNRS,

RIKEN AIP

Sorbonne Université

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. Preprint arXiv :2302.11709.

Pierre Alquier, ESSEC

Bayesian meta-learning

Introduction : Bayesian learning and meta-learning
Overview of our results
More detailed view of our results

1

Introduction : Bayesian learning and meta-learning

2

Overview of our results

3

More detailed view of our results

Pierre Alquier, ESSEC

Bayesian meta-learning

Introduction : Bayesian learning and meta-learning
Overview of our results
More detailed view of our results

1

Introduction : Bayesian learning and meta-learning

2

Overview of our results

3

More detailed view of our results

Pierre Alquier, ESSEC

Bayesian meta-learning

Introduction : Bayesian learning and meta-learning
Overview of our results
More detailed view of our results

Pierre Alquier, ESSEC

Bayesian meta-learning

Introduction : Bayesian learning and meta-learning
Overview of our results
More detailed view of our results

To keep the results as simple as possible :S = (X1 , . . . , Xn ) i.i.d. from P,ℓ(x, θ) bounded by 1.
Generalization risk : R(θ) = EX ∼P [ℓ(X , θ)].
Objective : θ∗ = arg minθ∈Θ R(θ).
Risk of the “Bayes” procedure ρ : Eθ∼ρ [R(θ)].
Theorem (stated informally)rnod log(n)ES Eθ∼ρ [R(θ)] ≤ R(θ∗ ) + cn
where d = d(P, π) defined in the next slide, for α well chosen.
Pierre Alquier, ESSEC

Bayesian meta-learning

Introduction : Bayesian learning and meta-learning
Overview of our results
More detailed view of our resultsN(θ∗ , s) := {θ ∈ Θ : R(θ) − R(θ∗ ) ≤ s}.
d = d(P, π) is the smallest number such that, for any s smallenough :π(N(θ∗ , s)) ≥ s d .
Pierre Alquier, ESSEC

Bayesian meta-learning

Introduction : Bayesian learning and meta-learning
Overview of our results
More detailed view of our results

How do we prove the theorem ?
ρ(θ) ∝ π(θ)e−αPn

i=1 ℓ(xi ,θ)(= arg minp∈Prob(Θ)

Eθ∼p")#n1XKL(p, π).
ℓ(xi , θ) +n i=1αn

PAC-Bayes / Information bounds
noKL(p, π)
ES Eθ∼ρ [R(θ)] ≤ inf Eθ∼p [R(θ)] + α +.
pαnIn particular, for p as the restriction of π to N(θ∗ , s),nod log 1s∗ES Eθ∼ρ [R(θ)] ≤ inf R(θ ) + s + α +.
s>0αnPierre Alquier, ESSEC

Bayesian meta-learning

Introduction : Bayesian learning and meta-learning
Overview of our results
More detailed view of our results

Old result : in a “noiseless setting”, when there is a θ suchthat ℓ(x, θ) = 0 almost surely for x ∼ P,nod log(n)ES Eθ∼ρ [R(θ)] ≤ R(θ∗ ) +c.
| {z }
n=0Similar fast rates obtained in classification under
Mammen and Tsybakov margin assumption (1999).
Also with Lipschitz and strongly convex losses ℓ(x, ·) by
Bartlett and Mendelson (2006).
All these assumptions turned out to be a special case of :Bernstein conditionno∗ 2Ex∼P [ℓ(x, θ) − ℓ(x, θ )] ≤ C [R(θ) − R(θ∗ )] .
Pierre Alquier, ESSEC

Bayesian meta-learning

Introduction : Bayesian learning and meta-learning
Overview of our results
More detailed view of our results

What about variational Bayes ?
Let W be a subset of Prob(Θ), and put :(" n#)
1XKL(p, π)Wρ (θ) = arg minEθ∼pℓ(xi , θ) +.
Wn i=1αnProb(Θ)p∈ P. Alquier, J. Ridgway , N. Chopin (2016). On the Properties of Variational Approximations ofGibbs Posteriors. JMLR.

provides minimal assumptions on W ensuringβnod(P, π) log(n)∗ES Eθ∼ρW [R(θ)] ≤ R(θ ) + cn
where β = 1 under Bernstein condition, β = 1/2 otherwise.
Pierre Alquier, ESSEC

Bayesian meta-learning

Introduction : Bayesian learning and meta-learning
Overview of our resultsMore detailed view of our results

Recapρ(θ) ∝ π(θ)e−αPn

i=1 ℓ(xi ,θ).

We have :βnod log(n)∗ES Eθ∼ρ [R(θ)] ≤ R(θ ) + cn
where β = 1 under Bernstein condition, β = 1/2 otherwise.
The generalization error is driven by d = d(P, π) that
depends on π.
Tempting to learn a better π, but π is not allowed todepend on the data...
Pierre Alquier, ESSEC

Bayesian meta-learning

Introduction : Bayesian learning and meta-learning
Overview of our results
More detailed view of our results

Idea of Bayesian meta-learning :We solve many related tasks (say T ) using Bayesianlearning.
By related, we mean that the same prior could be used in
all tasks.
Based on past tasks, can we define a π that would work
better for future tasks ?
Pierre Alquier, ESSEC

Bayesian meta-learning

Introduction : Bayesian learning and meta-learning
Overview of our results
More detailed view of our results

Notations :Tasks : t = 1, . . . , T .
P1 , . . . , PT are i.i.d from P.
Task t : St = (xt,1 , . . . , xt,n ) i.i.d from Pt .
Generalization error in task t : Rt (θ) = Ex∼Pt [ℓ(x, θ)].
Best error in task t : Rt (θt∗ ) = minθ Rt (θ).
P
ρt (π, α)(θ) ∝ π(θ) exp[−α ni=1 ℓ(θ, xt,i )].
Objective
Learn π̂ = π̂(S1 , . . . , ST ).
For a new task PT +1 ∼ P, ST +1 = (xT +1,1 , . . . , xT +1,n )
i.i.d. from PT +1 , we want :Eθ∼ρT +1 (π̂,α) [RT +1 (θ)] ≤ Eθ∼ρT +1 (π,α) [RT +1 (θ)] .
Pierre Alquier, ESSEC

Bayesian meta-learning

Introduction : Bayesian learning and meta-learning
Overview of our results
More detailed view of our results

Pierre Alquier, ESSEC

Bayesian meta-learning

Introduction : Bayesian learning and meta-learning
Overview of our results
More detailed view of our results

Past tasks, used to learn a better prior. Expectation withrespect to P1 , . . . , PT , S1 , . . . , ST denoted by Edata .
New task. Expectation with respect to PT +1 and ST +1
will be denoted by Enew .
Pierre Alquier, ESSECBayesian meta-learning

Introduction : Bayesian learning and meta-learning
Overview of our results
More detailed view of our results

1

Introduction : Bayesian learning and meta-learning

2

Overview of our results

3

More detailed view of our results

Pierre Alquier, ESSEC

Bayesian meta-learning

Introduction : Bayesian learning and meta-learning
Overview of our results
More detailed view of our results

Ultimate (non-achievable) performance :E ∗ = Enew [RT +1 (θT∗ +1 )] = EPT +1 ∼P [RT +1 (θT∗ +1 )].
With a fixed prior :noE(π) = Enew Eθ∼ρT +1 (π,α) [RT +1 (θ)]"β #d(P,π)
log(n)
T +1≤ E ∗ + c EPT +1 ∼P.
nTo give an overview of our results, let us consider first an easy
situation : we want to find the best of K priors, say
π1 , . . . , π K .
Pierre Alquier, ESSEC

Bayesian meta-learning

Introduction : Bayesian learning and meta-learning
Overview of our results
More detailed view of our results

Recall :("ρt (π, α) = arg min Eθ∼pp|#)nKL(p, π)1Xℓ(xt,i , θ) +.
n i=1αn{z}R̂t (p,π)In this case, our procedure boils down to :)(Ti1 X hπ̂ = arg minR̂t ρt (π, α), π .
T t=1
π∈{π1 ,...,πK }Pierre Alquier, ESSEC

Bayesian meta-learning

Introduction : Bayesian learning and meta-learning
Overview of our results
More detailed view of our results

Theorem
Edata [E(π̂)]≤min E(πk ) +k=1,...,Klog KT"∗≤ E + c min EPT +1 ∼P
k=1,...,Kd(PT +1 , πk ) log(n)nβ #+clog K.
TImportant observations :gain expected only if T ≫ n.
the rate for learning the prior is in 1/T regardless or therate within tasks (β = 1 or β = 1/2).
Pierre Alquier, ESSEC

Bayesian meta-learning

Introduction : Bayesian learning and meta-learning
Overview of our results
More detailed view of our results

More generally, we can learn the best prior in an infinite
set Q (for example, all Gaussian priors, etc).
The definition of π̂ gets a little more convoluted.
We will recover similar results
Edata [E(π̂)] ≤ min E(π) +π∈QC(Q)T

where C(Q) is a complexity measure of Q.

Pierre Alquier, ESSEC

Bayesian meta-learning

Introduction : Bayesian learning and meta-learning
Overview of our results
More detailed view of our results

Example 1 : Gaussian priors.
θ ∈ Rp .
Q = {N (µ, Σ), µ ∈ Rp , Σ ∈ S+p }.

fix some m and put V = Enew ∥θT∗ +1 − m∥2 .
Very approximatevely,
Edata [E(π̂)] ≤ E ∗ + c

If V ≤pp+ c log (1 + nV ) .
Tnp
1, Edata [E(π̂)] ≤ E ∗ + c .
TTPierre Alquier, ESSEC

Bayesian meta-learning

Introduction : Bayesian learning and meta-learning
Overview of our results
More detailed view of our results

Example 2 : mixture of Gaussian priors.
θ ∈ Rnp .
oPK
Q=pN(µ,Σ).
kkkk=1
fix m1 , . . . , mK and put V = Enew mink ∥θT∗ +1 − mk ∥2 .

Edata [E(π̂)] ≤ E ∗ + cpKlog Kp+c+ c log (1 + nV ) .
Tnn

Pierre Alquier, ESSEC

Bayesian meta-learning

Introduction : Bayesian learning and meta-learning
Overview of our results
More detailed view of our results

1

Introduction : Bayesian learning and meta-learning

2

Overview of our results

3

More detailed view of our results

Pierre Alquier, ESSEC

Bayesian meta-learning

Introduction : Bayesian learning and meta-learning
Overview of our results
More detailed view of our results

The general procedure π̂ = π̂(S1 , . . . , ST ) is a little more
convoluted, it is actually a Bayesian procedure :fix a prior Π on the set of priors Q : Π ∈ Prob(Q),define :("#)
T
1 X KL(Λ, Π)Λ̂ = arg min Eπ∼ΛR̂t ρt (π, α), π +,T t=1γT
Λ∈Prob(Q)draw π̂ ∼ Λ̂.

Pierre Alquier, ESSEC

Bayesian meta-learning

Introduction : Bayesian learning and meta-learning
Overview of our results
More detailed view of our results

Definehi
π = arg min Enew R̂T +1 ρT +1 (π, α), π .
∗πLemma – Bernstein condition at the meta-level
For any π ∈ Q,∗∗

2 R̂T +1 ρT +1 (π, α), π − R̂T +1 ρT +1 (π , α), πih≤ C Enew R̂T +1 ρT +1 (π, α), π − R̂T +1 ρT +1 (π ∗ , α), π ∗ .
Enew

Pierre Alquier, ESSEC

Bayesian meta-learning

Introduction : Bayesian learning and meta-learning
Overview of our results
More detailed view of our results

TheoremnoEdata Eπ̂∼Λ̂ [E(π̂)] ≤ E ∗(+minΛ∈Prob(Q)Eπ∼Λ EPT +1 ∼P"d(PT +1 , π) log(n)nβ #)K(Λ, Π)+.
γT
The aforementioned examples are obtained by specification ofΠ, and taking an explicit Λ above.

Pierre Alquier, ESSEC

Bayesian meta-learning

Introduction : Bayesian learning and meta-learning
Overview of our results
More detailed view of our results

Remark :(Λ̂ = arg minΛ∈Prob(Q)"Eπ∼Λ#)T
1 X KL(Λ, Π)R̂t ρt (π, α), π +.
T t=1γT

What happens if we minimize over a smaller set
V ⊂ Prob(Q) ?
("#)
T
1 X KL(Λ, Π)Λ̂V = arg min Eπ∼ΛR̂t ρt (π, α), π +.
T t=1γTΛ∈V
Note : can be seen as a variational Bayes version of Λ̂.

Pierre Alquier, ESSEC

Bayesian meta-learningIntroduction : Bayesian learning and meta-learning
Overview of our results
More detailed view of our results

TheoremnoEdata Eπ̂∼Λ̂V [E(π̂)] ≤ E ∗("+ min Eπ∼Λ EPT +1 ∼PΛ∈Vd(PT +1 , π) log(n)nβ #)K(Λ, Π)+.
γTFor example, in the case Q = {π1 , . . . , πK }, taking V as theset of Dirac masses allows to define π̂ by a minimization rather
than by randomisation.
Pierre Alquier, ESSEC

Bayesian meta-learning

Introduction : Bayesian learning and meta-learning
Overview of our resultsMore detailed view of our results

Note however that our result require to use “exact” Bayes
within tasks.
Lemma – Bernstein condition at the meta-level
For any π ∈ Q,∗∗

2 R̂T +1 ρT +1 (π, α), π − R̂T +1 ρT +1 (π , α), πhi≤ C Enew R̂T +1 ρT +1 (π, α), π − R̂T +1 ρT +1 (π ∗ , α), π ∗ .
Enew

We don’t know how to extend this lemma if we replace
ρT +1 (π, α) by a variational approximation.
Pierre Alquier, ESSECBayesian meta-learning

Introduction : Bayesian learning and meta-learning
Overview of our results
More detailed view of our results

Some important open questions :extending the Lemma to allow variational approximations.
lower bounds.

Pierre Alquier, ESSEC

Bayesian meta-learning