Sparsity in penalized empirical risk minimization

Koltchinskii, Vladimir 

Annales de l'I.H.P. Probabilités et statistiques, Tome 45 (2009) no. 1, pp. 7-57

Abstract (VO)

Let $(X,Y)$ be a random couple in $S\times T$ with unknown distribution $P$. Let $(X_1,Y_1),...,(X_n,Y_n)$ be i.i.d. copies of $(X,Y)$, $P_n$ being their empirical distribution. Let $h_1,...,h_N:S\mapsto \left[-1,1\right]$ be a dictionary consisting of $N$ functions. For $\lambda \in {ℝ}^N$, denote $f_{\lambda }:={\sum }_{j=1}^N{\lambda }_j{h}_j$. Let $\ell :T\times ℝ\mapsto ℝ$ be a given loss function, which is convex with respect to the second variable. Denote $(\ell •f)(x,y):=\ell (y;f(x\left)\right)$. We study the following penalized empirical risk minimization problem

$${\widehat{\lambda }}^{\epsilon }:=\underset{\lambda \in {ℝ}^N}{argmin}\left[P_n(\ell •f_{\lambda })+\epsilon {\parallel \lambda \parallel }_{{\ell }_p}^p\right],$$

which is an empirical version of the problem

$${\lambda }^{\epsilon }:=\underset{\lambda \in {ℝ}^N}{argmin}\left[P(\ell •f_{\lambda })+\epsilon {\parallel \lambda \parallel }_{{\ell }_p}^p\right]$$

(here $\epsilon \ge 0$ is a regularization parameter; ${\lambda }^0$ corresponds to $\epsilon =0$). A number of regression and classification problems fit this general framework. We are interested in the case when $p\ge 1$, but it is close enough to 1 (so that $p-1$ is of the order $\frac{1}{logN}$, or smaller). We show that the “sparsity” of ${\lambda }^{\epsilon }$ implies the “sparsity” of ${\widehat{\lambda }}^{\epsilon }$ and study the impact of “sparsity” on bounding the excess risk $P(\ell •f_{{\widehat{\lambda }}^{\epsilon }})-P(\ell •f_{{\lambda }^0})$ of solutions of empirical risk minimization problems.

Résumé

Soit $(X,Y)$ un couple aléatoire à valeurs dans $S\times T$ et de loi $P$ inconnue. Soient $(X_1,Y_1),...,(X_n,Y_n)$ des répliques i.i.d. de $(X,Y)$, de loi empirique associée $P_n$. Soit $h_1,...,h_N:S\mapsto \left[-1,1\right]$ un dictionnaire composé de $N$ fonctions. Pour tout $\lambda \in {ℝ}^N$, on note $f_{\lambda }:={\sum }_{j=1}^N{\lambda }_j{h}_j$. Soit $\ell :T\times ℝ\mapsto ℝ$ fonction de perte donnée que l’on suppose convexe en la seconde variable. On note $(\ell •f)(x,y):=\ell (y;f(x\left)\right)$. On étudie le problème de minimisation du risque empirique pénalisé suivant

$${\widehat{\lambda }}^{\epsilon }:=\underset{\lambda \in {ℝ}^N}{argmin}\left[P_n(\ell •f_{\lambda })+\epsilon {\parallel \lambda \parallel }_{{\ell }_p}^p\right],$$

qui correspond à la version empirique du problème

$${\lambda }^{\epsilon }:=\underset{\lambda \in {ℝ}^N}{argmin}\left[P(\ell •f_{\lambda })+\epsilon {\parallel \lambda \parallel }_{{\ell }_p}^p\right]$$

(ici $\epsilon \ge 0$ est un paramètre de régularisation; ${\lambda }^0$ correspond au cas $\epsilon =0$). Ce cadre général englobe un certain nombre de problèmes de régression et de classification. On s’intéresse au cas où $p\ge 1$, mais reste proche de 1 (de sorte que $p-1$ soit de l’ordre $\frac{1}{logN}$, ou inférieur). On montre que la «sparsité» de ${\lambda }^{\epsilon }$ implique la «sparsité» de ${\widehat{\lambda }}^{\epsilon }$. En outre, on étudie les conséquences de la «sparsité» en termes de bornes supérieures sur l’excès de risque $P(\ell •f_{{\widehat{\lambda }}^{\epsilon }})-P(\ell •f_{{\lambda }^0})$ des solutions obtenues pour les différents problèmes de minimisation du risque empirique.

Détail

DOI : 10.1214/07-AIHP146

Classification : 62G99, 62J99, 62H30
Keywords: empirical risk, penalized empirical risk, ℓ_p-penalty, sparsity, oracle inequalities