Meta-Strategy for Learning Tuning
Parameters with Guarantees
Pierre Alquier – ABI team

AIP open seminar – 2021年3月10日

Pierre Alquier, RIKEN AIP

Meta-Strategy for Learning Tuning Parameters

Joint work with Dimitri Meunier
Talk based on a joint workwith :Dimitri Meunier2020 : ENSAE Paris and ABI team2021 : IIT Genoa

D. Meunier, P. Alquier (2021). Meta-Strategy for Learning Tuning Parameters with Guarantees.
Preprint arXiv :2102.02504. Submitted.

Thank you to rc3 for the drawings in this talk.

Pierre Alquier, RIKEN AIP

Meta-Strategy for Learning Tuning Parameters

Solving a task with an algorithm

0.269
0.852
0.339
0.798

0.444
0.633
0.804
0.592

0.341
0.211
0.333
0.242

…
…
…
…

...
...
...
OUTPUT

Pierre Alquier, RIKEN AIP

Meta-Strategy for Learning Tuning Parameters

Solving a task with an algorithm

0.269
0.852
0.339
0.798

0.444
0.633
0.804
0.592

0.341
0.211
0.333
0.242

…
…
…
…

Examples :

...
...
...
OUTPUT

Pierre Alquier, RIKEN AIP

Meta-Strategy for Learning Tuning Parameters

Solving a task with an algorithm

0.269
0.852
0.339
0.798

0.444
0.633
0.804
0.592

0.341
0.211
0.333
0.242

Examples :

…
…
…
…

LASSO

...
...
...

min ky−Xθk2 +γkθk1 .
θ

OUTPUT

Pierre Alquier, RIKEN AIP

Meta-Strategy for Learning Tuning Parameters

Solving a task with an algorithm

0.269
0.852
0.339
0.798

0.444
0.633
0.804
0.592

0.341
0.211
0.333
0.242

Examples :

…
…
…
…

LASSO

...
...
...

min ky−Xθk2 +γkθk1 .
θ

RIDGE

OUTPUT

Pierre Alquier, RIKEN AIP

min ky−Xθk2 +αkθk22 .
θMeta-Strategy for Learning Tuning ParametersSolving tasks sequentially to learn tuning parameters

0.403
0.301
0.051
0.882

0.420
0.191
0.807
0.306

0.147
0.949
0.187
0.632

…
…
…
…

0.539
0.090
0.919
0.301

0.738
0.245
0.017
0.796

0.466
0.438
0.719
0.602

…
…
…
…

0.747
0.225
0.512
0.871

0.708
0.186
0.653
0.100

0.646
0.037
0.197
0.178

…
…
…
…

...
...
...

...
...
...

...
...
...

OUTPUTOUTPUTOUTPUT

Pierre Alquier, RIKEN AIP

Meta-Strategy for Learning Tuning Parameters

A meta-strategy

Assume that we have an upper bound on the generalization
error of a strategy when used with hyperparameter λ on taskt:L(datat , λ) = Lt (λ).

Pierre Alquier, RIKEN AIP

Meta-Strategy for Learning Tuning Parameters

A meta-strategy

Assume that we have an upper bound on the generalization
error of a strategy when used with hyperparameter λ on taskt:L(datat , λ) = Lt (λ).
Idea : use online optimization algorithm to minimize the Lt ’s...

Pierre Alquier, RIKEN AIP

Meta-Strategy for Learning Tuning Parameters

A meta-strategy

Assume that we have an upper bound on the generalization
error of a strategy when used with hyperparameter λ on taskt:L(datat , λ) = Lt (λ).
Idea : use online optimization algorithm to minimize the Lt ’s...
Online Proximal Meta-Strategy (OPMS)kλ − λt k2
λt+1 = argmin Lt (λ) +.
2αλPierre Alquier, RIKEN AIP

Meta-Strategy for Learning Tuning Parameters

Example : tasks are online prediction
Sequential regression tasks t = 1, 2, . . . , T

Pierre Alquier, RIKEN AIP

Meta-Strategy for Learning Tuning Parameters

Example : tasks are online prediction
Sequential regression tasks t = 1, 2, . . . , T
1xt,1 given

Pierre Alquier, RIKEN AIP

Meta-Strategy for Learning Tuning Parameters

Example : tasks are online prediction
Sequential regression tasks t = 1, 2, . . . , T
1xt,1 given
predict yt,1 : fθt,1 (xt,1 )Pierre Alquier, RIKEN AIP

Meta-Strategy for Learning Tuning Parameters

Example : tasks are online prediction
Sequential regression tasks t = 1, 2, . . . , T
1xt,1 given
predict yt,1 : fθt,1 (xt,1 )
yt,1 is revealed

Pierre Alquier, RIKEN AIP

Meta-Strategy for Learning Tuning Parameters

Example : tasks are online prediction
Sequential regression tasks t = 1, 2, . . . , T1

xt,1 given
predict yt,1 : fθt,1 (xt,1 )
yt,1 is revealed
update θt,1 → θt,2

Pierre Alquier, RIKEN AIP

Meta-Strategy for Learning Tuning Parameters

Example : tasks are online prediction
Sequential regression tasks t = 1, 2, . . . , T1

xt,1 given
predict yt,1 : fθt,1 (xt,1 )
yt,1 is revealed
update θt,1 → θt,22xt,2 given

Pierre Alquier, RIKEN AIP

Meta-Strategy for Learning Tuning Parameters

Example : tasks are online prediction
Sequential regression tasks t = 1, 2, . . . , T
1xt,1 given
predict yt,1 : fθt,1 (xt,1 )
yt,1 is revealed
update θt,1 → θt,22xt,2 given
predict yt,2 : fθt,2 (xt,2 )Pierre Alquier, RIKEN AIP

Meta-Strategy for Learning Tuning Parameters

Example : tasks are online prediction
Sequential regression tasks t = 1, 2, . . . , T
1xt,1 given
predict yt,1 : fθt,1 (xt,1 )
yt,1 is revealed
update θt,1 → θt,2

2xt,2 given
predict yt,2 : fθt,2 (xt,2 )
yt,2 revealed

Pierre Alquier, RIKEN AIP

Meta-Strategy for Learning Tuning Parameters

Example : tasks are online prediction
Sequential regression tasks t = 1, 2, . . . , T
1xt,1 given
predict yt,1 : fθt,1 (xt,1 )
yt,1 is revealed
update θt,1 → θt,2

2xt,2 given
predict yt,2 : fθt,2 (xt,2 )
yt,2 revealed
update θt,2 → θt,3

Pierre Alquier, RIKEN AIP

Meta-Strategy for Learning Tuning Parameters

Example : tasks are online prediction
Sequential regression tasks t = 1, 2, . . . , T
1xt,1 given
predict yt,1 : fθt,1 (xt,1 )
yt,1 is revealed
update θt,1 → θt,2

2xt,2 given
predict yt,2 : fθt,2 (xt,2 )
yt,2 revealed
update θt,2 → θt,3

3xt,3 given

Pierre Alquier, RIKEN AIP

Meta-Strategy for Learning Tuning Parameters

Example : tasks are online prediction
Sequential regression tasks t = 1, 2, . . . , T
1xt,1 given
predict yt,1 : fθt,1 (xt,1 )
yt,1 is revealed
update θt,1 → θt,22xt,2 given
predict yt,2 : fθt,2 (xt,2 )
yt,2 revealed
update θt,2 → θt,33xt,3 given
predict yt,3 : fθt,3 (xt,3 )Pierre Alquier, RIKEN AIP

Meta-Strategy for Learning Tuning Parameters

Example : tasks are online prediction
Sequential regression tasks t = 1, 2, . . . , T
1xt,1 given
predict yt,1 : fθt,1 (xt,1 )
yt,1 is revealed
update θt,1 → θt,22xt,2 given
predict yt,2 : fθt,2 (xt,2 )
yt,2 revealed
update θt,2 → θt,33xt,3 given
predict yt,3 : fθt,3 (xt,3 )
yt,3 revealed

Pierre Alquier, RIKEN AIP

Meta-Strategy for Learning Tuning Parameters

Example : tasks are online prediction
Sequential regression tasks t = 1, 2, . . . , T
1xt,1 given
predict yt,1 : fθt,1 (xt,1 )
yt,1 is revealed
update θt,1 → θt,2

2xt,2 given
predict yt,2 : fθt,2 (xt,2 )
yt,2 revealed
update θt,2 → θt,33xt,3 given
predict yt,3 : fθt,3 (xt,3 )
yt,3 revealed
update θt,3 → θt,4

4...
Pierre Alquier, RIKEN AIP

Meta-Strategy for Learning Tuning Parameters

Example : tasks are online prediction
Sequential regression tasks t = 1, 2, . . . , T
xt,1 given
predict yt,1 : fθt,1 (xt,1 )
yt,1 is revealed
update θt,1 → θt,2

12xt,2 given
predict yt,2 : fθt,2 (xt,2 )
yt,2 revealed
update θt,2 → θt,33xt,3 given
predict yt,3 : fθt,3 (xt,3 )
yt,3 revealed
update θt,3 → θt,44

Loss function `.

...
Pierre Alquier, RIKEN AIP

Meta-Strategy for Learning Tuning Parameters

Example : tasks are online prediction
Sequential regression tasks t = 1, 2, . . . , T
xt,1 given
predict yt,1 : fθt,1 (xt,1 )
yt,1 is revealed
update θt,1 → θt,2

12xt,2 given
predict yt,2 : fθt,2 (xt,2 )
yt,2 revealed
update θt,2 → θt,3

3xt,3 given
predict yt,3 : fθt,3 (xt,3 )
yt,3 revealed
update θt,3 → θt,44Loss function `.
For short,`t,i (θ) = `(yt,i , fθ (xt,i )).

...
Pierre Alquier, RIKEN AIP

Meta-Strategy for Learning Tuning Parameters

Example : tasks are online prediction
Sequential regression tasks t = 1, 2, . . . , T
xt,1 given
predict yt,1 : fθt,1 (xt,1 )
yt,1 is revealed
update θt,1 → θt,2

1xt,2 given
predict yt,2 : fθt,2 (xt,2 )
yt,2 revealed
update θt,2 → θt,32xt,3 given
predict yt,3 : fθt,3 (xt,3 )
yt,3 revealedupdate θt,3 → θt,434

Loss function `.
For short,`t,i (θ) = `(yt,i , fθ (xt,i )).
Objective :nX`t,i (θt,i )

i=1as small as possible.

...
Pierre Alquier, RIKEN AIP

Meta-Strategy for Learning Tuning Parameters

Example : online gradient algorithm (OGA)
θt,i+1 = θt,i − η∇`t,i (θt,i )Pierre Alquier, RIKEN AIP

Meta-Strategy for Learning Tuning Parameters

Example : online gradient algorithm (OGA)
θt,i+1 = θt,i − η∇`t,i (θt,i )Regret bound for OGA
If each `t,i is convex and L-Lipschitz,
( n)
nX
X
ηnL2 kθ − θ1,t k2`t,i (θ) +.
`t,i (θt,i ) ≤ inf+kθk≤B22η
i=1
i=1|{z}Lt (η,θt,1 )=Lt (λ)

Pierre Alquier, RIKEN AIP

Meta-Strategy for Learning Tuning Parameters

Example : online gradient algorithm (OGA)
θt,i+1 = θt,i − η∇`t,i (θt,i )Regret bound for OGA
If each `t,i is convex and L-Lipschitz,( n)nXX
ηnL2 kθ − θ1,t k2`t,i (θ) +.
`t,i (θt,i ) ≤ inf+kθk≤B22η
i=1i=1|{z}Lt (η,θt,1 )=Lt (λ)√Take η ∼ 1/ n to get :nX
i=1`t,i (θt,i ) ≤ infkθk≤B

Pierre Alquier, RIKEN AIPnX√`t,i (θ) + O( n).

i=1Meta-Strategy for Learning Tuning Parameters

Example : online gradient algorithm (OGA)
θt,i+1 = θt,i − η∇`t,i (θt,i )Regret bound for OGA
If each `t,i is convex and L-Lipschitz,
( n)
nX
X
ηnL2 kθ − θ1,t k2`t,i (θ) +.
`t,i (θt,i ) ≤ inf+kθk≤B22η
i=1i=1|{z}Lt (η,θt,1 )=Lt (λ)√Take η ∼ 1/ n to get :
nn
1X
1X
1
`t,i (θt,i ) ≤ inf`t,i (θ) + O √.
kθk≤B nn i=1n
i=1Pierre Alquier, RIKEN AIP

Meta-Strategy for Learning Tuning Parameters

Meta-learning for OGA
0.403
0.301
0.051
0.882

0.420
0.191
0.807
0.306

0.147
0.949
0.187
0.632

…
…
…
…

0.539
0.090
0.919
0.301

0.738
0.245
0.017
0.796

0.466
0.438
0.719
0.602

…
…
…
…

...
...
...

...
...
...

OUTPUTOUTPUT

Pierre Alquier, RIKEN AIP

0.747
0.225
0.512
0.871

...

0.708
0.186
0.653
0.100

0.646
0.037
0.197
0.178

…
…
…
…

...
...
...
OUTPUT

Meta-Strategy for Learning Tuning Parameters

Meta-learning for OGA
Online Proximal Meta-Strategy (OPMS)kλ − λt k2
λt+1 = argmin Lt (λ) +.
2αλPierre Alquier, RIKEN AIP

Meta-Strategy for Learning Tuning Parameters

Meta-learning for OGA
Online Proximal Meta-Strategy (OPMS)kλ − λt k2λt+1 = argmin Lt (λ) +.
2αλ(ηt+1 , θt+1,1 )= argmin minη,ϑkθk≤B( nX`t,i (θ) +i=1

ηnL2 kθ − ϑk2+22η)kϑ − θt,1 k2 + (η − ηt )2+.
2αPierre Alquier, RIKEN AIP

Meta-Strategy for Learning Tuning Parameters

The big question : what do we win ?

Question : what do we win ?

Pierre Alquier, RIKEN AIP

Meta-Strategy for Learning Tuning Parameters

Standard : learning in isolation
nn
1X
1X
1
`1,i (θ1,i ) ≤ inf`1,i (θ) + O √kθk≤B nn i=1ni=1+..
.
+nn
1X
1X
1
`T ,i (θT ,i ) ≤ inf`T ,i (θ) + O √kθk≤B nn i=1ni=1

Pierre Alquier, RIKEN AIP

Meta-Strategy for Learning Tuning Parameters

Standard : learning in isolation
nn
1X
1X
1
`1,i (θ1,i ) ≤ inf`1,i (θ) + O √kθk≤B nn i=1
ni=1+..
.
+

nn
1X
1X
1
`T ,i (θT ,i ) ≤ inf`T ,i (θ) + O √kθk≤B nn i=1ni=1

TnTn
1 XX
1 XX
1`t,i (θ1,i ) ≤ inf`t,i (θt )+O √.
kθ1 k ≤ B nT
nT t=1 i=1nt=1 i=1...
kθT k ≤ B
Pierre Alquier, RIKEN AIP

Meta-Strategy for Learning Tuning Parameters

Guarantees for our meta-strategy

TheoremTn

1 XX`t,i (θ1,i ) ≤ infkθ1 k ≤ B
nT t=1 i=1...

(Tn

1 XX
`t,i (θt )nT t=1 i=1kθT k ≤ B

q P)
2T1
θ−θ̄t
1nt=1T√+O+ +√  .
nn
T

Pierre Alquier, RIKEN AIP

Meta-Strategy for Learning Tuning Parameters

Simulated examples

Pierre Alquier, RIKEN AIP

Meta-Strategy for Learning Tuning Parameters

Simulated examples

r=5
6.44
0.27
0.15
r=30
13.60
7.93
3.72

Pierre Alquier, RIKEN AIP

Meta-Strategy for Learning Tuning ParametersBut....

Pierre Alquier, RIKEN AIP

Meta-Strategy for Learning Tuning ParametersBut.... but .....

Pierre Alquier, RIKEN AIP

Meta-Strategy for Learning Tuning ParametersBut.... but ..... but....

Pierre Alquier, RIKEN AIP

Meta-Strategy for Learning Tuning ParametersBut !

Pierre Alquier, RIKEN AIP

Meta-Strategy for Learning Tuning Parameters

Where is Bayes ? ?

Pierre Alquier, RIKEN AIP

Meta-Strategy for Learning Tuning Parameters

Bayesian inference

0.101
0.943
0.433
0.074

0.156
0.507
0.624
0.990

0.514
0.333
0.844
0.707

…
…
…
…

...
...
...
OUTPUT

Pierre Alquier, RIKEN AIP

Meta-Strategy for Learning Tuning Parameters

Learning the prior

Pierre Alquier, RIKEN AIP

Meta-Strategy for Learning Tuning Parameters

Online variational inference
B.-E. Chérief-Abdellatif, P. Alquier, M. E. Khan (2019). A generalization bound for online
variational inference. ACML.

Online variational inference :(µt,i = argmin µT
µ∈M

i−1X

∇µt,j Eθ∼qµt,j [`t,j (θ)] +j=1

Pierre Alquier, RIKEN AIPK(qµ , π)η).

Meta-Strategy for Learning Tuning Parameters

Online variational inference
B.-E. Chérief-Abdellatif, P. Alquier, M. E. Khan (2019). A generalization bound for online
variational inference. ACML.

Online variational inference :(µt,i = argmin µT
µ∈M

i−1X

∇µt,j Eθ∼qµt,j [`t,j (θ)] +j=1

K(qµ , π)η).

Regret bound :nX
i=1(Eθ∼qµt,i [`t,i (θ)] ≤ infµ∈MEθ∼qµPierre Alquier, RIKEN AIP)
η4L2 n K(qµ , π)+.
`t,i (θ) +αηi=1" nX#Meta-Strategy for Learning Tuning Parameters

Online variational inference
B.-E. Chérief-Abdellatif, P. Alquier, M. E. Khan (2019). A generalization bound for online
variational inference. ACML.

Online variational inference :(µt,i = argmin µT
µ∈M

i−1X

∇µt,j Eθ∼qµt,j [`t,j (θ)] +j=1

K(qµ , π)η).

Regret bound :nX
i=1(Eθ∼qµt,i [`t,i (θ)] ≤ infµ∈MEθ∼qµ)η4L2 n K(qµ , π)+.
`t,i (θ) +αηi=1" nX#kµ − mk2
If qµ = N (µ, I ) and π = N (m, I ), K(qµ , π) =.
2
Pierre Alquier, RIKEN AIP

Meta-Strategy for Learning Tuning Parametersどうも ありがとう ございました !

Pierre Alquier, RIKEN AIP

Meta-Strategy for Learning Tuning Parameters