Short introduction to machine learning theory
Machine learning and time series

Machine learning theory for time series
Exponential inequalities for nonstationary Markov chains

Pierre Alquier

CIMFAV seminar
January 16, 2019
Pierre Alquier

Machine learning theory for time series

Short introduction to machine learning theory
Machine learning and time series

1

Short introduction to machine learning theory2

Machine learning and time series
Machine learning & stationary time series
Nonstationary Markov chains

Pierre Alquier

Machine learning theory for time series

Short introduction to machine learning theory
Machine learning and time series

Generic machine learning problem
Main ingredients :Pierre Alquier

Machine learning theory for time series

Short introduction to machine learning theory
Machine learning and time series

Generic machine learning problem
Main ingredients :observations : (X1 , Y1 ), (X2 , Y2 ), ..., (Xn , Yn )Pierre Alquier

Machine learning theory for time series

Short introduction to machine learning theory
Machine learning and time series

Generic machine learning problem
Main ingredients :observations : (X1 , Y1 ), (X2 , Y2 ), ..., (Xn , Yn )→ usually i.i.d from an unknown distribution P...

Pierre Alquier

Machine learning theory for time series

Short introduction to machine learning theory
Machine learning and time series

Generic machine learning problem
Main ingredients :observations : (X1 , Y1 ), (X2 , Y2 ), ..., (Xn , Yn )→ usually i.i.d from an unknown distribution P...
a restricted set of predictors (fθ , θ ∈ Θ)

Pierre Alquier

Machine learning theory for time series

Short introduction to machine learning theory
Machine learning and time series

Generic machine learning problem
Main ingredients :observations : (X1 , Y1 ), (X2 , Y2 ), ..., (Xn , Yn )→ usually i.i.d from an unknown distribution P...
a restricted set of predictors (fθ , θ ∈ Θ)
→ fθ (X ) meant to predict Y .

Pierre Alquier

Machine learning theory for time series

Short introduction to machine learning theory
Machine learning and time series

Generic machine learning problem
Main ingredients :observations : (X1 , Y1 ), (X2 , Y2 ), ..., (Xn , Yn )→ usually i.i.d from an unknown distribution P...
a restricted set of predictors (fθ , θ ∈ Θ)
→ fθ (X ) meant to predict Y .
A loss function `→ `(y 0 − y ) incurred by predicting y 0 while the truth is y .

Pierre Alquier

Machine learning theory for time series

Short introduction to machine learning theory
Machine learning and time series

Generic machine learning problem
Main ingredients :observations : (X1 , Y1 ), (X2 , Y2 ), ..., (Xn , Yn )→ usually i.i.d from an unknown distribution P...
a restricted set of predictors (fθ , θ ∈ Θ)
→ fθ (X ) meant to predict Y .
A loss function `→ `(y 0 − y ) incurred by predicting y 0 while the truth is y .
the risk R(θ)

Pierre Alquier

Machine learning theory for time series

Short introduction to machine learning theory
Machine learning and time series

Generic machine learning problem
Main ingredients :observations : (X1 , Y1 ), (X2 , Y2 ), ..., (Xn , Yn )→ usually i.i.d from an unknown distribution P...
a restricted set of predictors (fθ , θ ∈ Θ)
→ fθ (X ) meant to predict Y .
A loss function `→ `(y 0 − y ) incurred by predicting y 0 while the truth is y .
the risk R(θ)→ R(θ) = E(X ,Y )∼P [`(fθ (X ) − Y )]. Not observable.

Pierre Alquier

Machine learning theory for time series

Short introduction to machine learning theory
Machine learning and time series

Generic machine learning problem
Main ingredients :observations : (X1 , Y1 ), (X2 , Y2 ), ..., (Xn , Yn )→ usually i.i.d from an unknown distribution P...
a restricted set of predictors (fθ , θ ∈ Θ)
→ fθ (X ) meant to predict Y .
A loss function `→ `(y 0 − y ) incurred by predicting y 0 while the truth is y .
the risk R(θ)→ R(θ) = E(X ,Y )∼P [`(fθ (X ) − Y )]. Not observable.
an empirical proxy r (θ) for R(θ)

Pierre Alquier

Machine learning theory for time series

Short introduction to machine learning theory
Machine learning and time series

Generic machine learning problem
Main ingredients :observations : (X1 , Y1 ), (X2 , Y2 ), ..., (Xn , Yn )→ usually i.i.d from an unknown distribution P...
a restricted set of predictors (fθ , θ ∈ Θ)
→ fθ (X ) meant to predict Y .
A loss function `→ `(y 0 − y ) incurred by predicting y 0 while the truth is y .
the risk R(θ)→ R(θ) = E(X ,Y )∼P [`(fθ (X ) − Y )]. Not observable.
an empirical proxy r (θ) forPnR(θ)
1→ for example r (θ) = n i=1 `(fθ (Xi ) − Yi ).
empirical risk minimizer θ̂

Pierre Alquier

Machine learning theory for time series

Short introduction to machine learning theory
Machine learning and time series

Generic machine learning problem
Main ingredients :observations : (X1 , Y1 ), (X2 , Y2 ), ..., (Xn , Yn )→ usually i.i.d from an unknown distribution P...
a restricted set of predictors (fθ , θ ∈ Θ)
→ fθ (X ) meant to predict Y .
A loss function `→ `(y 0 − y ) incurred by predicting y 0 while the truth is y .
the risk R(θ)→ R(θ) = E(X ,Y )∼P [`(fθ (X ) − Y )]. Not observable.
an empirical proxy r (θ) forPnR(θ)
1→ for example r (θ) = n i=1 `(fθ (Xi ) − Yi ).
empirical risk minimizer θ̂→ θ̂ = argmin r (θ).
θ∈Θ
Pierre Alquier

Machine learning theory for time series

Short introduction to machine learning theory
Machine learning and time series

Sub-gamma random variables
Definition
T is said to be sub-gamma iff∃(v , w ) such that ∀k ≥ 2,
 k!vw k−2
E |T |k ≤.
2

Pierre Alquier

Machine learning theory for time series

Short introduction to machine learning theory
Machine learning and time series

Sub-gamma random variables
Definition
T is said to be sub-gamma iff∃(v , w ) such that ∀k ≥ 2,
 k!vw k−2
E |T |k ≤.
2
Examples :T ∼ Γ(a, b), holds with(v , w ) = (ab 2 , b).

Pierre Alquier

Machine learning theory for time series

Short introduction to machine learning theory
Machine learning and time series

Sub-gamma random variables
Definition
T is said to be sub-gamma iff∃(v , w ) such that ∀k ≥ 2,
 k!vw k−2
E |T |k ≤.
2
Examples :T ∼ Γ(a, b), holds with(v , w ) = (ab 2 , b).
any Z with
P(|Z | ≥ t) ≤ P(|T | ≥ t).
Pierre Alquier

Machine learning theory for time series

Short introduction to machine learning theory
Machine learning and time series

Bernstein’s inequality
Theorem
Let T1 , . . . , Tn be i.i.d and (v , w )-sub-gamma randomvariables. Then, ∀ζ ∈ (0, 1/w ),
!


n
X
nv ζ 2.
E exp ζ[Ti − ETi ] ≤ exp
2(1
−
w
ζ)
i=1

Pierre Alquier

Machine learning theory for time series

Short introduction to machine learning theory
Machine learning and time series

Bernstein’s inequality
Theorem
Let T1 , . . . , Tn be i.i.d and (v , w )-sub-gamma randomvariables. Then, ∀ζ ∈ (0, 1/w ),
!


n
X
nv ζ 2.
E exp ζ[Ti − ETi ] ≤ exp
2(1
−
w
ζ)
i=1
Consequence in ML : put Ti = −`(fθ (Xi ) − Yi ) and assume
Ti is (v , w )-sub-gamma, then

Pierre Alquier

Machine learning theory for time series

Short introduction to machine learning theory
Machine learning and time series

Bernstein’s inequality
Theorem
Let T1 , . . . , Tn be i.i.d and (v , w )-sub-gamma randomvariables. Then, ∀ζ ∈ (0, 1/w ),
!


n
X
nv ζ 2.
E exp ζ[Ti − ETi ] ≤ exp
2(1
−
w
ζ)
i=1
Consequence in ML : put Ti = −`(fθ (Xi ) − Yi ) and assume
Ti is (v , w )-sub-gamma, then for any s > 0,
"
(
)
h
i
P R(θ) − r (θ) > t = P exp [s (R(θ) − r (θ))] > exp(st)Pierre Alquier

Machine learning theory for time series

Short introduction to machine learning theory
Machine learning and time series

Bernstein’s inequality
Theorem
Let T1 , . . . , Tn be i.i.d and (v , w )-sub-gamma randomvariables. Then, ∀ζ ∈ (0, 1/w ),
!


n
X
nv ζ 2.
E exp ζ[Ti − ETi ] ≤ exp
2(1
−
w
ζ)
i=1
Consequence in ML : put Ti = −`(fθ (Xi ) − Yi ) and assume
Ti is (v , w )-sub-gamma, then for any s > 0,
"
"
#
h
i
P R(θ) − r (θ) > t ≤ E exp s (R(θ) − r (θ)) − stPierre Alquier

Machine learning theory for time series

Short introduction to machine learning theory
Machine learning and time series

Bernstein’s inequality
Theorem
Let T1 , . . . , Tn be i.i.d and (v , w )-sub-gamma randomvariables. Then, ∀ζ ∈ (0, 1/w ),
!


n
X
nv ζ 2.
E exp ζ[Ti − ETi ] ≤ exp
2(1
−
w
ζ)
i=1
Consequence in ML : put Ti = −`(fθ (Xi ) − Yi ) and assume
Ti is (v , w )-sub-gamma, then for any s > 0,
"
"
!
#
h
i
P
n
P R(θ) − r (θ) > t ≤ E exp ns− sti=1 [Ti − ETi ]Pierre Alquier

Machine learning theory for time series

Short introduction to machine learning theory
Machine learning and time series

Bernstein’s inequality
Theorem
Let T1 , . . . , Tn be i.i.d and (v , w )-sub-gamma randomvariables. Then, ∀ζ ∈ (0, 1/w ),
!


n
X
nv ζ 2.
E exp ζ[Ti − ETi ] ≤ exp
2(1
−
w
ζ)
i=1
Consequence in ML : put Ti = −`(fθ (Xi ) − Yi ) and assume
Ti is (v , w )-sub-gamma, then for any s > 0,
"
"
!
#
h
i
P
n
P R(θ) − r (θ) > t ≤ E exp ns− sti=1 [Ti − ETi ]Pierre Alquier

Machine learning theory for time series

Short introduction to machine learning theory
Machine learning and time series

Bernstein’s inequality
Theorem
Let T1 , . . . , Tn be i.i.d and (v , w )-sub-gamma randomvariables. Then, ∀ζ ∈ (0, 1/w ),
!


n
X
nv ζ 2.
E exp ζ[Ti − ETi ] ≤ exp
2(1
−
w
ζ)
i=1
Consequence in ML : put Ti = −`(fθ (Xi ) − Yi ) and assume
Ti is (v , w )-sub-gamma, then for any s > 0,
"
"
#
h
i
2
vs
P R(θ) − r (θ) > t ≤ exp− st2(n − w s)
Pierre Alquier

Machine learning theory for time series

Short introduction to machine learning theory
Machine learning and time series

Bernstein’s inequality
Theorem
Let T1 , . . . , Tn be i.i.d and (v , w )-sub-gamma randomvariables. Then, ∀ζ ∈ (0, 1/w ),
!


n
X
nv ζ 2.
E exp ζ[Ti − ETi ] ≤ exp
2(1
−
w
ζ)
i=1
Consequence in ML : put Ti = −`(fθ (Xi ) − Yi ) and assume
Ti is (v , w )-sub-gamma, then for any s > 0,
"
"
#
h
i
2
vs
P R(θ) − r (θ) > t ≤ exp− st2(n − ws)
Pierre Alquier

Machine learning theory for time series

Short introduction to machine learning theory
Machine learning and time series

Bernstein’s inequality
Theorem
Let T1 , . . . , Tn be i.i.d and (v , w )-sub-gamma randomvariables. Then, ∀ζ ∈ (0, 1/w ),
!


n
X
nv ζ 2.
E exp ζ[Ti − ETi ] ≤ exp
2(1
−
w
ζ)
i=1
Consequence in ML : put Ti = −`(fθ (Xi ) − Yi ) and assume
Ti is (v , w )-sub-gamma, then for any s > 0,
"
"
#
h
i
2
vs
P |R(θ) − r (θ)| > t ≤ 2 exp− st
2(n − ws)
Pierre Alquier

Machine learning theory for time series

Short introduction to machine learning theory
Machine learning and time series

Finite set of predictors and union bound

"
#
h
i
o
[n
P ∃θ ∈ Θ, |R(θ) − r (θ)| > t = P|R(θ) − r (θ)| ≥ tθ∈ΘPierre Alquier

Machine learning theory for time series

Short introduction to machine learning theory
Machine learning and time series

Finite set of predictors and union bound

"
#
h
i
X
P ∃θ ∈ Θ, |R(θ) − r (θ)| > t ≤P |R(θ) − r (θ)| ≥ tθ∈ΘPierre Alquier

Machine learning theory for time series

Short introduction to machine learning theory
Machine learning and time series

Finite set of predictors and union boundhiP ∃θ ∈ Θ, |R(θ) − r (θ)| > t ≤ 2|Θ| exp

Pierre Alquier

2

vs
− st
2(n − ws)

Machine learning theory for time series!

Short introduction to machine learning theory
Machine learning and time series

Finite set of predictors and union boundhiP ∃θ ∈ Θ, |R(θ) − r (θ)| > t ≤ 2|Θ| exp

vs 2
− st
2(n − ws)

,On the complement,, R(θ̂) ≤ r (θ̂) + t

Pierre Alquier

Machine learning theory for time series!

Short introduction to machine learning theory
Machine learning and time series

Finite set of predictors and union boundhiP ∃θ ∈ Θ, |R(θ) − r (θ)| > t ≤ 2|Θ| exp

vs 2
− st
2(n − ws)

,On the complement, ∀θ0 ,, R(θ̂) ≤ r (θ̂) + t

Pierre Alquier

Machine learning theory for time series!

Short introduction to machine learning theory
Machine learning and time series

Finite set of predictors and union boundhiP ∃θ ∈ Θ, |R(θ) − r (θ)| > t ≤ 2|Θ| exp

vs 2
− st
2(n − ws)

,On the complement, ∀θ0 ,, R(θ̂) ≤ r (θ0 ) + t

Pierre Alquier

Machine learning theory for time series!

Short introduction to machine learning theory
Machine learning and time series

Finite set of predictors and union boundhiP ∃θ ∈ Θ, |R(θ) − r (θ)| > t ≤ 2|Θ| exp

vs 2
− st
2(n − ws)

,On the complement, ∀θ0 ,, R(θ̂) ≤ R(θ0 ) + 2t

Pierre Alquier

Machine learning theory for time series!

Short introduction to machine learning theory
Machine learning and time series

Finite set of predictors and union boundhiP ∃θ ∈ Θ, |R(θ) − r (θ)| > t ≤ 2|Θ| exp

2

vs
− st
2(n − ws)

,On the complement,R(θ) + 2t, R(θ̂) ≤ minθ∈Θ

Pierre Alquier

Machine learning theory for time series!

Short introduction to machine learning theory
Machine learning and time series

Finite set of predictors and union boundhiP ∃θ ∈ Θ, |R(θ) − r (θ)| > t ≤ 2|Θ| exp
|

!
vs 2
− st
2(n − ws){z}
=α

,On the complement,
2|Θ|

θ∈Θ

2 log αvs+n − wss

Pierre Alquier

Machine learning theory for time series, R(θ̂) ≤ min R(Θ) +Short introduction to machine learning theory
Machine learning and time series

Finite set of predictors and union boundhiP ∃θ ∈ Θ, |R(θ) − r (θ)| > t ≤ 2|Θ| exp
|

!
vs 2
− st
2(n − ws){z}
=α

,On the complement,forps = [n/(2w )] ∧ (n/v ) log(2|Θ|/α),
2|Θ|

θ∈Θ

2 log αvs+n − wss

Pierre Alquier

Machine learning theory for time series, R(θ̂) ≤ min R(Θ) +Short introduction to machine learning theory
Machine learning and time series

Finite set of predictors and union boundhiP ∃θ ∈ Θ, |R(θ) − r (θ)| > t ≤ 2|Θ| exp
|

!
vs 2
− st
2(n − ws){z}
=α

,On the complement,
we obtain :,TheoremWith probability at least 1 − α,sR(θ̂) ≤ min R(θ) + 2
θ∈Θ

Pierre Alquierv log 2|Θ|
2w log 2|Θ|
α
α
∨
.
n
n
Machine learning theory for time series

Short introduction to machine learning theory
Machine learning and time series

Finite set of predictors and union boundhiP ∃θ ∈ Θ, |R(θ) − r (θ)| > t ≤ 2|Θ| exp
|

!
vs 2
− st
2(n − ws){z}
=α

,On the complement,
we obtain :,TheoremWith proba. at least 1 − α, with α not rediculously small,sv log 2|Θ|αR(θ̂) ≤ min R(θ) + 2θ∈ΘnPierre Alquier

Machine learning theory for time series

Short introduction to machine learning theory
Machine learning and time series

Infinite parameter set
Θ compact ⇒ ∃ a finite Θ(ε) such that∀θ ∈ Θ, ∃θ0 ∈ Θ(ε) with δ(θ, θ0 ) ≤ ε.

Pierre Alquier

Machine learning theory for time series

Short introduction to machine learning theory
Machine learning and time series

Infinite parameter set (image from Wikipedia)
Θ compact ⇒ ∃ a finite Θ(ε) such that∀θ ∈ Θ, ∃θ0 ∈ Θ(ε) with δ(θ, θ0 ) ≤ ε.

Pierre Alquier

Machine learning theory for time series

Short introduction to machine learning theory
Machine learning and time series

Infinite parameter set
Θ compact ⇒ ∃ a finite Θ(ε) such that∀θ ∈ Θ, ∃θ0 ∈ Θ(ε) with δ(θ, θ0 ) ≤ ε.

Assume θ 7→ `(fθ (X ) − Y ) is a.s. L-Lipschitz w.r.t δ(·, ·), thenrR(θ̂) ≤ minθ∈Θ R(θ) + 2Lε + 2
Pierre Alquierv log

2|Θ(ε) |αnMachine learning theory for time series

Short introduction to machine learning theory
Machine learning and time series

Infinite parameter set
Θ compact ⇒ ∃ a finite Θ(ε) such that∀θ ∈ Θ, ∃θ0 ∈ Θ(ε) with δ(θ, θ0 ) ≤ ε.
Example : in the finite
dimensional case, there isΘε with|Θ(ε) | .

1.
εdAssume θ 7→ `(fθ (X ) − Y ) is a.s. L-Lipschitz w.r.t δ(·, ·), thenq
2v d log εαR(θ̂) ≤ minθ∈Θ R(θ) + 2Lε + 2nPierre Alquier

Machine learning theory for time series

Short introduction to machine learning theory
Machine learning and time series

Infinite parameter set
Θ compact ⇒ ∃ a finite Θ(ε) such that∀θ ∈ Θ, ∃θ0 ∈ Θ(ε) with δ(θ, θ0 ) ≤ ε.
Example : in the finite
dimensional case, there isΘε with|Θ(ε) | .

1.
εdAssume θ 7→ `(fθ (X ) − Y ) is a.s. L-Lipschitz w.r.t δ(·, ·), thenqq2v d log εα, ε = dnR(θ̂) ≤ minθ∈Θ R(θ) + 2Lε + 2nPierre Alquier

Machine learning theory for time series

Short introduction to machine learning theory
Machine learning and time series

Infinite parameter set
Θ compact ⇒ ∃ a finite Θ(ε) such that∀θ ∈ Θ, ∃θ0 ∈ Θ(ε) with δ(θ, θ0 ) ≤ ε.
Example : in the finite
dimensional case, there isΘε with|Θ(ε) | .

1.
εdAssume θ 7→ `(fθ (X ) − Y ) is a.s. L-Lipschitz w.r.t δ(·, ·), then
q 
q

2n
R(θ̂) ≤ minθ∈Θ R(θ) + dn 2L + 2 v log dα
Pierre Alquier

Machine learning theory for time series

Short introduction to machine learning theory
Machine learning and time series

Infinite parameter set
Θ compact ⇒ ∃ a finite Θ(ε) such that∀θ ∈ Θ, ∃θ0 ∈ Θ(ε) with δ(θ, θ0 ) ≤ ε.
Example : in the finite
dimensional case, there isΘε with|Θ(ε) | .

1.
εdWith the loss is L-Lipschitz, with proba. at least 1 − α,
!
r
r
d
2n
R(θ̂) ≤ min R(θ) +2L + 2 v log
.
θ∈Θ
n
dα
Pierre Alquier

Machine learning theory for time series

Short introduction to machine learning theory
Machine learning and time series

Model selection
Now we consider Θ1 , . . . , ΘM with estimators θ̂1 , . . . θ̂M :Pierre Alquier

Machine learning theory for time series

Short introduction to machine learning theory
Machine learning and time series

Model selection
Now we consider Θ1 , . . . , ΘM with estimators θ̂1 , . . . θ̂M :hiP ∃m, ∃θ ∈ Θm , |R(θ) − r (θ)| > tm ≤ α.

Pierre Alquier

Machine learning theory for time series

Short introduction to machine learning theory
Machine learning and time series

Model selection
Now we consider Θ1 , . . . , ΘM with estimators θ̂1 , . . . θ̂M :hiP ∃m, ∃θ ∈ Θm , |R(θ) − r (θ)| > tm ≤ α.
Define m̂ = argmin[r (θ̂m ) + tm ], similar derivations lead tom

Pierre Alquier

Machine learning theory for time series

Short introduction to machine learning theory
Machine learning and time series

Model selection
Now we consider Θ1 , . . . , ΘM with estimators θ̂1 , . . . θ̂M :hiP ∃m, ∃θ ∈ Θm , |R(θ) − r (θ)| > tm ≤ α.
Define m̂ = argmin[r (θ̂m ) + tm ], similar derivations lead tomWith proba. at least 1 − α,(rR(θ̂) ≤ min

1≤m≤M

min R(θ) +θ∈Θm

Pierre Alquier

dm
n

r

2nM
2L + 2 v log
dαMachine learning theory for time series!).

Short introduction to machine learning theory
Machine learning and time series

Going further

Improvements, extensions...
removing log(n) by refinment of the ε-net structure.

Pierre Alquier

Machine learning theory for time series

Short introduction to machine learning theory
Machine learning and time series

Going further

Improvements, extensions...
removing log(n) by refinment of the ε-net structure.
pfaster rates : d/n becomes d/n thanks to a better
analysis of v under the Bernstein condition.

Pierre Alquier

Machine learning theory for time series

Short introduction to machine learning theory
Machine learning and time series

Going further

Improvements, extensions...
removing log(n) by refinment of the ε-net structure.
pfaster rates : d/n becomes d/n thanks to a better
analysis of v under the Bernstein condition.
relaxing the sub-gamma assumption.

Pierre Alquier

Machine learning theory for time series

Short introduction to machine learning theory
Machine learning and time series

Going further

Improvements, extensions...
removing log(n) by refinment of the ε-net structure.
pfaster rates : d/n becomes d/n thanks to a better
analysis of v under the Bernstein condition.
relaxing the sub-gamma assumption.
more flexible way to measure the complexity of Θ :PAC-Bayesian bounds.

Pierre Alquier

Machine learning theory for time series

Short introduction to machine learning theory
Machine learning and time series

Machine learning & stationary time series
Nonstationary Markov chains1

Short introduction to machine learning theory2

Machine learning and time series
Machine learning & stationary time series
Nonstationary Markov chains

Pierre Alquier

Machine learning theory for time series

Short introduction to machine learning theory
Machine learning and time series

Machine learning & stationary time series
Nonstationary Markov chains

Extension to time series
Machine learning studied for time series with various
techniqes. Asymptotic study in the mixing case :I. Steinwart, D. Hush, C. Scovel. Learning from dependent observations. Journal ofMultivariate Analysis, 2009.

Pierre Alquier

Machine learning theory for time series

Short introduction to machine learning theory
Machine learning and time series

Machine learning & stationary time series
Nonstationary Markov chains

Extension to time series
Machine learning studied for time series with various
techniqes. Asymptotic study in the mixing case :I. Steinwart, D. Hush, C. Scovel. Learning from dependent observations. Journal ofMultivariate Analysis, 2009.

In order to extend the previous (non-asymptotic) approach tonon-independent observations, exponential inequalities(Hoeffding, Bernstein, etc.) required.

Pierre Alquier

Machine learning theory for time series

Short introduction to machine learning theory
Machine learning and time series

Machine learning & stationary time series
Nonstationary Markov chains

Extension to time series
Machine learning studied for time series with various
techniqes. Asymptotic study in the mixing case :I. Steinwart, D. Hush, C. Scovel. Learning from dependent observations. Journal ofMultivariate Analysis, 2009.

In order to extend the previous (non-asymptotic) approach tonon-independent observations, exponential inequalities(Hoeffding, Bernstein, etc.) required. These inequalities
require some assumption on the dependence of the series :Markov, mixing, weak dependence, martingale,...
Pierre Alquier

Machine learning theory for time series

Short introduction to machine learning theory
Machine learning and time series

Machine learning & stationary time series
Nonstationary Markov chainsAn example on Markov chains

Pierre Alquier

Machine learning theory for time series

Short introduction to machine learning theory
Machine learning and time series

Machine learning & stationary time series
Nonstationary Markov chainsAn example on Markov chains

Pierre Alquier

Machine learning theory for time series

Short introduction to machine learning theory
Machine learning and time series

Machine learning & stationary time series
Nonstationary Markov chainsAn example on Markov chains

Let F : X × Y → X and(Xt )t≥1 be the Markov chain
Xt = F (Xt−1 , εt ).

Pierre Alquier

Machine learning theory for time series

Short introduction to machine learning theory
Machine learning and time series

Machine learning & stationary time series
Nonstationary Markov chainsAn example on Markov chains

Let F : X × Y → X and(Xt )t≥1 be the Markov chain
Xt = F (Xt−1 , εt ).
Assume, for ρ ∈ [0, 1) and C > 0,
E d F (x, ε1 ), F (x 0 , ε1 ) ≤ ρd(x, x 0 )d(F (x, y ), F (x, y 0 )) ≤ C δ(y , y 0 ).
Pierre Alquier

Machine learning theory for time series

Short introduction to machine learning theory
Machine learning and time series

Machine learning & stationary time series
Nonstationary Markov chains

Objective
Xt = F (Xt−1 , εt ).

Pierre Alquier

Machine learning theory for time series

Short introduction to machine learning theory
Machine learning and time series

Machine learning & stationary time series
Nonstationary Markov chains

Objective
Xt = F (Xt−1 , εt ).
In this case, we study one step ahead prediction :n
1 X
r (θ) =`(fθ (Xi−1 ) − Xi ),n − 1 i=2

R(θ) = E[`(fθ (X1 ) − X2 )].

Pierre Alquier

Machine learning theory for time series

Short introduction to machine learning theory
Machine learning and time series

Machine learning & stationary time series
Nonstationary Markov chains

Objective
Xt = F (Xt−1 , εt ).
In this case, we study one step ahead prediction :n
1 X
r (θ) =`(fθ (Xi−1 ) − Xi ),n − 1 i=2

R(θ) = E[`(fθ (X1 ) − X2 )].
Defineθ̂ = argmin r (θ).
θ∈Θ

Pierre Alquier

Machine learning theory for time series

Short introduction to machine learning theory
Machine learning and time series

Machine learning & stationary time series
Nonstationary Markov chains

Notations in DF15Zd(x, x 0 )PX1 (dx 0 ),ZGε (y ) =C δ(y , y 0 )Pε (dy 0 ).

Pierre Alquier

Machine learning theory for time series

Define GX1 (x) =Short introduction to machine learning theory
Machine learning and time series

Machine learning & stationary time series
Nonstationary Markov chains

Notations in DF15Zd(x, x 0 )PX1 (dx 0 ),ZC δ(y , y 0 )Pε (dy 0 ).

Define GX1 (x) =Gε (y ) =Assumption : for any k ≥ 2,hi k!
E GX1 (X1 )k ≤ V1 M k−2 , and2hi k!
E Gε (ε)k ≤ V2 M k−2 .
2Pierre Alquier

Machine learning theory for time series

Short introduction to machine learning theory
Machine learning and time series

Machine learning & stationary time series
Nonstationary Markov chains

Notations in DF15Zd(x, x 0 )PX1 (dx 0 ),ZC δ(y , y 0 )Pε (dy 0 ).

Define GX1 (x) =Gε (y ) =Assumption : for any k ≥ 2,hi k!
E GX1 (X1 )k ≤ V1 M k−2 , and2hi k!
E Gε (ε)k ≤ V2 M k−2 .
2Define V =V1 + V2
1−ρ
,δ=
.
2
1−ρ
M

Pierre Alquier

Machine learning theory for time series

Short introduction to machine learning theory
Machine learning and time series

Machine learning & stationary time series
Nonstationary Markov chains

Dedecker and Fan’s inequality
Theorem (Dedecker & Fan 2015)
Consider a separately Lipschitz function f : X n → R :|f (x1 , . . . , xn ) − f (x10 , . . . , xn0 )| ≤nXd(xt , xt0 ) .

t=1

Then, for any s ∈ [0, δ −1 ),E [e±s{f (X1 ,...,Xn )−E[f (X1 ,...,Xn )]}Pierre Alquier] ≤ exp(n − 1)s 2 V
2(1 − s δ)Machine learning theory for time series.

Short introduction to machine learning theory
Machine learning and time series

Machine learning & stationary time series
Nonstationary Markov chains

Consequences of DF15 for prediction
E e ±s{f (X1 ,...,Xn )−E[f (X1 ,...,Xn )]} ≤ exp

Pierre Alquier(n − 1)s 2 V
2(1 − s δ)Machine learning theory for time series.

Short introduction to machine learning theory
Machine learning and time series

Machine learning & stationary time series
Nonstationary Markov chains

Consequences of DF15 for prediction
E e ±s{f (X1 ,...,Xn )−E[f (X1 ,...,Xn )]} ≤ exp(n − 1)s 2 V
2(1 − s δ)



n

1X
`(fθ (Xi−1 ) − Xi ).
Take f (X1 , . . . , Xn ) =L i=2

Pierre Alquier

Machine learning theory for time series.

Short introduction to machine learning theory
Machine learning and time series

Machine learning & stationary time series
Nonstationary Markov chains

Consequences of DF15 for prediction
E e ±s{f (X1 ,...,Xn )−E[f (X1 ,...,Xn )]} ≤ exp(n − 1)s 2 V
2(1 − s δ)


.

n

1X
`(fθ (Xi−1 ) − Xi ).
Take f (X1 , . . . , Xn ) =L i=2
Then for any 0 ≤ s < (n − 1)/(L(1 + ρ)δ),hi
P |R(θ) − r (θ)| > t≤ 2 exp

s 2 (1 + ρ)2 L2 V
− st .
2(n − 1) − 2s(1 + ρ)δL

Pierre Alquier

Machine learning theory for time series

Short introduction to machine learning theory
Machine learning and time series

Machine learning & stationary time series
Nonstationary Markov chains

Learning theorem for Markov chains
Assume |Θ(ε) | ≤ ε−d .
Theorem
As soon as n ≥ 1 + 4δ 2 d log(Ln)/V we have, with probability
at least 1 − α,rlog α4d log(Ln)
C3
R(θ̂) ≤ inf R(θ) + C1
+ C2 √
+ ,
θ∈Θ
n−1
n
n−1
√
√
where C1 = 4(1 + ρ)L V, C2 = 2(1 + ρ)L V + 2δ andC3 = 3[Gε (0) + GX1 (0)]/(1 − ρ) + V/(2δ).

Pierre Alquier

Machine learning theory for time series

Short introduction to machine learning theory
Machine learning and time series

Machine learning & stationary time series
Nonstationary Markov chains

Other works on ML & TS
Study of Xt = F (εt ; Xt−1 , Xt−1 , . . . ) in
P. Alquier, O. Wintengerger. Model selection for weakly dependent time series
forecasting. Bernoulli, 2012.

based on Rio’s version of Hoeffding’s inequality
E. Rio. Inégalités de Hoeffding pour les fonctions lipschitziennes de suites dépendantes.
CRAS, 2000.

r
Rates in
Pierre Alquierd.
nMachine learning theory for time series

Short introduction to machine learning theory
Machine learning and time series

Machine learning & stationary time series
Nonstationary Markov chains

Fast rates
Rates indfor quadratic ` inn

P. Alquier, X. Li, O. Wintengerger. Prediction of time series by statistical learning :general losses and fast rates.. Dependence Modeling, 2013.

based on Samson’s version of Bernstein’s inequality for
ϕ-mixing processes
P.-M. Samson. Concentration of measure inequalities for markov chains and ϕ-mixing
processes. The Annals of Probability, 2000.

Pierre Alquier

Machine learning theory for time series

Short introduction to machine learning theory
Machine learning and time series

Machine learning & stationary time series
Nonstationary Markov chains

Online prediction approach
The online prediction approachprovides tools to aggregate predictors without stochastic assumptions on the data.

Pierre Alquier

Machine learning theory for time series

Short introduction to machine learning theory
Machine learning and time series

Machine learning & stationary time series
Nonstationary Markov chains

Online prediction approach
The online prediction approachprovides tools to aggregate predictors without stochastic assumptions on the data.

C. Giraud, F. Roueff, A.
Sanchez-Perez. Aggregation ofpredictors for nonstationary
sub-linear processes and online
adaptive forecasting of time varying
autoregressive processes. The
Annals of Statistics, 2015.

takes advantage of this approach to predict time varying
AR processes.
Pierre Alquier

Machine learning theory for time series

Short introduction to machine learning theory
Machine learning and time series

Machine learning & stationary time series
Nonstationary Markov chains1

Short introduction to machine learning theory2

Machine learning and time series
Machine learning & stationary time series
Nonstationary Markov chains

Pierre Alquier

Machine learning theory for time series

Short introduction to machine learning theory
Machine learning and time series

Machine learning & stationary time series
Nonstationary Markov chains

Nonstationary Markov chains

P. Alquier, P. Doukhan, X. Fan.
Exponential inequalities for
nonstationary Markov Chains.
Preprint arxiv :1808.08811, 2018.

Pierre Alquier

Machine learning theory for time series

Short introduction to machine learning theory
Machine learning and time series

Machine learning & stationary time series
Nonstationary Markov chains

Non-stationary Markov chains
We now assume
Xt = Ft (Xt−1 , εt ),Pierre Alquier

Machine learning theory for time series

Short introduction to machine learning theory
Machine learning and time series

Machine learning & stationary time series
Nonstationary Markov chains

Non-stationary Markov chains
We now assume
Xt = Ft (Xt−1 , εt ),sup E d Ft (x, ε1 ), Ft (x 0 , ε1 ) ≤ ρd(x, x 0 )t

sup d(Ft (x, y ), Ft (x, y 0 )) ≤ C δ(y , y 0 ).
t

Pierre Alquier

Machine learning theory for time series

Short introduction to machine learning theory
Machine learning and time series

Machine learning & stationary time series
Nonstationary Markov chains

Non-stationary Markov chains
We now assume
Xt = Ft (Xt−1 , εt ),sup E d Ft (x, ε1 ), Ft (x 0 , ε1 ) ≤ ρd(x, x 0 )t

sup d(Ft (x, y ), Ft (x, y 0 )) ≤ C δ(y , y 0 ).
t

Example 1 : time-varying AR(1)Xt = at Xt−1 + εt , sup |at | ≤ ρ.
t

Pierre Alquier

Machine learning theory for time series

Short introduction to machine learning theory
Machine learning and time series

Machine learning & stationary time series
Nonstationary Markov chains

Non-stationary Markov chains
We now assume
Xt = Ft (Xt−1 , εt ),sup E d Ft (x, ε1 ), Ft (x 0 , ε1 ) ≤ ρd(x, x 0 )t

sup d(Ft (x, y ), Ft (x, y 0 )) ≤ C δ(y , y 0 ).
t

Example 1 : time-varying AR(1)Xt = at Xt−1 + εt , sup |at | ≤ ρ.
t

Example 2 : T -periodic AR(1)Xt = at[T ] Xt−1 + εt , max |at | ≤ ρ.
1≤t≤T

Pierre Alquier

Machine learning theory for time series

Short introduction to machine learning theory
Machine learning and time series

Machine learning & stationary time series
Nonstationary Markov chains

Example : T -periodic AR(1)4-periodic AR(1), (a1 , a2 , a3 , a4 ) = (0.8, 0.5, 0.9, −0.7).

Figure – Simulated data.
Pierre Alquier

Figure – Autocorrelations.
Machine learning theory for time series

Short introduction to machine learning theory
Machine learning and time series

Machine learning & stationary time series
Nonstationary Markov chains

Bernstein’s inequality
Theorem (ADF18)
Assume that, for any k ≥ 2,i k!
h
E GX1 (X1 )k ≤ V1 M k−2 , and2hi k!
E Gε (ε)k ≤ V2 M k−2 .
2Consider a separately Lipschitz function f : X n → R. For anys ∈ [0, δ −1 ),(n − 1)s 2 V±s{f (X1 ,...,Xn )−E[f (X1 ,...,Xn )]}E [e] ≤ exp.
2(1 − s δ)
Pierre Alquier

Machine learning theory for time series

Short introduction to machine learning theory
Machine learning and time series

Machine learning & stationary time series
Nonstationary Markov chains

Problem : estimation of the (best) period
From now, assume that
Xt = ft∗ (Xt−1 ) + εt(not necessarily periodic, but we hope so).

Pierre Alquier

Machine learning theory for time series

Short introduction to machine learning theory
Machine learning and time series

Machine learning & stationary time series
Nonstationary Markov chains

Problem : estimation of the (best) period
From now, assume that
Xt = ft∗ (Xt−1 ) + εt(not necessarily periodic, but we hope so).
Let (fθ , θ ∈ Θ) be a set of predictors X → X , define H(ε) as
log |Θ(ε) |. Put, for any T and θ1:T = (θ1 , . . . , θT ) ∈ ΘT :n
1 X
rn (θ1:T ) =`(fθi[T ] (Xi−1 ) − Xi )n − 1 i=2
R(θ1:T ) = E[rn (θ1:T )]Pierre Alquier

Machine learning theory for time series

Short introduction to machine learning theory
Machine learning and time series

Machine learning & stationary time series
Nonstationary Markov chains

Problem : estimation of the (best) period
From now, assume that
Xt = ft∗ (Xt−1 ) + εt(not necessarily periodic, but we hope so).
Let (fθ , θ ∈ Θ) be a set of predictors X → X , define H(ε) as
log |Θ(ε) |. Put, for any T and θ1:T = (θ1 , . . . , θT ) ∈ ΘT :n
1 X
rn (θ1:T ) =`(fθi[T ] (Xi−1 ) − Xi )n − 1 i=2
"
#
T
1 X
C0 T
E[`(fθt[T ] (Xt−1 ) − Xt )] ±R(θ1:T ) = E[rn (θ1:T )] ∈
T t=1
n−1
h
i
Gε (0)∗
if actually ft∗ = ft[T
,
where
C
=
L(1
+
ρ)
+
G
(0)
.
0
X1
]
1−ρ
Pierre Alquier

Machine learning theory for time series

Short introduction to machine learning theory
Machine learning and time series

Machine learning & stationary time series
Nonstationary Markov chains

Estimators
Estimation for a given period T :θ̂1:T = (θ̂1 , . . . , θT ) =argminrn (θ1:T ).

θ1:T =(θ1 ,...,θT )Period selection :
C1T̂ = argmin rn (fˆ1:T ) +2
1≤T ≤Tmaxs1
T H( Ln)n−1√where C1 is as in the stationary case : C1 = 4(1 + ρ)L V.

Pierre Alquier

Machine learning theory for time series

Short introduction to machine learning theory
Machine learning and time series

Machine learning & stationary time series
Nonstationary Markov chains

Analysis of the estimators
Theorem (ADF18)
1
As soon as n ≥ 1 + 4δ 2 Tmax H( Ln)/V, with probability at least
1 − α,"

R(θ̂1:T̂ ) ≤

inf

inf

1≤T ≤Tmax θ1:T ∈ΘTs+ C1

R(θ1:T )#1
log 4Tαmax)
T H( Ln
C3+ C2 √
+
.
n−1
n
n−1

Pierre Alquier

Machine learning theory for time series

Short introduction to machine learning theory
Machine learning and time series

Machine learning & stationary time series
Nonstationary Markov chains

Analysis of the estimators
Theorem (ADF18)
1
As soon as n ≥ 1 + 4δ 2 Tmax H( Ln)/V, with probability at least
1 − α,"

R(θ̂1:T̂ ) ≤

inf

inf

1≤T ≤Tmax θ1:T ∈ΘTs+ C1

R(θ1:T )#1
log 4Tαmax)
T H( Ln
C3+ C2 √
+
.
n−1
n
n−1

In practice, C1 , C2 and C3 are too large and ρ is not known
anyway... we recommend to use the slope heuristic here.
Pierre Alquier

Machine learning theory for time series

Short introduction to machine learning theory
Machine learning and time series

Machine learning & stationary time series
Nonstationary Markov chains

Slope heuristic

Figure – Empirical risk as a function of T .
Pierre Alquier

Machine learning theory for time series

Short introduction to machine learning theory
Machine learning and time series

Machine learning & stationary time series
Nonstationary Markov chains

Thank you !

Pierre Alquier

Machine learning theory for time series