Estimation dans un modèle linéaire parcimonieux
Généralisation à l’autorégression
Au-delà du modèle linéaire

Contributions à l’apprentissage statistiquedans les modèles parcimonieux
Pierre AlquierSoutenance d’HDR
Vendredi 06/12/2013
Université Paris 6
Pierre AlquierApprentissage statistique dans les modèles parcimonieux

Estimation dans un modèle linéaire parcimonieux
Généralisation à l’autorégression
Au-delà du modèle linéaire

2003-2006étudiant en thèse
dir. : Olivier Catoni
2006-2007 ATER
2007-2012 maître de conférences
2012-20XX lecturer

Pierre Alquier

Université Paris 6(financé par le CREST)
Université Paris Dauphine
Université Paris Diderot
University College Dublin

Apprentissage statistique dans les modèles parcimonieux

Estimation dans un modèle linéaire parcimonieux
Généralisation à l’autorégression
Au-delà du modèle linéaire

Introduction
Inégalités PAC-Bayésiennes

Contexte
On observe, sur un espace (Ω, A, P), n paires aléatoires(X1 , Y1 ), . . . , (Xn , Yn ) indépendantes sous P, Xi ∈ Rp etYi ∈ R. On suppose que
Yi = f (Xi ) + Wi
pour f mesurable Wi avec E(Wi |Xi ) = 0 et E(Wi2 |Xi ) ≤ σ 2 .

Pierre AlquierApprentissage statistique dans les modèles parcimonieux

Estimation dans un modèle linéaire parcimonieux
Généralisation à l’autorégression
Au-delà du modèle linéaire

Introduction
Inégalités PAC-Bayésiennes

Contexte
On observe, sur un espace (Ω, A, P), n paires aléatoires(X1 , Y1 ), . . . , (Xn , Yn ) indépendantes sous P, Xi ∈ Rp etYi ∈ R. On suppose que
Yi = f (Xi ) + Wi
pour f mesurable Wi avec E(Wi |Xi ) = 0 et E(Wi2 |Xi ) ≤ σ 2 .
Prédicteurs linéaires∀θ, x ∈ Rp ,Pierre Alquierfθ (x) := θ · x.

Apprentissage statistique dans les modèles parcimonieux

Estimation dans un modèle linéaire parcimonieux
Généralisation à l’autorégression
Au-delà du modèle linéaire

Introduction
Inégalités PAC-Bayésiennes

Contexte
On observe, sur un espace (Ω, A, P), n paires aléatoires(X1 , Y1 ), . . . , (Xn , Yn ) indépendantes sous P, Xi ∈ Rp etYi ∈ R. On suppose que
Yi = f (Xi ) + Wi
pour f mesurable Wi avec E(Wi |Xi ) = 0 et E(Wi2 |Xi ) ≤ σ 2 .
Prédicteurs linéaires∀θ, x ∈ Rp ,fθ (x) := θ · x.

Risquesn

1X
r (θ) :=
(Yi − fθ (Xi ))2 , R(θ) := E [r (θ)] et R = inf R.
n i=1
Pierre AlquierApprentissage statistique dans les modèles parcimonieux

Estimation dans un modèle linéaire parcimonieux
Généralisation à l’autorégression
Au-delà du modèle linéaire

Introduction
Inégalités PAC-Bayésiennes

Idée d’inégalité oracle/ I}θ̂IMCO = arg min{r (θ) : θi = 0 pour i ∈θI = arg min{R(θ) : θi = 0 pour i ∈/ I }.

Pierre AlquierApprentissage statistique dans les modèles parcimonieux

Estimation dans un modèle linéaire parcimonieux
Généralisation à l’autorégression
Au-delà du modèle linéaire

Introduction
Inégalités PAC-Bayésiennes

Idée d’inégalité oracle/ I}θ̂IMCO = arg min{r (θ) : θi = 0 pour i ∈θI = arg min{R(θ) : θi = 0 pour i ∈/ I }.
A design fixe, Wi ∼ N (0, σ 2 ),hi
σ 2 card(I )MCO) − R ≤ R(θI ) − R +E R(θ̂In

Pierre AlquierApprentissage statistique dans les modèles parcimonieux

Estimation dans un modèle linéaire parcimonieux
Généralisation à l’autorégression
Au-delà du modèle linéaire

Introduction
Inégalités PAC-Bayésiennes

Idée d’inégalité oracleθ̂IMCO = arg min{r (θ) : θi = 0 pour i ∈/ I}
θI = arg min{R(θ) : θi = 0 pour i ∈/ I }.
A design fixe, Wi ∼ N (0, σ 2 ),hi
σ 2 card(I )E R(θ̂IMCO ) − R ≤ R(θI ) − R +nPeut-on proposer θ̂ tel que

h
i


E R(θ̂) − R ≤ inf R(θI ) − R +I

Pierre Alquierσ 2 card(I )n?

Apprentissage statistique dans les modèles parcimonieux

Estimation dans un modèle linéaire parcimonieux
Généralisation à l’autorégression
Au-delà du modèle linéaire

Introduction
Inégalités PAC-Bayésiennes

Idée d’inégalité oracleθ̂IMCO = arg min{r (θ) : θi = 0 pour i ∈/ I}
θI = arg min{R(θ) : θi = 0 pour i ∈/ I }.
A design fixe, Wi ∼ N (0, σ 2 ),hi
σ 2 card(I )E R(θ̂IMCO ) − R ≤ R(θI ) − R +nOn peut fabriquer θ̂ tel que


h
i


σ 2 card(I )log(p)E R(θ̂) − R ≤ inf R(θI ) − R + C
Inet c’est le mieux que l’on puisse faire...
Bunea, F., Tsybakov, A. B. and Wegkamp, M. H. (2007) Aggregation for Gaussian Regression.
The Annals of Statistics 35(4), pp. 1674–1697.
Pierre AlquierApprentissage statistique dans les modèles parcimonieux

Estimation dans un modèle linéaire parcimonieux
Généralisation à l’autorégression
Au-delà du modèle linéaire

Introduction
Inégalités PAC-Bayésiennes

Comment obtenir des inégalités oracle ?
AIC,BIC...
Définition
Inég. oracle ?
Calcul ?

Pierre AlquierApprentissage statistique dans les modèles parcimonieux

Estimation dans un modèle linéaire parcimonieux
Généralisation à l’autorégression
Au-delà du modèle linéaire

Introduction
Inégalités PAC-Bayésiennes

Comment obtenir des inégalités oracle ?

Définition
Inég. oracle ?
Calcul ?

AIC,BIC...
min{r (θ) + λkθk0 }Pierre AlquierApprentissage statistique dans les modèles parcimonieux

Estimation dans un modèle linéaire parcimonieux
Généralisation à l’autorégression
Au-delà du modèle linéaire

Introduction
Inégalités PAC-Bayésiennes

Comment obtenir des inégalités oracle ?

Définition
Inég. oracle ?
Calcul ?

AIC,BIC...
min{r (θ) + λkθk0 }ouiPierre AlquierApprentissage statistique dans les modèles parcimonieux

Estimation dans un modèle linéaire parcimonieux
Généralisation à l’autorégression
Au-delà du modèle linéaire

Introduction
Inégalités PAC-Bayésiennes

Comment obtenir des inégalités oracle ?

Définition
Inég. oracle ?
Calcul ?

AIC,BIC...
min{r (θ) + λkθk0 }oui
p petit

Pierre AlquierApprentissage statistique dans les modèles parcimonieux

Estimation dans un modèle linéaire parcimonieux
Généralisation à l’autorégression
Au-delà du modèle linéaire

Introduction
Inégalités PAC-Bayésiennes

Comment obtenir des inégalités oracle ?

Définition
Inég. oracle ?
Calcul ?

AIC,BIC...
min{r (θ) + λkθk0 }oui
p petit

Pierre Alquier

LASSO

Apprentissage statistique dans les modèles parcimonieux

Estimation dans un modèle linéaire parcimonieux
Généralisation à l’autorégression
Au-delà du modèle linéaire

Introduction
Inégalités PAC-Bayésiennes

Comment obtenir des inégalités oracle ?

Définition
Inég. oracle ?
Calcul ?

AIC,BIC...
min{r (θ) + λkθk0 }oui
p petit

Pierre Alquier

LASSO
min{r (θ) + λkθk1 }Apprentissage statistique dans les modèles parcimonieux

Estimation dans un modèle linéaire parcimonieux
Généralisation à l’autorégression
Au-delà du modèle linéaire

Introduction
Inégalités PAC-Bayésiennes

Comment obtenir des inégalités oracle ?

Définition
Inég. oracle ?
Calcul ?

AIC,BIC...
min{r (θ) + λkθk0 }oui
p petit

Pierre Alquier

LASSO
min{r (θ) + λkθk1 }p grandApprentissage statistique dans les modèles parcimonieux

Estimation dans un modèle linéaire parcimonieux
Généralisation à l’autorégression
Au-delà du modèle linéaire

Introduction
Inégalités PAC-Bayésiennes

Comment obtenir des inégalités oracle ?

Définition
Inég. oracle ?
Calcul ?

AIC,BIC...
min{r (θ) + λkθk0 }oui
p petit

Pierre Alquier

LASSO
min{r (θ) + λkθk1 }hypothèses sur X1 , . . . , Xn
p grandApprentissage statistique dans les modèles parcimonieux

Estimation dans un modèle linéaire parcimonieux
Généralisation à l’autorégression
Au-delà du modèle linéaire

Introduction
Inégalités PAC-Bayésiennes

Comment obtenir des inégalités oracle ?

Définition
Inég. oracle ?
Calcul ?

AIC,BIC...
min{r (θ) + λkθk0 }oui
p petit

LASSO
min{r (θ) + λkθk1 }hypothèses sur X1 , . . . , Xn
p grand

Références pour pénalisation `0
Barron, A. R., Birgé, L. and Massart, P. (1999) Risk Bounds for Model Selection via Penalization.
Probability Theory and Related Fields 113(3), pp. 301–413.

Pierre AlquierApprentissage statistique dans les modèles parcimonieux

Estimation dans un modèle linéaire parcimonieux
Généralisation à l’autorégression
Au-delà du modèle linéaire

Introduction
Inégalités PAC-Bayésiennes

Comment obtenir des inégalités oracle ?

Définition
Inég. oracle ?
Calcul ?

AIC,BIC...
min{r (θ) + λkθk0 }oui
p petit

LASSO
min{r (θ) + λkθk1 }hypothèses sur X1 , . . . , Xn
p grand

Références pour pénalisation `0
Barron, A. R., Birgé, L. and Massart, P. (1999) Risk Bounds for Model Selection via Penalization.
Probability Theory and Related Fields 113(3), pp. 301–413.
Références pour pénalisation `1
Tibshirani, R. (1996) Regression Shrinkage and Selection via the LASSO. Journal of the Royal
Statistical Society : Series B 58(1), pp. 267–288.
Bickel, P., Ritov, Y. and Tsybakov, A. B. (2009) Simultaneous Analysis of LASSO and Dantzig
Selector. The Annals of Statistics 37(4), pp. 1705–1732.

Pierre AlquierApprentissage statistique dans les modèles parcimonieux

Estimation dans un modèle linéaire parcimonieux
Généralisation à l’autorégression
Au-delà du modèle linéaire

Introduction
Inégalités PAC-Bayésiennes

Comment obtenir des inégalités oracle ?

Définition
Inég. oracle ?
Calcul ?

AIC,BIC...
min{r (θ) + λkθk0 }oui
p petit

LASSO
min{r (θ) + λkθk1 }hypothèses sur X1 , . . . , Xn
p grand

Références pour pénalisation `0
Barron, A. R., Birgé, L. and Massart, P. (1999) Risk Bounds for Model Selection via Penalization.
Probability Theory and Related Fields 113(3), pp. 301–413.
Références pour pénalisation `1
Tibshirani, R. (1996) Regression Shrinkage and Selection via the LASSO. Journal of the Royal
Statistical Society : Series B 58(1), pp. 267–288.
Bickel, P., Ritov, Y. and Tsybakov, A. B. (2009) Simultaneous Analysis of LASSO and Dantzig
Selector. The Annals of Statistics 37(4), pp. 1705–1732.

→ idée : estimateur agrégé, calculable par Monte-Carlo
Dalalyan, A. and Tsybakov, A. B. (2008) Aggregation by Exponential Weighting, Sharp
PAC-Bayesian Bounds and Sparsity. Machine Learning 72(1-2), pp. 39–61.
Pierre AlquierApprentissage statistique dans les modèles parcimonieux

Estimation dans un modèle linéaire parcimonieux
Généralisation à l’autorégression
Au-delà du modèle linéaire

Introduction
Inégalités PAC-Bayésiennes

Plan de la présentation
1

Estimation dans un modèle linéaire parcimonieux
Introduction
Inégalités PAC-Bayésiennes

2

Généralisation à l’autorégression
Prédiction de séries temporelles
Inégalités PAC-Bayésiennes

3

Au-delà du modèle linéaire
Modèle à direction révélatrice parcimonieux
Régression de faible rang
Modèles à complexité bornée

Pierre AlquierApprentissage statistique dans les modèles parcimonieux

Estimation dans un modèle linéaire parcimonieux
Généralisation à l’autorégression
Au-delà du modèle linéaire

Introduction
Inégalités PAC-Bayésiennes

Premier estimateur agrégé θ̂λπI =αcard(I ) Pnpcard(I )Pierre Alquier

j=0 α

j

.

Apprentissage statistique dans les modèles parcimonieux

Estimation dans un modèle linéaire parcimonieux
Généralisation à l’autorégression
Au-delà du modèle linéaire

Introduction
Inégalités PAC-Bayésiennes

Premier estimateur agrégé θ̂λαcard(I )
 Pn
p

πI =

card(I )

j=0 α

j

.

Définition
P
θ̂λ =

h



2

)
r (θ̂IMCO ) + 2σ card(I
n

i

−λ
θ̂IMCOhi .
P
2σ 2 card(I )
MCO
)
+
π
exp
−λ
r
(
θ̂
I
I
card(I )≤nncard(I )≤n πI exp

Pierre AlquierApprentissage statistique dans les modèles parcimonieux

Estimation dans un modèle linéaire parcimonieux
Généralisation à l’autorégression
Au-delà du modèle linéaire

Introduction
Inégalités PAC-Bayésiennes

Premier estimateur agrégé θ̂λThéorème (A & Lounici 2011)
Les Xi déterministes et les W(i iid N (0, σ 2 ), λ = 1/(4σ 2 ),
E R(θ̂λ ) − R ≤ inf
R(θI ) − Rcard(I )≤n

)




1
4σ 2 log 1−α
σ 2 card(I )
pe
+
4 log
+1 +
.
n
αcard(I )nPierre AlquierApprentissage statistique dans les modèles parcimonieux

Estimation dans un modèle linéaire parcimonieux
Généralisation à l’autorégression
Au-delà du modèle linéaire

Introduction
Inégalités PAC-Bayésiennes

Premier estimateur agrégé θ̂λThéorème (A & Lounici 2011)
Les Xi déterministes et les W(i iid N (0, σ 2 ), λ = 1/(4σ 2 ),
E R(θ̂λ ) − R ≤ inf
R(θI ) − Rcard(I )≤n

)




1
4σ 2 log 1−α
σ 2 card(I )
pe
+
4 log
+1 +
.
n
αcard(I )nPreuve : Lemme de Stein + méthodes PAC-Bayésiennes :Leung, G. and Barron, A. R. (2006) Information Theory and Mixing Least-Square Regressions.
IEEE Transactions on Information Theory 52(8), pp. 3396–3410.1.
Catoni, O. (2004) Statistical Learning Theory and Stochastic Optimization. Ecole d’Été deProbabilités de Saint-Flour XXXI - 2001. J. Picard Editor. Springer Lecture Notes in Mathematics
1851.

Pierre AlquierApprentissage statistique dans les modèles parcimonieux

Estimation dans un modèle linéaire parcimonieux
Généralisation à l’autorégression
Au-delà du modèle linéaire

Introduction
Inégalités PAC-Bayésiennes

Deuxième estimateur agrégé θ̃λ1

on suppose que R(θ) = R et kθk1 ≤ K , soit uI proba.
uniforme sur {kθk1 ≤ K + 1, θi = 0 pour i ∈/ I } etXπ(dθ) =
πI uI (dθ),
card(I )≤n

Pierre AlquierApprentissage statistique dans les modèles parcimonieux

Estimation dans un modèle linéaire parcimonieux
Généralisation à l’autorégression
Au-delà du modèle linéaire

Introduction
Inégalités PAC-Bayésiennes

Deuxième estimateur agrégé θ̃λ1

on suppose que R(θ) = R et kθk1 ≤ K , soit uI proba.
uniforme sur {kθk1 ≤ K + 1, θi = 0 pour i ∈/ I } etXπ(dθ) =
πI uI (dθ),
card(I )≤n2

kf k∞ ≤ L, kXi k∞ ≤ L0 ,Pierre AlquierApprentissage statistique dans les modèles parcimonieux

Estimation dans un modèle linéaire parcimonieux
Généralisation à l’autorégression
Au-delà du modèle linéaire

Introduction
Inégalités PAC-Bayésiennes

Deuxième estimateur agrégé θ̃λ1

on suppose que R(θ) = R et kθk1 ≤ K , soit uI proba.
uniforme sur {kθk1 ≤ K + 1, θi = 0 pour i ∈/ I } etXπ(dθ) =
πI uI (dθ),
card(I )≤n2
3

kf k∞ ≤ L, kXi k∞ ≤ L0 ,Wi est sous-exponentiel (σ, ξ), Xi peuvent êtredéterministes ou aléatoires.

Pierre AlquierApprentissage statistique dans les modèles parcimonieux

Estimation dans un modèle linéaire parcimonieux
Généralisation à l’autorégression
Au-delà du modèle linéaire

Introduction
Inégalités PAC-Bayésiennes

Deuxième estimateur agrégé θ̃λ1

on suppose que R(θ) = R et kθk1 ≤ K , soit uI proba.
uniforme sur {kθk1 ≤ K + 1, θi = 0 pour i ∈/ I } etXπ(dθ) =
πI uI (dθ),
card(I )≤n2
3

kf k∞ ≤ L, kXi k∞ ≤ L0 ,Wi est sous-exponentiel (σ, ξ), Xi peuvent êtredéterministes ou aléatoires.

Définitiondρ̃λexp(−λr (θ))(θ) = Ret θ̃λ =dπexp(−λr (θ0 ))π(dθ0 )ΘKPierre AlquierZθρ̃λ (dθ).
ΘKApprentissage statistique dans les modèles parcimonieux

Estimation dans un modèle linéaire parcimonieux
Généralisation à l’autorégression
Au-delà du modèle linéaire

Introduction
Inégalités PAC-Bayésiennes

Deuxième estimateur agrégé θ̃λThéorème (A & Lounici 2011)
Pour C = C(σ, ξ, L, L0 , K ) connu, λ = n/C, pour tout ε > 0,("

P R(θ̃λ ) − R(θ) ≤ C inf R(θI ) − R(θ)
I

card(I ) log+



enp(K +1)
αcard(I )nPierre Alquier



log
+



2
ε(1−α)n #)≥ 1 − ε.

Apprentissage statistique dans les modèles parcimonieux

Estimation dans un modèle linéaire parcimonieux
Généralisation à l’autorégression
Au-delà du modèle linéaire

Introduction
Inégalités PAC-Bayésiennes

Deuxième estimateur agrégé θ̃λThéorème (A & Lounici 2011)
Pour C = C(σ, ξ, L, L0 , K ) connu, λ = n/C, pour tout ε > 0,("

P R(θ̃λ ) − R(θ) ≤ C inf R(θI ) − R(θ)
I

card(I ) log+



enp(K +1)
αcard(I )

n



log
+



2
ε(1−α)

 #)n≥ 1 − ε.

Preuve : inégalité de Bernstein + PAC-Bayes, suitCatoni, O. (2004) Statistical Learning Theory and Stochastic Optimization. Ecole d’Été deProbabilités de Saint-Flour XXXI - 2001. J. Picard Editor. Springer Lecture Notes in Mathematics
1851.

Pierre AlquierApprentissage statistique dans les modèles parcimonieux

Estimation dans un modèle linéaire parcimonieux
Généralisation à l’autorégression
Au-delà du modèle linéaire

Introduction
Inégalités PAC-Bayésiennes

Publications liées à cette thématique

Alquier, P. (2008) Iterative Feature Selection in Least Square Regression Estimation. Annales del’Institut Henri Poincarré, Probabilités et Statistiques 44(1), pp. 47–88.
Alquier, P. (2008) Density Estimation with Quadratic Loss, a Confidence Intervals Method.
ESAIM Probability & Statistics 12, pp. 438–463.
Alquier, P. (2008) LASSO, Iterative Feature Selection & the Correlation Selector : Oracle
Inequalities & Numerical Performances. Electronic Journal of Statistics 2, pp. 1129–1152.
Alquier, P. & Lounici, K. (2011) PAC-Bayesian Theorems for Sparse Regression Estimation with
Exponential Weights. Electronic Journal of Statistics 5, pp. 127–145.
Alquier, P. & Hebiri, M. (2011) Generalization of L1 Constraints for High Dimensional Regression
Problems. Statistics & Probability Letters 81(12), pp. 1760–1765.
Alquier, P. & Hebiri, M. (2012) Transductive Versions of the LASSO & the Dantzig Selector.
Journal of Statistical Planning & Inference 142(9), pp. 2485–2500.

Pierre AlquierApprentissage statistique dans les modèles parcimonieux

Estimation dans un modèle linéaire parcimonieux
Généralisation à l’autorégression
Au-delà du modèle linéaire

Prédiction de séries temporelles
Inégalités PAC-Bayésiennes

Menu
1

Estimation dans un modèle linéaire parcimonieux
Introduction
Inégalités PAC-Bayésiennes

2

Généralisation à l’autorégression
Prédiction de séries temporelles
Inégalités PAC-Bayésiennes

3

Au-delà du modèle linéaire
Modèle à direction révélatrice parcimonieux
Régression de faible rang
Modèles à complexité bornée

Pierre AlquierApprentissage statistique dans les modèles parcimonieux

Estimation dans un modèle linéaire parcimonieux
Généralisation à l’autorégression
Au-delà du modèle linéaire

Prédiction de séries temporelles
Inégalités PAC-Bayésiennes

Contexte(Xt )t∈Z série temporelle à valeurs ds Rp . Obs : X1 , . . . , Xn .

Pierre AlquierApprentissage statistique dans les modèles parcimonieux

Estimation dans un modèle linéaire parcimonieux
Généralisation à l’autorégression
Au-delà du modèle linéaire

Prédiction de séries temporelles
Inégalités PAC-Bayésiennes

Contexte(Xt )t∈Z série temporelle à valeurs ds Rp . Obs : X1 , . . . , Xn .
Pour fθ : (Rp )k → Rp on poseX̂tθ = fθ (Xt−1 , . . . , Xt−k ).

Pierre AlquierApprentissage statistique dans les modèles parcimonieux

Estimation dans un modèle linéaire parcimonieux
Généralisation à l’autorégression
Au-delà du modèle linéaire

Prédiction de séries temporelles
Inégalités PAC-Bayésiennes

Contexte(Xt )t∈Z série temporelle à valeurs ds Rp . Obs : X1 , . . . , Xn .
Pour fθ : (Rp )k → Rp on poseX̂tθ = fθ (Xt−1 , . . . , Xt−k ).

Hypothèse :(P
kfθ (x1 , . . . , xk ) − fθ (y1 , . . . , yk )k ≤ kj=1 aj (θ) kxj − yj k ,Pk
j=1 aj (θ) ≤ L.

Pierre AlquierApprentissage statistique dans les modèles parcimonieux

Estimation dans un modèle linéaire parcimonieux
Généralisation à l’autorégression
Au-delà du modèle linéaire

Prédiction de séries temporelles
Inégalités PAC-Bayésiennes

Contexte(Xt )t∈Z série temporelle à valeurs ds Rp . Obs : X1 , . . . , Xn .
Pour fθ : (Rp )k → Rp on poseX̂tθ = fθ (Xt−1 , . . . , Xt−k ).

Hypothèse :(P
kfθ (x1 , . . . , xk ) − fθ (y1 , . . . , yk )k ≤ kj=1 aj (θ) kxj − yj k ,Pk
j=1 aj (θ) ≤ L.
Risques - ` perte convexe et K -Lipshitzh i
R (θ) = E ` X̂tθ , Xt
et r (θ) =n

1 X  θ 
` X̂i , Xi .
n−k
i=k+1

Pierre AlquierApprentissage statistique dans les modèles parcimonieux

Estimation dans un modèle linéaire parcimonieux
Généralisation à l’autorégression
Au-delà du modèle linéaire

Prédiction de séries temporelles
Inégalités PAC-Bayésiennes

Hypotheses de dépendance/mélange
φ-mélange pour (Wi )i∈Z suite de v.a.
noϕW (r ) =sup
|P(B|A) − P(B)| .
A ∈ σ(Wk , Wk−1 , . . . )B ∈ σ(Wk+r )k ∈ZHypothèse PhiMix(C) : 1 +P∞ p Wϕ (j) ≤ C.
j=1

Pierre AlquierApprentissage statistique dans les modèles parcimonieux

Estimation dans un modèle linéaire parcimonieux
Généralisation à l’autorégression
Au-delà du modèle linéaire

Prédiction de séries temporelles
Inégalités PAC-Bayésiennes

Hypotheses de dépendance/mélange
φ-mélange pour (Wi )i∈Z suite de v.a.
noϕW (r ) =sup
|P(B|A) − P(B)| .
A ∈ σ(Wk , Wk−1 , . . . )B ∈ σ(Wk+r )k ∈ZHypothèse PhiMix(C) : 1 +P∞ p Wϕ (j) ≤ C.
j=1

Hypothèse CBS(cξ , (aj ))(ξi )i∈Z iid, kξi k ≤ cξ ,Wi = H(ξi , ξi−1 , ξi−2 . . . )PP∞0avec kH(v ) − H(v 0 )k ≤ ∞j=0 aj kvj − vj k et
j=0 aj < +∞.
Pierre AlquierApprentissage statistique dans les modèles parcimonieux

Estimation dans un modèle linéaire parcimonieux
Généralisation à l’autorégression
Au-delà du modèle linéaire

Prédiction de séries temporelles
Inégalités PAC-Bayésiennes

Hypotheses de dépendance/mélange
Hypothèse ThetaDep(C)Dedecker, J., Doukhan, P., Lang, G., Leon, J. R., Louhichi, S. and Prieur, C. (2007) Weak
Dependance : with Examples and Applications. Springer Lecture Notes in Statistics 190.

Pierre AlquierApprentissage statistique dans les modèles parcimonieux

Estimation dans un modèle linéaire parcimonieux
Généralisation à l’autorégression
Au-delà du modèle linéaire

Prédiction de séries temporelles
Inégalités PAC-Bayésiennes

Hypotheses de dépendance/mélange
Hypothèse ThetaDep(C)Dedecker, J., Doukhan, P., Lang, G., Leon, J. R., Louhichi, S. and Prieur, C. (2007) Weak
Dependance : with Examples and Applications. Springer Lecture Notes in Statistics 190.

Proposition
PhiMix(C)∀i, kWi k ≤ cW

Pierre Alquier⇒ ThetaDep(cW C).

Apprentissage statistique dans les modèles parcimonieux

Estimation dans un modèle linéaire parcimonieux
Généralisation à l’autorégression
Au-delà du modèle linéaire

Prédiction de séries temporelles
Inégalités PAC-Bayésiennes

Hypotheses de dépendance/mélange
Hypothèse ThetaDep(C)Dedecker, J., Doukhan, P., Lang, G., Leon, J. R., Louhichi, S. and Prieur, C. (2007) Weak
Dependance : with Examples and Applications. Springer Lecture Notes in Statistics 190.

Proposition

PhiMix(C)⇒ ThetaDep(cW C).
∀i, kWi k ≤ cW

∞
X
CBS(c
,
(a
))
ξ
j
P∞
⇒ ThetaDep(2cξjaj ).
j=0 jaj < ∞j=0

Pierre AlquierApprentissage statistique dans les modèles parcimonieux

Estimation dans un modèle linéaire parcimonieux
Généralisation à l’autorégression
Au-delà du modèle linéaire

Prédiction de séries temporelles
Inégalités PAC-Bayésiennes

Inégalité PAC-Bayésienne
Estimateur de Gibbs pour une loi a priori πZe −λr (θ) π(dθ)θ̃λ =θρ̃λ (dθ), avec ρ̃λ (dθ) = R −λr (θ0 ).
eπ(dθ0 )
Θ

Pierre AlquierApprentissage statistique dans les modèles parcimonieux

Estimation dans un modèle linéaire parcimonieux
Généralisation à l’autorégression
Au-delà du modèle linéaire

Prédiction de séries temporelles
Inégalités PAC-Bayésiennes

Inégalité PAC-Bayésienne
Estimateur de Gibbs pour une loi a priori πZe −λr (θ) π(dθ)θ̃λ =θρ̃λ (dθ), avec ρ̃λ (dθ) = R −λr (θ0 ).
eπ(dθ0 )
Θ
Théorème (A, Li & Wintenberger, 2012)√(Xt ) satisfait ThetaDep(C), κ := K (1 + L)(cX + C)/ 2. Pourλ > 0, pour tout ε > 0,
"Z
 
2λκ2
P R θ̃λ ≤ inf
R(θ)ρ(dθ) +2ρn 1 − kn #!
2K(ρ, π) + 2 log 2ε+≥ 1 − ε.
λ
Pierre AlquierApprentissage statistique dans les modèles parcimonieux

Estimation dans un modèle linéaire parcimonieux
Généralisation à l’autorégression
Au-delà du modèle linéaire

Prédiction de séries temporelles
Inégalités PAC-Bayésiennes

Un exemple : ensemble fini de prédicteursCas θ ∈ Θ, card(Θ) = M < ∞. Soit λ = 1−k/nκPierre Alquierpn log(M).

Apprentissage statistique dans les modèles parcimonieux

Estimation dans un modèle linéaire parcimonieux
Généralisation à l’autorégression
Au-delà du modèle linéaire

Prédiction de séries temporelles
Inégalités PAC-Bayésiennes

Un exemple : ensemble fini de prédicteursCas θ ∈ Θ, card(Θ) = M < ∞. Soit λ = 1−k/nκ R θ̃λ ≤ R +4κ
1 − knrp
n log(M).

2κ log 2εlog (M)+.
pn
1 − knn log(M)

Pierre AlquierApprentissage statistique dans les modèles parcimonieux

Estimation dans un modèle linéaire parcimonieux
Généralisation à l’autorégression
Au-delà du modèle linéaire

Prédiction de séries temporelles
Inégalités PAC-Bayésiennes

Un exemple : ensemble fini de prédicteursCas θ ∈ Θ, card(Θ) = M < ∞. Soit λ = 1−k/nκ R θ̃λ ≤ R +4κ
1 − knrp
n log(M).

2κ log 2εlog (M)+.
pn
1 − knn log(M)Vitesse optimale
Audibert, J.-Y. (2009) Fast Learning Rates in Statistical Inference Through Aggregation.
The Annals of Statistics 38(4), pp. 1591–1646.

Pierre AlquierApprentissage statistique dans les modèles parcimonieux

Estimation dans un modèle linéaire parcimonieux
Généralisation à l’autorégression
Au-delà du modèle linéaire

Prédiction de séries temporelles
Inégalités PAC-Bayésiennes

Un exemple : ensemble fini de prédicteursCas θ ∈ Θ, card(Θ) = M < ∞. Soit λ = 1−k/nκ R θ̃λ ≤ R +4κ
1 − knrp
n log(M).

2κ log 2εlog (M)+.
pn
1 − knn log(M)Vitesse optimale
Audibert, J.-Y. (2009) Fast Learning Rates in Statistical Inference Through Aggregation.
The Annals of Statistics 38(4), pp. 1591–1646.

Preuve du théorème : repose sur l’inégalité deHoeffding pour les variables dépendantes de Rio
Rio, E. (2000) Inégalité de Hoeffding pour les Fonctions Lipshitziennes de Suites
Dépendantes. Comptes Rendus de l’Académie des Sciences - Series I - Mathematics
330(10), pp. 905–908.

Pierre AlquierApprentissage statistique dans les modèles parcimonieux

Estimation dans un modèle linéaire parcimonieux
Généralisation à l’autorégression
Au-delà du modèle linéaire

Prédiction de séries temporelles
Inégalités PAC-Bayésiennes

Un exemple : ensemble fini de prédicteursCas θ ∈ Θ, card(Θ) = M < ∞. Soit λ = 1−k/nκ R θ̃λ ≤ R +4κ
1 − knrp
n log(M).

2κ log 2εlog (M)+.
pn
1 − knn log(M)Vitesse optimale
Audibert, J.-Y. (2009) Fast Learning Rates in Statistical Inference Through Aggregation.
The Annals of Statistics 38(4), pp. 1591–1646.

Preuve du théorème : repose sur l’inégalité deHoeffding pour les variables dépendantes de Rio
Rio, E. (2000) Inégalité de Hoeffding pour les Fonctions Lipshitziennes de Suites
Dépendantes. Comptes Rendus de l’Académie des Sciences - Series I - Mathematics
330(10), pp. 905–908.

√
on ne dépassera pas les vitesses en 1/ n avec ce
théorème...
Pierre AlquierApprentissage statistique dans les modèles parcimonieux

Estimation dans un modèle linéaire parcimonieux
Généralisation à l’autorégression
Au-delà du modèle linéaire

Prédiction de séries temporelles
Inégalités PAC-Bayésiennes

Vitesses rapides
Xt ∈ R, θ ∈ Rd , même loi π que dans la première partie surfθ (Xt−1 , . . . , Xt−k ) =dXθj φj (Xt−1 , . . . , Xt−k ), perte quadratique.

j=1

Théorème (A, Li & Wintenberger, 2012)(Xt ) satisfait PhiMix(C), R(θ) = R et kθk1 ≤ L. PourC 0 = C 0 (C, L, cX ) connu λ = C 0 /n, pour ε > 0,(
P R(θ̃λ ) − R ≤ 4 inf R(θJ ) − RJ+ C0card(J) log

(n−k)dcard(J)

n−k
Pierre Alquier



+ log

2
ε

 )!
≥ 1 − ε.

Apprentissage statistique dans les modèles parcimonieux

Estimation dans un modèle linéaire parcimonieux
Généralisation à l’autorégression
Au-delà du modèle linéaire

Prédiction de séries temporelles
Inégalités PAC-Bayésiennes

Vitesses rapides
Théorème (A, Li & Wintenberger, 2012)(Xt ) satisfait PhiMix(C), R(θ) = R et kθk1 ≤ L. PourC 0 = C 0 (C, L, cX ) connu λ = C 0 /n, pour ε > 0,(
P R(θ̃λ ) − R ≤ 4 inf R(θJ ) − RJ+ C0card(J) log

(n−k)dcard(J)

n−k



+ log

2
ε

 )!
≥ 1 − ε.

Preuve du théorème : repose sur l’inégalité de Bernstein deSamsonSamson, P.-M. (2000) Concentration of Measure Inequalities for Markov Chains and Φ-Mixing
Processes. Annals of Probability 28(1), pp. 416–461.
Pierre AlquierApprentissage statistique dans les modèles parcimonieux

Estimation dans un modèle linéaire parcimonieux
Généralisation à l’autorégression
Au-delà du modèle linéaire

Prédiction de séries temporelles
Inégalités PAC-Bayésiennes

Publications liées à cette thématique

Alquier, P. & Doukhan, P. (2011) Sparsity Considerations for Dependent Observations. Electronic
Journal of Statistics 5, pp. 750–774.
Alquier, P. & Wintenberger, O. (2012) Model Selection for Weakly Dependent Time Series
Forecasting. Bernoulli 18(3), pp. 883–913.
Alquier, P. & Li, X. (2012) Prediction of Quantiles by Statistical Learning & Application to GDP
Forecasting. In Proceedings of the 15th International Conference on Discovery Science (DS’12),
J.-G. Ganascia, P. Lenca & J.-M. Petit Editors, Springer Lecture Notes in Artificial Intelligence7569, pp. 22–36.
Alquier, P., Li, X. & Wintenberger, O. (2012) Prediction of Time Series by Statistical Learning :General Losses & Fast Rates. Preprint arXiv :1202.4283v1. Currently in minor revision for
Dependence Modeling.

Pierre AlquierApprentissage statistique dans les modèles parcimonieux

Estimation dans un modèle linéaire parcimonieux
Généralisation à l’autorégression
Au-delà du modèle linéaire

Modèle à direction révélatrice parcimonieux
Régression de faible rang
Modèles à complexité bornée

Menu
1

Estimation dans un modèle linéaire parcimonieux
Introduction
Inégalités PAC-Bayésiennes

2

Généralisation à l’autorégression
Prédiction de séries temporelles
Inégalités PAC-Bayésiennes

3

Au-delà du modèle linéaire
Modèle à direction révélatrice parcimonieux
Régression de faible rang
Modèles à complexité bornée

Pierre AlquierApprentissage statistique dans les modèles parcimonieux

Estimation dans un modèle linéaire parcimonieux
Généralisation à l’autorégression
Au-delà du modèle linéaire

Modèle à direction révélatrice parcimonieux
Régression de faible rang
Modèles à complexité bornéeAutres modèles

Possibles fonctions reliant x ∈ Rp et y :Pierre AlquierApprentissage statistique dans les modèles parcimonieux

Estimation dans un modèle linéaire parcimonieux
Généralisation à l’autorégression
Au-delà du modèle linéaire

Modèle à direction révélatrice parcimonieux
Régression de faible rang
Modèles à complexité bornéeAutres modèles

Possibles fonctions reliant x ∈ Rp et y :single-index parcimonieux y = g (β · x) et kβk0  p,Pierre AlquierApprentissage statistique dans les modèles parcimonieux

Estimation dans un modèle linéaire parcimonieux
Généralisation à l’autorégression
Au-delà du modèle linéaire

Modèle à direction révélatrice parcimonieux
Régression de faible rang
Modèles à complexité bornéeAutres modèles

Possibles fonctions reliant x ∈ Rp et y :single-index parcimonieux y = g (β · x) et kβk0  p,
Pmodèle additif y = pj=1 fj (xj ) et card({j : fj 6= 0})  p,Pierre AlquierApprentissage statistique dans les modèles parcimonieux

Estimation dans un modèle linéaire parcimonieux
Généralisation à l’autorégression
Au-delà du modèle linéaire

Modèle à direction révélatrice parcimonieux
Régression de faible rang
Modèles à complexité bornéeAutres modèles

Possibles fonctions reliant x ∈ Rp et y :single-index parcimonieux y = g (β · x) et kβk0  p,
Pmodèle additif y = pj=1 fj (xj ) et card({j : fj 6= 0})  p,régression de faible rang y = Mx ∈ Rm , rg(M)  m ∧ p,

Pierre AlquierApprentissage statistique dans les modèles parcimonieux

Estimation dans un modèle linéaire parcimonieux
Généralisation à l’autorégression
Au-delà du modèle linéaire

Modèle à direction révélatrice parcimonieux
Régression de faible rang
Modèles à complexité bornéeAutres modèles

Possibles fonctions reliant x ∈ Rp et y :single-index parcimonieux y = g (β · x) et kβk0  p,
Pmodèle additif y = pj=1 fj (xj ) et card({j : fj 6= 0})  p,régression de faible rang y = Mx ∈ Rm , rg(M)  m ∧ p,
modèles en physique quantique induisant des contraintes
de parcimonie ou de faible rang,

Pierre AlquierApprentissage statistique dans les modèles parcimonieux

Estimation dans un modèle linéaire parcimonieux
Généralisation à l’autorégression
Au-delà du modèle linéaire

Modèle à direction révélatrice parcimonieux
Régression de faible rang
Modèles à complexité bornéeAutres modèles

Possibles fonctions reliant x ∈ Rp et y :single-index parcimonieux y = g (β · x) et kβk0  p,
Pmodèle additif y = pj=1 fj (xj ) et card({j : fj 6= 0})  p,régression de faible rang y = Mx ∈ Rm , rg(M)  m ∧ p,
modèles en physique quantique induisant des contraintes
de parcimonie ou de faible rang,
que peut-on dire de façon générale ?

Pierre AlquierApprentissage statistique dans les modèles parcimonieux

Estimation dans un modèle linéaire parcimonieux
Généralisation à l’autorégression
Au-delà du modèle linéaire

Modèle à direction révélatrice parcimonieux
Régression de faible rang
Modèles à complexité bornéeAutres modèles

Possibles fonctions reliant x ∈ Rp et y :single-index parcimonieux y = g (θT x) et kθk0  p,
Pmodèle additif y = pj=1 fj (xj ) et card({j : fj 6= 0})  p,régression de faible rang y = Mx ∈ Rm , rg(M)  m ∧ p,
modèles en physique quantique induisant des contraintes
de parcimonie ou de faible rang,
que peut-on dire de façon générale ?

Pierre AlquierApprentissage statistique dans les modèles parcimonieux

Estimation dans un modèle linéaire parcimonieux
Généralisation à l’autorégression
Au-delà du modèle linéaire

Modèle à direction révélatrice parcimonieux
Régression de faible rang
Modèles à complexité bornée

Modèle à direction révélatrice parcimonieux(Xi , Yi )ni=1 i.i.d. sous P, loi commune P, Xi ∈ [−1, 1]p ,Yi = g (β · Xi ) + Wi ,

θ = (g , β)E(Wi |Xi ) = 0, g : R → [−C , C ], et β ∈ Rp , kβk0  p. Pertequadratique.

Pierre AlquierApprentissage statistique dans les modèles parcimonieux

Estimation dans un modèle linéaire parcimonieux
Généralisation à l’autorégression
Au-delà du modèle linéaire

Modèle à direction révélatrice parcimonieux
Régression de faible rang
Modèles à complexité bornée

Modèle à direction révélatrice parcimonieux(Xi , Yi )ni=1 i.i.d. sous P, loi commune P, Xi ∈ [−1, 1]p ,Yi = g (β · Xi ) + Wi ,

θ = (g , β)E(Wi |Xi ) = 0, g : R → [−C , C ], et β ∈ Rp , kβk0  p. Pertequadratique.

On peut définir une loi a priori dans ce modèle, et un
estimateur de Gibbs randomisé θ̌λ .

Pierre AlquierApprentissage statistique dans les modèles parcimonieux

Estimation dans un modèle linéaire parcimonieux
Généralisation à l’autorégression
Au-delà du modèle linéaire

Modèle à direction révélatrice parcimonieux
Régression de faible rang
Modèles à complexité bornée

Inégalité oracle
Théorème (A & Biau, 2013)
Les Wi sont sous-exponentiels (σ, ξ), constante connueΞ = Ξ(C , ξ, σ) > 0, λ = n/Ξ. Pour tout ε > 0,("

P R(θ̌λ ) − R ≤ Ξ

inf

inf

I ⊂{1,...,p} 1≤M≤n

R(θI ,M ) − R

M log(n) + card(I ) log(pn) + log
+
n

2
ε

 #)
≥ 1 − ε,où θI ,M = (g M , β I ) est la meilleure approximation I -sparse deβ et la meilleure approximation de g avec M fonctions d’une
base.
Pierre AlquierApprentissage statistique dans les modèles parcimonieux

Estimation dans un modèle linéaire parcimonieux
Généralisation à l’autorégression
Au-delà du modèle linéaire

Modèle à direction révélatrice parcimonieux
Régression de faible rang
Modèles à complexité bornéeApplication : ellipsoïde de Sobolev
Sous quelques
hypothèses supplémentaires, dont

6C 2
g ∈ W s, π2 pour s ≥ 2, avec s inconnu :Pierre AlquierApprentissage statistique dans les modèles parcimonieux

Estimation dans un modèle linéaire parcimonieux
Généralisation à l’autorégression
Au-delà du modèle linéaire

Modèle à direction révélatrice parcimonieux
Régression de faible rang
Modèles à complexité bornéeApplication : ellipsoïde de Sobolev
Sous quelques
hypothèses supplémentaires, dont

6C 2
g ∈ W s, π2 pour s ≥ 2, avec s inconnu :Corollaire (A & Biau, 2013)

0

P R(θ̌λ ) − R ≤ Ξ(log(n)n

Pierre Alquier2s 2s+1

kβk0 log(pn)n)!
log 2ε+≥ 1 − ε.
n+Apprentissage statistique dans les modèles parcimonieux

Estimation dans un modèle linéaire parcimonieux
Généralisation à l’autorégression
Au-delà du modèle linéaire

Modèle à direction révélatrice parcimonieux
Régression de faible rang
Modèles à complexité bornée

Modèle de régression de faible rang
ModèleX déterministe, E(E) = 0 et
Y = |{z}X |{z}
B +E, rg(B)  min(p, m).
|{z}
n×m

n×p p×m

Pierre AlquierApprentissage statistique dans les modèles parcimonieux

Estimation dans un modèle linéaire parcimonieux
Généralisation à l’autorégression
Au-delà du modèle linéaire

Modèle à direction révélatrice parcimonieux
Régression de faible rang
Modèles à complexité bornée

Modèle de régression de faible rang
ModèleX déterministe, E(E) = 0 et
Y = |{z}X |{z}
B +E, rg(B)  min(p, m).
|{z}
n×m

n×p p×m

Il faut définir une loi a priori pour approcher les matrices defaibles rang. Utile aussi pour d’autres modèles :complétion de matrice,
régression trace...

Pierre AlquierApprentissage statistique dans les modèles parcimonieux

Estimation dans un modèle linéaire parcimonieux
Généralisation à l’autorégression
Au-delà du modèle linéaire

Modèle à direction révélatrice parcimonieux
Régression de faible rang
Modèles à complexité bornée

Loi a priori
J. Geweke (1996). Bayesian reduced rank regression in econometrics. Journal of Econometrics 75
121–146.

k fixé, |{z}B = |{z}M |{z}NT .
p×m

Pierre Alquierp×k k×m

Apprentissage statistique dans les modèles parcimonieux

Estimation dans un modèle linéaire parcimonieux
Généralisation à l’autorégression
Au-delà du modèle linéaire

Modèle à direction révélatrice parcimonieux
Régression de faible rang
Modèles à complexité bornée

Loi a priori
J. Geweke (1996). Bayesian reduced rank regression in econometrics. Journal of Econometrics 75
121–146.

k fixé, |{z}B = |{z}M |{z}NT .
p×m

p×k k×m

Soit M·,` la `-ième colonne de M, on ak
X
B=M·,` (N·,` )T ⇒ rg(B) ≤ k.
`=1

Pierre AlquierApprentissage statistique dans les modèles parcimonieux

Estimation dans un modèle linéaire parcimonieux
Généralisation à l’autorégression
Au-delà du modèle linéaire

Modèle à direction révélatrice parcimonieux
Régression de faible rang
Modèles à complexité bornée

Loi a priori
J. Geweke (1996). Bayesian reduced rank regression in econometrics. Journal of Econometrics 75
121–146.

k fixé, |{z}B = |{z}M |{z}NT .
p×m

p×k k×m

Soit M·,` la `-ième colonne de M, on ak
X
B=M·,` (N·,` )T ⇒ rg(B) ≤ k.
`=1

Loi a priori π : les M·,` et N·,` sont indépendants N (0, γ` I ).

Pierre AlquierApprentissage statistique dans les modèles parcimonieux

Estimation dans un modèle linéaire parcimonieux
Généralisation à l’autorégression
Au-delà du modèle linéaire

Modèle à direction révélatrice parcimonieux
Régression de faible rang
Modèles à complexité bornée

Loi a priori
J. Geweke (1996). Bayesian reduced rank regression in econometrics. Journal of Econometrics 75
121–146.

k fixé, |{z}B = |{z}M |{z}NT .
p×m

p×k k×m

Soit M·,` la `-ième colonne de M, on ak
X
B=M·,` (N·,` )T ⇒ rg(B) ≤ k.
`=1

Loi a priori π : les M·,` et N·,` sont indépendants N (0, γ` I ).
R. Salakhutdinov & A. Mnih (2008). Bayesian probabilistic matrix factorization using MCMC.
Proceedings of ICML’08.

Fixer k = min(m, p), les γ` sont i.i.d. 1/γ` ∼ Γ(a, b), calibréede telle façon que γ` proche de 0.
Pierre AlquierApprentissage statistique dans les modèles parcimonieux

Estimation dans un modèle linéaire parcimonieux
Généralisation à l’autorégression
Au-delà du modèle linéaire

Modèle à direction révélatrice parcimonieux
Régression de faible rang
Modèles à complexité bornée

Inégalité oracleρ̂λ (db) ∝ exp[−λkXb − Y k2F ]π(db) et B̂λ =Zbρ̂λ (db).
2σ
Si Ei,j i.i.d. N (0, σ 2 ), λ = 4σ1 2 , a = 1, b = npk 2 (m2 +p 2 ) .

Théorème (A, 2013)∀ r , M et N tq M·,`= N·,` = 0 si ` > r , |Mi,j |, |Ni,j | ≤ c 0 ,≤ kX (MN T − B)k2Fn nmp o
0
2
4
+ C (c, c ) σ r (m + p) log+σ .
σ2

E kX B̂ − XBk2F

Pierre AlquierApprentissage statistique dans les modèles parcimonieux

Estimation dans un modèle linéaire parcimonieux
Généralisation à l’autorégression
Au-delà du modèle linéaire

Modèle à direction révélatrice parcimonieux
Régression de faible rang
Modèles à complexité bornée

Inégalité oracleρ̂λ (db) ∝ exp[−λkXb − Y k2F ]π(db) et B̂λ =Zbρ̂λ (db).
2σ
Si Ei,j i.i.d. N (0, σ 2 ), λ = 4σ1 2 , a = 1, b = npk 2 (m2 +p 2 ) .

Théorème (A, 2013)∀ r , M et N tq M·,`= N·,` = 0 si ` > r , |Mi,j |, |Ni,j | ≤ c 0 ,≤ kX (MN T − B)k2Fn nmp o
0
2
4
+ C (c, c ) σ r (m + p) log+σ .
σ2

E kX B̂ − XBk2F

F. Bunea, Y. She & M. Wegkamp (2011). Optimal selection of reduced rank estimators ofhigh-dimensional matrices. The Annals of Statistics 39 1282–1309.
A. Rohde & A. Tsybakov (2011). Estimation of high-dimensional low-rank matrices. The Annalsof Statistics 39 887–930.
Pierre AlquierApprentissage statistique dans les modèles parcimonieux

Estimation dans un modèle linéaire parcimonieux
Généralisation à l’autorégression
Au-delà du modèle linéaire

Modèle à direction révélatrice parcimonieux
Régression de faible rang
Modèles à complexité bornée

Contexte
n paires i.i.d. (X1 , Y1 ), . . . , (Xn , Yn ), (Xi , Yi ) ∼ P, Xi ∈ X ,Yi ∈ Y.

Pierre AlquierApprentissage statistique dans les modèles parcimonieux

Estimation dans un modèle linéaire parcimonieux
Généralisation à l’autorégression
Au-delà du modèle linéaire

Modèle à direction révélatrice parcimonieux
Régression de faible rang
Modèles à complexité bornée

Contexte
n paires i.i.d. (X1 , Y1 ), . . . , (Xn , Yn ), (Xi , Yi ) ∼ P, Xi ∈ X ,Yi ∈ Y.
()[
fθ : X → Y, θ ∈Θi = Θ
i∈I

Pierre AlquierApprentissage statistique dans les modèles parcimonieux

Estimation dans un modèle linéaire parcimonieux
Généralisation à l’autorégression
Au-delà du modèle linéaire

Modèle à direction révélatrice parcimonieux
Régression de faible rang
Modèles à complexité bornée

Contexte
n paires i.i.d. (X1 , Y1 ), . . . , (Xn , Yn ), (Xi , Yi ) ∼ P, Xi ∈ X ,Yi ∈ Y.
()[
fθ : X → Y, θ ∈Θi = Θ
i∈I
2

Fonction de perte ` : Y → R+ , P(`(fθ (X ), Y ) ≤ C ) = 1.

Pierre AlquierApprentissage statistique dans les modèles parcimonieux

Estimation dans un modèle linéaire parcimonieux
Généralisation à l’autorégression
Au-delà du modèle linéaire

Modèle à direction révélatrice parcimonieux
Régression de faible rang
Modèles à complexité bornée

Contexte
n paires i.i.d. (X1 , Y1 ), . . . , (Xn , Yn ), (Xi , Yi ) ∼ P, Xi ∈ X ,Yi ∈ Y.
()[
fθ : X → Y, θ ∈Θi = Θ
i∈I
2

Fonction de perte ` : Y → R+ , P(`(fθ (X ), Y ) ≤ C ) = 1.
n

1X`(fθ (Xi ), Yi ).
R(θ) = E(X ,Y )∼P [`(fθ (X ), Y )], et r (θ) =n i=1Pierre AlquierApprentissage statistique dans les modèles parcimonieux

Estimation dans un modèle linéaire parcimonieux
Généralisation à l’autorégression
Au-delà du modèle linéaire

Modèle à direction révélatrice parcimonieux
Régression de faible rang
Modèles à complexité bornée

Contexte
n paires i.i.d. (X1 , Y1 ), . . . , (Xn , Yn ), (Xi , Yi ) ∼ P, Xi ∈ X ,Yi ∈ Y.
()[
fθ : X → Y, θ ∈Θi = Θ
i∈I
2

Fonction de perte ` : Y → R+ , P(`(fθ (X ), Y ) ≤ C ) = 1.
n

1X`(fθ (Xi ), Yi ).
R(θ) = E(X ,Y )∼P [`(fθ (X ), Y )], et r (θ) =n i=1
θ ∈ arg min R, θi ∈ arg min R.
Θ

Pierre AlquierΘiApprentissage statistique dans les modèles parcimonieux

Estimation dans un modèle linéaire parcimonieux
Généralisation à l’autorégression
Au-delà du modèle linéaire

Modèle à direction révélatrice parcimonieux
Régression de faible rang
Modèles à complexité bornée

Un estimateur de Gibbs dans chaque modèle...
loi a priori πi dans chaque Θi ,Pierre AlquierApprentissage statistique dans les modèles parcimonieux

Estimation dans un modèle linéaire parcimonieux
Généralisation à l’autorégression
Au-delà du modèle linéaire

Modèle à direction révélatrice parcimonieux
Régression de faible rang
Modèles à complexité bornée

Un estimateur de Gibbs dans chaque modèle...
loi a priori πi dans chaque Θi ,P
poids µi ≥ 0 tels que i∈I µi = 1,

Pierre AlquierApprentissage statistique dans les modèles parcimonieux

Estimation dans un modèle linéaire parcimonieux
Généralisation à l’autorégression
Au-delà du modèle linéaire

Modèle à direction révélatrice parcimonieux
Régression de faible rang
Modèles à complexité bornée

Un estimateur de Gibbs dans chaque modèle...
loi a priori πi dans chaque Θi ,P
poids µi ≥ 0 tels que i∈I µi = 1,ρ̃i,λ (dθ) ∝ exp(−λr (θ))πi (dθ)1(θ ∈ Θi ),Pierre AlquierApprentissage statistique dans les modèles parcimonieux

Estimation dans un modèle linéaire parcimonieux
Généralisation à l’autorégression
Au-delà du modèle linéaire

Modèle à direction révélatrice parcimonieux
Régression de faible rang
Modèles à complexité bornée

Un estimateur de Gibbs dans chaque modèle...
loi a priori πi dans chaque Θi ,P
poids µi ≥ 0 tels que i∈I µi = 1,ρ̃i,λ (dθ) ∝ exp(−λr (θ))πi (dθ)1(θ ∈ Θi ),
log(n)
Λ = {20 , 21 , . . . , 2b log(2) c },Pierre AlquierApprentissage statistique dans les modèles parcimonieux

Estimation dans un modèle linéaire parcimonieux
Généralisation à l’autorégression
Au-delà du modèle linéaire

Modèle à direction révélatrice parcimonieux
Régression de faible rang
Modèles à complexité bornée

Un estimateur de Gibbs dans chaque modèle...
loi a priori πi dans chaque Θi ,P
poids µi ≥ 0 tels que i∈I µi = 1,ρ̃i,λ (dθ) ∝ exp(−λr (θ))πi (dθ)1(θ ∈ Θi ),
log(n)
Λ = {20 , 21 , . . . , 2b log(2) c },θ̌i,λ ∼ ρ̃i,λ ,Pierre AlquierApprentissage statistique dans les modèles parcimonieux

Estimation dans un modèle linéaire parcimonieux
Généralisation à l’autorégression
Au-delà du modèle linéaire

Modèle à direction révélatrice parcimonieux
Régression de faible rang
Modèles à complexité bornée

Un estimateur de Gibbs dans chaque modèle...
loi a priori πi dans chaque Θi ,P
poids µi ≥ 0 tels que i∈I µi = 1,ρ̃i,λ (dθ) ∝ exp(−λr (θ))πi (dθ)1(θ ∈ Θi ),
log(n)
Λ = {20 , 21 , . . . , 2b log(2) c },θ̌i,λ ∼ ρ̃i,λ ,un niveau de confiance ε.

Pierre AlquierApprentissage statistique dans les modèles parcimonieux

Estimation dans un modèle linéaire parcimonieux
Généralisation à l’autorégression
Au-delà du modèle linéaire

Modèle à direction révélatrice parcimonieux
Régression de faible rang
Modèles à complexité bornée

Un estimateur de Gibbs dans chaque modèle...
loi a priori πi dans chaque Θi ,P
poids µi ≥ 0 tels que i∈I µi = 1,ρ̃i,λ (dθ) ∝ exp(−λr (θ))πi (dθ)1(θ ∈ Θi ),
log(n)
Λ = {20 , 21 , . . . , 2b log(2) c },θ̌i,λ ∼ ρ̃i,λ ,un niveau de confiance ε.
Il existe B̃ε ((i, λ), (i 0 , λ0 )), qui ne dépend pas de P, t.q.
P ∀i, i 0 , λ, λ0 , R(θ̌i,λ ) − R(θ̌i 0 ,λ0 ) ≤ B̃ε ((i, λ), (i 0 , λ0 )) ≥ 1 − εB̃ε ((i, λ), (i 0 , λ0 )) ≤ B̃ε ((i, λ), (i 00 , λ00 )) + B̃ε ((i 00 , λ00 ), (i 0 , λ0 )),et il existe une mesure de complexité Cε ((i, λ)).
Pierre AlquierApprentissage statistique dans les modèles parcimonieux

Estimation dans un modèle linéaire parcimonieux
Généralisation à l’autorégression
Au-delà du modèle linéaire

Modèle à direction révélatrice parcimonieux
Régression de faible rang
Modèles à complexité bornée

Procédure de Lepski
On organise les paires (i, λ) par complexité croissante :{tj , j ∈ {1, . . . , M}} = I × Λ et Cε (t1 ) ≤ · · · ≤ Cε (tM ).

Pierre AlquierApprentissage statistique dans les modèles parcimonieux

Estimation dans un modèle linéaire parcimonieux
Généralisation à l’autorégression
Au-delà du modèle linéaire

Modèle à direction révélatrice parcimonieux
Régression de faible rang
Modèles à complexité bornée

Procédure de Lepski
On organise les paires (i, λ) par complexité croissante :{tj , j ∈ {1, . . . , M}} = I × Λ et Cε (t1 ) ≤ · · · ≤ Cε (tM ).
s(k) = inf{j ∈ {1, . . . , M}, B̃ε (tk , tj ) > 0},
par convention s(k) = 0 si pour tout j, B̃ε (tk , tj ) ≤ 0.

Pierre AlquierApprentissage statistique dans les modèles parcimonieux

Estimation dans un modèle linéaire parcimonieux
Généralisation à l’autorégression
Au-delà du modèle linéaire

Modèle à direction révélatrice parcimonieux
Régression de faible rang
Modèles à complexité bornée

Procédure de Lepski
On organise les paires (i, λ) par complexité croissante :{tj , j ∈ {1, . . . , M}} = I × Λ et Cε (t1 ) ≤ · · · ≤ Cε (tM ).
s(k) = inf{j ∈ {1, . . . , M}, B̃ε (tk , tj ) > 0},
par convention s(k) = 0 si pour tout j, B̃ε (tk , tj ) ≤ 0. Enfink̂ = min(arg max s)
et (î, λ̂) est la paire telle que (î, λ̂) = tk̂ , finalement :θ̌ = θ̌î,λ̂ .

Pierre AlquierApprentissage statistique dans les modèles parcimonieux

Estimation dans un modèle linéaire parcimonieux
Généralisation à l’autorégression
Au-delà du modèle linéaire

Modèle à direction révélatrice parcimonieux
Régression de faible rang
Modèles à complexité bornéeHypothèsesHypothèse de marge pour (κ, c) ∈ [1, +∞[×R∗+noV (θ, θ0 ) = E(X ,Y )∼P [`(fθ (X ), Y ) − `(fθ0 (X ), Y )]21
V (θ, θ) ≤ c R(θ) − R(θ) κ .
Mammen, E. and Tsybakov, A. B. (1999) Smooth Discrimination Analysis. The Annals of
Statistics 27(6), pp. 1808–1829.

Pierre AlquierApprentissage statistique dans les modèles parcimonieux

Estimation dans un modèle linéaire parcimonieux
Généralisation à l’autorégression
Au-delà du modèle linéaire

Modèle à direction révélatrice parcimonieux
Régression de faible rang
Modèles à complexité bornéeHypothèsesHypothèse de marge pour (κ, c) ∈ [1, +∞[×R∗+noV (θ, θ0 ) = E(X ,Y )∼P [`(fθ (X ), Y ) − `(fθ0 (X ), Y )]21
V (θ, θ) ≤ c R(θ) − R(θ) κ .
Mammen, E. and Tsybakov, A. B. (1999) Smooth Discrimination Analysis. The Annals of
Statistics 27(6), pp. 1808–1829.

Dimension
 Z


i
sup ξ
R(θ)πexp(−ξR) (dθ) − R θi
≤ di , où
ξ∈R

Θi

i
πexp(−ξR)(dθ) ∝ exp[−ξR(θ)]πi (dθ)1(θ ∈ Θi ).
Catoni, O. (2007) PAC-Bayesian Supervised Classification : The Thermodnamics of Statistical
Learning. Institute of Mathematical Statistics (IMS) Lecture notes - monograph series 56.
Pierre AlquierApprentissage statistique dans les modèles parcimonieux

Estimation dans un modèle linéaire parcimonieux
Généralisation à l’autorégression
Au-delà du modèle linéaire

Modèle à direction révélatrice parcimonieux
Régression de faible rang
Modèles à complexité bornée

Inégalité oracle
Théorème (A, 2008)
Sous l’hypothèse de marge et l’hypothèse de dimension, il
existe C = C(κ, c, C ) t.q.
"(
P R(θ̌) − R(θ) ≤ inf R θi − R(θ)
i∈I( 
+ C max

!1 1 2 (n)2R θi − R θ κ di + log 1+log
εµi
n
2 (n)
di + log 1+log
εµ(i)nPierre Alquier

,

κ )#)
! 2κ−1≥ 1 − ε.

Apprentissage statistique dans les modèles parcimonieux

Estimation dans un modèle linéaire parcimonieux
Généralisation à l’autorégression
Au-delà du modèle linéaire

Modèle à direction révélatrice parcimonieux
Régression de faible rang
Modèles à complexité bornée

Publications liées à cette chapitre
Alquier, P. (2008) PAC-Bayesian Bounds for R&omized Empirical Risk Minimizers. Mathematical
Methods of Statistics 17(4), pp. 279–304.
Alquier, P. (2010) An Algorithm for Iterative Selection of Blocks of Features. In Proceedings ofthe 21th International Conference on Algorithmic Learning Theory (ALT’10), M. Hutter, F.
Stephan, V. Vovk & T. Zeugmann Editors, Springer Lecture Notes in Artificial Intelligence 6331,
pp. 35–49.
Guedj, B. & Alquier, P. (2013) PAC-Bayesian Estimation & Prediction in Sparse Additive Models.
Electronic Journal of Statistics 7, pp. 264–291.
Alquier, P. & Biau, G. (2013) Sparse Single-Index Models. Journal of Machine Learning Research
14, pp. 243–280.
Alquier, P., Meziani, K. & Peyré, G. (2013) Adaptive Estimation of the Density Matrix in
Quantum Homodyne Tomography with Noisy Data. Inverse Problems 29(7), 075017.
Alquier, P., Butucea, C., Hebiri, M., Meziani, K. & Morimae, T. (2013) Rank Penalized
Estimation of a Quantum System. Physical Review A 88(3), 032113.
Alquier, P. (2013) Bayesian Methods for Low-rank Matrix Estimation : Short Survey &Theoretical Study. In Proceedings of the 24th International Conference on Algorithmic Learning
Theory (ALT’13), S. Jain, R. Munos, F. Stephan & T. Zeugmann Editors, Springer Lecture Notes
in Artificial Intelligence 8139, pp. 309–323.

Pierre AlquierApprentissage statistique dans les modèles parcimonieux