Transfer learning, multitask learning, lifelong learning...
A strategy for lifelong learning, with regret analysis
Open questions

Regret Bounds for Lifelong Learning
Pierre AlquierGroupe de Travail de Machine learning du CMLAENS Paris-Saclay
Pierre Alquier

Lifelong Learning

Transfer learning, multitask learning, lifelong learning...
A strategy for lifelong learning, with regret analysis
Open questions

1

Transfer learning, multitask learning, lifelong learning...

2

A strategy for lifelong learning, with regret analysis

3Open questions

Pierre Alquier

Lifelong Learning

Transfer learning, multitask learning, lifelong learning...
A strategy for lifelong learning, with regret analysis
Open questions

1

Transfer learning, multitask learning, lifelong learning...

2

A strategy for lifelong learning, with regret analysis

3Open questions

Pierre Alquier

Lifelong Learning

Transfer learning, multitask learning, lifelong learning...
A strategy for lifelong learning, with regret analysis
Open questions

Generic learning task
A generic learning task
Given pairs object-label(X1 , Y1 ), . . . , (Xn , Yn )learn to predict labels from objects.

Pierre Alquier

Lifelong Learning

Transfer learning, multitask learning, lifelong learning...
A strategy for lifelong learning, with regret analysis
Open questions

Generic learning task
A generic learning task
Given pairs object-label(X1 , Y1 ), . . . , (Xn , Yn )learn to predict labels from objects.
self-driving car : road scene / presence of pedestrian ?

Pierre Alquier

Lifelong Learning

Transfer learning, multitask learning, lifelong learning...
A strategy for lifelong learning, with regret analysis
Open questions

Generic learning task
A generic learning task
Given pairs object-label(X1 , Y1 ), . . . , (Xn , Yn )learn to predict labels from objects.
self-driving car : road scene / presence of pedestrian ?
recommender system : customer / will buy my stuff ?

Pierre Alquier

Lifelong Learning

Transfer learning, multitask learning, lifelong learning...
A strategy for lifelong learning, with regret analysis
Open questions

Generic learning task
A generic learning task
Given pairs object-label(X1 , Y1 ), . . . , (Xn , Yn )learn to predict labels from objects.
self-driving car : road scene / presence of pedestrian ?
recommender system : customer / will buy my stuff ?
Cambridge analytica : facebook user / believes fakenews ?

Pierre Alquier

Lifelong Learning

Transfer learning, multitask learning, lifelong learning...
A strategy for lifelong learning, with regret analysis
Open questions

Generic learning task
A generic learning task
Given pairs object-label(X1 , Y1 ), . . . , (Xn , Yn )learn to predict labels from objects.
self-driving car : road scene / presence of pedestrian ?
recommender system : customer / will buy my stuff ?
Cambridge analytica : facebook user / believes fakenews ?
...
Pierre Alquier

Lifelong Learning

Transfer learning, multitask learning, lifelong learning...
A strategy for lifelong learning, with regret analysis
Open questions

Batch learning

data often assumed
i.i.d from P,
build fˆ based on thewhole dataset,minimize R(fˆ) whereR(f ) = E(X ,Y )∼P [`(Y , f (X ))].

Pierre Alquier

Lifelong Learning

Transfer learning, multitask learning, lifelong learning...
A strategy for lifelong learning, with regret analysis
Open questions

Batch learning : more books

Pierre Alquier

Lifelong Learning

Transfer learning, multitask learning, lifelong learning...
A strategy for lifelong learning, with regret analysis
Open questions

Online learning
no probabilistic
assumption,
data revealed
sequentially, at time tbuild fˆt based on data
seen so far
minimize
T
X`(Yt , fˆt (Xt ))t=1

Pierre Alquier

Lifelong Learning

Transfer learning, multitask learning, lifelong learning...
A strategy for lifelong learning, with regret analysis
Open questions

Online learning : a good starting point

Pierre Alquier

Lifelong Learning

Transfer learning, multitask learning, lifelong learning...
A strategy for lifelong learning, with regret analysis
Open questions

A few facts - motivation for transfer learningwhen we solve different tasks, it seems we start fromscratch at each task

Pierre Alquier

Lifelong Learning

Transfer learning, multitask learning, lifelong learning...
A strategy for lifelong learning, with regret analysis
Open questions

A few facts - motivation for transfer learningwhen we solve different tasks, it seems we start fromscratch at each task
still, our knowledge on “solving tasks” improves at each
time

Pierre Alquier

Lifelong Learning

Transfer learning, multitask learning, lifelong learning...
A strategy for lifelong learning, with regret analysis
Open questions

A few facts - motivation for transfer learningwhen we solve different tasks, it seems we start fromscratch at each task
still, our knowledge on “solving tasks” improves at eachtime
for similar task, it seems indeed reasonnable to transfer
information from one task to another.

Pierre Alquier

Lifelong Learning

Transfer learning, multitask learning, lifelong learning...
A strategy for lifelong learning, with regret analysis
Open questions

Tentative definition - from Thrun and PrattGiven
a task,a training experience,anda performancemeasure,a program is said to learn if
its performance at the task
improves with experience.

Pierre Alquier

Lifelong Learning

Transfer learning, multitask learning, lifelong learning...
A strategy for lifelong learning, with regret analysis
Open questions

Tentative definition - from Thrun and PrattGiven
a family of tasks,
training experience foreach of these tasks,
anda family of
performance measures,
an algorithm is said to learn
to learn if its performanceat each task improve withexperience and with thenumber of tasks.
Pierre Alquier

Lifelong Learning

Transfer learning, multitask learning, lifelong learning...
A strategy for lifelong learning, with regret analysis
Open questions

Multitask learning
Multitask learning
Given M tasks t, with M risks Rt (·) and M datasets
St := (Xt,1 , Yt,1 ), . . . , (Xt,nM , Yt,nM )propose M predictorsfˆt (·) = fˆt (S1 , . . . , SM ; ·)that aims at minimizing (for example)
R1 (fˆ1 ) + · · · + RM (fˆM ).

Pierre Alquier

Lifelong Learning

Transfer learning, multitask learning, lifelong learning...
A strategy for lifelong learning, with regret analysis
Open questions

Multitask learning
Multitask learning
Given M tasks t, with M risks Rt (·) and M datasets
St := (Xt,1 , Yt,1 ), . . . , (Xt,nM , Yt,nM )propose M predictorsfˆt (·) = fˆt (S1 , . . . , SM ; ·)that aims at minimizing (for example)
R1 (fˆ1 ) + · · · + RM (fˆM ).
Nice, but what if yet another new task appears ?
Pierre Alquier

Lifelong Learning

Transfer learning, multitask learning, lifelong learning...
A strategy for lifelong learning, with regret analysis
Open questions

Learning-to-learn
Learning-to-learn (LTL)
Given M tasks t with risk Rt (·), and M datasets
St := (Xt,1 , Yt,1 ), . . . , (Xt,nM , Yt,nM )learn information I = I(S1 , . . . , SM ) such that, when a newtask with risk R(·) and a new dataset
S := (X1 , Y1 ), . . . , (Xn , Yn )arrives, I can build a predictorfˆt (·) = fˆt (S, I; ·) such that R(fˆ) is small.
Pierre Alquier

Lifelong Learning

Transfer learning, multitask learning, lifelong learning...
A strategy for lifelong learning, with regret analysis
Open questions

Probabilistic setting for LTL
Possible probabilistic setting :Pierre Alquier

Lifelong Learning

Transfer learning, multitask learning, lifelong learning...
A strategy for lifelong learning, with regret analysis
Open questions

Probabilistic setting for LTL
Possible probabilistic setting :P1 , . . . , PM i.i.d from P,

Pierre Alquier

Lifelong Learning

Transfer learning, multitask learning, lifelong learning...
A strategy for lifelong learning, with regret analysis
Open questions

Probabilistic setting for LTL
Possible probabilistic setting :P1 , . . . , PM i.i.d from P,(Xt,1 , Yt,1 ), . . . , (Xt,nM , Yt,nM ) i.i.d from Pt ,Pierre Alquier

Lifelong Learning

Transfer learning, multitask learning, lifelong learning...
A strategy for lifelong learning, with regret analysis
Open questions

Probabilistic setting for LTL
Possible probabilistic setting :P1 , . . . , PM i.i.d from P,(Xt,1 , Yt,1 ), . . . , (Xt,nM , Yt,nM ) i.i.d from Pt ,Rt (f ) = E(X ,Y )∼Pt [`(Y , f (X ))],

Pierre Alquier

Lifelong Learning

Transfer learning, multitask learning, lifelong learning...
A strategy for lifelong learning, with regret analysis
Open questions

Probabilistic setting for LTL
Possible probabilistic setting :P1 , . . . , PM i.i.d from P,(Xt,1 , Yt,1 ), . . . , (Xt,nM , Yt,nM ) i.i.d from Pt ,Rt (f ) = E(X ,Y )∼Pt [`(Y , f (X ))],
quantitative criterion to minimize w.r.t I

RLTL (I) = EP∼P min E(X ,Y )∼P [`(Y , f (I, X ))] .
f ∈C

Pierre Alquier

Lifelong Learning

Transfer learning, multitask learning, lifelong learning...
A strategy for lifelong learning, with regret analysis
Open questions

Probabilistic setting for LTL
Possible probabilistic setting :P1 , . . . , PM i.i.d from P,(Xt,1 , Yt,1 ), . . . , (Xt,nM , Yt,nM ) i.i.d from Pt ,Rt (f ) = E(X ,Y )∼Pt [`(Y , f (X ))],
quantitative criterion to minimize w.r.t I

RLTL (I) = EP∼P min E(X ,Y )∼P [`(Y , f (I, X ))] .
f ∈C

Note the strong Bayesian flavor...

Pierre Alquier

Lifelong Learning

Transfer learning, multitask learning, lifelong learning...
A strategy for lifelong learning, with regret analysis
Open questions

Example of LTL : dictionary learning
Example taken from :Pierre Alquier

Lifelong Learning

Transfer learning, multitask learning, lifelong learning...
A strategy for lifelong learning, with regret analysis
Open questions

Example of LTL : dictionary learning
Example : dictionary learning. The Xt,i ∈ RK , but all the
relevant information is in DXt,i ∈ Rk , k  K . The matrix D is
unknown.

Pierre Alquier

Lifelong Learning

Transfer learning, multitask learning, lifelong learning...
A strategy for lifelong learning, with regret analysis
Open questions

Example of LTL : dictionary learning
Example : dictionary learning. The Xt,i ∈ RK , but all the
relevant information is in DXt,i ∈ Rk , k  K . The matrix D is
unknown.
β1 , . . . , βM i.i.d from P,

Pierre Alquier

Lifelong Learning

Transfer learning, multitask learning, lifelong learning...
A strategy for lifelong learning, with regret analysis
Open questions

Example of LTL : dictionary learning
Example : dictionary learning. The Xt,i ∈ RK , but all the
relevant information is in DXt,i ∈ Rk , k  K . The matrix D is
unknown.
β1 , . . . , βM i.i.d from P,(Xt,1 , Yt,1 ), . . . , (Xt,n , Yt,n ) i.i.d from Pβt :Y = βtT DX + ε,

Pierre Alquier

Lifelong Learning

Transfer learning, multitask learning, lifelong learning...
A strategy for lifelong learning, with regret analysis
Open questions

Example of LTL : dictionary learning
Example : dictionary learning. The Xt,i ∈ RK , but all the
relevant information is in DXt,i ∈ Rk , k  K . The matrix D is
unknown.
β1 , . . . , βM i.i.d from P,(Xt,1 , Yt,1 ), . . . , (Xt,n , Yt,n ) i.i.d from Pβt :Y = βtT DX + ε,Rt (β, ∆) = E(X ,Y )∼Pβt [`(Y , β T ∆X )],Pierre Alquier

Lifelong Learning

Transfer learning, multitask learning, lifelong learning...
A strategy for lifelong learning, with regret analysis
Open questions

Example of LTL : dictionary learning
Example : dictionary learning. The Xt,i ∈ RK , but all the
relevant information is in DXt,i ∈ Rk , k  K . The matrix D is
unknown.
β1 , . . . , βM i.i.d from P,(Xt,1 , Yt,1 ), . . . , (Xt,n , Yt,n ) i.i.d from Pβt :Y = βtT DX + ε,Rt (β, ∆) = E(X ,Y )∼Pβt [`(Y , β T ∆X )],quantitative criterion to minimize w.r.t M
RLTL (∆) = Eβ∼P E(X ,Y )∼Pβ `(Y , β T ∆X ) .
Pierre Alquier

Lifelong Learning

Transfer learning, multitask learning, lifelong learning...
A strategy for lifelong learning, with regret analysis
Open questions

Example of LTL : dictionary learning
Maurer, Pontil and Romera-Paredes propose :D̂ = arg min∆

MX

arg minnX

t=1 kβt k1 ≤α i=1`(Yt,i , βtT ∆Xt,i )Theorem (Maurer et al)
Under suitable assumptions, with probability at least 1 − δ,
 r
s
r 

1
log
1
1
δ
.
RLTL (D̂) ≤ inf RLTL (∆)+C αk
+
+α
∆
M
M
n
Note that C can depend on (k, K ) or not, depending on
assumptions on the distribution of X under Pβ ...
Pierre Alquier

Lifelong Learning

Transfer learning, multitask learning, lifelong learning...
A strategy for lifelong learning, with regret analysis
Open questions

Going online : lifelong learning
Lifelong learning (LL)
Online version of learning-to-learn ?
Recent work with The Tien Mai and Massimiliano Pontil.
Objectives :Pierre Alquier

Lifelong Learning

Transfer learning, multitask learning, lifelong learning...
A strategy for lifelong learning, with regret analysis
Open questions

Going online : lifelong learning
Lifelong learning (LL)
Online version of learning-to-learn ?
Recent work with The Tien Mai and Massimiliano Pontil.
Objectives :consider that tasks can be revealed sequentially. Use thetools of online learning theory : avoid probabilistic
assumptions.

Pierre Alquier

Lifelong Learning

Transfer learning, multitask learning, lifelong learning...
A strategy for lifelong learning, with regret analysis
Open questions

Going online : lifelong learning
Lifelong learning (LL)
Online version of learning-to-learn ?
Recent work with The Tien Mai and Massimiliano Pontil.
Objectives :consider that tasks can be revealed sequentially. Use thetools of online learning theory : avoid probabilistic
assumptions.
if possible, define a general strategy that does not dependon the learning algorithm used within each task.

Pierre Alquier

Lifelong Learning

Transfer learning, multitask learning, lifelong learning...
A strategy for lifelong learning, with regret analysis
Open questions

1

Transfer learning, multitask learning, lifelong learning...

2

A strategy for lifelong learning, with regret analysis

3Open questions

Pierre Alquier

Lifelong Learning

Transfer learning, multitask learning, lifelong learning...
A strategy for lifelong learning, with regret analysis
Open questions

Massimiliano Pontil(UCL, IIT)

Pierre Alquier

The Tien Mai(U. of Oslo)

Lifelong Learning

Transfer learning, multitask learning, lifelong learning...
A strategy for lifelong learning, with regret analysis
Open questions

Setting
objects in X , labels in Y,

Pierre Alquier

Lifelong Learning

Transfer learning, multitask learning, lifelong learning...
A strategy for lifelong learning, with regret analysis
Open questions

Setting
objects in X , labels in Y,
set of functions G : X → Z and H : Z → Y,

Pierre Alquier

Lifelong Learning

Transfer learning, multitask learning, lifelong learning...
A strategy for lifelong learning, with regret analysis
Open questions

Setting
objects in X , labels in Y,
set of functions G : X → Z and H : Z → Y,
loss function `.
Lifelong-learning problem (LL)
Propose initial g .

Pierre Alquier

Lifelong Learning

Transfer learning, multitask learning, lifelong learning...
A strategy for lifelong learning, with regret analysis
Open questions

Setting
objects in X , labels in Y,
set of functions G : X → Z and H : Z → Y,
loss function `.
Lifelong-learning problem (LL)
Propose initial g .
For t = 1, 2, . . . ,Pierre Alquier

Lifelong Learning

Transfer learning, multitask learning, lifelong learning...
A strategy for lifelong learning, with regret analysis
Open questions

Setting
objects in X , labels in Y,
set of functions G : X → Z and H : Z → Y,
loss function `.
Lifelong-learning problem (LL)
Propose initial g .
For t = 1, 2, . . . ,1
propose initial ht .
For i = 1, . . . , nt

Pierre Alquier

Lifelong Learning

Transfer learning, multitask learning, lifelong learning...
A strategy for lifelong learning, with regret analysis
Open questions

Setting
objects in X , labels in Y,
set of functions G : X → Z and H : Z → Y,
loss function `.
Lifelong-learning problem (LL)
Propose initial g .
For t = 1, 2, . . . ,1
propose initial ht .
For i = 1, . . . , nt
1xt,i revealed,

Pierre Alquier

Lifelong Learning

Transfer learning, multitask learning, lifelong learning...
A strategy for lifelong learning, with regret analysis
Open questions

Setting
objects in X , labels in Y,
set of functions G : X → Z and H : Z → Y,
loss function `.
Lifelong-learning problem (LL)
Propose initial g .
For t = 1, 2, . . . ,1
propose initial ht .
For i = 1, . . . , nt
12xt,i revealed,predict ŷt,i = ht ◦ g (xt,i ),Pierre Alquier

Lifelong Learning

Transfer learning, multitask learning, lifelong learning...
A strategy for lifelong learning, with regret analysis
Open questions

Setting
objects in X , labels in Y,
set of functions G : X → Z and H : Z → Y,
loss function `.
Lifelong-learning problem (LL)
Propose initial g .
For t = 1, 2, . . . ,1
propose initial ht .
For i = 1, . . . , nt
12
3xt,i revealed,predict ŷt,i = ht ◦ g (xt,i ),yt,i revealed, suffer loss `ˆt,i := `(yt,i , ŷt,i ),Pierre Alquier

Lifelong Learning

Transfer learning, multitask learning, lifelong learning...
A strategy for lifelong learning, with regret analysis
Open questions

Setting
objects in X , labels in Y,
set of functions G : X → Z and H : Z → Y,
loss function `.
Lifelong-learning problem (LL)
Propose initial g .
For t = 1, 2, . . . ,1
propose initial ht .
For i = 1, . . . , nt
12
3
4xt,i revealed,predict ŷt,i = ht ◦ g (xt,i ),yt,i revealed, suffer loss `ˆt,i := `(yt,i , ŷt,i ),update ht .
Pierre Alquier

Lifelong Learning

Transfer learning, multitask learning, lifelong learning...
A strategy for lifelong learning, with regret analysis
Open questions

Setting
objects in X , labels in Y,
set of functions G : X → Z and H : Z → Y,
loss function `.
Lifelong-learning problem (LL)
Propose initial g .
For t = 1, 2, . . . ,1
propose initial ht .
For i = 1, . . . , nt
1
2
3
4
2

xt,i revealed,predict ŷt,i = ht ◦ g (xt,i ),yt,i revealed, suffer loss `ˆt,i := `(yt,i , ŷt,i ),update ht .

udpate g .
Pierre Alquier

Lifelong Learning

Transfer learning, multitask learning, lifelong learning...
A strategy for lifelong learning, with regret analysis
Open questions

Within-task algorithm
For t = 1, 2, . . . ,1
Solve a usual online task, input zt,i = g (xt,i ), output yt,i .
2udpate g .

Pierre Alquier

Lifelong Learning

Transfer learning, multitask learning, lifelong learning...
A strategy for lifelong learning, with regret analysis
Open questions

Within-task algorithm
For t = 1, 2, . . . ,1
Solve a usual online task, input zt,i = g (xt,i ), output yt,i .
2udpate g .
We can do it using any online algorithm. Will be refered to as“within-task algorithm”.
For many algorithms, bounds are known on the(normalized)-regret :
nt
nt
X
1 X
1
Rt (g ) =`(yt,i , ŷt,i ) − inf`(yt,i , h(zt,i )).
nt i=1nt h∈H i=1
|
{z
}
= n1

t

Pnt

ˆ

i=1 `t,i =L̂t (g )Pierre Alquier

Lifelong Learning

Transfer learning, multitask learning, lifelong learning...
A strategy for lifelong learning, with regret analysis
Open questions

Examples of within-task algorithms
Online gradient for convex `Initialize h = 0.
Update h ← h − η∇f =h `(yt,i , f (zt,i )).

Pierre Alquier

Lifelong Learning

Transfer learning, multitask learning, lifelong learning...
A strategy for lifelong learning, with regret analysis
Open questions

Examples of within-task algorithms
Online gradient for convex `Initialize h = 0.
Update h ← h − η∇f =h `(yt,i , f (zt,i )).
Many variants and improvements (projected gradient, online
Newton-step, ...).
√Rt (g ) in 1/ nt or 1/nt depending on assumptions on `.

Pierre Alquier

Lifelong Learning

Transfer learning, multitask learning, lifelong learning...
A strategy for lifelong learning, with regret analysis
Open questions

Examples of within-task algorithms
Online gradient for convex `Initialize h = 0.
Update h ← h − η∇f =h `(yt,i , f (zt,i )).
Many variants and improvements (projected gradient, online
Newton-step, ...).
√Rt (g ) in 1/ nt or 1/nt depending on assumptions on `.
EWA (Exponentially Weighted Aggregation)
Prior ρ1 = π, initialize h ∼ ρ1 .
Update ρi+1 (df ) ∝ exp[−η`(yt,i , f (zt,i ))]ρi (df ), h ∼ ρi+1 .

Pierre Alquier

Lifelong Learning

Transfer learning, multitask learning, lifelong learning...
A strategy for lifelong learning, with regret analysis
Open questions

Examples of within-task algorithms
Online gradient for convex `Initialize h = 0.
Update h ← h − η∇f =h `(yt,i , f (zt,i )).
Many variants and improvements (projected gradient, online
Newton-step, ...).
√Rt (g ) in 1/ nt or 1/nt depending on assumptions on `.
EWA (Exponentially Weighted Aggregation)
Prior ρ1 = π, initialize h ∼ ρ1 .
Update ρi+1 (df ) ∝ exp[−η`(yt,i , f (zt,i ))]ρi (df ), h ∼ ρi+1 .
√E[Rt (g )] in 1/ nt under boundedness assumption.
Integrated variant : Rt (g ) in 1/nt if ` is exp-concave.
Pierre Alquier

Lifelong Learning

Transfer learning, multitask learning, lifelong learning...
A strategy for lifelong learning, with regret analysis
Open questions

EWA for lifelong learning
EWA-LL
Prior π = ρ1 on G. Draw g ∼ π.
For t = 1, 2, . . .
1
run the within-task algorithm on task t. Suffer L̂t (g ).
2update ρt+1 (df ) ∝ exp[−η L̂t (f )]ρt (df ).
3
draw g ∼ ρt+1 .

Pierre Alquier

Lifelong Learning

Transfer learning, multitask learning, lifelong learning...
A strategy for lifelong learning, with regret analysis
Open questions

EWA for lifelong learning
EWA-LL
Prior π = ρ1 on G. Draw g ∼ π.
For t = 1, 2, . . .
1
run the within-task algorithm on task t. Suffer L̂t (g ).
2update ρt+1 (df ) ∝ exp[−η L̂t (f )]ρt (df ).
3
draw g ∼ ρt+1 .

Next : we provide two examples that are corollaries of ageneral result (stated later).
Pierre Alquier

Lifelong Learning

Transfer learning, multitask learning, lifelong learning...
A strategy for lifelong learning, with regret analysis
Open questions

Example 1 : dictionary learning
X = RK → Z = Rk →
Y=R
x
7→
Dx
7→ hh, Dxi = hT Dx.

Pierre Alquier

Lifelong Learning

Transfer learning, multitask learning, lifelong learning...
A strategy for lifelong learning, with regret analysis
Open questions

Example 1 : dictionary learning
X = RK → Z = Rk →
Y=R
x
7→
Dx
7→ hh, Dxi = hT Dx.
within-task algorithm : online gradient descent on h.

Pierre Alquier

Lifelong Learning

Transfer learning, multitask learning, lifelong learning...
A strategy for lifelong learning, with regret analysis
Open questions

Example 1 : dictionary learning
X = RK → Z = Rk →
Y=R
x
7→
Dx
7→ hh, Dxi = hT Dx.
within-task algorithm : online gradient descent on h.
EWA-LL, prior : columns of D i.i.d uniform on unit sphere.

Pierre Alquier

Lifelong Learning

Transfer learning, multitask learning, lifelong learning...
A strategy for lifelong learning, with regret analysis
Open questions

Example 1 : dictionary learning
X = RK → Z = Rk →
Y=R
x
7→
Dx
7→ hh, Dxi = hT Dx.
within-task algorithm : online gradient descent on h.
EWA-LL, prior : columns of D i.i.d uniform on unit sphere.
Theorem (Corollary 4.4) - ` is bounded by B & L-Lipschitz
"

#
T
nt
T
nt
1 X 1 X
1 X
1 X
ˆE`t,i ≤ inf
inf`(yt,i , htT Dxt,i )D T
kht k≤C nt
T t=1 nt i=1
t=1
i=1
r
√
T
C Kk
BL
1 X BL 2k+(log(T ) + 7) + √ +
.
√
4
T
T t=1
nt
T
Pierre Alquier

Lifelong Learning

Transfer learning, multitask learning, lifelong learning...
A strategy for lifelong learning, with regret analysis
Open questions

Example 1 : dictionary learning
X = RK → Z = Rk →
Y=R
x
7→
Dx
7→ hh, Dxi = hT Dx.
within-task algorithm : online gradient descent on h.
EWA-LL, prior : columns of D i.i.d uniform on unit sphere.
Theorem (Corollary 4.4) - ` is bounded by B & L-Lipschitz
"

#
T
nt
T
nt
1 X 1 X
1 X
1 X
ˆE`t,i ≤ inf
inf`(yt,i , htT Dxt,i )D T
kht k≤C nt
T t=1 nt i=1
t=1
i=1
r
√
C Kk
BL
BL 2k
+
(log(T ) + 7) + √ + √ .
4Tn̄TPierre Alquier

Lifelong Learning

Transfer learning, multitask learning, lifelong learning...
A strategy for lifelong learning, with regret analysis
Open questions

Example 1 (dictionary learning) : simulations
simulations X = R5 → Z = R2 → Y = R with ` thequadratic loss, T = 150, each nt = 100.

Pierre Alquier

Lifelong Learning

Transfer learning, multitask learning, lifelong learning...
A strategy for lifelong learning, with regret analysis
Open questions

Example 1 (dictionary learning) : simulations
simulations X = R5 → Z = R2 → Y = R with ` thequadratic loss, T = 150, each nt = 100.
implementation of EWA-LL, at each step, D is updated
using N iterations of Metropolis-Hastings.

Pierre Alquier

Lifelong Learning

Transfer learning, multitask learning, lifelong learning...
A strategy for lifelong learning, with regret analysis
Open questions

Example 1 (dictionary learning) : simulations
simulations X = R5 → Z = R2 → Y = R with ` thequadratic loss, T = 150, each nt = 100.
implementation of EWA-LL, at each step, D is updated
using N iterations of Metropolis-Hastings.

Pierre Alquier

Lifelong Learning

Transfer learning, multitask learning, lifelong learning...
A strategy for lifelong learning, with regret analysis
Open questions

Example 2 : finite set of predictors
g ∈G

h∈H

x 7→ g (x) 7→ h(g (x)).
card(G) = G < +∞, card(H) = H < +∞Pierre Alquier

Lifelong Learning

Transfer learning, multitask learning, lifelong learning...
A strategy for lifelong learning, with regret analysis
Open questions

Example 2 : finite set of predictors
g ∈G

h∈H

x 7→ g (x) 7→ h(g (x)).
card(G) = G < +∞, card(H) = H < +∞within-task algorithm : EWA, uniform prior.

Pierre Alquier

Lifelong Learning

Transfer learning, multitask learning, lifelong learning...
A strategy for lifelong learning, with regret analysis
Open questions

Example 2 : finite set of predictors
g ∈G

h∈H

x 7→ g (x) 7→ h(g (x)).
card(G) = G < +∞, card(H) = H < +∞within-task algorithm : EWA, uniform prior.
EWA-LL, uniform prior.

Pierre Alquier

Lifelong Learning

Transfer learning, multitask learning, lifelong learning...
A strategy for lifelong learning, with regret analysis
Open questions

Example 2 : finite set of predictors
g ∈G

h∈H

x 7→ g (x) 7→ h(g (x)).
card(G) = G < +∞, card(H) = H < +∞within-task algorithm : EWA, uniform prior.
EWA-LL, uniform prior.
Theorem (Corollary 4.2) - ` bounded by C & α-exp-concave
"

#
T
m
T
m
1 X 1 Xˆ1 X
1 X
E`t,i ≤ inf
inf`(yt,i , ht ◦g (xt,i ))g ∈G Tht ∈H m
T t=1 m i=1
t=1
i=1
r
log G
α log H
+C
+
.
2T
n̄
Pierre Alquier

Lifelong Learning

Transfer learning, multitask learning, lifelong learning...
A strategy for lifelong learning, with regret analysis
Open questions

Example 2 : improvement on existing results
The “online-to-batch” trick allows to deduce from our online
method a statistical estimator with a controled LTL risk in
!
r
log G
log H
O
+
.
T
n

Pierre Alquier

Lifelong Learning

Transfer learning, multitask learning, lifelong learning...
A strategy for lifelong learning, with regret analysis
Open questions

Example 2 : improvement on existing results
The “online-to-batch” trick allows to deduce from our online
method a statistical estimator with a controled LTL risk in
!
r
log G
log H
O
+
.
T
n
In this case, a previous bound by Pentina and Lampert was in
!
r
r
log G
log H
O
+
.
T
n

Pierre Alquier

Lifelong Learning

Transfer learning, multitask learning, lifelong learning...
A strategy for lifelong learning, with regret analysis
Open questions

General regret boundTheorem (Theorem 3.1) - ` bounded by C
If for any g ∈ G, the within-task algorithm has a regret boundRt (g ) ≤ β(g , nt ), then
"

#
T
nt
1 X 1 XE
`ˆt,i
T t=1 nt i=1
(Z "
T
nt

1 X
1 X
` yt,i , ht ◦ g (xt,i )
inf
≤ inf
ρ
T t=1 ht ∈H nt i=1
#
)
T
1 X
ηC 2 K(ρ, π)+β(g , nt ) ρ(dg ) +
+
.
T t=1
8
ηT
Pierre Alquier

Lifelong Learning

Transfer learning, multitask learning, lifelong learning...
A strategy for lifelong learning, with regret analysis
Open questions

1

Transfer learning, multitask learning, lifelong learning...

2

A strategy for lifelong learning, with regret analysis

3Open questions

Pierre Alquier

Lifelong Learning

Transfer learning, multitask learning, lifelong learning...
A strategy for lifelong learning, with regret analysis
Open questions

Efficient algorithms ?
Our online analysis allows to avoid explicit probabilistic
assumptions on the data, and allows a free choice of thewithin-task algorithm.

Pierre Alquier

Lifelong Learning

Transfer learning, multitask learning, lifelong learning...
A strategy for lifelong learning, with regret analysis
Open questions

Efficient algorithms ?
Our online analysis allows to avoid explicit probabilistic
assumptions on the data, and allows a free choice of thewithin-task algorithm.

However, EWA-LL is not “truly online” as its computation
requires to store all the data seen so far.

Pierre Alquier

Lifelong Learning

Transfer learning, multitask learning, lifelong learning...
A strategy for lifelong learning, with regret analysis
Open questions

Efficient algorithms ?
Our online analysis allows to avoid explicit probabilistic
assumptions on the data, and allows a free choice of thewithin-task algorithm.

However, EWA-LL is not “truly online” as its computation
requires to store all the data seen so far.

Moreover, its computation is not scalable.

Pierre Alquier

Lifelong Learning

Transfer learning, multitask learning, lifelong learning...
A strategy for lifelong learning, with regret analysis
Open questions

Efficient Lifelong Learning Algorithm : ELLA

dictionary learning,

Pierre Alquier

Lifelong Learning

Transfer learning, multitask learning, lifelong learning...
A strategy for lifelong learning, with regret analysis
Open questions

Efficient Lifelong Learning Algorithm : ELLA

dictionary learning,
fast update of D and β
at each step, truly
online : no need tostore the data,

Pierre Alquier

Lifelong Learning

Transfer learning, multitask learning, lifelong learning...
A strategy for lifelong learning, with regret analysis
Open questions

Efficient Lifelong Learning Algorithm : ELLA

dictionary learning,
fast update of D and β
at each step, truly
online : no need tostore the data,
very good empiricalperformances,

Pierre Alquier

Lifelong Learning

Transfer learning, multitask learning, lifelong learning...
A strategy for lifelong learning, with regret analysis
Open questions

Efficient Lifelong Learning Algorithm : ELLA

dictionary learning,
fast update of D and β
at each step, truly
online : no need tostore the data,
very good empiricalperformances,
no regret bound.

Pierre Alquier

Lifelong Learning

Transfer learning, multitask learning, lifelong learning...
A strategy for lifelong learning, with regret analysis
Open questions

More progress on dictionary learning
dictionary learning,

Pierre Alquier

Lifelong Learning

Transfer learning, multitask learning, lifelong learning...
A strategy for lifelong learning, with regret analysis
Open questions

More progress on dictionary learning
dictionary learning,
fast update of β ateach step, fast updateof D at the end ofeach task, truly online,

Pierre Alquier

Lifelong Learning

Transfer learning, multitask learning, lifelong learning...
A strategy for lifelong learning, with regret analysis
Open questions

More progress on dictionary learning
dictionary learning,
fast update of β ateach step, fast updateof D at the end ofeach task, truly online,
very good empiricalperformances,

Pierre Alquier

Lifelong Learning

Transfer learning, multitask learning, lifelong learning...
A strategy for lifelong learning, with regret analysis
Open questions

More progress on dictionary learning
dictionary learning,
fast update of β ateach step, fast updateof D at the end ofeach task, truly online,
very good empiricalperformances,
LTL bound in
r
r !
1
1
O
+
.
T
n
Pierre Alquier

Lifelong Learning

Transfer learning, multitask learning, lifelong learning...
A strategy for lifelong learning, with regret analysis
Open questions

Algorithms : open questions

Open question 1
An efficient algorithm with theoretical guarantees (if possible
beyond dictionary learning).

Pierre Alquier

Lifelong Learning

Transfer learning, multitask learning, lifelong learning...
A strategy for lifelong learning, with regret analysis
Open questions

Algorithms : open questions

Open question 1
An efficient algorithm with theoretical guarantees (if possible
beyond dictionary learning).
theoretical analysis of ELLA ?

Pierre Alquier

Lifelong Learning

Transfer learning, multitask learning, lifelong learning...
A strategy for lifelong learning, with regret analysis
Open questions

Algorithms : open questions

Open question 1
An efficient algorithm with theoretical guarantees (if possible
beyond dictionary learning).
theoretical analysis of ELLA ?
can we justify to update D at each step ? this leads to thenext big open problem...

Pierre Alquier

Lifelong Learning

Transfer learning, multitask learning, lifelong learning...
A strategy for lifelong learning, with regret analysis
Open questions

Optimality of the bounds
ELLA : updates D at each step. Doing so, after T tasks
with n steps in each task, we would expect a bound in
r !
r
1
1
O
+
.
nT
n

Pierre Alquier

Lifelong Learning

Transfer learning, multitask learning, lifelong learning...
A strategy for lifelong learning, with regret analysis
Open questions

Optimality of the bounds
ELLA : updates D at each step. Doing so, after T tasks
with n steps in each task, we would expect a bound in
r !
r
1
1
O
+
.
nT
n
Denevi et al : bound inr
O

Pierre Alquier

1
+
T

r !
1
.
n

Lifelong Learning

Transfer learning, multitask learning, lifelong learning...
A strategy for lifelong learning, with regret analysis
Open questions

Optimality of the bounds
ELLA : updates D at each step. Doing so, after T tasks
with n steps in each task, we would expect a bound in
r !
r
1
1
O
+
.
nT
n
Denevi et al : bound in
r
O

1
+
T

r !
1
.
n

So, what are the optimal rates in LL & LTL ?
Pierre Alquier

Lifelong Learning

Transfer learning, multitask learning, lifelong learning...
A strategy for lifelong learning, with regret analysis
Open questions

Insights from a toy modelθ1 fixed once and for all,task t : θ2,t fixed for the task
for i = 1, . . . , n, yt,i = (θ1 + ε1,i,t , θ2,t + ε2,i,t ) with
εj,i,t ∼ N (0, 1).

Pierre Alquier

Lifelong Learning

Transfer learning, multitask learning, lifelong learning...
A strategy for lifelong learning, with regret analysis
Open questions

Insights from a toy modelθ1 fixed once and for all,task t : θ2,t fixed for the task
for i = 1, . . . , n, yt,i = (θ1 + ε1,i,t , θ2,t + ε2,i,t ) with
εj,i,t ∼ N (0, 1).
PT Pn
1θ̂1 = nTt=1
i=1 (yt,i )1 can be computed in the online
setting and one has
!
r


1
E |θ̂1 − θ1 | = O.
nTPierre Alquier

Lifelong Learning

Transfer learning, multitask learning, lifelong learning...
A strategy for lifelong learning, with regret analysis
Open questions

Insights from a toy modelθ1 fixed once and for all,task t : θ2,t fixed for the task
for i = 1, . . . , n, yt,i = (θ1 + ε1,i,t , θ2,t + ε2,i,t ) with
εj,i,t ∼ N (0, 1).
PT Pn
1θ̂1 = nTt=1
i=1 (yt,i )1 can be computed in the online
setting and one has
!
r


1
E |θ̂1 − θ1 | = O.
nT
Fits our setting with x = ∅, gθ1 (x) = θ1 , hθ2 (z) = (z, θ2 ).
Pierre Alquier

Lifelong Learning

Transfer learning, multitask learning, lifelong learning...
A strategy for lifelong learning, with regret analysis
Open questions

Insights from a toy modelθ1 fixed once and for all,task t : θ2,t and ε1,t ∼ N (0, 1) fixed for the task.
for i = 1, . . . , n, yt,i = (θ1 + ε1,t , θ2,t + ε2,i,t ) with
ε2,i,t ∼ N (0, 1).
Pθ̂1 = T1 Tt=1 (yt,i )1 can be computed in the online setting andone hasr !
1E |θ̂1 − θ1 | = O.
TStill fits our setting and LTL !

Pierre Alquier

Lifelong Learning

Transfer learning, multitask learning, lifelong learning...
A strategy for lifelong learning, with regret analysis
Open questions

Optimal rates : open questions

Open question 2
What are the optimal rates in lifelong learning and in LTL ?

Pierre Alquier

Lifelong Learning

Transfer learning, multitask learning, lifelong learning...
A strategy for lifelong learning, with regret analysis
Open questions

Optimal rates : open questions

Open question 2
What are the optimal rates in lifelong learning and in LTL ?
requires to define properly class of predictors,

Pierre Alquier

Lifelong Learning

Transfer learning, multitask learning, lifelong learning...
A strategy for lifelong learning, with regret analysis
Open questions

Optimal rates : open questions

Open question 2
What are the optimal rates in lifelong learning and in LTL ?
requires to define properly class of predictors,
the optimal rate will also depend on the setting. This
leads to the next question...

Pierre Alquier

Lifelong Learning

Transfer learning, multitask learning, lifelong learning...
A strategy for lifelong learning, with regret analysis
Open questions

Are our definitions even right ?

Note that the terminology is not exen fixed : for example,
Pentina and Lampert call lifelong learning what we calllearning to learn (we don’t claim we are right !).

Pierre Alquier

Lifelong Learning

Transfer learning, multitask learning, lifelong learning...
A strategy for lifelong learning, with regret analysis
Open questions

Are our definitions even right ?

Note that the terminology is not exen fixed : for example,
Pentina and Lampert call lifelong learning what we calllearning to learn (we don’t claim we are right !).
We used :1
2

3

LTL : samples from all the tasks presented at once.
LL : tasks presented sequentially, within each task, pairspresented sequentially.
why not tasks presented sequentially, but within eachtask, samples presented all at once ? .

Pierre Alquier

Lifelong Learning

Transfer learning, multitask learning, lifelong learning...
A strategy for lifelong learning, with regret analysis
Open questions

Are our definitions even right ?

Note that the terminology is not exen fixed : for example,
Pentina and Lampert call lifelong learning what we calllearning to learn (we don’t claim we are right !).
We used :1
2
3

LTL : “Batch-within-batch”
LL : “Online-within-online”“Batch-within-online”, see our paper and Denivi et al.

Pierre Alquier

Lifelong Learning

Transfer learning, multitask learning, lifelong learning...
A strategy for lifelong learning, with regret analysis
Open questions

Towards more models ?
One can imagine even more settings :observations not ordered by tasks ?

Pierre Alquier

Lifelong Learning

Transfer learning, multitask learning, lifelong learning...
A strategy for lifelong learning, with regret analysis
Open questions

Towards more models ?
One can imagine even more settings :observations not ordered by tasks ?
for some tasks, the information is complete, for othertasks, this is not the case. For example some tasks aresequential predictions, others are bandit problems.

Pierre Alquier

Lifelong Learning

Transfer learning, multitask learning, lifelong learning...
A strategy for lifelong learning, with regret analysis
Open questions

Towards more models ?
One can imagine even more settings :observations not ordered by tasks ?
for some tasks, the information is complete, for othertasks, this is not the case. For example some tasks aresequential predictions, others are bandit problems.
more complicated : we use within tasks an algorithm forwhich we don’t have a regret bound, for example deepneural network for image classification in self-driving cars.
We have a partial feedback that is not the
missclassification rate but depends on it : number ofaccidents, user feedback...

Pierre Alquier

Lifelong Learning

Transfer learning, multitask learning, lifelong learning...
A strategy for lifelong learning, with regret analysis
Open questions

Towards more models ?
One can imagine even more settings :observations not ordered by tasks ?
for some tasks, the information is complete, for othertasks, this is not the case. For example some tasks aresequential predictions, others are bandit problems.
more complicated : we use within tasks an algorithm forwhich we don’t have a regret bound, for example deepneural network for image classification in self-driving cars.
We have a partial feedback that is not the
missclassification rate but depends on it : number ofaccidents, user feedback...
Do we really need a paper for each possible variant ?...
Pierre Alquier

Lifelong Learning

Transfer learning, multitask learning, lifelong learning...
A strategy for lifelong learning, with regret analysis
Open questions

Setting : open questions

Open question 3
Which settings are relevant ? Which settings are not ? To what
extent is a general theory possible ?

Pierre Alquier

Lifelong Learning

Transfer learning, multitask learning, lifelong learning...
A strategy for lifelong learning, with regret analysis
Open questions

Setting : open questions

Open question 3
Which settings are relevant ? Which settings are not ? To what
extent is a general theory possible ?
depends on the applications.

Pierre Alquier

Lifelong Learning

Transfer learning, multitask learning, lifelong learning...
A strategy for lifelong learning, with regret analysis
Open questions

Setting : open questions

Open question 3
Which settings are relevant ? Which settings are not ? To what
extent is a general theory possible ?
depends on the applications.
should also have a look on other existing approaches(econometrics of panel data ↔ multitask learning).

Pierre Alquier

Lifelong Learning