Setting of the problem
Exponentially Weighted Aggregation (EWA)Open questions

Introduction to Sequential Prediction
Pierre Alquier

London Business School, Nov. 14, 2018
Pierre Alquier

Introduction to Sequential Prediction

Setting of the problem
Exponentially Weighted Aggregation (EWA)Open questions

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

Pierre Alquier

Introduction to Sequential Prediction

Setting of the problem
Exponentially Weighted Aggregation (EWA)Open questions

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

1x1 given

Pierre Alquier

Introduction to Sequential Prediction

Setting of the problem
Exponentially Weighted Aggregation (EWA)Open questions

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

x1 given
predict y1 : ŷ1

Pierre Alquier

Introduction to Sequential Prediction

Setting of the problem
Exponentially Weighted Aggregation (EWA)Open questions

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

1
2
3

x1 given
predict y1 : ŷ1
y1 is revealed

Pierre Alquier

Introduction to Sequential Prediction

Setting of the problem
Exponentially Weighted Aggregation (EWA)Open questions

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

Introduction to Sequential Prediction

Setting of the problem
Exponentially Weighted Aggregation (EWA)Open questions

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

Introduction to Sequential Prediction

Setting of the problem
Exponentially Weighted Aggregation (EWA)Open questions

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

Introduction to Sequential Prediction

Setting of the problem
Exponentially Weighted Aggregation (EWA)Open questions

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

Introduction to Sequential Prediction

Setting of the problem
Exponentially Weighted Aggregation (EWA)Open questions

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

Introduction to Sequential Prediction

Setting of the problem
Exponentially Weighted Aggregation (EWA)Open questions

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

Introduction to Sequential Prediction

Setting of the problem
Exponentially Weighted Aggregation (EWA)Open questions

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

Introduction to Sequential Prediction

Setting of the problem
Exponentially Weighted Aggregation (EWA)Open questions

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

Introduction to Sequential Prediction

Setting of the problem
Exponentially Weighted Aggregation (EWA)Open questions

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 revealed

TX

1(Ŷt 6= Yt )t=1

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

Pierre Alquier

Introduction to Sequential Prediction

Setting of the problem
Exponentially Weighted Aggregation (EWA)Open questions

References

Pierre Alquier

Introduction to Sequential Prediction

Setting of the problem
Exponentially Weighted Aggregation (EWA)Open questions

Outline of the talk1

Setting of the problem
Definitions
Toy examples
The regret

2

Exponentially Weighted Aggregation (EWA)
Prediction with expert advice
Further topics
The infinite case

3

Open questions
Confidence intervals
Fast algorithms
More open questions
Pierre Alquier

Introduction to Sequential Prediction

Setting of the problem
Exponentially Weighted Aggregation (EWA)Open questions

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
Further topics
The infinite case

3

Open questions
Confidence intervals
Fast algorithms
More open questions
Pierre Alquier

Introduction to Sequential Prediction

Setting of the problem
Exponentially Weighted Aggregation (EWA)Open questions

Definitions
Toy examples
The regret

Notations : loss function
General notations

Pierre Alquier

Introduction to Sequential Prediction

Setting of the problem
Exponentially Weighted Aggregation (EWA)Open questions

Definitions
Toy examples
The regret

Notations : loss function
General notations
xt ∈ X .

Pierre Alquier

Introduction to Sequential Prediction

Setting of the problem
Exponentially Weighted Aggregation (EWA)Open questions

Definitions
Toy examples
The regret

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

Pierre Alquier

Introduction to Sequential Prediction

Setting of the problem
Exponentially Weighted Aggregation (EWA)Open questions

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

Introduction to Sequential Prediction

Setting of the problem
Exponentially Weighted Aggregation (EWA)Open questions

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 loss
function `.

Pierre Alquier

Introduction to Sequential Prediction

Setting of the problem
Exponentially Weighted Aggregation (EWA)Open questions

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 loss
function `.
Classical examples :Pierre Alquier

Introduction to Sequential Prediction

Setting of the problem
Exponentially Weighted Aggregation (EWA)Open questions

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 loss
function `.
Classical examples :`(y , y 0 ) = a1(y = 1, y 0 = 0) + b1(y = 0, y 0 = 1) for
classification,

Pierre Alquier

Introduction to Sequential Prediction

Setting of the problem
Exponentially Weighted Aggregation (EWA)Open questions

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 loss
function `.
Classical examples :`(y , y 0 ) = a1(y = 1, y 0 = 0) + b1(y = 0, y 0 = 1) for
classification,`(y , y 0 ) = (y − y 0 )2 or `(y , y 0 ) = |y − y 0 | for regression,

Pierre Alquier

Introduction to Sequential Prediction

Setting of the problem
Exponentially Weighted Aggregation (EWA)Open questions

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 loss
function `.
Classical examples :`(y , y 0 ) = a1(y = 1, y 0 = 0) + b1(y = 0, y 0 = 1) for
classification,`(y , y 0 ) = (y − y 0 )2 or `(y , y 0 ) = |y − y 0 | for regression,...
Pierre Alquier

Introduction to Sequential Prediction

Setting of the problem
Exponentially Weighted Aggregation (EWA)Open questions

Definitions
Toy examples
The regret

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

Introduction to Sequential Prediction

Setting of the problem
Exponentially Weighted Aggregation (EWA)Open questions

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

Introduction to Sequential Prediction

Setting of the problem
Exponentially Weighted Aggregation (EWA)Open questions

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

Introduction to Sequential Prediction

Setting of the problem
Exponentially Weighted Aggregation (EWA)Open questions

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

Introduction to Sequential Prediction

Setting of the problem
Exponentially Weighted Aggregation (EWA)Open questions

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

Introduction to Sequential Prediction

Setting of the problem
Exponentially Weighted Aggregation (EWA)Open questions

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

Introduction to Sequential Prediction

Setting of the problem
Exponentially Weighted Aggregation (EWA)Open questions

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

Introduction to Sequential Prediction

Setting of the problem
Exponentially Weighted Aggregation (EWA)Open questions

Definitions
Toy examples
The regret

Prediction strategy

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

Pierre Alquier

Introduction to Sequential Prediction

Setting of the problem
Exponentially Weighted Aggregation (EWA)Open questions

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 ). We can also use
randomization if necessary.

Pierre Alquier

Introduction to Sequential Prediction

Setting of the problem
Exponentially Weighted Aggregation (EWA)Open questions

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 ). We can also use
randomization if necessary.
It must be computationnally feasible.

Pierre Alquier

Introduction to Sequential Prediction

Setting of the problem
Exponentially Weighted Aggregation (EWA)Open questions

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 ). We can also use
randomization if necessary.
It must be computationnally feasible.
We can use expert advice.

Pierre Alquier

Introduction to Sequential Prediction

Setting of the problem
Exponentially Weighted Aggregation (EWA)Open questions

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

Introduction to Sequential Prediction

Setting of the problem
Exponentially Weighted Aggregation (EWA)Open questions

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

Introduction to Sequential Prediction

Setting of the problem
Exponentially Weighted Aggregation (EWA)Open questions

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

Introduction to Sequential Prediction

Setting of the problem
Exponentially Weighted Aggregation (EWA)Open questions

Definitions
Toy examples
The regret

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

Pierre Alquier

Introduction to Sequential Prediction

Setting of the problem
Exponentially Weighted Aggregation (EWA)Open questions

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

Introduction to Sequential Prediction

Setting of the problem
Exponentially Weighted Aggregation (EWA)Open questions

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

Introduction to Sequential Prediction

Setting of the problem
Exponentially Weighted Aggregation (EWA)Open questions

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

Introduction to Sequential Prediction

Setting of the problem
Exponentially Weighted Aggregation (EWA)Open questions

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

Introduction to Sequential Prediction

Setting of the problem
Exponentially Weighted Aggregation (EWA)Open questions

Definitions
Toy examples
The regret

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

Pierre Alquier

Introduction to Sequential Prediction

Setting of the problem
Exponentially Weighted Aggregation (EWA)Open questions

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

Introduction to Sequential Prediction

Setting of the problem
Exponentially Weighted Aggregation (EWA)Open questions

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

Introduction to Sequential Prediction

Setting of the problem
Exponentially Weighted Aggregation (EWA)Open questions

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

Introduction to Sequential Prediction

Setting of the problem
Exponentially Weighted Aggregation (EWA)Open questions

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

Introduction to Sequential Prediction

Setting of the problem
Exponentially Weighted Aggregation (EWA)Open questions

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

Introduction to Sequential Prediction

Setting of the problem
Exponentially Weighted Aggregation (EWA)Open questions

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

Introduction to Sequential Prediction

Setting of the problem
Exponentially Weighted Aggregation (EWA)Open questions

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

}

+

B(T )
| {z }

as small as possible ! !

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

Pierre Alquier

Introduction to Sequential Prediction.

Setting of the problem
Exponentially Weighted Aggregation (EWA)Open questions

Definitions
Toy examples
The regret

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

f ∈F

t=1

Pierre AlquierTX`(f (xt ), yt )+B(T )t=1

Introduction to Sequential Prediction

Setting of the problem
Exponentially Weighted Aggregation (EWA)Open questions

Definitions
Toy examples
The regret

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

f ∈F

t=1

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

Introduction to Sequential Prediction

Setting of the problem
Exponentially Weighted Aggregation (EWA)Open questions

Definitions
Toy examples
The regret

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

f ∈F

t=1

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

Introduction to Sequential Prediction

Setting of the problem
Exponentially Weighted Aggregation (EWA)Open questions

Definitions
Toy examples
The regret

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

f ∈F

t=1

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

Introduction to Sequential Prediction

Setting of the problem
Exponentially Weighted Aggregation (EWA)Open questions

Definitions
Toy examples
The regret

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

f ∈F

t=1

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

Introduction to Sequential Prediction

Setting of the problem
Exponentially Weighted Aggregation (EWA)Open questions

Definitions
Toy examples
The regret

Important remarks
1

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

Pierre Alquier

Introduction to Sequential Prediction

Setting of the problem
Exponentially Weighted Aggregation (EWA)Open questions

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 AlquierTX`(f (xt ), yt ) + B(T ).

t=1

Introduction to Sequential Prediction

Setting of the problem
Exponentially Weighted Aggregation (EWA)Open questions

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

Introduction to Sequential Prediction

Setting of the problem
Exponentially Weighted Aggregation (EWA)Open questions

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

Introduction to Sequential Prediction

Setting of the problem
Exponentially Weighted Aggregation (EWA)Open questions

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

Introduction to Sequential Prediction

Setting of the problem
Exponentially Weighted Aggregation (EWA)Open questions

Prediction with expert advice
Further topics
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
Further topics
The infinite case

3

Open questions
Confidence intervals
Fast algorithms
More open questions
Pierre Alquier

Introduction to Sequential Prediction

Setting of the problem
Exponentially Weighted Aggregation (EWA)Open questions

Prediction with expert advice
Further topics
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

Introduction to Sequential Prediction

Setting of the problem
Exponentially Weighted Aggregation (EWA)Open questions

Prediction with expert advice
Further topics
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

Introduction to Sequential Prediction

Setting of the problem
Exponentially Weighted Aggregation (EWA)Open questions

Prediction with expert advice
Further topics
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(yi − β T xi )2 .

i=1
Introduction to Sequential Prediction

Setting of the problem
Exponentially Weighted Aggregation (EWA)Open questions

Prediction with expert advice
Further topics
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

Introduction to Sequential Prediction

Setting of the problem
Exponentially Weighted Aggregation (EWA)Open questions

Prediction with expert advice
Further topics
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

Introduction to Sequential Prediction

Setting of the problem
Exponentially Weighted Aggregation (EWA)Open questions

Prediction with expert advice
Further topics
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 Alquieri=1,...,M

T
X

(i)

`(ŷt , yt )≤?

t=1

Introduction to Sequential Prediction

Setting of the problem
Exponentially Weighted Aggregation (EWA)Open questions

Prediction with expert advice
Further topics
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

Introduction to Sequential Prediction

Setting of the problem
Exponentially Weighted Aggregation (EWA)Open questions

Prediction with expert advice
Further topics
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,yt )]

5: end for

Pierre Alquier

Introduction to Sequential Prediction

Setting of the problem
Exponentially Weighted Aggregation (EWA)Open questions

Prediction with expert advice
Further topics
The infinite case

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

Setting of the problem
Exponentially Weighted Aggregation (EWA)Open questions

Prediction with expert advice
Further topics
The infinite case

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

r

ηC 2 T
log(M)+8η

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

Pierre Alquierr

T log(M).
2

Introduction to Sequential Prediction

Setting of the problem
Exponentially Weighted Aggregation (EWA)Open questions

Prediction with expert advice
Further topics
The infinite case

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

r

ηC 2 T
log(M)+8η

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

Introduction to Sequential Prediction

Setting of the problem
Exponentially Weighted Aggregation (EWA)Open questions

Prediction with expert advice
Further topics
The infinite case

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

r

ηC 2 T
log(M)+8η

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

Introduction to Sequential Prediction

Setting of the problem
Exponentially Weighted Aggregation (EWA)Open questions

Prediction with expert advice
Further topics
The infinite case

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

r

ηC 2 T
log(M)+8η

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

Introduction to Sequential Prediction

Setting of the problem
Exponentially Weighted Aggregation (EWA)Open questions

Prediction with expert advice
Further topics
The infinite case

EWA strategy
Assume that `(·, y ) is convex. Input :learning rate η > 0,weights p1 (1), . . . , p1 (M).

Pierre Alquier

Introduction to Sequential Prediction

Setting of the problem
Exponentially Weighted Aggregation (EWA)Open questions

Prediction with expert advice
Further topics
The infinite case

EWA strategy
Assume that `(·, y ) is convex. 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,yt )]

4: end for

Pierre Alquier

Introduction to Sequential Prediction

Setting of the problem
Exponentially Weighted Aggregation (EWA)Open questions

Prediction with expert advice
Further topics
The infinite case

EWA - convex case
TheoremAssume that `(·, ·) ∈ [0, C ] and `(·, y ) is convex. Then
Regret(T ) ≤Pierre AlquierηC 2 T
log(M)+.
8ηIntroduction to Sequential Prediction

Setting of the problem
Exponentially Weighted Aggregation (EWA)Open questions

Prediction with expert advice
Further topics
The infinite case

EWA - convex case
TheoremAssume that `(·, ·) ∈ [0, C ] and `(·, y ) 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 Alquierr

T log(M).
2

Introduction to Sequential Prediction

Setting of the problem
Exponentially Weighted Aggregation (EWA)Open questions

Prediction with expert advice
Further topics
The infinite case

An example : air quality prediction

Pierre Alquier

Introduction to Sequential Prediction

Setting of the problem
Exponentially Weighted Aggregation (EWA)Open questions

Prediction with expert advice
Further topics
The infinite case

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

Pierre Alquier

Introduction to Sequential Prediction

Setting of the problem
Exponentially Weighted Aggregation (EWA)Open questions

Prediction with expert advice
Further topics
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

Introduction to Sequential Prediction

Setting of the problem
Exponentially Weighted Aggregation (EWA)Open questions

Prediction with expert advice
Further topics
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

Introduction to Sequential Prediction

Setting of the problem
Exponentially Weighted Aggregation (EWA)Open questions

Prediction with expert advice
Further topics
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

Introduction to Sequential Prediction

Setting of the problem
Exponentially Weighted Aggregation (EWA)Open questions

Prediction with expert advice
Further topics
The infinite case

Prediction by the experts

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

Introduction to Sequential Prediction

Setting of the problem
Exponentially Weighted Aggregation (EWA)Open questions

Prediction with expert advice
Further topics
The infinite case

Numerical performances

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

Pierre Alquier

Introduction to Sequential Prediction

Setting of the problem
Exponentially Weighted Aggregation (EWA)Open questions

Prediction with expert advice
Further topics
The infinite case

Weights

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

Introduction to Sequential Prediction

Setting of the problem
Exponentially Weighted Aggregation (EWA)Open questions

Prediction with expert advice
Further topics
The infinite case

Further topics
Better regret bounds
We obtainedpRegret(T ) = O( T log(M))
for EWA.

Pierre Alquier

Introduction to Sequential Prediction

Setting of the problem
Exponentially Weighted Aggregation (EWA)Open questions

Prediction with expert advice
Further topics
The infinite case

Further topics
Better regret bounds
We obtainedpRegret(T ) = O( T log(M))
for EWA. Under a stronger assumption (exp-concave loss `),Regret(T ) = O(log(M)).

Pierre Alquier

Introduction to Sequential Prediction

Setting of the problem
Exponentially Weighted Aggregation (EWA)Open questions

Prediction with expert advice
Further topics
The infinite case

Further topics
Better regret bounds
We obtainedpRegret(T ) = O( T log(M))
for EWA. Under a stronger assumption (exp-concave loss `),Regret(T ) = O(log(M)).
Other strategies
See the introduction by Shalev-Shwartz :online ridge regression,

Pierre Alquier

Introduction to Sequential Prediction

Setting of the problem
Exponentially Weighted Aggregation (EWA)Open questions

Prediction with expert advice
Further topics
The infinite case

Further topics
Better regret bounds
We obtainedpRegret(T ) = O( T log(M))
for EWA. Under a stronger assumption (exp-concave loss `),Regret(T ) = O(log(M)).
Other strategies
See the introduction by Shalev-Shwartz :online ridge regression, that is itself a special case of
online gradient descent...
Pierre Alquier

Introduction to Sequential Prediction

Setting of the problem
Exponentially Weighted Aggregation (EWA)Open questions

Pierre AlquierPrediction with expert advice
Further topics
The infinite case

Introduction to Sequential Prediction

Setting of the problem
Exponentially Weighted Aggregation (EWA)Open questions

Prediction with expert advice
Further topics
The infinite case

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

Pierre Alquier

Introduction to Sequential Prediction

Setting of the problem
Exponentially Weighted Aggregation (EWA)Open questions

Prediction with expert advice
Further topics
The infinite case

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

Pierre Alquier

Introduction to Sequential Prediction

Setting of the problem
Exponentially Weighted Aggregation (EWA)Open questions

Prediction with expert advice
Further topics
The infinite case

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

Pierre Alquier

Introduction to Sequential Prediction

Setting of the problem
Exponentially Weighted Aggregation (EWA)Open questions

Prediction with expert advice
Further topics
The infinite case

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

Pierre Alquier

Introduction to Sequential Prediction

Setting of the problem
Exponentially Weighted Aggregation (EWA)Open questions

Prediction with expert advice
Further topics
The infinite case

Regret bound in the general case
TheoremAssume that `(·, ·) ∈ [0, C ] (e.g. classification). Then

E

T
X
t=1

"Z

!
`(ŷt , yt )

≤ inf
p

T
X

`(fϑ (xt ), yt )p(dϑ)

t=1#
ηC 2 T
K(p, π)++.
8ηPierre Alquier

Introduction to Sequential Prediction

Setting of the problem
Exponentially Weighted Aggregation (EWA)Open questions

Prediction with expert advice
Further topics
The infinite case

Regret bound in the general case
TheoremAssume that `(·, ·) ∈ [0, C ] (e.g. classification). Then

E

T
X
t=1

"Z

!
`(ŷt , yt )

≤ inf
p

T
X

`(fϑ (xt ), yt )p(dϑ)

t=1#
ηC 2 T
K(p, π)++.
8ηthe expectation is w.r.t the algorithm. Convex case :possible to replace randomization by averaging.

Pierre Alquier

Introduction to Sequential Prediction

Setting of the problem
Exponentially Weighted Aggregation (EWA)Open questions

Prediction with expert advice
Further topics
The infinite case

Regret bound in the general case
TheoremAssume that `(·, ·) ∈ [0, C ] (e.g. classification). Then

E

T
X
t=1

"Z

!
`(ŷt , yt )

≤ inf
p

T
X

`(fϑ (xt ), yt )p(dϑ)

t=1#
ηC 2 T
K(p, π)++.
8ηthe expectation is w.r.t the algorithm. Convex case :possible to replace randomization by averaging.
the inf. is with respect to any probability distribution p.
Pierre Alquier

Introduction to Sequential Prediction

Setting of the problem
Exponentially Weighted Aggregation (EWA)Open questions

Prediction with expert advice
Further topics
The infinite case

Regret bound in the general case
TheoremAssume that `(·, ·) ∈ [0, C ] (e.g. classification). Then

E

T
X
t=1

"Z

!
`(ŷt , yt )

≤ inf
p

T
X

`(fϑ (xt ), yt )p(dϑ)

t=1#
ηC 2 T
K(p, π)++.
8ηthe expectation is w.r.t the algorithm. Convex case :possible to replace randomization by averaging.
the inf. is with respect to any probability distribution p.
K(p, π) is the Kullback divergence.
Pierre Alquier

Introduction to Sequential Prediction

Setting of the problem
Exponentially Weighted Aggregation (EWA)Open questions

Prediction with expert advice
Further topics
The infinite caseReminderThe Kullback divergence, or relative entropy : R dp 
log dπ(ϑ) p(dϑ) if p  π,K(p, π) =+∞ otherwise.

Pierre Alquier

Introduction to Sequential Prediction

Setting of the problem
Exponentially Weighted Aggregation (EWA)Open questions

Prediction with expert advice
Further topics
The infinite caseReminderThe Kullback divergence, or relative entropy : R dp 
log dπ(ϑ) p(dϑ) if p  π,K(p, π) =+∞ otherwise.
When π is uniform on {1, . . . , M} and when p is the Diracmass on i ∈ {1, . . . , M} thenK(p, π) = log(M)so the result in the finite case is indeed a corollary of thegeneral result.
Pierre Alquier

Introduction to Sequential Prediction

Setting of the problem
Exponentially Weighted Aggregation (EWA)Open questions

Prediction with expert advice
Further topics
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

Introduction to Sequential Prediction

Setting of the problem
Exponentially Weighted Aggregation (EWA)Open questions

Prediction with expert advice
Further topics
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

Introduction to Sequential Prediction

Setting of the problem
Exponentially Weighted Aggregation (EWA)Open questions

Prediction with expert advice
Further topics
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

Introduction to Sequential Prediction

Setting of the problem
Exponentially Weighted Aggregation (EWA)Open questions

Prediction with expert advice
Further topics
The infinite case

Concentration of the posterior in Bayesian statistics
The asymptotic concentrationof π(θ|y1 , . . . , yt ) is a wellknown topic. Requires :Pierre Alquier

Introduction to Sequential Prediction

Setting of the problem
Exponentially Weighted Aggregation (EWA)Open questions

Prediction with expert advice
Further topics
The infinite case

Concentration of the posterior in Bayesian statistics
The asymptotic concentrationof π(θ|y1 , . . . , yt ) is a wellknown topic. Requires :1model well specified,

Pierre Alquier

Introduction to Sequential Prediction

Setting of the problem
Exponentially Weighted Aggregation (EWA)Open questions

Prediction with expert advice
Further topics
The infinite case

Concentration of the posterior in Bayesian statistics
The asymptotic concentrationof π(θ|y1 , . . . , yt ) is a wellknown topic. Requires :1model well specified,2
a technical “test”
condition,

Pierre Alquier

Introduction to Sequential Prediction

Setting of the problem
Exponentially Weighted Aggregation (EWA)Open questions

Prediction with expert advice
Further topics
The infinite case

Concentration of the posterior in Bayesian statistics
The asymptotic concentrationof π(θ|y1 , . . . , yt ) is a wellknown topic. Requires :1model well specified,2
a technical “test”
condition,3
the prior mass condition :find r such that
π{B(θ∗ , ε)} ≥ e−r (ε) ,B(θ, x) = {θ0 : kθ−θ0 k ≤ x}.
Pierre Alquier

Introduction to Sequential Prediction

Setting of the problem
Exponentially Weighted Aggregation (EWA)Open questions

Prediction with expert advice
Further topics
The infinite case

Explicit regret boundHere, we did not assume the model is well speficied, nor thetest condition, nor η = 1. Put πθ,ε as π restricted to B(θ, ε).
!
TXE`(ŷt , yt )t=1

Pierre Alquier

Introduction to Sequential Prediction

Setting of the problem
Exponentially Weighted Aggregation (EWA)Open questions

Prediction with expert advice
Further topics
The infinite case

Explicit regret boundHere, we did not assume the model is well speficied, nor thetest condition, nor η = 1. Put πθ,ε as π restricted to B(θ, ε).
!
TXE`(ŷt , yt )
t=1

"Z
≤ inf
p

T
X

ηC 2 T
K(p, π)`(fϑ (xt ), yt )p(dϑ) +
+
8
η
t=1

Pierre Alquier#

Introduction to Sequential Prediction

Setting of the problem
Exponentially Weighted Aggregation (EWA)Open questions

Prediction with expert advice
Further topics
The infinite case

Explicit regret boundHere, we did not assume the model is well speficied, nor thetest condition, nor η = 1. Put πθ,ε as π restricted to B(θ, ε).
!
TXE`(ŷt , yt )
t=1

"Z

T
X

"Z

T
X

≤ inf
p

≤ inf
θ,ε

ηC 2 T
K(p, π)`(fϑ (xt ), yt )p(dϑ) +
+
8
η
t=1

#

ηC 2 TK(πθ,ε , π)`(fϑ (xt ), yt )πθ,ε (dϑ) +
+
8
η
t=1

Pierre Alquier

Introduction to Sequential Prediction#

Setting of the problem
Exponentially Weighted Aggregation (EWA)Open questions

Prediction with expert advice
Further topics
The infinite case

Explicit regret boundHere, we did not assume the model is well speficied, nor thetest condition, nor η = 1. Put πθ,ε as π restricted to B(θ, ε).
!
TXE`(ŷt , yt ) (assume θ 7→ `(fϑ (xt ), yt ) is L-Lipschitz)
t=1

"Z

T
X

"Z

T
X

≤ inf
p

ηC 2 T
K(p, π)`(fϑ (xt ), yt )p(dϑ) +
+
8
η
t=1

#

ηC 2 TK(πθ,ε , π)
≤ inf`(fϑ (xt ), yt )πθ,ε (dϑ) +
+
θ,ε
8
η
t=1


T
X
ηC 2 Tr (ε)≤ inf`(fθ (xt ), yt ) + inf T Lε +
+
ε
θ
8
η
t=1
Pierre Alquier

Introduction to Sequential Prediction#

Setting of the problem
Exponentially Weighted Aggregation (EWA)Open questions

Prediction with expert advice
Further topics
The infinite case

Explicit regret boundE [Regret(T )] = inf

ε>0

d log 1εT (ηB 2 + Lε) +η

Pierre Alquier!

Introduction to Sequential Prediction.

Setting of the problem
Exponentially Weighted Aggregation (EWA)Open questions

Prediction with expert advice
Further topics
The infinite case

Explicit regret bound

!
1
d
log
ε
.
E [Regret(T )] = inf T (ηB 2 + Lε) +ε>0ηpThe choice ε = d/(TLη) and η = d/(TB 2 ) leads to theregret bound
s 
 
LT
E [Regret(T )] =≤ B dT 2 + log.
Bd

Pierre Alquier

Introduction to Sequential Prediction

Setting of the problem
Exponentially Weighted Aggregation (EWA)Open questions

Confidence intervals
Fast algorithms
More open questions

Open questions
1

Setting of the problem
Definitions
Toy examples
The regret

2

Exponentially Weighted Aggregation (EWA)
Prediction with expert advice
Further topics
The infinite case

3

Open questions
Confidence intervals
Fast algorithms
More open questions
Pierre Alquier

Introduction to Sequential Prediction

Setting of the problem
Exponentially Weighted Aggregation (EWA)Open questions

Confidence intervals
Fast algorithms
More open questions

Example - GDP growth in France

Pierre Alquier

Introduction to Sequential Prediction

Setting of the problem
Exponentially Weighted Aggregation (EWA)Open questions

Confidence intervals
Fast algorithms
More open questions

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

Pierre Alquier

Introduction to Sequential Prediction

Setting of the problem
Exponentially Weighted Aggregation (EWA)Open questions

Confidence intervals
Fast algorithms
More open questions

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

Introduction to Sequential Prediction

Setting of the problem
Exponentially Weighted Aggregation (EWA)Open questions

Confidence intervals
Fast algorithms
More open questions

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

Introduction to Sequential Prediction

Setting of the problem
Exponentially Weighted Aggregation (EWA)Open questions

Confidence intervals
Fast algorithms
More open questions

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

Introduction to Sequential Prediction

Setting of the problem
Exponentially Weighted Aggregation (EWA)Open questions

Confidence intervals
Fast algorithms
More open questions

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

Introduction to Sequential Prediction

Setting of the problem
Exponentially Weighted Aggregation (EWA)Open questions

Confidence intervals
Fast algorithms
More open questions

Business 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

Introduction to Sequential Prediction

Setting of the problem
Exponentially Weighted Aggregation (EWA)Open questions

Confidence intervals
Fast algorithms
More open questions

Business 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

Introduction to Sequential Prediction

Setting of the problem
Exponentially Weighted Aggregation (EWA)Open questions

Confidence intervals
Fast algorithms
More open questions

Business 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

Introduction to Sequential Prediction

Setting of the problem
Exponentially Weighted Aggregation (EWA)Open questions

Confidence intervals
Fast algorithms
More open questions

Business 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

Introduction to Sequential Prediction

Setting of the problem
Exponentially Weighted Aggregation (EWA)Open questions

Confidence intervals
Fast algorithms
More open questions

M. Cornec’s predictorsf\ t = α + β∆GDPt−1 + γIt−1 + δ(It−1 − It−2 )|It−1 − It−2 |∆GDP

Pierre Alquier

Introduction to Sequential Prediction

Setting of the problem
Exponentially Weighted Aggregation (EWA)Open questions

Confidence intervals
Fast algorithms
More open questions

M. Cornec’s predictorsf\ t = α + β∆GDPt−1 + γIt−1 + δ(It−1 − It−2 )|It−1 − It−2 |∆GDPproposed by

Pierre Alquier

Introduction to Sequential Prediction

Setting of the problem
Exponentially Weighted Aggregation (EWA)Open questions

Confidence intervals
Fast algorithms
More open questions

M. Cornec’s predictorsf\ t = α + β∆GDPt−1 + γIt−1 + δ(It−1 − It−2 )|It−1 − It−2 |∆GDPproposed by

1

Pierre Alquier

forecasts similars to
the ones by the mostcomplex models usedby INSEE.

Introduction to Sequential Prediction

Setting of the problem
Exponentially Weighted Aggregation (EWA)Open questions

Confidence intervals
Fast algorithms
More open questions

M. Cornec’s predictorsf\ t = α + β∆GDPt−1 + γIt−1 + δ(It−1 − It−2 )|It−1 − It−2 |∆GDPproposed by1

forecasts similars to
the ones by the mostcomplex models usedby INSEE.

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

fPierre Alquier

Introduction to Sequential Prediction

Setting of the problem
Exponentially Weighted Aggregation (EWA)Open questions

Confidence intervals
Fast algorithms
More open questions

Forecastings

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

Introduction to Sequential Prediction

Setting of the problem
Exponentially Weighted Aggregation (EWA)Open questions

Confidence intervals
Fast algorithms
More open questions

Confidence intervals

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

Introduction to Sequential Prediction

Setting of the problem
Exponentially Weighted Aggregation (EWA)Open questions

Confidence intervals
Fast algorithms
More open questions

Matthieu Cornec - Xiaoyin Li

Pierre Alquier

Introduction to Sequential Prediction

Setting of the problem
Exponentially Weighted Aggregation (EWA)Open questions

Confidence intervals
Fast algorithms
More open questions

R. Deswarte’s algorithm

Pierre Alquier

Introduction to Sequential Prediction

Setting of the problem
Exponentially Weighted Aggregation (EWA)Open questions

Confidence intervals
Fast algorithms
More open questions

Application : oil prediction forecasting

Figure – 104 physical models build to predict oil production invarious wells.

Pierre Alquier

Introduction to Sequential Prediction

Setting of the problem
Exponentially Weighted Aggregation (EWA)Open questions

Confidence intervals
Fast algorithms
More open questions

Results

Figure – Confidence intervals by R. Deswarte’s algorithm.

Pierre Alquier

Introduction to Sequential Prediction

Setting of the problem
Exponentially Weighted Aggregation (EWA)Open questions

Confidence intervals
Fast algorithms
More open questions

Results

Figure – Confidence intervals by R. Deswarte’s algorithm.

Pierre Alquier

Introduction to Sequential Prediction

Setting of the problem
Exponentially Weighted Aggregation (EWA)Open questions

Confidence intervals
Fast algorithms
More open questions

Raphaël Deswarte

Pierre Alquier

Introduction to Sequential Prediction

Setting of the problem
Exponentially Weighted Aggregation (EWA)Open questions

Confidence intervals
Fast algorithms
More open questions

Raphaël Deswarte

Pierre Alquier

Introduction to Sequential Prediction

Setting of the problem
Exponentially Weighted Aggregation (EWA)Open questions

Confidence intervals
Fast algorithms
More open questions

Conformal prediction
Another approach was proposed by Vovk and coauthors.

Pierre Alquier

Introduction to Sequential Prediction

Setting of the problem
Exponentially Weighted Aggregation (EWA)Open questions

Confidence intervals
Fast algorithms
More open questions

Conformal prediction
Another approach was proposed by Vovk and coauthors.
It is extremely nice, flexible
and theoretically grounded.
But requires stochastic assumptions on the data. Also,very different from the previous approaches, so would
be too long to explain here...
so read :Pierre Alquier

Introduction to Sequential Prediction

Setting of the problem
Exponentially Weighted Aggregation (EWA)Open questions

Confidence intervals
Fast algorithms
More open questions

Fast algorithms ?
In the infinite case, the computation of EWA might beinfeasible or very slow...

Pierre Alquier

Introduction to Sequential Prediction

Setting of the problem
Exponentially Weighted Aggregation (EWA)Open questions

Confidence intervals
Fast algorithms
More open questions

Fast algorithms ?
In the infinite case, the computation of EWA might beinfeasible or very slow...
In
Bayesianstatistics,
fast
approximationsofπ(θ|y1 , . . . , yt ) available via“variational inference”.

Pierre Alquier

Introduction to Sequential Prediction

Setting of the problem
Exponentially Weighted Aggregation (EWA)Open questions

Confidence intervals
Fast algorithms
More open questions

Fast algorithms ?
In the infinite case, the computation of EWA might beinfeasible or very slow...
In
Bayesianstatistics,
fast
approximationsofπ(θ|y1 , . . . , yt ) available via“variational inference”.
Similar approaches are currently being developped in
the online (sequential prediction) framework for pt ...
Pierre Alquier

Introduction to Sequential Prediction

Setting of the problem
Exponentially Weighted Aggregation (EWA)Open questions

Confidence intervals
Fast algorithms
More open questions

Other (fast) approximations

Pierre Alquier

Introduction to Sequential Prediction

Setting of the problem
Exponentially Weighted Aggregation (EWA)Open questions

Confidence intervals
Fast algorithms
More open questions

More open questions

Pierre Alquier

Introduction to Sequential Prediction

Setting of the problem
Exponentially Weighted Aggregation (EWA)Open questions

Confidence intervals
Fast algorithms
More open questions

More open questions

theoretical study of the confidence intervals.

Pierre Alquier

Introduction to Sequential Prediction

Setting of the problem
Exponentially Weighted Aggregation (EWA)Open questions

Confidence intervals
Fast algorithms
More open questions

More open questions

theoretical study of the confidence intervals.
theoretical study of the fast algorithms.

Pierre Alquier

Introduction to Sequential Prediction

Setting of the problem
Exponentially Weighted Aggregation (EWA)Open questions

Confidence intervals
Fast algorithms
More open questions

More open questions

theoretical study of the confidence intervals.
theoretical study of the fast algorithms.
causal inference ?

Pierre Alquier

Introduction to Sequential Prediction

Setting of the problem
Exponentially Weighted Aggregation (EWA)Open questions

Confidence intervals
Fast algorithms
More open questions

More open questions

theoretical study of the confidence intervals.
theoretical study of the fast algorithms.
causal inference ?
tests ?

Pierre Alquier

Introduction to Sequential Prediction

Setting of the problem
Exponentially Weighted Aggregation (EWA)Open questions

Confidence intervals
Fast algorithms
More open questions

More open questions

theoretical study of the confidence intervals.
theoretical study of the fast algorithms.
causal inference ?
tests ?
...

Pierre Alquier

Introduction to Sequential Prediction

Setting of the problem
Exponentially Weighted Aggregation (EWA)Open questions

Confidence intervals
Fast algorithms
More open questions

Thank you ! !

Pierre Alquier

Introduction to Sequential Prediction