Setting of the problem
Exponentially Weighted Aggregation (EWA)
Online gradient and online variational inference

Introduction to sequential prediction
problems
Pierre Alquier

Online Summer School of ML, Moscow Skoltech, Aug. 19, 2020

Pierre Alquier, RIKEN AIP

Title

Setting of the problem
Exponentially Weighted Aggregation (EWA)
Online gradient and online variational inference

Pierre Alquier
PhD in statistics, Université Paris 6 (2006)
Lecturer, Université Paris Diderot (2007-2012)
Lecturer, UCD Dublin (2012-2014)
Professor, ENSAE Paris (2014-2019)
Research scientist, RIKEN (2019-...)For my research, please visit my page :https ://pierrealquier.github.io/
In case you have any question, please send an e-mail :pierrealain.alquier@riken.jp

Pierre Alquier, RIKEN AIP

Title

Setting of the problem
Exponentially Weighted Aggregation (EWA)
Online gradient and online variational inference

Sequential Prediction
Sequential classification problem - yt ∈ {0, 1}

Pierre Alquier, RIKEN AIP

Title

Setting of the problem
Exponentially Weighted Aggregation (EWA)
Online gradient and online variational inference

Sequential Prediction
Sequential classification problem - yt ∈ {0, 1}
1

1x1 given

Pierre Alquier, RIKEN AIP

Title

Setting of the problem
Exponentially Weighted Aggregation (EWA)
Online gradient and online variational inference

Sequential Prediction
Sequential classification problem - yt ∈ {0, 1}
11
2

x1 given
predict y1 : ŷ1

Pierre Alquier, RIKEN AIP

Title

Setting of the problem
Exponentially Weighted Aggregation (EWA)
Online gradient and online variational inference

Sequential Prediction
Sequential classification problem - yt ∈ {0, 1}
1

1
2
3

x1 given
predict y1 : ŷ1
y1 is revealed

Pierre Alquier, RIKEN AIP

Title

Setting of the problem
Exponentially Weighted Aggregation (EWA)
Online gradient and online variational inference

Sequential Prediction
Sequential classification problem - yt ∈ {0, 1}
1

3x1 given
predict y1 : ŷ1
y1 is revealed

1x2 given

1
2

2

Pierre Alquier, RIKEN AIP

Title

Setting of the problem
Exponentially Weighted Aggregation (EWA)
Online gradient and online variational inference

Sequential Prediction
Sequential classification problem - yt ∈ {0, 1}
1

1
2
3

2

1
2

x1 given
predict y1 : ŷ1
y1 is revealed
x2 given
predict y2 : ŷ2

Pierre Alquier, RIKEN AIP

Title

Setting of the problem
Exponentially Weighted Aggregation (EWA)
Online gradient and online variational inference

Sequential Prediction
Sequential classification problem - yt ∈ {0, 1}
1

1
2
3

2

1
2
3

x1 given
predict y1 : ŷ1
y1 is revealed
x2 given
predict y2 : ŷ2y2 revealed

Pierre Alquier, RIKEN AIP

Title

Setting of the problem
Exponentially Weighted Aggregation (EWA)
Online gradient and online variational inference

Sequential Prediction
Sequential classification problem - yt ∈ {0, 1}
1

1
2
3

2

3

x2 given
predict y2 : ŷ2y2 revealed

1x3 given

1
2

3

x1 given
predict y1 : ŷ1
y1 is revealed

Pierre Alquier, RIKEN AIP

Title

Setting of the problem
Exponentially Weighted Aggregation (EWA)
Online gradient and online variational inference

Sequential Prediction
Sequential classification problem - yt ∈ {0, 1}
1

1
2
3

2

1
2
3

3

1
2

x1 given
predict y1 : ŷ1
y1 is revealed
x2 given
predict y2 : ŷ2y2 revealed
x3 given
predict y3 : ŷ3

Pierre Alquier, RIKEN AIP

Title

Setting of the problem
Exponentially Weighted Aggregation (EWA)
Online gradient and online variational inference

Sequential Prediction
Sequential classification problem - yt ∈ {0, 1}
1

1
2
3

2

1
2
3

3

1
2
3

4

x1 given
predict y1 : ŷ1
y1 is revealed
x2 given
predict y2 : ŷ2y2 revealed
x3 given
predict y3 : ŷ3
y3 revealed...
Pierre Alquier, RIKEN AIP

Title

Setting of the problem
Exponentially Weighted Aggregation (EWA)
Online gradient and online variational inference

Sequential Prediction
Sequential classification problem - yt ∈ {0, 1}
1

1
2
3

2

1
2
3

3

1
2
3

4

x1 given
predict y1 : ŷ1
y1 is revealed

Objective :x2 given
predict y2 : ŷ2y2 revealed
x3 given
predict y3 : ŷ3
y3 revealed...
Pierre Alquier, RIKEN AIP

Title

Setting of the problem
Exponentially Weighted Aggregation (EWA)
Online gradient and online variational inference

Sequential Prediction
Sequential classification problem - yt ∈ {0, 1}
1

1
2
3

2

1
2
3

3

1
2
3

4

x1 given
predict y1 : ŷ1
y1 is revealed

Objective : make sure that
we learn to predict well assoon as possible.

x2 given
predict y2 : ŷ2y2 revealed
x3 given
predict y3 : ŷ3
y3 revealed...
Pierre Alquier, RIKEN AIP

Title

Setting of the problem
Exponentially Weighted Aggregation (EWA)
Online gradient and online variational inference

Sequential Prediction
Sequential classification problem - yt ∈ {0, 1}
1

1
2
3

2

1
2
3

3

1
2
3

4

...

Objective : make sure that
we learn to predict well assoon as possible. Keepx1 given
predict y1 : ŷ1
y1 is revealed
x2 given
predict y2 : ŷ2y2 revealed
x3 given
predict y3 : ŷ3
y3 revealedTX

1(ŷt 6= yt )t=1

as small as possible for any T ,without unrealistic
assumptions on the data.

Pierre Alquier, RIKEN AIP

Title

Setting of the problem
Exponentially Weighted Aggregation (EWA)
Online gradient and online variational inference

References

Pierre Alquier, RIKEN AIP

Title

Setting of the problem
Exponentially Weighted Aggregation (EWA)
Online gradient and online variational inference

Outline of the talk1

Setting of the problem
Definitions
Toy examples
The regret

2

Exponentially Weighted Aggregation (EWA)
Prediction with expert advice
Examples : air quality / GDP growth
The infinite case3

Online gradient and online variational inference
Online gradient algorithm
Example : glass identification
Online variational inference
Pierre Alquier, RIKEN AIP

Title

Setting of the problem
Exponentially Weighted Aggregation (EWA)
Online gradient and online variational inference

Definitions
Toy examples
The regret

Setting of the problem
1

Setting of the problem
Definitions
Toy examples
The regret

2

Exponentially Weighted Aggregation (EWA)
Prediction with expert advice
Examples : air quality / GDP growth
The infinite case3

Online gradient and online variational inference
Online gradient algorithm
Example : glass identification
Online variational inference
Pierre Alquier, RIKEN AIP

Title

Setting of the problem
Exponentially Weighted Aggregation (EWA)
Online gradient and online variational inference

Definitions
Toy examples
The regret

Notations : loss function
General notations

Pierre Alquier, RIKEN AIP

Title

Setting of the problem
Exponentially Weighted Aggregation (EWA)
Online gradient and online variational inference

Definitions
Toy examples
The regret

Notations : loss function
General notations
xt ∈ X .

Pierre Alquier, RIKEN AIP

Title

Setting of the problem
Exponentially Weighted Aggregation (EWA)
Online gradient and online variational inference

Definitions
Toy examples
The regret

Notations : loss function
General notations
xt ∈ X .
yt ∈ R (regression...) or yt ∈ {0, 1} (classification).

Pierre Alquier, RIKEN AIP

Title

Setting of the problem
Exponentially Weighted Aggregation (EWA)
Online gradient and online variational inference

Definitions
Toy examples
The regret

Notations : loss function
General notations
xt ∈ X .
yt ∈ R (regression...) or yt ∈ {0, 1} (classification).
ŷt prediction.

Pierre Alquier, RIKEN AIP

Title

Setting of the problem
Exponentially Weighted Aggregation (EWA)
Online gradient and online variational inference

Definitions
Toy examples
The regret

Notations : loss function
General notations
xt ∈ X .
yt ∈ R (regression...) or yt ∈ {0, 1} (classification).
ŷt prediction.
loss incurred at time t : `(ŷt , yt ) for some real-valued,
convex loss function `.

Pierre Alquier, RIKEN AIP

Title

Setting of the problem
Exponentially Weighted Aggregation (EWA)
Online gradient and online variational inference

Definitions
Toy examples
The regret

Notations : loss function
General notations
xt ∈ X .
yt ∈ R (regression...) or yt ∈ {0, 1} (classification).
ŷt prediction.
loss incurred at time t : `(ŷt , yt ) for some real-valued,
convex loss function `.

Classical examples : `(y ) = |y − y 0 | or `(y ) = |y − y 0 |2 ...

Pierre Alquier, RIKEN AIP

Title

Setting of the problem
Exponentially Weighted Aggregation (EWA)
Online gradient and online variational inference

Definitions
Toy examples
The regret

The data
We want to avoid assumptions on the data (xt , yt ), in order toinclude situations like :Pierre Alquier, RIKEN AIP

Title

Setting of the problem
Exponentially Weighted Aggregation (EWA)
Online gradient and online variational inference

Definitions
Toy examples
The regret

The data
We want to avoid assumptions on the data (xt , yt ), in order toinclude situations like :yt = F (xt , εt ) and the noise variables εt are i.i.d.

Pierre Alquier, RIKEN AIP

Title

Setting of the problem
Exponentially Weighted Aggregation (EWA)
Online gradient and online variational inference

Definitions
Toy examples
The regret

The data
We want to avoid assumptions on the data (xt , yt ), in order toinclude situations like :yt = F (xt , εt ) and the noise variables εt are i.i.d.
yt = G (xt−1 , yt−1 , xt , εt ).

Pierre Alquier, RIKEN AIP

Title

Setting of the problem
Exponentially Weighted Aggregation (EWA)
Online gradient and online variational inference

Definitions
Toy examples
The regret

The data
We want to avoid assumptions on the data (xt , yt ), in order toinclude situations like :yt = F (xt , εt ) and the noise variables εt are i.i.d.
yt = G (xt−1 , yt−1 , xt , εt ).
yt = H(xt , zt , εt ) where zt : omitted variables.

Pierre Alquier, RIKEN AIP

Title

Setting of the problem
Exponentially Weighted Aggregation (EWA)
Online gradient and online variational inference

Definitions
Toy examples
The regret

The data
We want to avoid assumptions on the data (xt , yt ), in order toinclude situations like :yt = F (xt , εt ) and the noise variables εt are i.i.d.
yt = G (xt−1 , yt−1 , xt , εt ).
yt = H(xt , zt , εt ) where zt : omitted variables.
yt = I (t, xt , εt ).

Pierre Alquier, RIKEN AIP

Title

Setting of the problem
Exponentially Weighted Aggregation (EWA)
Online gradient and online variational inference

Definitions
Toy examples
The regret

The data
We want to avoid assumptions on the data (xt , yt ), in order toinclude situations like :yt = F (xt , εt ) and the noise variables εt are i.i.d.
yt = G (xt−1 , yt−1 , xt , εt ).
yt = H(xt , zt , εt ) where zt : omitted variables.
yt = I (t, xt , εt ).
yt = J(ŷt ).

Pierre Alquier, RIKEN AIP

Title

Setting of the problem
Exponentially Weighted Aggregation (EWA)
Online gradient and online variational inference

Definitions
Toy examples
The regret

The data
We want to avoid assumptions on the data (xt , yt ), in order toinclude situations like :yt = F (xt , εt ) and the noise variables εt are i.i.d.
yt = G (xt−1 , yt−1 , xt , εt ).
yt = H(xt , zt , εt ) where zt : omitted variables.
yt = I (t, xt , εt ).
yt = J(ŷt ).
yt = K (t, (ŷ1 , . . . , ŷt ), (x1 , . . . , xt ), (y1 , . . . , yt−1 ), εt , zt ).

Pierre Alquier, RIKEN AIP

Title

Setting of the problem
Exponentially Weighted Aggregation (EWA)
Online gradient and online variational inference

Definitions
Toy examples
The regret

Prediction strategy

On the other hand, a realistic prediction cannot be completely
arbitrary.

Pierre Alquier, RIKEN AIP

Title

Setting of the problem
Exponentially Weighted Aggregation (EWA)
Online gradient and online variational inference

Definitions
Toy examples
The regret

Prediction strategy

On the other hand, a realistic prediction cannot be completely
arbitrary.
We have to be able to compute ŷt it can depend on(x1 , . . . , xt ) and (y1 , . . . , yt−1 ).

Pierre Alquier, RIKEN AIP

Title

Setting of the problem
Exponentially Weighted Aggregation (EWA)
Online gradient and online variational inference

Definitions
Toy examples
The regret

Prediction strategy

On the other hand, a realistic prediction cannot be completely
arbitrary.
We have to be able to compute ŷt it can depend on(x1 , . . . , xt ) and (y1 , . . . , yt−1 ).
It must be computationnally feasible.

Pierre Alquier, RIKEN AIP

Title

Setting of the problem
Exponentially Weighted Aggregation (EWA)
Online gradient and online variational inference

Definitions
Toy examples
The regret

Prediction strategy

On the other hand, a realistic prediction cannot be completely
arbitrary.
We have to be able to compute ŷt it can depend on(x1 , . . . , xt ) and (y1 , . . . , yt−1 ).
It must be computationnally feasible.
We can use expert advice.

Pierre Alquier, RIKEN AIP

Title

Setting of the problem
Exponentially Weighted Aggregation (EWA)
Online gradient and online variational inference

Definitions
Toy examples
The regret

What performance can we achieve in this setting ?
Consider binary classification with `(y , y 0 ) = 1(y 6= y 0 ), as weallowed yt = J(ŷt ), the opponent can always chose yt = 1 − ŷtwhich leads toTX`(ŷt , yt ) = T .
t=1

Pierre Alquier, RIKEN AIP

Title

Setting of the problem
Exponentially Weighted Aggregation (EWA)
Online gradient and online variational inference

Definitions
Toy examples
The regret

What performance can we achieve in this setting ?
Consider binary classification with `(y , y 0 ) = 1(y 6= y 0 ), as weallowed yt = J(ŷt ), the opponent can always chose yt = 1 − ŷtwhich leads toTX`(ŷt , yt ) = T .
t=1

On the other hand, many real world phenomena can be “quitewell” described by models. These models allow to do “sensible”
predictions.

Pierre Alquier, RIKEN AIP

Title

Setting of the problem
Exponentially Weighted Aggregation (EWA)
Online gradient and online variational inference

Definitions
Toy examples
The regret

What performance can we achieve in this setting ?
Consider binary classification with `(y , y 0 ) = 1(y 6= y 0 ), as weallowed yt = J(ŷt ), the opponent can always chose yt = 1 − ŷtwhich leads toTX`(ŷt , yt ) = T .
t=1

On the other hand, many real world phenomena can be “quitewell” described by models. These models allow to do “sensible”
predictions.
The extreme case would be the constraint yt = f (xt ), wheref ∈ F for a known class F. This is called the realizable case.
Let’s study it as a toy example when F is finite.
Pierre Alquier, RIKEN AIP

Title

Setting of the problem
Exponentially Weighted Aggregation (EWA)
Online gradient and online variational inference

Definitions
Toy examples
The regret

A naive strategy
Here yt = fi ∗ (xt ) where i ∗ ∈ {1, . . . , M} is unknown.
Naive strategy

Pierre Alquier, RIKEN AIP

Title

Setting of the problem
Exponentially Weighted Aggregation (EWA)
Online gradient and online variational inference

Definitions
Toy examples
The regret

A naive strategy
Here yt = fi ∗ (xt ) where i ∗ ∈ {1, . . . , M} is unknown.
Naive strategy
Start with i(1) = 1 and C (1) = {1, . . . , M}. At step t,

Pierre Alquier, RIKEN AIP

Title

Setting of the problem
Exponentially Weighted Aggregation (EWA)
Online gradient and online variational inference

Definitions
Toy examples
The regret

A naive strategy
Here yt = fi ∗ (xt ) where i ∗ ∈ {1, . . . , M} is unknown.
Naive strategy
Start with i(1) = 1 and C (1) = {1, . . . , M}. At step t,
1
predict ŷt = fi(t) (xt ), observe yt ,Pierre Alquier, RIKEN AIP

Title

Setting of the problem
Exponentially Weighted Aggregation (EWA)
Online gradient and online variational inference

Definitions
Toy examples
The regret

A naive strategy
Here yt = fi ∗ (xt ) where i ∗ ∈ {1, . . . , M} is unknown.
Naive strategy
Start with i(1) = 1 and C (1) = {1, . . . , M}. At step t,
1
predict ŷt = fi(t) (xt ), observe yt ,C (t + 1) = {i ∈ C (t) : fi (xt ) = yt },2
updatei(t + 1) = min C (t + 1).

Pierre Alquier, RIKEN AIP

Title

Setting of the problem
Exponentially Weighted Aggregation (EWA)
Online gradient and online variational inference

Definitions
Toy examples
The regret

A naive strategy
Here yt = fi ∗ (xt ) where i ∗ ∈ {1, . . . , M} is unknown.
Naive strategy
Start with i(1) = 1 and C (1) = {1, . . . , M}. At step t,
1
predict ŷt = fi(t) (xt ), observe yt ,C (t + 1) = {i ∈ C (t) : fi (xt ) = yt },2
updatei(t + 1) = min C (t + 1).
Theorem∀T ,TX`(ŷt , yt ) ≤ M − 1.

t=1
Pierre Alquier, RIKEN AIP

Title

Setting of the problem
Exponentially Weighted Aggregation (EWA)
Online gradient and online variational inference

Definitions
Toy examples
The regret

Naive strategy : an example

Pierre Alquier, RIKEN AIP

Title

Setting of the problem
Exponentially Weighted Aggregation (EWA)
Online gradient and online variational inference

Definitions
Toy examples
The regret

Naive strategy : an example

Pierre Alquier, RIKEN AIP

Title

Setting of the problem
Exponentially Weighted Aggregation (EWA)
Online gradient and online variational inference

Definitions
Toy examples
The regret

Naive strategy : an example

2−1
Pierre Alquier, RIKEN AIP

Title

Setting of the problem
Exponentially Weighted Aggregation (EWA)
Online gradient and online variational inference

Definitions
Toy examples
The regret

Naive strategy : an example

2−1
Pierre Alquier, RIKEN AIP

Title

Setting of the problem
Exponentially Weighted Aggregation (EWA)
Online gradient and online variational inference

Definitions
Toy examples
The regret

Naive strategy : an example

2−1

1−1
Pierre Alquier, RIKEN AIP

Title

Setting of the problem
Exponentially Weighted Aggregation (EWA)
Online gradient and online variational inference

Definitions
Toy examples
The regret

Naive strategy : an example

2−1

1−1
Pierre Alquier, RIKEN AIP

Title

Setting of the problem
Exponentially Weighted Aggregation (EWA)
Online gradient and online variational inference

Definitions
Toy examples
The regret

Naive strategy : an example

2−1

1−1
Pierre Alquier, RIKEN AIP

2−0
Title

Setting of the problem
Exponentially Weighted Aggregation (EWA)
Online gradient and online variational inference

Definitions
Toy examples
The regret

Naive strategy : an example

2−1

1−1
Pierre Alquier, RIKEN AIP

2−0
Title

Setting of the problem
Exponentially Weighted Aggregation (EWA)
Online gradient and online variational inference

Definitions
Toy examples
The regret

Naive strategy : an example

2−1

1−1
Pierre Alquier, RIKEN AIP

2−0
Title

3−0

Setting of the problem
Exponentially Weighted Aggregation (EWA)
Online gradient and online variational inference

Definitions
Toy examples
The regret

Naive strategy : an example

2−1

1−1
Pierre Alquier, RIKEN AIP

2−0
Title

3−0

Setting of the problem
Exponentially Weighted Aggregation (EWA)
Online gradient and online variational inference

Definitions
Toy examples
The regret

Naive strategy : an example

2−1

1−1
Pierre Alquier, RIKEN AIP

2−0
Title

3−0

0−1

Setting of the problem
Exponentially Weighted Aggregation (EWA)
Online gradient and online variational inference

Definitions
Toy examples
The regret

Naive strategy : an example

W

DL
Pierre Alquier, RIKEN AIP

W
Title

W

DL

Setting of the problem
Exponentially Weighted Aggregation (EWA)
Online gradient and online variational inference

Definitions
Toy examples
The regret

Naive strategy : an example
Remind that we have to assume that one of the experts isnever wrong. Is there such an expert ?

Pierre Alquier, RIKEN AIP

Title

Setting of the problem
Exponentially Weighted Aggregation (EWA)
Online gradient and online variational inference

Definitions
Toy examples
The regret

Naive strategy : an example
Remind that we have to assume that one of the experts isnever wrong. Is there such an expert ?

This is not a realistic example, so let us imagine a data
scientist built a perfect IA.
Pierre Alquier, RIKEN AIP

Title

Setting of the problem
Exponentially Weighted Aggregation (EWA)
Online gradient and online variational inference

Definitions
Toy examples
The regret

Naive strategy : an example

Pierre Alquier, RIKEN AIP

Title

Setting of the problem
Exponentially Weighted Aggregation (EWA)
Online gradient and online variational inference

Definitions
Toy examples
The regret

Naive strategy : an example

t=1

W

DL

W

Pierre Alquier, RIKEN AIP

W

Title

DL

W

Setting of the problem
Exponentially Weighted Aggregation (EWA)
Online gradient and online variational inference

Definitions
Toy examples
The regret

Naive strategy : an example

t=1

W

DL

W

Pierre Alquier, RIKEN AIP

W

Title

DL

W

Setting of the problem
Exponentially Weighted Aggregation (EWA)
Online gradient and online variational inference

Definitions
Toy examples
The regret

Naive strategy : an example

t=1

W

DL

W

Pierre Alquier, RIKEN AIP

W

Title

DL

W

Setting of the problem
Exponentially Weighted Aggregation (EWA)
Online gradient and online variational inference

Definitions
Toy examples
The regret

Naive strategy : an example

t=1

W

t=2

DL

DL

W

W

DL

W

Pierre Alquier, RIKEN AIP

Title

DL

W
DL

Setting of the problem
Exponentially Weighted Aggregation (EWA)
Online gradient and online variational inference

Definitions
Toy examples
The regret

Naive strategy : an example

t=1

W

t=2

DL

DL

W

W

DL

W

Pierre Alquier, RIKEN AIP

Title

DL

W
DL

Setting of the problem
Exponentially Weighted Aggregation (EWA)
Online gradient and online variational inference

Definitions
Toy examples
The regret

Naive strategy : an example

t=1

W

t=2

DL

DL

W

W

DL

W

Pierre Alquier, RIKEN AIP

Title

DL

W
DL

Setting of the problem
Exponentially Weighted Aggregation (EWA)
Online gradient and online variational inference

Definitions
Toy examples
The regret

Naive strategy : an example

t=1

W

t=2
t=3

DL

W

W

DL

DL

W

W

DL

Pierre Alquier, RIKEN AIP

DL

W
DL
W

Title

Setting of the problem
Exponentially Weighted Aggregation (EWA)
Online gradient and online variational inference

Definitions
Toy examples
The regret

Naive strategy : an example

t=1

W

t=2
t=3

DL

W

W

DL

DL

W

W

DL

Pierre Alquier, RIKEN AIP

DL

W
DL
W

Title

Setting of the problem
Exponentially Weighted Aggregation (EWA)
Online gradient and online variational inference

Definitions
Toy examples
The regret

Naive strategy : an example

t=1

W

t=2
t=3

DL

W

W

DL

DL

W

W

DL

Pierre Alquier, RIKEN AIP

DL

W
DL
W

Title

Setting of the problem
Exponentially Weighted Aggregation (EWA)
Online gradient and online variational inference

Definitions
Toy examples
The regret

Naive strategy : an example

t=1

W

t=2

DL

W

W

DL

DL

W

t=3

W

DL

t=4

DL

DL

W
DL
W
W

Pierre Alquier, RIKEN AIP

Title

Setting of the problem
Exponentially Weighted Aggregation (EWA)
Online gradient and online variational inference

Definitions
Toy examples
The regret

Naive strategy : an example

t=1

W

t=2

DL

W

W

DL

DL

W

t=3

W

DL

t=4

DL

DL

W
DL
W
W

Pierre Alquier, RIKEN AIP

Title

Setting of the problem
Exponentially Weighted Aggregation (EWA)
Online gradient and online variational inference

Definitions
Toy examples
The regret

Naive strategy : an example

t=1

W

t=2

DL

W

W

DL

DL

W

t=3

W

DL

t=4

DL

DL

W
DL
W
W

Pierre Alquier, RIKEN AIP

Title

Setting of the problem
Exponentially Weighted Aggregation (EWA)
Online gradient and online variational inference

Definitions
Toy examples
The regret

Naive strategy : an example

t=1

W

t=2

DL

W

W

DL

DL

W

t=3

W

DL

t=4

DL

DL

W
DL
W
W

t=5

W
Pierre Alquier, RIKEN AIP

Title

Setting of the problem
Exponentially Weighted Aggregation (EWA)
Online gradient and online variational inference

Definitions
Toy examples
The regret

The halving algorithm(Still yt = fi ∗ (xt ) where i ∗ ∈ {1, . . . , M} is unknown).
The halving algorithm

Pierre Alquier, RIKEN AIP

Title

Setting of the problem
Exponentially Weighted Aggregation (EWA)
Online gradient and online variational inference

Definitions
Toy examples
The regret

The halving algorithm(Still yt = fi ∗ (xt ) where i ∗ ∈ {1, . . . , M} is unknown).
The halving algorithm
Start with i(1) = 1 and C (1) = {1, . . . , M}. At step t,

Pierre Alquier, RIKEN AIP

Title

Setting of the problem
Exponentially Weighted Aggregation (EWA)
Online gradient and online variational inference

Definitions
Toy examples
The regret

The halving algorithm(Still yt = fi ∗ (xt ) where i ∗ ∈ {1, . . . , M} is unknown).
The halving algorithm
Start with i(1) = 1 and C (1) = {1, . . . , M}. At step t,
1
predict ŷt = “majority vote in C (t)”, observe yt ,Pierre Alquier, RIKEN AIP

Title

Setting of the problem
Exponentially Weighted Aggregation (EWA)
Online gradient and online variational inference

Definitions
Toy examples
The regret

The halving algorithm(Still yt = fi ∗ (xt ) where i ∗ ∈ {1, . . . , M} is unknown).
The halving algorithm
Start with i(1) = 1 and C (1) = {1, . . . , M}. At step t,
1
predict ŷt = “majority vote in C (t)”, observe yt ,2
update C (t + 1) = {i ∈ C (t) : fi (xt ) = yt }.

Pierre Alquier, RIKEN AIP

Title

Setting of the problem
Exponentially Weighted Aggregation (EWA)
Online gradient and online variational inference

Definitions
Toy examples
The regret

The halving algorithm(Still yt = fi ∗ (xt ) where i ∗ ∈ {1, . . . , M} is unknown).
The halving algorithm
Start with i(1) = 1 and C (1) = {1, . . . , M}. At step t,
1
predict ŷt = “majority vote in C (t)”, observe yt ,2
update C (t + 1) = {i ∈ C (t) : fi (xt ) = yt }.
Theorem∀T ,TX`(ŷt , yt ) ≤ log2 (M).

t=1

Pierre Alquier, RIKEN AIP

Title

Setting of the problem
Exponentially Weighted Aggregation (EWA)
Online gradient and online variational inference

Definitions
Toy examples
The regret

Halving algorithm : an example

Pierre Alquier, RIKEN AIP

Title

Setting of the problem
Exponentially Weighted Aggregation (EWA)
Online gradient and online variational inference

Definitions
Toy examples
The regret

Halving algorithm : an example

t=1

W

DL

W

Pierre Alquier, RIKEN AIP

W

Title

DL

W

Setting of the problem
Exponentially Weighted Aggregation (EWA)
Online gradient and online variational inference

Definitions
Toy examples
The regret

Halving algorithm : an example

t=1

W

DL

W

Pierre Alquier, RIKEN AIP

W

Title

DL

W

Setting of the problem
Exponentially Weighted Aggregation (EWA)
Online gradient and online variational inference

Definitions
Toy examples
The regret

Halving algorithm : an example

t=1

W

DL

W

Pierre Alquier, RIKEN AIP

W

Title

DL

W

Setting of the problem
Exponentially Weighted Aggregation (EWA)
Online gradient and online variational inference

Definitions
Toy examples
The regret

Halving algorithm : an example

t=1

W

t=2

DL

DL

W

W

DL

W

Pierre Alquier, RIKEN AIP

Title

DL

W
DL

Setting of the problem
Exponentially Weighted Aggregation (EWA)
Online gradient and online variational inference

Definitions
Toy examples
The regret

Halving algorithm : an example

t=1

W

t=2

DL

DL

W

W

DL

W

Pierre Alquier, RIKEN AIP

Title

DL

W
DL

Setting of the problem
Exponentially Weighted Aggregation (EWA)
Online gradient and online variational inference

Definitions
Toy examples
The regret

Halving algorithm : an example

t=1

W

t=2

DL

DL

W

W

DL

W

Pierre Alquier, RIKEN AIP

Title

DL

W
DL

Setting of the problem
Exponentially Weighted Aggregation (EWA)
Online gradient and online variational inference

Definitions
Toy examples
The regret

Halving algorithm : an example

t=1

W

t=2
t=3

DL

W

W

DL

DL

W

W

DL

Pierre Alquier, RIKEN AIP

DL

W
DL
W

Title

Setting of the problem
Exponentially Weighted Aggregation (EWA)
Online gradient and online variational inference

Definitions
Toy examples
The regret

Halving algorithm : an example

t=1

W

t=2
t=3

DL

W

W

DL

DL

W

W

DL

Pierre Alquier, RIKEN AIP

DL

W
DL
W

Title

Setting of the problem
Exponentially Weighted Aggregation (EWA)
Online gradient and online variational inference

Definitions
Toy examples
The regret

Halving algorithm : an example

t=1

W

t=2
t=3

DL

W

W

DL

DL

W

W

DL

Pierre Alquier, RIKEN AIP

DL

W
DL
W

Title

Setting of the problem
Exponentially Weighted Aggregation (EWA)
Online gradient and online variational inference

Definitions
Toy examples
The regret

Halving algorithm : an example

t=1

W

t=2

DL

W

W

DL

DL

W

t=3

W

DL

t=4

DL

DL

W
DL
W
W

Pierre Alquier, RIKEN AIP

Title

Setting of the problem
Exponentially Weighted Aggregation (EWA)
Online gradient and online variational inference

Definitions
Toy examples
The regret

Halving algorithm : an example

t=1

W

t=2

DL

W

W

DL

DL

W

t=3

W

DL

t=4

DL

DL

W
DL
W
W

Pierre Alquier, RIKEN AIP

Title

Setting of the problem
Exponentially Weighted Aggregation (EWA)
Online gradient and online variational inference

Definitions
Toy examples
The regret

Halving algorithm : an example

t=1

W

t=2

DL

W

W

DL

DL

W

t=3

W

DL

t=4

DL

DL

W
DL
W
W

Pierre Alquier, RIKEN AIP

Title

Setting of the problem
Exponentially Weighted Aggregation (EWA)
Online gradient and online variational inference

Definitions
Toy examples
The regret

Halving algorithm : an example

t=1

W

t=2

DL

W

W

DL

DL

W

t=3

W

DL

t=4

DL

DL

W
DL
W
W

t=5

W
Pierre Alquier, RIKEN AIP

Title

Setting of the problem
Exponentially Weighted Aggregation (EWA)
Online gradient and online variational inference

Definitions
Toy examples
The regret

Halving algorithm : another example

Pierre Alquier, RIKEN AIP

Title

Setting of the problem
Exponentially Weighted Aggregation (EWA)
Online gradient and online variational inference

Definitions
Toy examples
The regret

Halving algorithm : another example

t=1

W

DL

DL

Pierre Alquier, RIKEN AIP

DL

Title

DL

W

Setting of the problem
Exponentially Weighted Aggregation (EWA)
Online gradient and online variational inference

Definitions
Toy examples
The regret

Halving algorithm : another example

t=1

W

DL

DL

Pierre Alquier, RIKEN AIP

DL

Title

DL

W

Setting of the problem
Exponentially Weighted Aggregation (EWA)
Online gradient and online variational inference

Definitions
Toy examples
The regret

Halving algorithm : another example

t=1

W

DL

DL

Pierre Alquier, RIKEN AIP

DL

Title

DL

W

Setting of the problem
Exponentially Weighted Aggregation (EWA)
Online gradient and online variational inference

Definitions
Toy examples
The regret

Halving algorithm : another example

t=1

W

t=2

DL

DL

DL

DL

DL

W
DL

Pierre Alquier, RIKEN AIP

Title

Setting of the problem
Exponentially Weighted Aggregation (EWA)
Online gradient and online variational inference

Definitions
Toy examples
The regret

Halving algorithm : another example

t=1

W

t=2

DL

DL

DL

DL

DL

W
DL

Pierre Alquier, RIKEN AIP

Title

Setting of the problem
Exponentially Weighted Aggregation (EWA)
Online gradient and online variational inference

Definitions
Toy examples
The regret

Halving algorithm : another example

t=1

W

t=2

DL

DL

DL

DL

DL

W
DL

Pierre Alquier, RIKEN AIP

Title

Setting of the problem
Exponentially Weighted Aggregation (EWA)
Online gradient and online variational inference

Definitions
Toy examples
The regret

Halving algorithm : another example

t=1

W

DL

DL

t=2

DL

DL

t=3

DL

W

Pierre Alquier, RIKEN AIP

DL

Title

DL

W

Setting of the problem
Exponentially Weighted Aggregation (EWA)
Online gradient and online variational inference

Definitions
Toy examples
The regret

Halving algorithm : another example

t=1

W

DL

DL

t=2

DL

DL

t=3

DL

W

Pierre Alquier, RIKEN AIP

DL

Title

DL

W

Setting of the problem
Exponentially Weighted Aggregation (EWA)
Online gradient and online variational inference

Definitions
Toy examples
The regret

Halving algorithm : another example

t=1

W

DL

DL

t=2

DL

DL

t=3

DL

W

Pierre Alquier, RIKEN AIP

DL

Title

DL

W

Setting of the problem
Exponentially Weighted Aggregation (EWA)
Online gradient and online variational inference

Definitions
Toy examples
The regret

Halving algorithm : another example

t=1

W

DL

DL

DL

t=2

DL

DL

t=3

DL

W

t=4

DL

W

W

Pierre Alquier, RIKEN AIP

Title

Setting of the problem
Exponentially Weighted Aggregation (EWA)
Online gradient and online variational inference

Definitions
Toy examples
The regret

Halving algorithm : another example

t=1

W

DL

DL

DL

DL

W

t=2

DL

DL

t=3

DL

W

t=4

W

t=5

W
Pierre Alquier, RIKEN AIP

Title

Setting of the problem
Exponentially Weighted Aggregation (EWA)
Online gradient and online variational inference

Definitions
Toy examples
The regret

A feasible objective
Two extremes :playing against the devil yt = 1 − ŷt ,assuming a true, exact model F.

Pierre Alquier, RIKEN AIP

Title

Setting of the problem
Exponentially Weighted Aggregation (EWA)
Online gradient and online variational inference

Definitions
Toy examples
The regret

A feasible objective
Two extremes :playing against the devil yt = 1 − ŷt ,assuming a true, exact model F.
Real-life is somewhere in between !

Pierre Alquier, RIKEN AIP

Title

Setting of the problem
Exponentially Weighted Aggregation (EWA)
Online gradient and online variational inference

Definitions
Toy examples
The regret

A feasible objective
Two extremes :playing against the devil yt = 1 − ŷt ,assuming a true, exact model F.
Real-life is somewhere in between !
Objective
Strategy such thatTX
t=1`(ŷt , yt ) ≤

inf

f ∈F

|

T
X

`(f (xt ), yt )

t=1

{z

}

= T in the worst case (devil),= 0 in the ideal case (true model),almost always in between.

Pierre Alquier, RIKEN AIP

Title

+

B(T )
| {z }

as small as possible ! !

.

Setting of the problem
Exponentially Weighted Aggregation (EWA)
Online gradient and online variational inference

Definitions
Toy examples
The regret

The regretTX`(ŷt , yt )≤ inf

t=1

Pierre Alquier, RIKEN AIP

f ∈F

Title

T
X
t=1

`(f (xt ), yt )+B(T )Setting of the problem
Exponentially Weighted Aggregation (EWA)
Online gradient and online variational inference

Definitions
Toy examples
The regret

The regretTX`(ŷt , yt )− inf

t=1

Pierre Alquier, RIKEN AIP

f ∈F

Title

T
X
t=1

`(f (xt ), yt )≤B(T )Setting of the problem
Exponentially Weighted Aggregation (EWA)
Online gradient and online variational inference

Definitions
Toy examples
The regret

The regret
Regret(T ) =T
X`(ŷt , yt )− inf

t=1

Pierre Alquier, RIKEN AIP

f ∈F

Title

T
X
t=1

`(f (xt ), yt )≤B(T )Setting of the problem
Exponentially Weighted Aggregation (EWA)
Online gradient and online variational inference

Definitions
Toy examples
The regret

The regret
Regret(T ) =T
X`(ŷt , yt )− inf

t=1

f ∈F

T
X

`(f (xt ), yt )≤B(T )t=1

Objective
Strategy such that Regret(T ) ≤ B(T ) as small as possible, atleast B(T ) = o(T ).

Pierre Alquier, RIKEN AIP

Title

Setting of the problem
Exponentially Weighted Aggregation (EWA)
Online gradient and online variational inference

Definitions
Toy examples
The regret

The regret
Regret(T ) =T
X`(ŷt , yt )− inf

t=1

f ∈F

T
X

`(f (xt ), yt )≤B(T )t=1

Objective
Strategy such that Regret(T ) ≤ B(T ) as small as possible, atleast B(T ) = o(T ).
We’ll see that√for a bounded `, B(T ) = O( T ) always feasible with arandomized strategy.
deterministic results, and B(T ) = O(log(T )) or even
B(T ) = O(1), possible under more assumptions.
Pierre Alquier, RIKEN AIP

Title

Setting of the problem
Exponentially Weighted Aggregation (EWA)
Online gradient and online variational inference

Definitions
Toy examples
The regret

Important remarks
1

Common misunderstanding :machine learning ' prediction, opposed to modelization.

Pierre Alquier, RIKEN AIP

Title

Setting of the problem
Exponentially Weighted Aggregation (EWA)
Online gradient and online variational inference

Definitions
Toy examples
The regret

Important remarks
1

2

Common misunderstanding :machine learning ' prediction, opposed to modelization.
However ! modelization (economics, physics,
epidemiology) is required to build F :TX
t=1`(ŷt , yt ) ≤ inf

f ∈F

Pierre Alquier, RIKEN AIPTX`(f (xt ), yt ) + B(T ).

t=1

Title

Setting of the problem
Exponentially Weighted Aggregation (EWA)
Online gradient and online variational inference

Definitions
Toy examples
The regret

Important remarks
1

2

Common misunderstanding :machine learning ' prediction, opposed to modelization.
However ! modelization (economics, physics,
epidemiology) is required to build F :
T
X
t=1

3

`(ŷt , yt ) ≤ inf

f ∈F

T
X

`(f (xt ), yt ) + B(T ).

t=1

Common mistake : machine learning provides goodpredictions in practice, but has no theoretical ground.

Pierre Alquier, RIKEN AIP

Title

Setting of the problem
Exponentially Weighted Aggregation (EWA)
Online gradient and online variational inference

Definitions
Toy examples
The regret

Important remarks
1

2

Common misunderstanding :machine learning ' prediction, opposed to modelization.
However ! modelization (economics, physics,
epidemiology) is required to build F :
T
X
t=1

3

4

`(ŷt , yt ) ≤ inf

f ∈F

T
X

`(f (xt ), yt ) + B(T ).

t=1

Common mistake : machine learning provides goodpredictions in practice, but has no theoretical ground.
Wrong ! We’ll see some theoretical results below.
Pierre Alquier, RIKEN AIP

Title

Setting of the problem
Exponentially Weighted Aggregation (EWA)
Online gradient and online variational inference

Definitions
Toy examples
The regret

Proposition

My own view is that machine learning theory is itself a modelfor “the performance of a scientist who uses a model for
prediction in an environment where the model might not be
exactly correct”.

Pierre Alquier, RIKEN AIP

Title

Setting of the problem
Exponentially Weighted Aggregation (EWA)
Online gradient and online variational inference

Prediction with expert advice
Examples : air quality / GDP growth
The infinite case

Exponentially Weighted Aggregation (EWA)
1

Setting of the problem
Definitions
Toy examples
The regret

2

Exponentially Weighted Aggregation (EWA)
Prediction with expert advice
Examples : air quality / GDP growth
The infinite case3

Online gradient and online variational inference
Online gradient algorithm
Example : glass identification
Online variational inference
Pierre Alquier, RIKEN AIP

Title

Setting of the problem
Exponentially Weighted Aggregation (EWA)
Online gradient and online variational inference

Prediction with expert advice
Examples : air quality / GDP growth
The infinite case

Finite number of predictors
Let us start with the case of a finite set of M predictors :F = (f1 , . . . , fM ).

Pierre Alquier, RIKEN AIP

Title

Setting of the problem
Exponentially Weighted Aggregation (EWA)
Online gradient and online variational inference

Prediction with expert advice
Examples : air quality / GDP growth
The infinite case

Finite number of predictors
Let us start with the case of a finite set of M predictors :F = (f1 , . . . , fM ).
What should the fi ’s be ?

Pierre Alquier, RIKEN AIP

Title

Setting of the problem
Exponentially Weighted Aggregation (EWA)
Online gradient and online variational inference

Prediction with expert advice
Examples : air quality / GDP growth
The infinite case

Finite number of predictors
Let us start with the case of a finite set of M predictors :F = (f1 , . . . , fM ).
What should the fi ’s be ? By including side information in x̃tsuch as the past x̃t = (x1 , y1 , . . . , xt−1 , yt−1 , xt ), we can haverich predictors. For example :f1 (x̃t ) = β̂tT xt
whereβ̂t = arg min

t−1
X

β

Pierre Alquier, RIKEN AIP(yi − β T xi )2 .

i=1
Title

Setting of the problem
Exponentially Weighted Aggregation (EWA)
Online gradient and online variational inference

Prediction with expert advice
Examples : air quality / GDP growth
The infinite caseExpert advice
More importantly, we can use “expert advice” : an expert eproposes at each time t a forecast ŷte , why not using it ?

Pierre Alquier, RIKEN AIP

Title

Setting of the problem
Exponentially Weighted Aggregation (EWA)
Online gradient and online variational inference

Prediction with expert advice
Examples : air quality / GDP growth
The infinite caseExpert advice
More importantly, we can use “expert advice” : an expert eproposes at each time t a forecast ŷte , why not using it ?
For a while, we forget about the xt ’s. At each time t, M
different forecasts are proposed :
(1)

(M)

(ŷt , . . . , ŷt).

Some come from models, others from experts. For short werefer to all of them as “experts advice”. I have to make my own
prediction ŷt based on this.

Pierre Alquier, RIKEN AIP

Title

Setting of the problem
Exponentially Weighted Aggregation (EWA)
Online gradient and online variational inference

Prediction with expert advice
Examples : air quality / GDP growth
The infinite caseExpert advice
More importantly, we can use “expert advice” : an expert eproposes at each time t a forecast ŷte , why not using it ?
For a while, we forget about the xt ’s. At each time t, M
different forecasts are proposed :
(1)

(M)

(ŷt , . . . , ŷt).

Some come from models, others from experts. For short werefer to all of them as “experts advice”. I have to make my own
prediction ŷt based on this.
Regret(T ) =T
X`(ŷt , yt ) − mint=1
Pierre Alquier, RIKEN AIP

i=1,...,M

Title

T
X
t=1

(i)

`(ŷt , yt )≤?

Setting of the problem
Exponentially Weighted Aggregation (EWA)
Online gradient and online variational inference

Prediction with expert advice
Examples : air quality / GDP growth
The infinite caseRandomized EWA strategy
EWA : Exponentially Weighted Aggregation. Input :learning rate η > 0,P
initial weights p1 (1), . . . , p1 (M) ≥ 0 with M
i=1 p1 (i) = 1.

Pierre Alquier, RIKEN AIP

Title

Setting of the problem
Exponentially Weighted Aggregation (EWA)
Online gradient and online variational inference

Prediction with expert advice
Examples : air quality / GDP growth
The infinite caseRandomized EWA strategy
EWA : Exponentially Weighted Aggregation. Input :learning rate η > 0,P
initial weights p1 (1), . . . , p1 (M) ≥ 0 with M
i=1 p1 (i) = 1.
Algorithm 1 EWA (Randomized version)
1: for i = 1, 2, . . . do
2:
Draw It with P(It = i) = pt (i)(I )3:Predict ŷt = ŷt t ,(i)4:yt revealed, update pt+1 (i) = PMpt (i) exp[−η`(ŷt ,y(j)t )]j=1 pt (j) exp[−η`(ŷt

5: end for

Pierre Alquier, RIKEN AIP

Title,yt )]

Setting of the problem
Exponentially Weighted Aggregation (EWA)
Online gradient and online variational inference

Prediction with expert advice
Examples : air quality / GDP growth
The infinite case

Guarantees (in expectation)
TheoremAssume that `(·, ·) ∈ [0, C ] (e.g. classification). ThenηC 2 T
log(M)E (Regret(T )) ≤+8
η

Pierre Alquier, RIKEN AIP

Title

Setting of the problem
Exponentially Weighted Aggregation (EWA)
Online gradient and online variational inference

Prediction with expert advice
Examples : air quality / GDP growth
The infinite case

Guarantees (in expectation)
TheoremAssume that `(·, ·) ∈ [0, C ] (e.g. classification). ThenηC 2 T
log(M)E (Regret(T )) ≤
+
8
η
1
η=
C

r

8 log(M)⇒ E (Regret(T )) ≤ C
T

Pierre Alquier, RIKEN AIP

Title

r

T log(M).
2

Setting of the problem
Exponentially Weighted Aggregation (EWA)
Online gradient and online variational inference

Prediction with expert advice
Examples : air quality / GDP growth
The infinite case

Guarantees (in expectation)
TheoremAssume that `(·, ·) ∈ [0, C ] (e.g. classification). ThenηC 2 T
log(M)E (Regret(T )) ≤
+
8
η
1
η=
C

r

8 log(M)⇒ E (Regret(T )) ≤ C
Tr

T log(M).
2the expectation is only w.r.t the algorithm. No
assumption on the data.

Pierre Alquier, RIKEN AIP

Title

Setting of the problem
Exponentially Weighted Aggregation (EWA)
Online gradient and online variational inference

Prediction with expert advice
Examples : air quality / GDP growth
The infinite case

Guarantees (in expectation)
TheoremAssume that `(·, ·) ∈ [0, C ] (e.g. classification). ThenηC 2 T
log(M)E (Regret(T )) ≤
+
8
η
1
η=
C

r

8 log(M)⇒ E (Regret(T )) ≤ C
Tr

T log(M).
2the expectation is only w.r.t the algorithm. No
assumption on the data.
√
possible to take ηt ∼ 1/ t.
Pierre Alquier, RIKEN AIP

Title

Setting of the problem
Exponentially Weighted Aggregation (EWA)
Online gradient and online variational inference

Prediction with expert advice
Examples : air quality / GDP growth
The infinite case

Guarantees (in expectation)
TheoremAssume that `(·, ·) ∈ [0, C ] (e.g. classification). ThenηC 2 T
log(M)E (Regret(T )) ≤
+
8
η
1
η=
C

r

8 log(M)⇒ E (Regret(T )) ≤ C
Tr

T log(M).
2the expectation is only w.r.t the algorithm. No
assumption on the data.
√
possible to take ηt ∼ 1/ t.
what about deterministic prediction ?
Pierre Alquier, RIKEN AIP

Title

Setting of the problem
Exponentially Weighted Aggregation (EWA)
Online gradient and online variational inference

Prediction with expert advice
Examples : air quality / GDP growth
The infinite case

EWA strategy
Input :
learning rate η > 0,weights p1 (1), . . . , p1 (M).

Pierre Alquier, RIKEN AIP

Title

Setting of the problem
Exponentially Weighted Aggregation (EWA)
Online gradient and online variational inference

Prediction with expert advice
Examples : air quality / GDP growth
The infinite case

EWA strategy
Input :
learning rate η > 0,weights p1 (1), . . . , p1 (M).
Algorithm 2 EWA
1: for i = 1, 2, . . . do
P(i)
2:
Predict ŷt = M
i=1 pt (i)ŷt ,3:(i)yt revealed, update pt+1 (i) = PMpt (i) exp[−η`(ŷt ,y(j)t )]j=1 pt (j) exp[−η`(ŷt

4: end for

Pierre Alquier, RIKEN AIP

Title,yt )]

Setting of the problem
Exponentially Weighted Aggregation (EWA)
Online gradient and online variational inference

Prediction with expert advice
Examples : air quality / GDP growth
The infinite case

EWA - theorem
TheoremAssume that 0 ≤ ` ≤ C and ` is convex. Then
Regret(T ) ≤Pierre Alquier, RIKEN AIP

ηC 2 T
log(M)
+
.
8
η

Title

Setting of the problem
Exponentially Weighted Aggregation (EWA)
Online gradient and online variational inference

Prediction with expert advice
Examples : air quality / GDP growth
The infinite case

EWA - theorem
TheoremAssume that 0 ≤ ` ≤ C and ` is convex. Then
Regret(T ) ≤ηC 2 T
log(M)+.
8ηIn otherqwords, without any assumption on the data, with
η = C1TX
t=1

8 log(M)
,
T

T


X
(i)
`(ŷt , yt ) ≤ min` ŷt , yt + C
i=1,...,M

t=1

Pierre Alquier, RIKEN AIP

Title

r

T log(M).
2

Setting of the problem
Exponentially Weighted Aggregation (EWA)
Online gradient and online variational inference

Prediction with expert advice
Examples : air quality / GDP growth
The infinite case

EWA - theorem
TheoremAssume that 0 ≤ ` ≤ C and ` is convex. Then, withr
1 8 log(M)
.
ηt =
C
t
Then
r
Regret(T ) ≤ 2C

T log(M)+2

Pierre Alquier, RIKEN AIP

Title

s
log




M
.
8

Setting of the problem
Exponentially Weighted Aggregation (EWA)
Online gradient and online variational inference

Prediction with expert advice
Examples : air quality / GDP growth
The infinite caseExample 1 : air quality prediction

Pierre Alquier, RIKEN AIP

Title

Setting of the problem
Exponentially Weighted Aggregation (EWA)
Online gradient and online variational inference

Prediction with expert advice
Examples : air quality / GDP growth
The infinite case

The data and the problem
126 days during summer 2001. 241 stations in France andGermany.

Pierre Alquier, RIKEN AIP

Title

Setting of the problem
Exponentially Weighted Aggregation (EWA)
Online gradient and online variational inference

Prediction with expert advice
Examples : air quality / GDP growth
The infinite case

The data and the problem
126 days during summer 2001. 241 stations in France andGermany.
one-day ahead prediction, quadratic loss.

Pierre Alquier, RIKEN AIP

Title

Setting of the problem
Exponentially Weighted Aggregation (EWA)
Online gradient and online variational inference

Prediction with expert advice
Examples : air quality / GDP growth
The infinite case

The data and the problem
126 days during summer 2001. 241 stations in France andGermany.
one-day ahead prediction, quadratic loss.
typical ozone concentrations between 40µgm−3 and150µgm−3 , a few extreme values up to 240µgm−3 .

Pierre Alquier, RIKEN AIP

Title

Setting of the problem
Exponentially Weighted Aggregation (EWA)
Online gradient and online variational inference

Prediction with expert advice
Examples : air quality / GDP growth
The infinite case

The data and the problem
126 days during summer 2001. 241 stations in France andGermany.
one-day ahead prediction, quadratic loss.
typical ozone concentrations between 40µgm−3 and150µgm−3 , a few extreme values up to 240µgm−3 .
M = 48 experts taken from a paper in geophysics bychoosing a physical and chemical formulation, a numericalapproximation scheme to solve the involved PDEs, and aset of input data.

Pierre Alquier, RIKEN AIP

Title

Setting of the problem
Exponentially Weighted Aggregation (EWA)
Online gradient and online variational inference

Prediction with expert advice
Examples : air quality / GDP growth
The infinite case

Prediction by the experts

Figure – Predictions by the 48 experts for one day at one station.
Pierre Alquier, RIKEN AIP

Title

Setting of the problem
Exponentially Weighted Aggregation (EWA)
Online gradient and online variational inference

Prediction with expert advice
Examples : air quality / GDP growth
The infinite case

Numerical performances

RMSE
Best expert
22.43
Uniform mean 24.41
EWA
21.47
Figure – Numerical performances (RMSE).

Pierre Alquier, RIKEN AIP

Title

Setting of the problem
Exponentially Weighted Aggregation (EWA)
Online gradient and online variational inference

Prediction with expert advice
Examples : air quality / GDP growth
The infinite case

Weights

Figure – Evolution of the weights pi (t) w.r.t t.
Pierre Alquier, RIKEN AIP

Title

Setting of the problem
Exponentially Weighted Aggregation (EWA)
Online gradient and online variational inference

Prediction with expert advice
Examples : air quality / GDP growth
The infinite caseExample 2 : GDP growth in France
Data from :Pierre Alquier, RIKEN AIP

Title

Setting of the problem
Exponentially Weighted Aggregation (EWA)
Online gradient and online variational inference

Prediction with expert advice
Examples : air quality / GDP growth
The infinite caseExample 2 : GDP growth in France
Data from :It is a French institution similar to :Pierre Alquier, RIKEN AIP

Title

Setting of the problem
Exponentially Weighted Aggregation (EWA)
Online gradient and online variational inference

Prediction with expert advice
Examples : air quality / GDP growth
The infinite case

GDP growth forecasting
Objective : during the 3rd month of quarter t, predict what
will be the GDP growth during the quarter : ∆GDPt .

Pierre Alquier, RIKEN AIP

Title

Setting of the problem
Exponentially Weighted Aggregation (EWA)
Online gradient and online variational inference

Prediction with expert advice
Examples : air quality / GDP growth
The infinite case

GDP growth forecasting
Objective : during the 3rd month of quarter t, predict what
will be the GDP growth during the quarter : ∆GDPt .

Available from INSEE :Pierre Alquier, RIKEN AIP

Title

Setting of the problem
Exponentially Weighted Aggregation (EWA)
Online gradient and online variational inference

Prediction with expert advice
Examples : air quality / GDP growth
The infinite case

GDP growth forecasting
Objective : during the 3rd month of quarter t, predict what
will be the GDP growth during the quarter : ∆GDPt .

Available from INSEE :1
the past : ∆GDPt−1 , ...,
∆GDP1 , with t = 1 :1988-T1.

Pierre Alquier, RIKEN AIP

Title

Setting of the problem
Exponentially Weighted Aggregation (EWA)
Online gradient and online variational inference

Prediction with expert advice
Examples : air quality / GDP growth
The infinite case

GDP growth forecasting
Objective : during the 3rd month of quarter t, predict what
will be the GDP growth during the quarter : ∆GDPt .

Available from INSEE :1
the past : ∆GDPt−1 , ...,
∆GDP1 , with t = 1 :1988-T1.
2
French business surveys.

Pierre Alquier, RIKEN AIP

Title

Setting of the problem
Exponentially Weighted Aggregation (EWA)
Online gradient and online variational inference

Prediction with expert advice
Examples : air quality / GDP growth
The infinite case

GDP growth forecasting
Objective : during the 3rd month of quarter t, predict what
will be the GDP growth during the quarter : ∆GDPt .

Available from INSEE :1
the past : ∆GDPt−1 , ...,
∆GDP1 , with t = 1 :1988-T1.
2
French business surveys.
3much more...

Pierre Alquier, RIKEN AIP

Title

Setting of the problem
Exponentially Weighted Aggregation (EWA)
Online gradient and online variational inference

Prediction with expert advice
Examples : air quality / GDP growth
The infinite caseBusiness surveys
Business surveys : forms sent monthly to big companies, andto a sample of small companies. These data are to be taken
into account because

Pierre Alquier, RIKEN AIP

Title

Setting of the problem
Exponentially Weighted Aggregation (EWA)
Online gradient and online variational inference

Prediction with expert advice
Examples : air quality / GDP growth
The infinite caseBusiness surveys
Business surveys : forms sent monthly to big companies, andto a sample of small companies. These data are to be taken
into account because1
they don’t come from economists, but from economic
agents.

Pierre Alquier, RIKEN AIP

Title

Setting of the problem
Exponentially Weighted Aggregation (EWA)
Online gradient and online variational inference

Prediction with expert advice
Examples : air quality / GDP growth
The infinite caseBusiness surveys
Business surveys : forms sent monthly to big companies, andto a sample of small companies. These data are to be taken
into account because1
they don’t come from economists, but from economic
agents.
2
they are available almost immediately. During the 3rdmonth of quarter t, the analysis of the forms for the 1st
and the 2nd months are already known.

Pierre Alquier, RIKEN AIP

Title

Setting of the problem
Exponentially Weighted Aggregation (EWA)
Online gradient and online variational inference

Prediction with expert advice
Examples : air quality / GDP growth
The infinite caseBusiness surveys
Business surveys : forms sent monthly to big companies, andto a sample of small companies. These data are to be taken
into account because1
they don’t come from economists, but from economic
agents.
2
they are available almost immediately. During the 3rdmonth of quarter t, the analysis of the forms for the 1st
and the 2nd months are already known.
→ this information is summarized in the business climate
indicator It−1 .

Pierre Alquier, RIKEN AIP

Title

Setting of the problem
Exponentially Weighted Aggregation (EWA)
Online gradient and online variational inference

Prediction with expert advice
Examples : air quality / GDP growth
The infinite case

The experts
In this paper, M. Cornec
proposed simple econometricmodels that can be seen as
experts :Pierre Alquier, RIKEN AIP

Title

Setting of the problem
Exponentially Weighted Aggregation (EWA)
Online gradient and online variational inference

Prediction with expert advice
Examples : air quality / GDP growth
The infinite case

The experts
In this paper, M. Cornec
proposed simple econometricmodels that can be seen as
experts :1
forecasts similars to
the ones by the mostcomplex models usedby INSEE.

Pierre Alquier, RIKEN AIP

Title

Setting of the problem
Exponentially Weighted Aggregation (EWA)
Online gradient and online variational inference

Prediction with expert advice
Examples : air quality / GDP growth
The infinite case

The experts
In this paper, M. Cornec
proposed simple econometricmodels that can be seen as
experts :1
forecasts similars to
the ones by the mostcomplex models usedby INSEE.
f2

Pierre Alquier, RIKEN AIP

Title\ t is small,when ∆GDP
the accuracy
deteriorates.

Setting of the problem
Exponentially Weighted Aggregation (EWA)
Online gradient and online variational inference

Prediction with expert advice
Examples : air quality / GDP growth
The infinite case

Forecastings

Figure – Using M. Cornec’s predictor and the absolute loss function`(x, x 0 ) = |x − x 0 |.
Pierre Alquier, RIKEN AIP

Title

Setting of the problem
Exponentially Weighted Aggregation (EWA)
Online gradient and online variational inference

Prediction with expert advice
Examples : air quality / GDP growth
The infinite caseConfidence intervals

Figure – Using quantile loss `(x, x 0 ) = (x − x 0 )(τ − 1(x − x 0 < 0)).
Pierre Alquier, RIKEN AIP

Title

Setting of the problem
Exponentially Weighted Aggregation (EWA)
Online gradient and online variational inference

Prediction with expert advice
Examples : air quality / GDP growth
The infinite case

The infinite case
Infinite family of predictors fθ : X → R, θ ∈ Θ.

Pierre Alquier, RIKEN AIP

Title

Setting of the problem
Exponentially Weighted Aggregation (EWA)
Online gradient and online variational inference

Prediction with expert advice
Examples : air quality / GDP growth
The infinite case

The infinite case
Infinite family of predictors fθ : X → R, θ ∈ Θ.
learning rate η > 0.

Pierre Alquier, RIKEN AIP

Title

Setting of the problem
Exponentially Weighted Aggregation (EWA)
Online gradient and online variational inference

Prediction with expert advice
Examples : air quality / GDP growth
The infinite case

The infinite case
Infinite family of predictors fθ : X → R, θ ∈ Θ.
learning rate η > 0.
prior distribution on Θ, p1 = π.

Pierre Alquier, RIKEN AIP

Title

Setting of the problem
Exponentially Weighted Aggregation (EWA)
Online gradient and online variational inference

Prediction with expert advice
Examples : air quality / GDP growth
The infinite case

The infinite case
Infinite family of predictors fθ : X → R, θ ∈ Θ.
learning rate η > 0.
prior distribution on Θ, p1 = π.
Algorithm 3 EWA (general case)
1: for i = R1, 2, . . . do2:ŷt = fθ (xt )pt (dθ),θ (xt ),yt )]pt (dθ)
3:yt revealed, update pt+1 (dθ) = Rexp[−η`(f.
exp[−η`(fϑ (xt ),yt )]pt (dϑ)
4: end for

Pierre Alquier, RIKEN AIP

Title

Setting of the problem
Exponentially Weighted Aggregation (EWA)
Online gradient and online variational inference

Prediction with expert advice
Examples : air quality / GDP growth
The infinite case

Regret bound in the general case
TheoremAssume that 0 ≤ ` ≤ C . Then
T
X
t=1

"Z
`(ŷt , yt ) ≤ infpTX`(fϑ (xt ), yt )p(dϑ)

t=1#
ηC 2 T
KL(p||π)++.
8
η

Pierre Alquier, RIKEN AIP

Title

Setting of the problem
Exponentially Weighted Aggregation (EWA)
Online gradient and online variational inference

Prediction with expert advice
Examples : air quality / GDP growth
The infinite case

Regret bound in the general case
TheoremAssume that 0 ≤ ` ≤ C . Then
T
X
t=1

"Z
`(ŷt , yt ) ≤ infpTX`(fϑ (xt ), yt )p(dϑ)

t=1#
ηC 2 T
KL(p||π)++.
8η
the inf. is with respect to any probability distribution p.

Pierre Alquier, RIKEN AIP

Title

Setting of the problem
Exponentially Weighted Aggregation (EWA)
Online gradient and online variational inference

Prediction with expert advice
Examples : air quality / GDP growth
The infinite case

Regret bound in the general case
TheoremAssume that 0 ≤ ` ≤ C . Then
T
X
t=1

"Z
`(ŷt , yt ) ≤ infpTX`(fϑ (xt ), yt )p(dϑ)

t=1#
ηC 2 T
KL(p||π)++.
8η
the inf. is with respect to any probability distribution p.
KL(p||π) is the Kullback divergence.
Pierre Alquier, RIKEN AIP

Title

Setting of the problem
Exponentially Weighted Aggregation (EWA)
Online gradient and online variational inference

Prediction with expert advice
Examples : air quality / GDP growth
The infinite caseReminderThe Kullback divergence, or relative entropy : R dp 
log dπ(ϑ) p(dϑ) if p  π,KL(p||π) =+∞ otherwise.

Pierre Alquier, RIKEN AIP

Title

Setting of the problem
Exponentially Weighted Aggregation (EWA)
Online gradient and online variational inference

Prediction with expert advice
Examples : air quality / GDP growth
The infinite caseReminderThe Kullback divergence, or relative entropy : R dp 
log dπ(ϑ) p(dϑ) if p  π,KL(p||π) =+∞ otherwise.
When π is uniform on {1, . . . , M} and when p is the Diracmass on i ∈ {1, . . . , M} thenKL(p||π) = log(M)so the result in the finite case is indeed a corollary of thegeneral result.
Pierre Alquier, RIKEN AIP

Title

Setting of the problem
Exponentially Weighted Aggregation (EWA)
Online gradient and online variational inference

Prediction with expert advice
Examples : air quality / GDP growth
The infinite case

Link with Bayesian statistics
pt+1 (dθ) ∝ exp[−η`(fθ (xt ), yt )]pt (dθ( t)Yexp[−η`(fθ (xi ), yi )] π(dθ).
∝
i=1Pierre Alquier, RIKEN AIP

Title

Setting of the problem
Exponentially Weighted Aggregation (EWA)
Online gradient and online variational inference

Prediction with expert advice
Examples : air quality / GDP growth
The infinite case

Link with Bayesian statistics
pt+1 (dθ) ∝ exp[−η`(fθ (xt ), yt )]pt (dθ( t)Yexp[−η`(fθ (xi ), yi )] π(dθ).
∝
i=1Assume xt deterministic, yt ∼ N (fθ∗ (xt ), σ 2 ), take η = 1 and−y 0 )2. Then the likelihood is given by`(y , y 0 ) = (y 2σ2L(θ, y1 , . . . , yt ) =tY

exp[−η`(fθ (xi ), yi )]i=1

Pierre Alquier, RIKEN AIP

Title

Setting of the problem
Exponentially Weighted Aggregation (EWA)
Online gradient and online variational inference

Prediction with expert advice
Examples : air quality / GDP growth
The infinite case

Link with Bayesian statistics
pt+1 (dθ) ∝ exp[−η`(fθ (xt ), yt )]pt (dθ( t)Yexp[−η`(fθ (xi ), yi )] π(dθ).
∝
i=1Assume xt deterministic, yt ∼ N (fθ∗ (xt ), σ 2 ), take η = 1 and−y 0 )2. Then the likelihood is given by`(y , y 0 ) = (y 2σ2L(θ, y1 , . . . , yt ) =tY

exp[−η`(fθ (xi ), yi )]i=1⇒ pt+1 (dθ) ∝ L(θ, y1 , . . . , yt )π(dθ) ∝ π(θ|y1 , . . . , yt ).
Pierre Alquier, RIKEN AIP

Title

Setting of the problem
Exponentially Weighted Aggregation (EWA)
Online gradient and online variational inference

Online gradient algorithm
Example : glass identification
Online variational inference

Online gradient and online variational inference
1

Setting of the problem
Definitions
Toy examples
The regret

2

Exponentially Weighted Aggregation (EWA)
Prediction with expert advice
Examples : air quality / GDP growth
The infinite case3

Online gradient and online variational inference
Online gradient algorithm
Example : glass identification
Online variational inference
Pierre Alquier, RIKEN AIP

Title

Setting of the problem
Exponentially Weighted Aggregation (EWA)
Online gradient and online variational inference

Online gradient algorithm
Example : glass identification
Online variational inferenceContext
1

1
2
3

2

1
2
3

x1 given
predict y1 : ŷ1
y1 is revealed, we suffer loss `(ŷ1 , y1 ).
x2 given
predict y2 : ŷ2y2 revealed, we suffer loss `(ŷ2 , y2 ).

...
and this time, we would like to use a model like3ŷt = hθt , xt i .

Pierre Alquier, RIKEN AIP

Title

Setting of the problem
Exponentially Weighted Aggregation (EWA)
Online gradient and online variational inference

Online gradient algorithm
Example : glass identification
Online variational inferenceContext
1

1
2
3

2

1
2
3

x1 given
predict y1 : ŷ1
y1 is revealed, we suffer loss `(ŷ1 , y1 ).
x2 given
predict y2 : ŷ2y2 revealed, we suffer loss `(ŷ2 , y2 ).

...
and this time, we would like to use a model like3ŷt = hθt , xt i .
More generally, we study ŷt = g (θt , xt ).
Pierre Alquier, RIKEN AIP

Title

Setting of the problem
Exponentially Weighted Aggregation (EWA)
Online gradient and online variational inference

Online gradient algorithm
Example : glass identification
Online variational inference

OGA
Input :
learning rate η > 0,starting value θ1 , often 0,
link function g (θ, x) convex in θ, loss `(y , y 0 ) convex in y .

Pierre Alquier, RIKEN AIP

Title

Setting of the problem
Exponentially Weighted Aggregation (EWA)
Online gradient and online variational inference

Online gradient algorithm
Example : glass identification
Online variational inference

OGA
Input :
learning rate η > 0,starting value θ1 , often 0,
link function g (θ, x) convex in θ, loss `(y , y 0 ) convex in y .
Algorithm 3 OGA
1: for i = 1, 2, . . . do
2:
Predict ŷt = g (θt , xt ),3:
yt revealed, updateθt+1 = θt − η∂`(g (θt , xt ), yt ).
∂θ

4: end for
Pierre Alquier, RIKEN AIP

Title

Setting of the problem
Exponentially Weighted Aggregation (EWA)
Online gradient and online variational inference

Online gradient algorithm
Example : glass identification
Online variational inference

OGA - theorem
TheoremAssume that θ 7→ `(g (θ, x), y ) is convex and L-Lispchitz withrespect to θ, then :
" T
#
T
X
X
kθk2
`(g (θ, xt ), yt ) +`(ŷt , yt ) ≤ inf+ ηTL2 .
2η
θ∈Rd
t=1
t=1

Pierre Alquier, RIKEN AIP

Title

Setting of the problem
Exponentially Weighted Aggregation (EWA)
Online gradient and online variational inference

Online gradient algorithm
Example : glass identification
Online variational inference

OGA - theorem
TheoremAssume that θ 7→ `(g (θ, x), y ) is convex and L-Lispchitz withrespect to θ, then :
" T
#
T
X
X
kθk2
`(g (θ, xt ), yt ) +`(ŷt , yt ) ≤ inf+ ηTL2 .
2η
θ∈Rd
t=1
t=1
Choose B > 0 and η = L√B2T to obtain :TX
t=1`(ŷt , yt ) ≤ inf

kθk≤B

T
X

√
`(g (θ, xt ), yt ) + BL 2T .

t=1

Pierre Alquier, RIKEN AIP

Title

Setting of the problem
Exponentially Weighted Aggregation (EWA)
Online gradient and online variational inference

Online gradient algorithm
Example : glass identification
Online variational inference

OGA - theorem
TheoremAssume that θ 7→ `(g (θ, x), y ) is convex and L-Lispchitz withrespect to θ, then :
" T
#
T
X
X
kθk2
`(g (θ, xt ), yt ) +`(ŷt , yt ) ≤ inf+ ηTL2 .
2η
θ∈Rd
t=1
t=1
Choose B > 0 and η = L√B2T to obtain :TX
t=1`(ŷt , yt ) ≤ inf

kθk≤B

T
X

√
`(g (θ, xt ), yt ) + BL 2T .

t=1

The choice ηt = L√B2t leads to similar rate with worse constant.
Pierre Alquier, RIKEN AIP

Title

Setting of the problem
Exponentially Weighted Aggregation (EWA)
Online gradient and online variational inference

Online gradient algorithm
Example : glass identification
Online variational inference

Example : glass identification

Pierre Alquier, RIKEN AIP

Title

Setting of the problem
Exponentially Weighted Aggregation (EWA)
Online gradient and online variational inference

Online gradient algorithm
Example : glass identification
Online variational inference

Example : glass identification

Pierre Alquier, RIKEN AIP

Title

Setting of the problem
Exponentially Weighted Aggregation (EWA)
Online gradient and online variational inference

Online gradient algorithm
Example : glass identification
Online variational inference

Glass identification
Dataset from the Machine Learning Repository :https ://archive.ics.uci.edu/ml/index.php
yt = 1 (window) or yt = −1 (non window) ; attributes : xt
(chemical composition).

Pierre Alquier, RIKEN AIP

Title

Setting of the problem
Exponentially Weighted Aggregation (EWA)
Online gradient and online variational inference

Online gradient algorithm
Example : glass identification
Online variational inference

Glass identification
Dataset from the Machine Learning Repository :https ://archive.ics.uci.edu/ml/index.php
yt = 1 (window) or yt = −1 (non window) ; attributes : xt
(chemical composition).
Prediction : ŷt = hθt , xt i. Loss : `(ŷ , y ) = (1 − ŷ y )+ .

Pierre Alquier, RIKEN AIP

Title

Setting of the problem
Exponentially Weighted Aggregation (EWA)
Online gradient and online variational inference

Online gradient algorithm
Example : glass identification
Online variational inference

Glass identification
Dataset from the Machine Learning Repository :https ://archive.ics.uci.edu/ml/index.php
yt = 1 (window) or yt = −1 (non window) ; attributes : xt
(chemical composition).
Prediction : ŷt = hθt , xt i. Loss : `(ŷ , y ) = (1 − ŷ y )+ .
∂
−yt xt if sign(< θt , xt >) 6= yt`(< θt , xt >, yt ) =0 otherwise,∂θ

Pierre Alquier, RIKEN AIP

Title

Setting of the problem
Exponentially Weighted Aggregation (EWA)
Online gradient and online variational inference

Online gradient algorithm
Example : glass identification
Online variational inference

Glass identification
Dataset from the Machine Learning Repository :https ://archive.ics.uci.edu/ml/index.php
yt = 1 (window) or yt = −1 (non window) ; attributes : xt
(chemical composition).
Prediction : ŷt = hθt , xt i. Loss : `(ŷ , y ) = (1 − ŷ y )+ .
∂
−yt xt if sign(< θt , xt >) 6= yt`(< θt , xt >, yt ) =0 otherwise,∂θ

Pierre Alquier, RIKEN AIP

Title

Setting of the problem
Exponentially Weighted Aggregation (EWA)
Online gradient and online variational inference

Online gradient algorithm
Example : glass identification
Online variational inference

Online gradient and online variational inference
1

Setting of the problem
Definitions
Toy examples
The regret

2

Exponentially Weighted Aggregation (EWA)
Prediction with expert advice
Examples : air quality / GDP growth
The infinite case3

Online gradient and online variational inference
Online gradient algorithm
Example : glass identification
Online variational inference
Pierre Alquier, RIKEN AIP

Title

Setting of the problem
Exponentially Weighted Aggregation (EWA)
Online gradient and online variational inference

Online gradient algorithm
Example : glass identification
Online variational inference

Co-authors

Approximate Bayesian Inference teamhttps : //emtiyaz.github.io/

Chérief-Abdellatif, B.-E., Alquier, P. and Khan, M. E. (2019). A Generalization Bound for Online
Variational Inference. ACML.
Pierre Alquier, RIKEN AIP

Title

Setting of the problem
Exponentially Weighted Aggregation (EWA)
Online gradient and online variational inference

Online gradient algorithm
Example : glass identification
Online variational inference

Bayes and computational efficiency(Generalized) Bayes rule non feasible in complex models"
exp −η

T−1
X#`(fθ (xt ), yt ) π(θ)

t=1Pierre Alquier, RIKEN AIP

Title

Setting of the problem
Exponentially Weighted Aggregation (EWA)
Online gradient and online variational inference

Online gradient algorithm
Example : glass identification
Online variational inference

Bayes and computational efficiency(Generalized) Bayes rule non feasible in complex models"
exp −η

T−1
X#`(fθ (xt ), yt ) π(θ) ← minp

t=1

Pierre Alquier, RIKEN AIP

T
−1
X
t=1

Title

Eθ∼p [`(fθ (xt ), yt )] +KL(p||π)ηSetting of the problem
Exponentially Weighted Aggregation (EWA)
Online gradient and online variational inference

Online gradient algorithm
Example : glass identification
Online variational inference

Bayes and computational efficiency(Generalized) Bayes rule non feasible in complex models"
exp −η

T−1
X#`(fθ (xt ), yt ) π(θ) ← min
p

t=1

T
−1
X
t=1

Eθ∼p [`(fθ (xt ), yt )] +KL(p||π)η

We will propose a feasible version thanks to the ideas in :Pierre Alquier, RIKEN AIP

Title

Setting of the problem
Exponentially Weighted Aggregation (EWA)
Online gradient and online variational inference

Online gradient algorithm
Example : glass identification
Online variational inference

Online variational inference

propose a parametric family of probability distributions :(qµ ).
approximate pt by some qµt .

Pierre Alquier, RIKEN AIP

Title

Setting of the problem
Exponentially Weighted Aggregation (EWA)
Online gradient and online variational inference

Online gradient algorithm
Example : glass identification
Online variational inference

Online variational inference

propose a parametric family of probability distributions :(qµ ).
approximate pt by some qµt .
How ? We could for example perform an online gradientalgorithm on µ for :Eθ∼qµ [`(fθ (xt ), yt )].

Pierre Alquier, RIKEN AIP

Title

Setting of the problem
Exponentially Weighted Aggregation (EWA)
Online gradient and online variational inference

Online gradient algorithm
Example : glass identification
Online variational inference

Online variational inference

propose a parametric family of probability distributions :(qµ ).
approximate pt by some qµt .
How ? We could for example perform an online gradientalgorithm on µ for :Eθ∼qµ [`(fθ (xt ), yt )].
But there is a better thing to do...

Pierre Alquier, RIKEN AIP

Title

Setting of the problem
Exponentially Weighted Aggregation (EWA)
Online gradient and online variational inference

Online gradient algorithm
Example : glass identification
Online variational inferenceReminder on online gradientŷt = fθt (xt ) and θt+1 = θt − η∇θ `(fθt (xt ), yt ).

Pierre Alquier, RIKEN AIP

Title

Setting of the problem
Exponentially Weighted Aggregation (EWA)
Online gradient and online variational inference

Online gradient algorithm
Example : glass identification
Online variational inferenceReminder on online gradientŷt = fθt (xt ) and θt+1 = θt − η∇θ `t (θt ).

Pierre Alquier, RIKEN AIP

Title

Setting of the problem
Exponentially Weighted Aggregation (EWA)
Online gradient and online variational inference

Online gradient algorithm
Example : glass identification
Online variational inferenceReminder on online gradientŷt = fθt (xt ) and θt+1 = θt − η∇θ `t (θt ).
Note that θt+1 can be obtained by :
(* t
+
)
X
kθ − θ1 k2
1minθ,∇θ `s (θs ) +
,
θ
2η
s=1
)
(
D
E kθ − θ k2
t
2
.
min
θ, ∇θ `t (θt ) +θ
2η

Pierre Alquier, RIKEN AIP

Title

Setting of the problem
Exponentially Weighted Aggregation (EWA)
Online gradient and online variational inference

Online gradient algorithm
Example : glass identification
Online variational inference

Two options for online VI

Pierre Alquier, RIKEN AIP

Title

Setting of the problem
Exponentially Weighted Aggregation (EWA)
Online gradient and online variational inference

Online gradient algorithm
Example : glass identification
Online variational inference

Two options for online VI
1

Sequential Variational Approximation (SVA) :
+
(* t
)
X
kθ − θ1 k2
θ,,
θt+1 = arg min∇θ `s (θs ) +
θ
2η
s=1

2

Streaming Variational Bayes (SVB) :()
D
E kθ − θ k2t
θt+1 = arg minθ, ∇θ `t (θt ) +,θ
2η

Pierre Alquier, RIKEN AIP

Title

Setting of the problem
Exponentially Weighted Aggregation (EWA)
Online gradient and online variational inference

Online gradient algorithm
Example : glass identification
Online variational inference

Two options for online VI
1

Sequential Variational Approximation (SVA) :
+
(* t
)
X
kθ − θ1 k2
θ,,
θt+1 = arg min∇θ `s (θs ) +
θ
2η
s=1
(*
+
)
t
X
KL(qµ , π)µ,µt+1 = arg min∇µ Eθ∼qµs [`s (θ)] +
.
µ
η
s=1

2

Streaming Variational Bayes (SVB) :()
D
E kθ − θ k2t
θt+1 = arg minθ, ∇θ `t (θt ) +,θ
2η

Pierre Alquier, RIKEN AIP

Title

Setting of the problem
Exponentially Weighted Aggregation (EWA)
Online gradient and online variational inference

Online gradient algorithm
Example : glass identification
Online variational inference

Two options for online VI
1

Sequential Variational Approximation (SVA) :
+
(* t
)
X
kθ − θ1 k2
θ,,
θt+1 = arg min∇θ `s (θs ) +
θ
2η
s=1
(*
+
)
t
X
KL(qµ , π)µ,µt+1 = arg min∇µ Eθ∼qµs [`s (θ)] +
.
µ
η
s=1

2

Streaming Variational Bayes (SVB) :()
D
E kθ − θ k2t
θt+1 = arg minθ, ∇θ `t (θt ) +
,
θ
2η
D
E KL(q , q ) µ µtµt+1 = arg minµ, ∇µ Eθ∼qµt [`t (θ)] +.
µη
Pierre Alquier, RIKEN AIP

Title

Setting of the problem
Exponentially Weighted Aggregation (EWA)
Online gradient and online variational inference

Online gradient algorithm
Example : glass identification
Online variational inference

SVA & SVB are tractable, and not equivalent
Example : Gaussian prior θ ∼ π = N (0, s 2 I ) and mean-field
Gaussian approximation, µ = (m, σ).
SVA : mt+1 ← mt − ηs 2 ḡmt ,σt+1 ← h (ηsgt+1 ) s,

gt+1 ← gt + ḡσt ,SVB : mt+1 ← mt − ησt2 ḡmt ,σt+1 ← σt h (ησt ḡσt )√where h(x) := 1 + x 2 − x is applied componentwise, as wellas the multiplication of two vectors, and∂ḡmt =
Eθ∼πmt ,σt [`t (θ)],∂m∂ḡσt =
Eθ∼πmt ,σt [`t (θ)].
∂σ
Pierre Alquier, RIKEN AIP

Title

Setting of the problem
Exponentially Weighted Aggregation (EWA)
Online gradient and online variational inference

Online gradient algorithm
Example : glass identification
Online variational inference

Theoretical analysis of SVA
Theorem 1
Under convexity and L-Lipschitz assumption on the loss, underα-strong convexity assumption on the KL term, SVA leads toTXEθ∼qµt [`t (θ)]
t=1

≤ inf

µ∈M

( T
X

KL(qµ , π)
ηL2 T+Eθ∼qµ [`t (θ)] +αη
t=1Pierre Alquier, RIKEN AIP

Title

)
.

Setting of the problem
Exponentially Weighted Aggregation (EWA)
Online gradient and online variational inference

Online gradient algorithm
Example : glass identification
Online variational inference

Theoretical analysis of SVA
Theorem 1
Under convexity and L-Lipschitz assumption on the loss, underα-strong convexity assumption on the KL term, SVA leads toTXEθ∼qµt [`t (θ)]
t=1

≤ inf

µ∈M

( T
X

KL(qµ , π)
ηL2 T+Eθ∼qµ [`t (θ)] +
α
η
t=1

)
.

Application to Gaussian approximation leads toTX
t=1

Eθ∼qµt [`t (θ)] ≤ infθTX`t (θ) + (1 + o(1))

t=1Pierre Alquier, RIKEN AIP

Title

2L p
dT log(T ).
αSetting of the problem
Exponentially Weighted Aggregation (EWA)
Online gradient and online variational inference

Online gradient algorithm
Example : glass identification
Online variational inference

Theoretical analysis of SVB
Theorem 2
Using Gaussian approximations, assuming the loss is convex,
L-Lipschitz and the parameter space bounded (diameter = D),
SVB with adequate η leads to
T
T


X
X
√
`t Eθ∼qµt (θ) ≤ inf`t (θ) + DL 2T .
θ

t=1

Pierre Alquier, RIKEN AIP

t=1

Title

Setting of the problem
Exponentially Weighted Aggregation (EWA)
Online gradient and online variational inference

Online gradient algorithm
Example : glass identification
Online variational inference

Theoretical analysis of SVB
Theorem 2
Using Gaussian approximations, assuming the loss is convex,
L-Lipschitz and the parameter space bounded (diameter = D),
SVB with adequate η leads to
T
T


X
X
√
`t Eθ∼qµt (θ) ≤ inf`t (θ) + DL 2T .
θ

t=1

t=1

If, moreover, the loss is H-strongly convex,
T
T


X
X
L2 (1 + log(T ))`t Eθ∼qµt (θ) ≤ inf`t (θ) +
.
θ
H
t=1
t=1
Pierre Alquier, RIKEN AIP

Title

Setting of the problem
Exponentially Weighted Aggregation (EWA)
Online gradient and online variational inference

Online gradient algorithm
Example : glass identification
Online variational inference

Test on a simulated dataset

Figure – Average cumulative losses on different datasets forclassification and regression tasks with OGA (yellow), OGA-EL(red), SVA (blue), SVB (purple) and NGVI (green).
Pierre Alquier, RIKEN AIP

Title

Setting of the problem
Exponentially Weighted Aggregation (EWA)
Online gradient and online variational inference

Online gradient algorithm
Example : glass identification
Online variational inference

Test on the Breast dataset

Figure – Average cumulative losses on different datasets forclassification and regression tasks with OGA (yellow), OGA-EL(red), SVA (blue), SVB (purple) and NGVI (green).
Pierre Alquier, RIKEN AIP

Title

Setting of the problem
Exponentially Weighted Aggregation (EWA)
Online gradient and online variational inference

Online gradient algorithm
Example : glass identification
Online variational inference

Open questions

Pierre Alquier, RIKEN AIP

Title

Setting of the problem
Exponentially Weighted Aggregation (EWA)
Online gradient and online variational inference

Online gradient algorithm
Example : glass identification
Online variational inference

Open questions
1

Analysis of SVB in the general case.

Pierre Alquier, RIKEN AIP

Title

Setting of the problem
Exponentially Weighted Aggregation (EWA)
Online gradient and online variational inference

Online gradient algorithm
Example : glass identification
Online variational inference

Open questions
1
2

Analysis of SVB in the general case.
Analysis of the uncertainty quantification.

Pierre Alquier, RIKEN AIP

Title

Setting of the problem
Exponentially Weighted Aggregation (EWA)
Online gradient and online variational inference

Online gradient algorithm
Example : glass identification
Online variational inference

Open questions
1
2
3

Analysis of SVB in the general case.
Analysis of the uncertainty quantification.
NGVI is the next step in going closer to algorithms used
to train Neural Networks with Bayesian principles. But
being based on a different parametrization, it does notsatisfy our convexity assumption...

Pierre Alquier, RIKEN AIP

Title

Setting of the problem
Exponentially Weighted Aggregation (EWA)
Online gradient and online variational inference

Online gradient algorithm
Example : glass identification
Online variational inference

Open questions
1
2
3

Analysis of SVB in the general case.
Analysis of the uncertainty quantification.
NGVI is the next step in going closer to algorithms used
to train Neural Networks with Bayesian principles. But
being based on a different parametrization, it does notsatisfy our convexity assumption...
Uses exponential family approximations {qµ , µ ∈ M}
where m is the mean parameter. Denoting λ the naturalparameter (with λ = F (µ)),λt+1 = (1 − ρ)λt + ρ∇µ Eθ∼qµt [`t (θ)] ,M. E. Khan, D. Nielsen (2018). Fast yet Simple Natural-Gradient Descent for Variational
Inference in Complex Models. ISITA.
Pierre Alquier, RIKEN AIP

Title

Setting of the problem
Exponentially Weighted Aggregation (EWA)
Online gradient and online variational inference

Online gradient algorithm
Example : glass identification
Online variational inference

Thank you !

Pierre Alquier, RIKEN AIP

Title