Introduction
Matrix completion : the independent caseTime series completion

Tight Risk Bound for High Dimensional
Time Series Completion
Pierre Alquier

EcoDep 2021 Conference
September 16, 2021

Pierre Alquier, RIKEN AIPTime Series Completion

Introduction
Matrix completion : the independent caseTime series completion

Co-authors

Alquier, P., Marie, N. and Rosier, A. (2021). Tight Risk Bound for High Dimensional Time Series
Completion. Preprint arXiv :2102.08178.

Nicolas Marie

Amélie Rosier

Université Paris Nanterre

ESME Sudria and Université Paris Nanterre

Pierre Alquier, RIKEN AIPTime Series Completion

Introduction
Matrix completion : the independent caseTime series completion

Multivariate time series

Pierre Alquier, RIKEN AIPTime Series Completion

Introduction
Matrix completion : the independent caseTime series completion

Multivariate time series

S. Imperio et al. (2010). Investigating
population dynamics in ungulates : Do
hunting statistics make up a good index
of population abundance ? Wildlife
Biology.

multivariate seriescorrelations
noisy observations
missing entries

Pierre Alquier, RIKEN AIPTime Series Completion

Introduction
Matrix completion : the independent caseTime series completion

Partially observed multivariate time series
i1234
5678..
.

. . . t − 3 t − 2 t − 1 t+0 t + 1 t + 2 t + 3
...
12.5
17
. . . 1.2
3.8
2.9
...
0
7.2
...
4.2
3.1
2.4
2.3
. . . 23.1
45.1 39.9
...
4.1
4.1
6.3
2.9
. . . 0.1
0.9
0...
34.7..
..
.
.
Pierre Alquier, RIKEN AIPTime Series Completion

...
...
...
...
...
...
...
...
...
..
.

Introduction
Matrix completion : the independent caseTime series completion

Exampleseconometrics : panel data with missing entries,
industry : data from sensors at multiple locations,
ecology : spatial data with observations from a few sites
only at each date,...
more generally, any situation where we have multivariate
time series and each measurement is expensive.

Pierre Alquier, RIKEN AIPTime Series Completion

Introduction
Matrix completion : the independent caseTime series completion

Matrix completion methods
matrix completion
algorithms exist, andwere successful inmany applications.
many of them arebased on a low-rank
assumption and on
matrix factorization.
however, the theory
was developped only in
the independent case.
Pierre Alquier, RIKEN AIPTime Series Completion

Introduction
Matrix completion : the independent caseTime series completion

Contents
1Introduction

2

Matrix completion : the independent caseMatrix completion model
Minimax rate of estimation

3

Time series completion
Generalization of the results for i.i.d data to time series
Using the time series structure : faster rates

Pierre Alquier, RIKEN AIPTime Series Completion

Introduction
Matrix completion : the independent caseTime series completion

Matrix completion model
Minimax rate of estimation

Contents
1

Introduction

2

Matrix completion : the independent caseMatrix completion modelMinimax rate of estimation

3Time series completion
Generalization of the results for i.i.d data to time series
Using the time series structure : faster rates

Pierre Alquier, RIKEN AIPTime Series Completion

Introduction
Matrix completion : the independent caseTime series completion

Matrix completion model
Minimax rate of estimation

Classical example : collaborative filtering

Stan
PierreZoe
BobOscar
Léa
Tony

Pierre Alquier, RIKEN AIPTime Series Completion

Introduction
Matrix completion : the independent caseTime series completion

Matrix completion model
Minimax rate of estimation

A statistical model
There is a d × T matrix M and n i.i.d observations Y1 , . . . , Yn
drawn as :(i` , j` ) drawn uniformly on {1, . . . , d} × {1, . . . , T },Y` = Mi` ,j` + ε`
where ε` is some noise (= 0 in the first papers on the topic,subgaussian with variance σ 2 later).

Pierre Alquier, RIKEN AIPTime Series Completion

Introduction
Matrix completion : the independent caseTime series completion

Matrix completion model
Minimax rate of estimation

A statistical model
There is a d × T matrix M and n i.i.d observations Y1 , . . . , Yn
drawn as :(i` , j` ) drawn uniformly on {1, . . . , d} × {1, . . . , T },Y` = Mi` ,j` + ε`
where ε` is some noise (= 0 in the first papers on the topic,subgaussian with variance σ 2 later).
Key assumption : k := rank(M)  min(d, T ) = K .

Pierre Alquier, RIKEN AIPTime Series Completion

Introduction
Matrix completion : the independent caseTime series completion

Matrix completion model
Minimax rate of estimation

SVD & matrix factorization

σ1 0 .

M =U1 . . . Uk . . .  ..
|{z=U (d×K )}|Pierre Alquier, RIKEN AIP



0 ...
..
. 0 ...
σk0...
{z=Σ (K ×K )Time Series Completion
}|V1T..
.

VkT..
.







{z}

=V T (K ×T )

Introduction
Matrix completion : the independent caseTime series completion

Matrix completion model
Minimax rate of estimation

SVD & matrix factorization
σ1
 0
 .

M =
U1 . . . Uk . . .  ..
|{z=U (d×K )M =  U1|}|

0 ...
..
. 0 ...
σk0...
{z=Σ (K ×K )


σ10

...
. . . Uk  
0σk{z}|=A (d×k)

Pierre Alquier, RIKEN AIPTime Series Completion
}|

VkT..
.







{z}

=V T (K ×T )V1T..
.
VkT{zV1T..
.

=B (k×T )}Introduction
Matrix completion : the independent caseTime series completion

Matrix completion model
Minimax rate of estimation

EstimationM̂ λ = arg min
XnX

min(d,T )(Y` − Xi` ,j` )2 + λ`=1Pierre Alquier, RIKEN AIPXh=1Time Series Completion

σh (X ) .
Introduction
Matrix completion : the independent caseTime series completion

Matrix completion model
Minimax rate of estimation

EstimationM̂ λ = arg minXnXmin(d,T )(Y` − Xi` ,j` )2 + λ

`=1X
h=1


σh (X ) .
Theorem
For a well chosen λ that does not depend on k, and underminimal assumptions on M, with large probability
21 X λσk(d + T ) log(d + T )M̂i,j − Mi,j ≤ Cst
dT i,jnKoltchinskii, V., Lounici, K. and Tsybakov, A. (2011). Nuclear-norm penalization and optimal
rates for noisy low-rank matrix completion. The Annals of Statistics.
Pierre Alquier, RIKEN AIPTime Series Completion

Introduction
Matrix completion : the independent caseTime series completion

Generalization of the results for i.i.d data to time series
Using the time series structure : faster rates

Contents
1Introduction

2Matrix completion : the independent caseMatrix completion model
Minimax rate of estimation

3Time series completion
Generalization of the results for i.i.d data to time series
Using the time series structure : faster rates

Pierre Alquier, RIKEN AIPTime Series Completion

Introduction
Matrix completion : the independent caseTime series completion

Generalization of the results for i.i.d data to time series
Using the time series structure : faster rates

Time series completion : the model

Pierre Alquier, RIKEN AIPTime Series Completion

Introduction
Matrix completion : the independent caseTime series completion

Generalization of the results for i.i.d data to time series
Using the time series structure : faster ratesTime series completion : the model
low-rank trend :M = |{z}A |{z}B
d×k k×T

Pierre Alquier, RIKEN AIPTime Series Completion

Introduction
Matrix completion : the independent caseTime series completion

Generalization of the results for i.i.d data to time series
Using the time series structure : faster rates

Time series completion : the model
low-rank trend :M = |{z}A |{z}B
d×k k×T

temporal correlated
noise ε :εi,t indep. εj,t 0 (i 6= j)εi,t not indep. εi,t 0

Pierre Alquier, RIKEN AIPTime Series Completion

IntroductionMatrix completion : the independent caseTime series completion

Generalization of the results for i.i.d data to time series
Using the time series structure : faster rates

Time series completion : the model
low-rank trend :M = |{z}A |{z}B
d×k k×T

temporal correlated
noise ε :εi,t indep. εj,t 0 (i 6= j)εi,t not indep. εi,t 0(i` , t` ) i.i.d uniform, ξ`observation noise :Y` = Mi` ,t` + εi` ,t` + ξ` .
Pierre Alquier, RIKEN AIPTime Series Completion

Introduction
Matrix completion : the independent caseTime series completion

Generalization of the results for i.i.d data to time series
Using the time series structure : faster rates

Assumptions
Reminder : the modelY` = Mi` ,t` + εi` ,t` + ξ` .

Pierre Alquier, RIKEN AIPTime Series Completion

Introduction
Matrix completion : the independent caseTime series completion

Generalization of the results for i.i.d data to time series
Using the time series structure : faster rates

Assumptions
Reminder : the modelY` = Mi` ,t` + εi` ,t` + ξ` .
√M = |{z}
A |{z}
B and |Ai,h |, |Bh,t | ≤ cA,B / k.
d×k k×T(i` , t` ) i.i.d uniform on {1, . . . , d} × {1 . . . , T } ;(εi,t )t=1,...,T is a bounded, φ-mixing time series :∞X|εi,t | ≤ mε andφεi,· (t) ≤ Φε .
t=1(ξ` ) are i.i.d, sub-exponential variables : for k ≥ 2,vξ cξq−2 q!
.
E(|ξ` | ) ≤2q

Pierre Alquier, RIKEN AIPTime Series Completion

Introduction
Matrix completion : the independent caseTime series completion

Generalization of the results for i.i.d data to time series
Using the time series structure : faster rates

Estimator and risk boundM̂ (k) =nX(Y` − Xi` ,j` )2 .
arg min
X =|{z}A |{z}
B `=1|{z}d×Td×k

Pierre Alquier, RIKEN AIP

k×TTime Series Completion

Introduction
Matrix completion : the independent caseTime series completion

Generalization of the results for i.i.d data to time series
Using the time series structure : faster rates

Estimator and risk boundM̂ (k) =nX(Y` − Xi` ,j` )2 .
arg min
X =|{z}A |{z}
B `=1|{z}
d×T

d×k

k×T

TheoremWith probability at least 1 − η,
2k(d + T ) log(n) + log
1 X  (k)M̂i,j − Mi,j ≤ C
dT i,jnwhere C = C (cA,B , mε , Φε , vξ , cξ ) is known.
Pierre Alquier, RIKEN AIPTime Series Completion 1ηIntroduction
Matrix completion : the independent caseTime series completion

Generalization of the results for i.i.d data to time series
Using the time series structure : faster rates

Remarks on the proof
12

decompose the P
difference between empirical
P risk andn112
expected risk n `=1 (Y` − Xi` ,j` ) − dT i,j (Mi,j − Xi,j )2in elementary terms.
some of these terms are sums of i.i.d variables. Boundthem via Bernstein inequality. Some are sums of φ-mixing
variables, use :Samson, P.-M. (2000). Concentration of measure inequalities for Markov chains and Φ-mixing
processes. The Annals of Probability.

3union bound.

Pierre Alquier, RIKEN AIPTime Series Completion

Introduction
Matrix completion : the independent caseTime series completion

Generalization of the results for i.i.d data to time series
Using the time series structure : faster ratesRemarks on the proof
12

decompose the P
difference between empirical
P risk andn112
expected risk n `=1 (Y` − Xi` ,j` ) − dT i,j (Mi,j − Xi,j )2
in elementary terms.
some of these terms are sums of i.i.d variables. Boundthem via Bernstein inequality. Some are sums of φ-mixing
variables, use :Samson, P.-M. (2000). Concentration of measure inequalities for Markov chains and Φ-mixing
processes. The Annals of Probability.

3union bound.

REMARK : if the εi,· satisfy another notion of mixing or weak-dependence, we can use alternative√
versions of Bernstein inequality but this lead to slower rates of convergence, in 1/ n.

Pierre Alquier, RIKEN AIPTime Series Completion

Introduction
Matrix completion : the independent caseTime series completion

Generalization of the results for i.i.d data to time series
Using the time series structure : faster rates

Rank selection(k̂ = arg min
1≤k≤Knk(d + T ) log(n)1X(Y` − Xi` ,j` )2 + C 0n `=1n)where C 0 = C 0 (cA,B , mε , Φε , vξ , cξ ) is known but too large.

Pierre Alquier, RIKEN AIPTime Series Completion

Introduction
Matrix completion : the independent caseTime series completion

Generalization of the results for i.i.d data to time series
Using the time series structure : faster rates

Rank selection(k̂ = arg min
1≤k≤Knk(d + T ) log(n)1X(Y` − Xi` ,j` )2 + C 0n `=1n)where C 0 = C 0 (cA,B , mε , Φε , vξ , cξ ) is known but too large.
In practice : we use the slope heuristic to calibrate a better C 0 .

Pierre Alquier, RIKEN AIPTime Series Completion

Introduction
Matrix completion : the independent caseTime series completion

Generalization of the results for i.i.d data to time series
Using the time series structure : faster rates

Rank selection(k̂ = arg min
1≤k≤Knk(d + T ) log(n)1X(Y` − Xi` ,j` )2 + C 0n `=1n)where C 0 = C 0 (cA,B , mε , Φε , vξ , cξ ) is known but too large.
In practice : we use the slope heuristic to calibrate a better C 0 .
TheoremWith probability at least 1 − η,1 XdT(k̂)
M̂i,j − Mi,j2≤Ci,jPierre Alquier, RIKEN AIP

00k(d + T ) log(n) + log
nTime Series Completion

 1
η.

Introduction
Matrix completion : the independent caseTime series completion

Generalization of the results for i.i.d data to time series
Using the time series structure : faster rates

Time series with a structure
Example : assume that the trends in M are p-periodic. Thismeans that
M = |{z}C (Ip | . . . |Ip ) .
|{z}| {z }
d×T

d×p

Pierre Alquier, RIKEN AIP=Λ (p×T )Time Series Completion

Introduction
Matrix completion : the independent caseTime series completion

Generalization of the results for i.i.d data to time series
Using the time series structure : faster rates

Time series with a structure
Example : assume that the trends in M are p-periodic. Thismeans that
M = |{z}C (Ip | . . . |Ip ) .
|{z}| {z }d×T

d×p=Λ (p×T )More generally, we can assume that there is a known structure
in M :
M = |{z}C |{z}
Λ|{z}d×T

d×p p×Tand still add the initial “low-rank decomposition” to ensure
correlations in the rows :M = |{z}A |{z}
B |{z}
Λ .
|{z}
d×T

d×k k×p p×T

Pierre Alquier, RIKEN AIPTime Series Completion

Introduction
Matrix completion : the independent caseTime series completion

Generalization of the results for i.i.d data to time series
Using the time series structure : faster rates

Faster ratesM̂ (k) =n
X
arg min(Y` − Xi` ,j` )2 .
X =|{z}A |{z}
B |{z}
Λ `=1|{z}
d×T

d×k

k×p

Pierre Alquier, RIKEN AIPp×TTime Series Completion

Introduction
Matrix completion : the independent caseTime series completion

Generalization of the results for i.i.d data to time series
Using the time series structure : faster rates

Faster ratesM̂ (k) =n
Xarg min(Y` − Xi` ,j` )2 .
X =|{z}A |{z}
B |{z}
Λ `=1|{z}
d×T

d×k

k×p

p×TTheorem
With probability at least 1 − η,1 X
dT(k)M̂i,j − Mi,j2k(d + p) log(n) + log≤Ci,jPierre Alquier, RIKEN AIPnTime Series Completion 1η.

Introduction
Matrix completion : the independent caseTime series completion

Generalization of the results for i.i.d data to time series
Using the time series structure : faster rates

Faster ratesM̂ (k) =nXarg min(Y` − Xi` ,j` )2 .
X =|{z}A |{z}
B |{z}
Λ `=1|{z}
d×T

d×k

k×p

p×T

TheoremWith probability at least 1 − η,1 X
dT(k)M̂i,j − Mi,j2k(d + p) log(n) + log≤Ci,jnWe also have a similar rank-selection procedure.
Pierre Alquier, RIKEN AIPTime Series Completion 1η.

Introduction
Matrix completion : the independent caseTime series completion

Generalization of the results for i.i.d data to time series
Using the time series structure : faster rates

RIKEN AIP : position in the ABI teamApproximate BayesianInference team (ABI), leadby Emtiyaz Khan
Please visit the team website
https ://team-approx-bayes.github.io/
Open Position : Research Scientist (1 position, Female only)
research only (= chargé de recherches),indefinite-term,
located in Tokyo center.

Pierre Alquier, RIKEN AIPTime Series Completion

Introduction
Matrix completion : the independent caseTime series completion

Pierre Alquier, RIKEN AIPGeneralization of the results for i.i.d data to time series
Using the time series structure : faster rates

Time Series Completion