Introduction Le Lasso Sélection de modèle Estimation Prédiction Compléments

Régression pénalisée : le Lasso

V. Viallon

M2 Maths Appli
Introduction Le Lasso Sélection de modèle Estimation Prédiction Compléments

1 Introduction

2 Le Lasso

3 Sélection de modèle

4 Estimation

5 Prédiction

6 Compléments
Introduction Le Lasso Sélection de modèle Estimation Prédiction Compléments

Cadre considéré dans ce cours

On supposera disposer d’un échantillon

(x1 , Y1 ), . . . , (xn , Yn ) tel que

Yi = xiT β∗ + ξi , i = 1, . . . , n,

où les ξi ∼ N(0, σ2 ) sont i.i.d., les Yi ∈ IR sont aléatoires

mais les xi ∈ IRp sont déterministes, et le paramètre
β∗ ∈ IRp est inconnu.
⇒ régression linéaire sur design fixe, avec erreurs gaussiennes
(sans intercept).
Exemple typique :
Yi : niveau d’expression du gène G chez l’individu i
xi = (xi 1 , . . . , xip )T : SNPs pour l’individu i (à valeurs dans
{0, 1, 2} généralement).
Introduction Le Lasso Sélection de modèle Estimation Prédiction Compléments

Ecriture matricielle

Le modèle peut se réécrire sous forme matricielle

Y = Xβ∗ + ξ

où
Y = (Y1 , . . . , Yn )T ∈ IRn et ξ = (ξ1 , . . . , ξn )T ∈ IRn
X = (x1T , . . . , xnT )T ∈ IRn×p .

Rq: Dans ce cours, on considère que p = p(n) (typiquement,

fonction croissante de n).
Introduction Le Lasso Sélection de modèle Estimation Prédiction Compléments

Cadre "standard"
n  p, et rang(X) = p
alors l’estimateur des MCO

β̃ = arg minp kY − Xβk22

β∈IR

est donné par

β̃ = (XT X)−1 XT Y.
On a
kX(β̃ − β∗ )k22
∼ χ2p
σ2
et donc [exercice: utilisez l’inégalité de Tchebychev1 ]

kX(β̃ − β∗ )k22 p 
(ii ) = OIP
n n
où Xn = OIP (an ) : ∀, ∃M : IP(|Xn /an | > M ) 6 .
1
Soit X , une v.a. d’espérance µ et de variance finie σ2 , alors pour tout
α > 0, IP(|X − µ| > α) 6 σ2 /a 2 .
Introduction Le Lasso Sélection de modèle Estimation Prédiction Compléments

Cadre de la grande dimension

p > n (voire p  n)
alors rang(X) < p (et donc XT X n’est pas inversible)
l’estimateur des MCO n’est plus unique (même formule
avec pseudo-inverse de Moore-Penrose)
et il "overfit" les données
notamment
kX(β̃ − β∗ )k22
= OIP (1).
n

(Exemple avec n = p et X = In .)
Introduction Le Lasso Sélection de modèle Estimation Prédiction Compléments

"Solutions"

Hypothèse de parcimonie : β∗ est "creux", i.e.

s0 := ]{j : β∗j 6= 0}  p (et surtout  n).

Introduction Le Lasso Sélection de modèle Estimation Prédiction Compléments

"Solutions"

Hypothèse de parcimonie : β∗ est "creux", i.e.

s0 := ]{j : β∗j 6= 0}  p (et surtout  n).

Alors, si l’on connaissait l’ensemble J0 := {j : β∗j 6= 0}, on

s 
0
aurait une erreur de prédiction : OIP →IP 0.
n
Introduction Le Lasso Sélection de modèle Estimation Prédiction Compléments

"Solutions"

Hypothèse de parcimonie : β∗ est "creux", i.e.

s0 := ]{j : β∗j 6= 0}  p (et surtout  n).

Alors, si l’on connaissait l’ensemble J0 := {j : β∗j 6= 0}, on

s 
0
aurait une erreur de prédiction : OIP →IP 0.
n

⇒ Sélection de variables
meilleure interprétabilité du modèle
meilleur pouvoir prédictif aussi

Autre hypothèse possible : peu de coefficients "grands"

(plutôt que peu de coefficients non nuls).
Introduction Le Lasso Sélection de modèle Estimation Prédiction Compléments

Principe général de la régression pénalisée

Pour un λ > 0,

kY − Xβk22
φP (λ) := minp + λP(β).
β∈IR 2n

Si λ = 0 : MCO

Différents choix pour P(β) :

kβk0 = ]{j : βj 6= 0} : Théorie +++, Implémentation –

AIC : λ = σ2 /n
BIC : λ = σ2 log(n)/(2n)
Pb "combinatoire" : on doit énumérer les 2p modèles
possibles
Introduction Le Lasso Sélection de modèle Estimation Prédiction Compléments

Principe général de la régression pénalisée

Pour un λ > 0,

kY − Xβk22
φP (λ) := minp + λP(β).
β∈IR 2n

Si λ = 0 : MCO

Différents choix pour P(β) :

kβk0 = ]{j : βj 6= 0} : Théorie +++, Implémentation –

P
kβk1 = j |βj | (Lasso) : Théorie : ++, Implémentation ++
P
kβk22 = j β2j (Ridge) : Théorie : +, Implémentation ++
...
Introduction Le Lasso Sélection de modèle Estimation Prédiction Compléments

Least Absolute Shrinkage and Selection Operator

Pour λ > 0,

kY − Xβk22
β̂(λ) ∈ Arg minp + λkβk1 . (1)
β∈IR 2n

Problème convexe, mais la solution n’est pas

nécessairement unique

Si λ = 0 : MCO

la solution est typiquement creuse : plus λ est grand, et

plus β̂(λ) est creux (en "gros").
Introduction Le Lasso Sélection de modèle Estimation Prédiction Compléments

Propriétés de sélection du Lasso: intuition

Le problème d’optimisation

kY − Xβk22
φ(λ) := minp + λkβk1 .
β∈IR 2n

est équivalent, pour une certaine valeur de T = T (λ), à

kY − Xβk22
φ̃(T ) := min .
kβk1 6T 2n

Ex: dans le cas où n = p et X = In . On cherche alors à

résoudre
1 X
n
φ̃(T ) := min (Yi − βi )2 .
kβk1 6T 2n
i =1
Introduction Le Lasso Sélection de modèle Estimation Prédiction Compléments

Cône `1

Emprunté aux slides de J. Mairal

Introduction Le Lasso Sélection de modèle Estimation Prédiction Compléments

Cône `2

Emprunté aux slides de J. Mairal

Introduction Le Lasso Sélection de modèle Estimation Prédiction Compléments

Propriétés du Lasso : que peut-on espérer ?

On peut espérer qu’avec grande probabilité, sous certaines
hypothèses et pour des choix appropriés de λ,
Estimation : β̂ ≈ β∗

Sélection : Jb (λ) ≈ J0 , où Jb (λ) = {j : β̂j (λ) 6= 0}.

Prédiction : n −1 kX(β̂ − β∗ )k22 ≈ s0 /n

On précisera plus tard la signification de ≈ dans chacun des cas

précédents.

Rq1: "Difficulté" pour l’analyse des propriétés des estimateurs

Lasso (par rapport aux MCO): pas de forme explicite (on
va utiliser des conditions d’optimalité qui caractérisent les
solutions du problème (1)).
Rq2: Propriétés non asymptotiques.
Introduction Le Lasso Sélection de modèle Estimation Prédiction Compléments

Une première condition d’optimalité

Pour simplifier les notations, on suppose que λ est fixé et on

pose β̂ = β̂(λ), une solution de (1).

Lemme 2.1
Dénotons le gradient de (2n)−1 kY − Xβk22 par
G(β) = −XT (Y − Xβ)/n. Alors une CNS pour que β̂ soit
solution du problème (1) est

Gk (β̂) = −λ sign(β̂k ) si β̂k 6= 0

|Gj (β̂)| 6 λ si β̂j = 0

Cette caractérisation nous sera utile pour établir les propriétés

de sélection du Lasso.
Introduction Le Lasso Sélection de modèle Estimation Prédiction Compléments

Lasso et soft-thresholding

Elle nous permet également de déduire le résultat suivant.

Si XT X/n = Ip (⇒ p 6 n), alors Lasso =

soft-thresholding :

β̂j (λ) = sign(β̃j )(|β̃j | − λ)+ .

⇒ Rq : Le Lasso sélectionne.. mais shrinke aussi : les estimateurs

sont généralement biaisés (cf. regularization path).
Diverses extensions pour débiaiser les estimateurs Lasso
P
Adaptive Lasso (Zou): kβk1 ⇒ j |βj |/|β̂init
j | : on pénalise
plus βj si |β̂j | est petit.
init

Lasso-OLS Hybrid (= Relaxed Lasso de Meinshausen, avec

φ = 0)
On reviendra sur ces approches plus tard.
Introduction Le Lasso Sélection de modèle Estimation Prédiction Compléments

Regularization path

Linear Lasso
0 7 15 26 37

0.2
3
0.1

15
Coefficients

30
32
17
36
14
13
23
26
24
10
29
0.0

19
20
11
33
37
2
18
25
31
21
34
27
12
38
35

28
9
1
−0.1

22

4
−0.2

0.0 0.5 1.0 1.5 2.0

L1 Norm
Introduction Le Lasso Sélection de modèle Estimation Prédiction Compléments

Une seconde condition d’optimalité

Lemme 2.2
Une autre CNS pour que β̂ soit solution de (1) est que pour
tout β ∈ IRp

kY − Xβ̂k22 kY − Xβk22
+ λkβ̂k1 6 + λkβk1
2n 2n
En particulier, on a la CN suivante :

kY − Xβ̂k22 kY − Xβ∗ k22

+ λkβ̂k1 6 + λkβ∗ k1
2n 2n

Cette caractérisation nous sera utile pour étudier les propriétés

d’estimation et d’erreur de prédiction du Lasso.
Introduction Le Lasso Sélection de modèle Estimation Prédiction Compléments

"Sparsistency" du Lasso

Une procédure de sélection de variables est dite consistante

en sélection de variables, ou "sparsistent", ssi le support du
vecteur estimé est identique au support du vecteur
théorique, Jb = J0 , avec grande probabilité.

Intuitivement, 2 types d’hypothèses sont nécessaires pour

la sparsistency.
conditions d’identifiabilité
beta-min conditions
Introduction Le Lasso Sélection de modèle Estimation Prédiction Compléments

Hypothèses liées à l’identifiabilité

On supposera qu’il existe un paramètre de non-représentabilité

γ ∈ (0, 1] et une constante Cmin > 0 tels que

maxc kXjT XJ0 (XT −1

J0 XJ0 ) k1 6 (1 − γ) (2)
j ∈J0
 XT X J 
J0 0
Λmin > Cmin (3)
n

Remarque : On ne peut pas savoir si ces conditions sont

vérifiées a priori puisque J0 est inconnu.
Introduction Le Lasso Sélection de modèle Estimation Prédiction Compléments

Interprétations de ces hypothèses

Hypothèse de valeur propre minimale (3) : identifiabilité

du problème restreint à J0 .
Introduction Le Lasso Sélection de modèle Estimation Prédiction Compléments

Interprétations de ces hypothèses

Hypothèse de valeur propre minimale (3) : identifiabilité

du problème restreint à J0 .

Condition de non-représentabilité (2) :

pour tout j ∈ J0c , kXjT XJ0 (XT
J0 XJ0 )
−1
k1 : norme `1 du
paramètre de la régression linéaire de Xj sur XJ0 , estimé
par MCO.
un design idéal est tel que Xj est orthogonal aux colonnes
de la matrice XJ0 , auquel cas on aurait γ = 1.
En grande dimension, on ne peut pas avoir cette
orthogonalité stricte, mais on peut espérer être dans une
situation de "quasi-orthogonalité".
Introduction Le Lasso Sélection de modèle Estimation Prédiction Compléments

Liens avec d’autres hypothèses "classiques"

Dans ce cours, on se contentera de présenter des résultats

obtenus sous la condition de non-représentabilité.
On peut aussi travailler sous les hypothèses suivantes
hypothèse d’incohérence mutuelle : le paramètre
d’incohérence de la matrice de design est "petit":

XjT Xk
ι(1) (X) = max 6 ν.
j 6=k n

RIP (restricted isometry property) : la constante

d’isométrie restreinte est "petite"

XT
S XS
s (X) = inf  : ∀S : |S | 6 s,
ι(2) − Is×s 6 .
n 2
Introduction Le Lasso Sélection de modèle Estimation Prédiction Compléments

Résultat principal

Soit ΠX⊥ := In×n − XJ0 (XT −1 T

J 0 X J 0 ) XJ 0 .
J0

Théorème 3.1
Sous les hypothèses (2) et (3) précédentes, l’estimateur
Lasso vérifie, pour λ > (2/γ)kXTJ c ΠX⊥ ξ/nk∞ ,0 J0
1 Unicité : Le Lasso (1) a une solution unique β̂.
2 Absence de "faux positif" : Jb ⊆ J0 .
3 Borne sur la norme `∞ : kβ̂J0 − β∗J0 k∞ 6 B (λ, X) avec

 XT XJ −1 ξ  XT XJ −1

J0 J0
XT
0 0
B (λ, X) = J0 +λ
n n ∞ n ∞

4 Absence de "faux négatif" : le Lasso est sparsistent si

mink ∈J0 |β∗k | > B (λ, X).
Introduction Le Lasso Sélection de modèle Estimation Prédiction Compléments

Corollaire 3.1
On suppose que les ξi ∼ N(0, σ2 ), et que la matrice de design
X est déterministe, vérifie les conditions (2) et (3), et a ses
colonnes normalisées, telles que
n −1/2 maxj =1,...,p kXj k2 6 C , pour une constante C > 0.
Pour le choix
s
2C σ 2 log(p − s0 ) + δ2
λ= ,
γ n

pour une constante δ > 0, on a le résultat suivant, avec

2 2
probabilité supérieure à 1 − 2e −δ /2 − 2e −ε /2 : pour tout
ε > 0, la solution optimale β̂ est unique, de support Jb ⊆ J0
et telle que
r √
∗ σ 2 log s0 + ε2 λ s0
kβ̂ − β k∞ 6 √ + .
Cmin n Cmin
Introduction Le Lasso Sélection de modèle Estimation Prédiction Compléments

Preuve
On doit premièrement montrer que ce choix de λ vérifie, avec
grande probabilité, la condition sur le λ du Théorème 3.1. Soit,
pour tout j ∈ J0c , Vj = XjT ΠX⊥ ξ/n. Ces variables aléatoires
J0
sont gaussiennes, centrées, et de variance bornée par

σ2 kΠX⊥ Xj /nk22 6 σ2 kXj /nk22 6 σ2 C 2 /n.

J0

On en déduit que2
2 /(2C 2 σ2 )
IP(maxc |Vj | > t ) 6 2(p − s0 )e −nt
j ∈J0

et donc que
r
 ξ 2 log(p − s0 ) + δ2  2
IP XT
J0c ΠX⊥ > Cσ 6 2e −δ /2
J0 n ∞ n
2
par l’Union Bound et l’inégalité de concentration pour variable
gaussienne : X ∼ N(µ, σ2 ) : IP(|X − µ| > t ) 6 2 exp(−t 2 /(2σ2 ))
Introduction Le Lasso Sélection de modèle Estimation Prédiction Compléments

Preuve (suite) T −1 XT ξ

ek = e T XJ0 XJ0 J0
Soit V k n n , pour tout k ∈ J0 . On montre
facilement que les Vek sont gaussiennes, centrées de variance
bornée par
σ2  XT J 0 XJ 0
−1 σ2
6 .
n n 2 Cmin n
En procédant comme précédemment, il vient donc
r
 σ 2 log s0 + ε2  2
IP max |V ek | > √ 6 2e −ε /2 .
k =1,...,s0 Cmin n

Comme enfin
 XT XJ −1  XT XJ −1 √
J0 0 √ J0 0 s0
6 s0 6 ,
n ∞ n 2 Cmin
le résultat du Lemme est donc vérifié avec probabilité
2 2
supérieure à 1 − 2e −δ /2 − 2e −ε /2 .
Introduction Le Lasso Sélection de modèle Estimation Prédiction Compléments

Corollaire 3.2
On suppose que la matrice de design X vérifie les
hypothèses du Théorème 3.1, que p = O(exp(n δ3 )),
s0 = O(n δ1 ), et que β2min > n −(1−δ2 ) avec

0 < δ1 + δ3 < δ2 < 1.

Si λn = n −(1−δ4 )/2 pour un δ4 ∈ (δ3 , δ2 − δ1 ), alors le Lasso

est sparsistent avec probabilité supérieure à 1 − exp(−c1 n δ4 ),
pour une certaine constante c1 .
Introduction Le Lasso Sélection de modèle Estimation Prédiction Compléments

Corollaire 3.2
On suppose que la matrice de design X vérifie les
hypothèses du Théorème 3.1, que p = O(exp(n δ3 )),
s0 = O(n δ1 ), et que β2min > n −(1−δ2 ) avec

0 < δ1 + δ3 < δ2 < 1.

Si λn = n −(1−δ4 )/2 pour un δ4 ∈ (δ3 , δ2 − δ1 ), alors le Lasso

est sparsistent avec probabilité supérieure à 1 − exp(−c1 n δ4 ),
pour une certaine constante c1 .

p peut croître exponentiellement avec n

s0 /p ≈ n δ1 exp(−n δ3 ) décroît exponentiellement avec n.
Si p (et s0 ) fixe, λ = n −(1−δ)/2 et βmin > c2 n −(1−δ)/2
(pour δ > 0) assurent la sparsistency avec probabilité
> 1 − 2 exp(−c1 nδ), pour une constante c1 > 0.
Introduction Le Lasso Sélection de modèle Estimation Prédiction Compléments

Une condition suffisante d’échec pour le Lasso

Théorème 3.2
On suppose que la condition sur la valeur propre minimale
(3) est vérifiée et que le vecteur de bruit ξ a une
distribution symétrique autour de 0.
1 Si la condition de non-représentabilité (2) n’est pas
vérifiée, en particulier si
∗
maxc |XjT XJ0 (XT
J0 XJ0 )sign(βJ0 )| = 1 + ν > 1, (4)
j ∈J0

alors pour tout λn > 0 et n

IP[sign(β̂) = sign(β∗ )] 6 1/2.

Introduction Le Lasso Sélection de modèle Estimation Prédiction Compléments

Lemme 2.1 "étendu"

Lemme 3.1
1 Un vecteur β̂ ∈ IRp est optimal ssi ∃ẑ ∈ ∂kβ̂k1 tel que

XT X XT ξ
(β̂ − β∗ ) − + λẑ = 0 (5)
n n
2 Pour tout j ∈ Jb c , si |ẑj | < 1 alors toute solution
optimale β̄ du Lasso est telle que β̄j = 0.
Introduction Le Lasso Sélection de modèle Estimation Prédiction Compléments

Lemme 2.1 "étendu"

Lemme 3.1
1 Un vecteur β̂ ∈ IRp est optimal ssi ∃ẑ ∈ ∂kβ̂k1 tel que

XT X XT ξ
(β̂ − β∗ ) − + λẑ = 0 (5)
n n
2 Pour tout j ∈ Jb c , si |ẑj | < 1 alors toute solution
optimale β̄ du Lasso est telle que β̄j = 0.

Preuve : D’après la règle de Fermat (cf. cours de N.P.),

β̂ ∈ Argminβ (2n)−1 kY − Xβk22 + λkβk1 est équivalent à :
∃ẑ ∈ ∂kβ̂k1 tel que n1 XT (Xβ̂ − Y) + λẑ = 0. La partie (1) du
Lemme découle ensuite de l’égalité Y = Xβ∗ + ξ. On en déduit
également le résultat du Lemme 2.1 puisque Gj (β̂) = −λẑj .
Introduction Le Lasso Sélection de modèle Estimation Prédiction Compléments

Preuve (suite)
Pour le point (2), raisonnons par l’absurde.
Soit β́ une autre solution du problème Lasso (1) et j ∈ Jb c
tel que |ẑj | < 1 et β́j 6= 0.
Puisque le problème Lasso est convexe, l’ensemble de ses
solutions est convexe et donc, pour tout ρ ∈ [0, 1],

β̂ρ = (1 − ρ)β̂ + ρβ́

est également solution du Lasso.

Pour tout ρ ∈ (0, 1], on a par ailleurs β̂ρ,j 6= 0 (par
construction), et donc, d’après le résultat du Lemme 2.1,
|Gj (β̂ρ )| = λ.
En définissant la fonction f (ρ) = |Gj (β̂ρ )|, on a donc
f (0) < λ et f (ρ) = λ, pour tout ρ ∈ (0, 1].
Ceci est en contradiction avec la continuité de la fonction f .
Introduction Le Lasso Sélection de modèle Estimation Prédiction Compléments

Primal-Dual Witness construction

On va chercher à construire une paire (β̂, ẑ) ∈ IRp × IRp de la

manière suivante :
1 Soit β̂J0c = 0.

2 Soit (β̂J0 , ẑJ0 ), avec β̂J0 ∈ IRs0 une solution du problème

Lasso oraculaire:
kY − XJ0 βJ0 k22
β̂J0 ∈ Arg min + λkβJ0 k1
βJ0 ∈IRs0 2n

et ẑJ0 ∈ ∂kβ̂J0 k1 tel que GJ0 (β̂J0 ) + λẑJ0 = 0.

3 On résout, en ẑJ0c ∈ IRp−s0 , l’équation (5), et on vérifie la

condition de faisabilité stricte, |ẑj | < 1, pour tout j ∈ J0c
Introduction Le Lasso Sélection de modèle Estimation Prédiction Compléments

PDW et sparsistency du Lasso

6= méthode de résolution numérique pour le Lasso !!

Lemme 3.2
Si la construction PDW aboutit, alors sous l’hypothèse de
valeur propre minimale (3), le vecteur (β̂J0 , 0) est l’unique
solution du Lasso.
Introduction Le Lasso Sélection de modèle Estimation Prédiction Compléments

PDW et sparsistency du Lasso

6= méthode de résolution numérique pour le Lasso !!

Lemme 3.2
Si la construction PDW aboutit, alors sous l’hypothèse de
valeur propre minimale (3), le vecteur (β̂J0 , 0) est l’unique
solution du Lasso.

Preuve : Sous la condition de faisabilité stricte, le Lemme 3.1

assure que toute solution du Lasso β̄ est telle que β̄j = 0 pour
tout j ∈ J0c . Toute solution est donc de la forme (β̄J0 , 0), et on
peut donc obtenir β̄J0 en résolvant le Lasso oraculaire.
D’autre part, sous l’hypothèse (3), le Lasso oraculaire est
strictement convexe, et admet donc une solution unique.
Introduction Le Lasso Sélection de modèle Estimation Prédiction Compléments

Preuve du Théorème 3.1

Pour établir les points (1) et (2), au vu du Lemme 3.2, il
suffit de montrer que la faisabilité stricte est vérifiée dans
le PDW.
En réécrivant (5) par bloc, on a β̂J0 , ẑJ0 et ẑJ0c qui vérifient:
" # " # 
1 XT TX c ∗ Tξ
 
J0 X J 0 X J0 J 0 β̂J0 − βJ0 − 1 X J0 ẑJ0
+λ = 0.
n XT T
J0c XJ0 XJ0c XJ0
c 0 n XT J0c ξ ẑJ0c

On a donc
 XT XJ −1 h XT ξ i
J0 J0
β∗J0
0
β̂J0 − = − λẑJ0 (6)
n n
et
 ξ 
ẑJ0c = XT T −1 T
J0c XJ0 (XJ0 XJ0 ) ẑJ0 + XJ0c ΠX⊥ J0 nλ
=: µ + V
Introduction Le Lasso Sélection de modèle Estimation Prédiction Compléments

Preuve du Théorème 3.1 (suite)

Sous la condition de non-représentabilité, on a

kµk∞ 6 (1 − γ).

La condition sur λ assure pour sa part que kV k∞ 6 γ/2.

La faisabilité stricte suit facilement en utilisant

kẑJ0c k∞ 6 kµk∞ + kV k∞ 6 (1 − γ/2) < 1.

Pour le point (3), il vient de (6) que

 XT XJ −1 XT ξ  XT XJ −1
J0 J0 J0
kβ̂J0 − β∗J0 k∞ 6
0 0
+λ .
n n ∞ n ∞

La preuve du point (4) est directe.

Introduction Le Lasso Sélection de modèle Estimation Prédiction Compléments

Restricted Eigenvalue condition

Définition 4.1
Soit, pour tout α > 0, le "cône" Cα (J0 ) de IRp défini par

Cα (J0 ) = {∆ ∈ IRp : k∆J0c k1 6 αk∆J0 k1 }

Définition 4.2
La matrice de design X vérifie la Restricted Eigenvalue
condition sur J0 , avec les paramètres (κ, α), avec κ > 0, si
1
kX∆k22 > κk∆k22 pour tout ∆ ∈ Cα (J0 ).
n
Introduction Le Lasso Sélection de modèle Estimation Prédiction Compléments

Intuition pour la RE

Considérons la version contrainte avec T = kβ∗ k1 .

Soit Ln (β) = kY − Xβk22 /(2n).
Si n → ∞, on peut espérer Ln (β̂) ≈ Ln (β∗ ).
Sous quelles conditions cela implique-t-il que β̂ ≈ β∗ ?

D’après Wainwright (unpublished)

Introduction Le Lasso Sélection de modèle Estimation Prédiction Compléments

Intuition pour la RE (suite)

En multivarié, la courbure est liée au Hessien de Ln :
(XT X)/n : si cette matrice est définie positive, i.e.,
1
kX∆k22 > κk∆k22 > 0 pour tout ∆ ∈ IRp \ {0},
n
alors Ln aurait une courbure élevée dans toutes les
directions.
Impossible en grande dimension (p > n) : il y a forcément
au moins p − n directions selon lesquelles Ln est "plate".
Introduction Le Lasso Sélection de modèle Estimation Prédiction Compléments

Résultat principal

Théorème 4.1
On suppose que X vérifie la condition RE sur J0 avec les
paramètres (κ, 3). Alors toute solution du Lasso avec
√
λ > 2kXT ξ/nk∞ est telle que kβ̂ − β∗ k2 6 3λ s0 /κ.

Corollaire 4.1
Supposons que les conditions du Théorème 4.1 et les
hypothèses de normalité des résidus ξi ∼ N(0, σ2 ) et de
standardisation des variables, n −1/2 maxj =1,...,p kXj k2 6 C
(pour une constante C 6 0) sont vérifiées. Alors, pour le
choix r
2 log p + δ2
λ = 2C σ
n
le résultat du Théorème 4.1 est vérifié avec probabilité
2
supérieure à 1 − 2e −δ /2 .
Introduction Le Lasso Sélection de modèle Estimation Prédiction Compléments

Preuve du corollaire

Sous les conditions du corollaire, la quantité kXT ξ/nk∞

correspond au maximum de la valeur absolue de p variables
gaussiennes, centrées et de variance bornée par C 2 σ2 /n.
En procédant comme précédemment, on obtient alors que pour
tout δ > 0,
r
 2 log p + δ2  2
IP kXT ξ/nk∞ > C σ 6 2e −δ /2 .
n
Le résultat du Théorème 4.1 permet donc de conclure qu’avec
2
une probabilité supérieure à 1 − 2e −δ /2 , on a
r
∗ 6C σ 2s0 log p + s0 δ2
kβ̂ − β k2 6 .
κ n
Introduction Le Lasso Sélection de modèle Estimation Prédiction Compléments

Preuve du Théorème 4.1

b = (β̂ − β∗ ) ∈ C3 (J0 )
1 Si λ > 2kXT ξ/nk , alors ∆
∞
Introduction Le Lasso Sélection de modèle Estimation Prédiction Compléments

Preuve du Théorème 4.1

1 Si λ > 2kXT ξ/nk , alors ∆
∞
b = (β̂ − β∗ ) ∈ C3 (J0 )
Puisque β̂ est optimal, on a les propriétés suivantes
kY − Xβ̂k22 kY − Xβ∗ k22
+ λkβ̂k1 6 + λkβ∗ k1
2n 2n
kY − Xβ̂k22 kξk22
+ λkβ̂k1 6 + λkβ∗ k1
2n 2n
Introduction Le Lasso Sélection de modèle Estimation Prédiction Compléments

Preuve du Théorème 4.1

1 Si λ > 2kXT ξ/nk , alors ∆
∞
b = (β̂ − β∗ ) ∈ C3 (J0 )
Puisque β̂ est optimal, on a les propriétés suivantes
kY − Xβ̂k22 kY − Xβ∗ k22
+ λkβ̂k1 6 + λkβ∗ k1
2n 2n
kY − Xβ̂k22 kξk22
+ λkβ̂k1 6 + λkβ∗ k1
2n 2n
b 2 T
kX∆k b J c k1 ) 6 2 ξ X∆ + 2λkβ∗ k1
b
2
+ 2λ(kβ∗J0 + ∆
b J k1 + k∆
0 J0
n 0
n
b 2 T
kX∆k 2 b J c k1 6 2k∆kb 1 ξ X +2λk∆ b J k1
+ 2λk∆ 0
n 0
n ∞
kX∆k b 2
06 2
6 λ{3k∆ b J c k1 }.
b J k1 − k∆
0
n 0
Introduction Le Lasso Sélection de modèle Estimation Prédiction Compléments

Preuve du Théorème 4.1

1 Si λ > 2kXT ξ/nk , alors ∆
∞
b = (β̂ − β∗ ) ∈ C3 (J0 )
Puisque β̂ est optimal, on a les propriétés suivantes
kY − Xβ̂k22 kY − Xβ∗ k22
+ λkβ̂k1 6 + λkβ∗ k1
2n 2n
kY − Xβ̂k22 kξk22
+ λkβ̂k1 6 + λkβ∗ k1
2n 2n
b 2 T
kX∆k b J c k1 ) 6 2 ξ X∆ + 2λkβ∗ k1
b
2
+ 2λ(kβ∗J0 + ∆
b J k1 + k∆
0 J0
n 0
n
b 2 T
kX∆k 2 b J c k1 6 2k∆kb 1 ξ X +2λk∆ b J k1
+ 2λk∆ 0
n 0
n ∞
kX∆k b 2
06 2
6 λ{3k∆ b J c k1 }.
b J k1 − k∆
0
n 0

2 On conclut la preuve du Théorème 4.1 en appliquant la RE

b 2 6 3λk∆
pour obtenir κk∆k b J k1 6 3λ√s0 k∆k
b 2.
2 0
Introduction Le Lasso Sélection de modèle Estimation Prédiction Compléments

Résultat principal

Théorème 5.1
Soit β̂ une solution optimale du problème Lasso (1) avec le
choix λ > 2kXT ξ/nk∞ .
1 On a toujours la vitesse lente suivante:

kX(β̂ − β∗ )k22
6 12kβ∗ k1 λ.
n
2 Si le support de β∗ , J0 , est tel que |J0 | = s0 et que la
matrice de design X vérifie la condition RE avec
paramètres (κ, 3) sur J0 , on a alors la vitesse rapide
suivante
kX(β̂ − β∗ )k22 9
6 s0 λ2 .
n κ
Introduction Le Lasso Sélection de modèle Estimation Prédiction Compléments

Corollaire
En procédant comme précédemment, on montre que si les
ξj ∼ N(0, σ2 ), et sous l’hypothèse de variables p
normalisées,
n −1/2 maxj kXj k 6 C , alors le choix λ = 2C σ (2 log p + δ2 )/n
est "valide" avec probabilité supérieure à 1 − exp(−δ2 /2), et
alors :
1 la partie (1) du Théorème implique que

r
kX(β̂ − β∗ )k22 ∗ 2 log p + δ2
6 24kβ k1 C σ .
n n

sous la seule contrainte kβ∗ k1 6 T , cette borne ne peut pas

être améliorée.
2 sous les hypothèses de sparsité et RE, alors on obtient la
borne
kX(β̂ − β∗ )k22  36C 2 σ2  2s0 log p + s0 δ2
6 .
n κ n
Introduction Le Lasso Sélection de modèle Estimation Prédiction Compléments

Preuve du point (2) du Théorème 5.1

En procédant comme dans la preuve du Théorème 4.1, il vient

b 2
kX∆k 2 b J k1 6 3λ√s0 k∆
6 3λk∆ b J k2 .
0 0
n

D’autre part, comme on a toujours ∆ b ∈ C3 (J0 ), on peut

appliquer une nouvelle fois la condition RE−(κ, 3) :

b 2
kX∆k
b 26
k∆k 2
,
2
nκ
ce qui, combiné à l’inégalité précédente, conduit à
√
kX∆k 3λ s0
√ 2 6 √
b
n κ
Introduction Le Lasso Sélection de modèle Estimation Prédiction Compléments

Preuve du point (1) du Théorème 5.1

1 b 1 6 4kβ∗ k1 .
Montrons que k∆k
Introduction Le Lasso Sélection de modèle Estimation Prédiction Compléments

Preuve du point (1) du Théorème 5.1

1 b 1 6 4kβ∗ k1 .
Montrons que k∆k
En procédant comme précédemment on obtient aisément

b 2
kX∆k ξT X ∆
b
06 2
6 + λ{kβ∗ k1 − kβ̂k1 }. (7)
2n n
D’après l’inégalité d’Hölder, le choix de λ, puis l’inégalité
triangulaire, il vient

ξ T X∆
b XT ξ λ
6 k∆k
b 16 (kβ∗ k1 + kβ̂k1 ). (8)
n n ∞ 2

En combinant ces deux inégalités, il vient kβ̂k1 6 3kβ∗ k1 ,

et donc, via l’inégalité triangulaire,
b 1 6 kβ̂k1 + kβ∗ k1 6 4kβ∗ k1 .
k∆k
Introduction Le Lasso Sélection de modèle Estimation Prédiction Compléments

Preuve du point (1) du Théorème 5.1 (suite)

2 En combinant les résultats obtenus dans les dérivations des

équations (7) et (8), il vient également

b 2
kX∆k λ b ∗ ∗
1 + λ{kβ k1 − kβ + ∆k1 }
2
6 k∆k b
2n 2
3λ b
6 k∆k1
2
6 6λkβ∗ k1

où la 2ème ligne vient de l’inégalité triangulaire

kβ∗ + ∆k
b 1 > kβ∗ k1 − k∆k
b 1,

b 1 6 4kβ∗ k1 .
et la 3ème ligne de la borne k∆k
Introduction Le Lasso Sélection de modèle Estimation Prédiction Compléments

Sur les conditions RE, MI, etc.

Table : Récapitulatif des liens "Résultats-conditions"

Propriétés conditions sur X beta-min
Prédiction Vitesse Lente "Rien" Non
Prédiction Vitesse Rapide RE (pas nécess.) Non
J0 ⊆ Jb RE Oui
J0 = Jb Non-Repres. Oui

On peut montrer que RE n’est pas nécessaire pour vitesse

rapide en prédiction (mais il faut quand même certaines
hypothèses sur la matrice de design, contrairement à
d’autres approches telles que `0 )
Pour sparsistency (et estimation), il faut des conditions,
liées à l’identifiabilité.
Cas de design aléatoire
Introduction Le Lasso Sélection de modèle Estimation Prédiction Compléments

Qq conditions proposées, et leurs inter-relations....

D’après van de Geer et Bühlmann, EJS, 2009.

Introduction Le Lasso Sélection de modèle Estimation Prédiction Compléments

Modèles Linéaires généralisés

Pour ces modèles,

P la vraisemblance s’exprime généralement
sous la forme i L(Yi , XT
i β)
Régression logistique : L(y, η) = yη − log(1 + e η )

Le Lasso se généralise alors :

X
n
φ(λ) := minp − L(Yi , xT
i β) + λkβk1 .
β∈IR
i =1

ou
X
n
φ(λ) := maxp L(Yi , xT
i β) − λkβk1 .
β∈IR
i =1
Introduction Le Lasso Sélection de modèle Estimation Prédiction Compléments

En pratique

On travaille généralement sur variables "standardisées"

Différentes approches ont été proposées, à partir du Lasso,

pour l’améliorer
Adaptive Lasso
Thresholded Lasso
Relaxed Lasso
BoLasso
...
Introduction Le Lasso Sélection de modèle Estimation Prédiction Compléments

Biblio
1 Wainwright. Sharp thresholds for high-dimensional ...,

IEEE Trans. Inform. Theory, 2009.

2 Wainwright. Livre en cours d’écriture.

3 Lounici. Sup-norm convergence rate and sign

concentration property of Lasso and Dantzig

estimators. EJS, 2008.
4 Bickel, Ritov, Tsybakov. Simultaneous analysis of Lasso

and Dantzig Selector, AoS, 2009.

5 van de Geer et Bühlmann. Statistics for

high-dimensional data, (Chap. 2, 6, 7), Springer, 2011.

6 van de Geer et Bühlmann. On the conditions used to

prove oracle results for the Lasso, EJS, 2009.

7 Giraud. High-dimensional statistics, 2013.

[Link]
[Link]
8 Horn et Johnson. Matrix Analysis, 2nd Ed., Cambridge

Univ. Press, 2013.