Deviation inequalities for time series : introduction
Non-homogeneous Markov chains

Deviation inequalities for Markov chains,with applications to SGD
and empirical risk minimization
Pierre AlquierHigh-Dimensional Statistical Modeling Team Seminar
March 1st, 2022

Pierre Alquier, RIKEN AIP

Deviation inequalities for Markov chains

Deviation inequalities for time series : introduction
Non-homogeneous Markov chains

Co-authors
Fan, X. and Alquier, P. and Doukhan, P. (2021). Deviation inequalities for stochastic
approximation by averaging. Preprint arXiv :2102.08685.

Xiequan Fan

Paul Doukhan

Tianjin University

CY Cergy Paris Université

Pierre Alquier, RIKEN AIP

Deviation inequalities for Markov chains

Deviation inequalities for time series : introduction
Non-homogeneous Markov chains

Why deviation inequalities ?
Deviation inequalities for time series

Objective

General problem in probability and statistics()
nn
1X
1 X P
Xi − EXi ≥ x ≤ ?
n i=1
ni=1

Pierre Alquier, RIKEN AIP

Deviation inequalities for Markov chains

Deviation inequalities for time series : introduction
Non-homogeneous Markov chains

Why deviation inequalities ?
Deviation inequalities for time series

What can we expect ? (1/2)
Chebyshev’s inequality
no Var(U)P |U − E(U)| ≥ x ≤.
x2
In a first time, assume the Xi ’s are independent, E(Xi ) = µand Var(Xi ) = σ 2 ,(Pn1X
Xi − µ ≥ xn i=1)

PVar ( ni=1 Xi )≤n2 x 2=Pierre Alquier, RIKEN AIP

σ2.
nx 2

Deviation inequalities for Markov chains

Deviation inequalities for time series : introduction
Non-homogeneous Markov chains

Why deviation inequalities ?
Deviation inequalities for time series

But...

(Photo : Wikipedia).
Pierre Alquier, RIKEN AIP

Deviation inequalities for Markov chains

Deviation inequalities for time series : introduction
Non-homogeneous Markov chains

Why deviation inequalities ?
Deviation inequalities for time series

What can we expect ? (2/2)(Pn1Xn i=1)
Xi − µ ≥ xσ2≤ 2.
nx

However, CLT :
rn
σ2n

1X
Xi − µn i=1!
N (0, 1).

So, we expect :(Pn1X
Xi − µ ≥ xn i=1)

Pierre Alquier, RIKEN AIP √ x2nx n2e− 2σ2' 2Φ∼ x √n √ .
σ2πσDeviation inequalities for Markov chains

Deviation inequalities for time series : introduction
Non-homogeneous Markov chains

Why deviation inequalities ?
Deviation inequalities for time series

Chernoff boundChernoff boundnono E es(U−E(U)) s(U−E(U))
sx
P U − E(U) ≥ x = P e
≥e
≤
.
esx

(Pn1X
Xi − µ ≥ xn i=1s Pni=1 (Xi −µ))≤E en

esx
−sx

=enY

s
E e n (Xi −µ) .

i=1Pierre Alquier, RIKEN AIPDeviation inequalities for Markov chains

Deviation inequalities for time series : introduction
Non-homogeneous Markov chains

Why deviation inequalities ?
Deviation inequalities for time series

Hoeffding’s inequality(Pn1Xn i=1)
Xi − µ ≥ x−sx

≤enY


s
E e n (Xi −µ) .

i=1

Hoeffding’s lemma - U bounded : a ≤ U ≤ bs 2 (b−a)2
E es[U−E(U)] ≤ e 8 .
Hoeffding’s inequality
Assume the Xi ’s are independent and a ≤ Xi ≤ b,)(n21X− 2nx
PXi − µ ≥ x ≤ 2e (b−a)2 .
n i=1Pierre Alquier, RIKEN AIP

Deviation inequalities for Markov chains

Deviation inequalities for time series : introduction
Non-homogeneous Markov chains

Why deviation inequalities ?
Deviation inequalities for time series

McDiarmid’s inequality
McDiarmid’s inequality
Assume the Xi ’s are independent and f : X n → R such that|f (x1 , . . . , xi−1 , xi , xi+1 , . . . , xn ) − f (x1 , . . . , xi−1 , xi0 , xi+1 , . . . , xn )| ≤ c.

then2x 2 nf (X1 , . . . , Xn ) − E[f (X1 , . . . , Xn )]P≥ x ≤ 2e− c 2 .
nWe recover Hoeffding for f (x1 , . . . , xn ) =Pierre Alquier, RIKEN AIP

Pn

i=1 xi , c = (b − a).

Deviation inequalities for Markov chains

Deviation inequalities for time series : introduction
Non-homogeneous Markov chains

Why deviation inequalities ?
Deviation inequalities for time series

Assumptions on moments
Hoeffding’s lemma - U bounded : a ≤ U ≤ bs 2 (b−a)2
E es[U−E(U)] ≤ e 8 .
In general, why not assuming U satisfies such an inequality ?
Definition - sub-Gaussian random variable U
2 2E es[U−E(U)] ≤ es C0
U sub-Gaussian ⇔ ∀k ∈ N, E(|U|2k ) ≤ k!C1k .

Pierre Alquier, RIKEN AIP

Deviation inequalities for Markov chains

Deviation inequalities for time series : introduction
Non-homogeneous Markov chains

Why deviation inequalities ?
Deviation inequalities for time series

Contents1

Deviation inequalities for time series : introduction
Why deviation inequalities ?
Deviation inequalities for time series2

Non-homogeneous Markov chains
Inequalities for non-homogeneous Markov chains
Applications in machine learning

Pierre Alquier, RIKEN AIP

Deviation inequalities for Markov chains

Deviation inequalities for time series : introduction
Non-homogeneous Markov chains

Why deviation inequalities ?
Deviation inequalities for time series

Objective of this talkObjective : for some time series {Xt , t = 0, . . . , ∞}(nn1 X 1X
Xt − E
Xt ≥ xn t=1nt=1)

f (X1 , . . . , Xn ) − E[f (X1 , . . . , Xn )]≥xnP
P

Pierre Alquier, RIKEN AIP≤?
≤?

Deviation inequalities for Markov chains

Deviation inequalities for time series : introduction
Non-homogeneous Markov chains

Why deviation inequalities ?
Deviation inequalities for time series

Objective of this talkObjective : for some time series {Xt , t = 0, . . . , ∞}(nn1 X 1X
Xt − E
Xt ≥ xn t=1nt=1)

f (X1 , . . . , Xn ) − E[f (X1 , . . . , Xn )]
≥xn

P
P

Pierre Alquier, RIKEN AIP≤?
≤?

Deviation inequalities for Markov chains

Deviation inequalities for time series : introduction
Non-homogeneous Markov chains

Why deviation inequalities ?
Deviation inequalities for time series

Deviation for time series : an active research field

Pierre Alquier, RIKEN AIP

Deviation inequalities for Markov chains

Deviation inequalities for time series : introduction
Non-homogeneous Markov chains

Why deviation inequalities ?
Deviation inequalities for time series

A remarkable result for Markov chainsstudy Markov chains ofthe form
Xn = F (Xn−1 , εn )provide deviationinequalities when 0E d F (x, εn ), F (x , εn )≤ ρd(x, x 0 )for some ρ < 1.

Pierre Alquier, RIKEN AIP

Deviation inequalities for Markov chains

Deviation inequalities for time series : introduction
Non-homogeneous Markov chains

Why deviation inequalities ?
Deviation inequalities for time series

Example (1/2)
AR(1) process
Xn = F (Xn−1 , εn ) := ρXn−1 + εn|F (x, εn ) − F (x 0 , εn )| ≤ ρ|x − x 0 |ρ=0Pierre Alquier, RIKEN AIP

ρ = 0.5
Deviation inequalities for Markov chains

Deviation inequalities for time series : introduction
Non-homogeneous Markov chains

Why deviation inequalities ?
Deviation inequalities for time series

Example (2/2)
AR(1) process
Xn = F (Xn−1 , εn ) := ρXn−1 + εn|F (x, εn ) − F (x 0 , εn )| ≤ ρ|x − x 0 |ρ = 0.8
Pierre Alquier, RIKEN AIP

ρ=1
Deviation inequalities for Markov chains

Deviation inequalities for time series : introduction
Non-homogeneous Markov chains

Why deviation inequalities ?
Deviation inequalities for time series

What happens for non-homogeneous chains ?
AR(1) process with varying coefficients
Xn = Fn (Xn−1 , εn ) := ρn Xn−1 + εnρn = 1 − √1n .
Pierre Alquier, RIKEN AIP

Deviation inequalities for Markov chains

Deviation inequalities for time series : introduction
Non-homogeneous Markov chains

Inequalities for non-homogeneous Markov chains
Applications in machine learning

Inequalities for non-homogeneous Markov chains

1

Deviation inequalities for time series : introduction
Why deviation inequalities ?
Deviation inequalities for time series

2Non-homogeneous Markov chains
Inequalities for non-homogeneous Markov chains
Applications in machine learning

Pierre Alquier, RIKEN AIP

Deviation inequalities for Markov chains

Deviation inequalities for time series : introduction
Non-homogeneous Markov chains

Inequalities for non-homogeneous Markov chains
Applications in machine learning

A class of non-homogeneous Markov chains
Xn takes values in (X , d). Example : X = Rd , d large.
(εn ) are i.i.d random variables in (Y, δ).
Definition1
Xn = Fn (Xn−1 , εn ).
 
02
E d Fn (x, εn ), Fn (x , εn )≤ ρn d(x, x 0 ).
03d Fn (x, y ), Fn (x, y ) ≤ τn δ(y , y 0 ) + ξn .

Pierre Alquier, RIKEN AIP

Deviation inequalities for Markov chains

Deviation inequalities for time series : introduction
Non-homogeneous Markov chains

Inequalities for non-homogeneous Markov chains
Applications in machine learning

VAR with variying coefficients

Phillips, P.C.B. (1988). Regression theory for near integrated time series. Econometrica.

Xn ∈ Rd .
(εn ) are i.i.d N (0, σ 2 Id ).
1Xn = Fn (Xn−1 , εn ) = An Xn−1 + εn .

2n xk
ρn = kAn kop = supx6=0 kAkxk−−−→ 1.

3

τn = 1, ξn = 0.

<n→∞Pierre Alquier, RIKEN AIP

Deviation inequalities for Markov chains

Deviation inequalities for time series : introduction
Non-homogeneous Markov chains

Inequalities for non-homogeneous Markov chains
Applications in machine learning

Example : stochastic optimization
Minimize L(x) =NX`i (x)

i=1

For I drawn uniformly in {1, . . . , N} with M elements,X
ˆ n L(x) := 1∇∇`i (x).
M i∈I
Projected tochastic gradient descent (SGD) :hiγ ˆ
Xn = ΠC Xn−1 − α ∇n L(Xn−1 )nProjected stochastic gradient Langevin descent (SGLD) :hη iγ ˆXn = ΠC Xn−1 − α ∇n L(Xn−1 ) + β εnnn
Pierre Alquier, RIKEN AIP

Deviation inequalities for Markov chains

Deviation inequalities for time series : introduction
Non-homogeneous Markov chains

Inequalities for non-homogeneous Markov chains
Applications in machine learning

Example : SGD
Assume L is m-strongly convex, M-Lipschitz and ∇L is`-Lipschitz.
SGD - α ∈ [0, 1], γ > 0123ih
ˆ n L(Xn−1 ) .
Xn = Fn (Xn−1 , εn ) = ΠC Xn−1 − nγα ∇ρn ∼ 1 − mγnα for α > 0,ρn = 1 − 2mγ + `2 γ 2 if α = 0.

ξn = 2γM, τn = 0.
nαPierre Alquier, RIKEN AIP

Deviation inequalities for Markov chains

Deviation inequalities for time series : introduction
Non-homogeneous Markov chains

Inequalities for non-homogeneous Markov chains
Applications in machine learning

Example : SGLD
Assume L is m-strongly convex, M-Lipschitz and ∇L is`-Lipschitz.
SGLD - α, β ∈ [0, 1], γ, η > 0, εn ∼ N (0, 1)hiˆ n L(Xn−1 ) + ηβ εn .
1
Xn = Fn (Xn−1 , εn ) = ΠC Xn−1 − nγα ∇n23ρn ∼ 1 − mγ
nα for α > 0,ρn = 1 − 2mγ + `2 γ 2 if α = 0.

ξn = 2γM, τn = nηβ .
nαPierre Alquier, RIKEN AIP

Deviation inequalities for Markov chains

Deviation inequalities for time series : introduction
Non-homogeneous Markov chains

Inequalities for non-homogeneous Markov chains
Applications in machine learning

Deviation inequality
Theorem (Proposition 3.1 in the paper) - p ∈ [1, +∞], d ∈ N
Assume f : X n → Rd such that|f (x1 , . . . , xi , . . . , xn ) − f (x1 , . . . , xi0 , . . . , xn )| ≤ d(xi , xi0 ),Eεn ([Eε0n δ(εn , ε0n )]k ) ≤ C1k k! and a similar condition for X1 ,(f (X1 , . . . , Xn ) − E[f (X1 , . . . , Xn )]≥xnp(e−cp,d nx2e−cp,d n(x1x>1 +x 1x≤1 )1−2α 2xe−cp,d nP≤)

ρn ≤ 1 − ρ < 1, τn + ξn ≤ nτα , α ∈ (0, 1]
ρn ≤ 1 − nρα , τn + ξn ≤ nτα , α ∈ [0, 1),ρn ≤ 1 − nρα , τn + ξn ≤ τ ,α ∈ (0, 1/2).

Pierre Alquier, RIKEN AIP

Deviation inequalities for Markov chains

Deviation inequalities for time series : introduction
Non-homogeneous Markov chains

Inequalities for non-homogeneous Markov chains
Applications in machine learning

Proof technique
The proof technique relies on martingale decomposition :f (X1 , . . . , Xn ) − E[f (X1 , . . . , Xn )] =nX

Mt

t=1whereMt = E[f (X1 , . . . , Xn )|X1 , . . . , Xt ]−E[f (X1 , . . . , Xn )|X1 , . . . , Xt−1 ].
Conditional Chernoff :h s Pn−1
is
Mt
Mns Pnt=1nn
ME eE e |X1 , . . . , Xn−1E e n t=1 t=.
esxesxs
Here the study of E e n Mn |X1 , . . . , Xn−1 requires some care...
Pierre Alquier, RIKEN AIP

Deviation inequalities for Markov chains

Deviation inequalities for time series : introduction
Non-homogeneous Markov chains

Inequalities for non-homogeneous Markov chains
Applications in machine learning

Shameless name-dropping
In the paper, we provide an exhaustive list of inequalities,
under various moment assumptions :exponential inequalities :McDiarmid,
Hoeffding,Bernstein.

semi-exponential inequalities :Fuk-Nagaev,
von Bahr-Esseen.

moment inequalities :Marcinkiewicz-Zygmund,von Bahr-Esseen.
Pierre Alquier, RIKEN AIP

Deviation inequalities for Markov chains

Deviation inequalities for time series : introduction
Non-homogeneous Markov chains

Inequalities for non-homogeneous Markov chains
Applications in machine learning

Applications

1

Deviation inequalities for time series : introduction
Why deviation inequalities ?
Deviation inequalities for time series

2Non-homogeneous Markov chains
Inequalities for non-homogeneous Markov chains
Applications in machine learning

Pierre Alquier, RIKEN AIP

Deviation inequalities for Markov chains

Deviation inequalities for time series : introduction
Non-homogeneous Markov chains

Inequalities for non-homogeneous Markov chains
Applications in machine learning

Empirical risk minimization (1/2)
In the stationary case,n1X`(θ, Xi ) = Rn (θ)
f (X1 , . . . , Xn ) =n t=1thenE [f (X1 , . . . , Xn )] = E [`(θ, X )] = R(θ).
P
R(θ) − Rn (θ) ≥ x

Pierre Alquier, RIKEN AIP

 −cnx, e2e−cn(x1x>1 +x 1x≤1 ) ,≤ −cn1−2α x 2e.

Deviation inequalities for Markov chains

Deviation inequalities for time series : introduction
Non-homogeneous Markov chains

Inequalities for non-homogeneous Markov chains
Applications in machine learning

Empirical risk minimization (2/2)

ERMθ̂ = arg min Rn (θ).
θ∈Θ

Say Card(Θ) = N is finite,  Ne−cnx ,2Ne−cn(x1x>1 +x 1x≤1 ) ,P R(θ̂) ≥ Rn (θ̂) + x ≤
1−2α x 2Ne−cn.

Pierre Alquier, RIKEN AIP

Deviation inequalities for Markov chains

Deviation inequalities for time series : introduction
Non-homogeneous Markov chains

Inequalities for non-homogeneous Markov chains
Applications in machine learning

Application to SGLD (1/2)
L is m-strongly convex, M-Lipschitz and ∇L is `-Lipschitz.
SGLD - α ∈ (0, 1), β < α, γ > 0, η ≥ 0nhη iγ ˆ1X
Xn = ΠC Xn−1 − α ∇Xt .
L(X)+ε,X̄=nn−1nnnnβn t=1

For some cp,d = cp,d (`, m, M),
2P X̄n − E(X̄n ) ≥ x ≤ e−cp,d n(x1x>1 +x 1x≤1 ) .
pPierre Alquier, RIKEN AIP

Deviation inequalities for Markov chains

Deviation inequalities for time series : introduction
Non-homogeneous Markov chains

Inequalities for non-homogeneous Markov chainsApplications in machine learning

Application to SGLD (2/2)
Theorem - Moulines and Bach 2011
EkX̄n − x ∗ k22 ≤C0.
nMoulines, E. and Bach, F. (2011). Non-asymptotic analysis of stochastic approximation
algorithms for machine learning. NIPS.

Combine with our inequalitys1
C0 + c2,dlog∗PX̄n − x≤n2Pierre Alquier, RIKEN AIP1δ≥ 1 − δ.

Deviation inequalities for Markov chains