Sparse recovery in convex hulls via entropy penalization

Abstract

Let $(X,Y)$ be a random couple in $S\times T$ with unknown distribution $P$ and $(X_1,Y_1),...,(X_n,Y_n)$ be i.i.d. copies of $(X,Y).$ Denote $P_n$ the empirical distribution of $(X_1,Y_1),...,(X_n,Y_n).$ Let $h_1,...,h_N:S\mapsto [-1,1]$ be a dictionary that consists of $N$ functions. For $\lambda \in {\mathbb{R}}^N,$ denote $f_{\lambda }:={\sum }_{j=1}^N{\lambda }_j{h}_j.$ Let $\ell :T\times \mathbb{R}\mapsto \mathbb{R}$ be a given loss function and suppose it is convex with respect to the second variable. Let $(\ell \bullet f)(x,y):=\ell (y;f(x)).$ Finally, let $\Lambda \subset {\mathbb{R}}^N$ be the simplex of all probability distributions on $\{1,...,N\}.$ Consider the following penalized empirical risk minimization problem \begin{eqnarray*}\hatλ^{\varepsilon}:={\mathop {argmin}_{λ\in Λ}}\Biggl[P_n(\ell \bullet f_λ)+\varepsilon \sum_{j=1}^Nλ_j\log λ_j\Biggr]\end{eqnarray*} along with its distribution dependent version \begin{eqnarray*}λ^{\varepsilon}:={\mathop {argmin}_{λ\in Λ}}\Biggl[P(\ell \bullet f_λ)+\varepsilon \sum_{j=1}^Nλ_j\log λ_j\Biggr],\end{eqnarray*} where $\epsilon \ge 0$ is a regularization parameter. It is proved that the ``approximate sparsity'' of ${\lambda }^{\epsilon }$ implies the ``approximate sparsity'' of ${\hat{\lambda }}^{\epsilon }$ and the impact of ``sparsity'' on bounding the excess risk of the empirical solution is explored. Similar results are also discussed in the case of entropy penalized density estimation.

Published in at http://dx.doi.org/10.1214/08-AOS621 the Annals of Statistics (http://www.imstat.org/aos/) by the Institute of Mathematical Statistics (http://www.imstat.org)

References in corpus (6)

• Simultaneous analysis of Lasso and Dantzig selector
• High-dimensional generalized linear models and the lasso
• 2004 IMS Medallion Lecture: Local Rademacher complexities and oracle inequalities in risk minimization
• Sparsity oracle inequalities for the Lasso
• From $\epsilon$-entropy to KL-entropy: Analysis of minimum information complexity density estimation
• The Dantzig selector and sparsity oracle inequalities

Cited by in corpus (10)

• Sparsity in multiple kernel learning
• Sparse Regression Learning by Aggregation and Langevin Monte-Carlo
• A Selective Overview of Variable Selection in High Dimensional Feature Space (Invited Review Article)
• Mirror averaging with sparsity priors
• Variational Gaussian Dropout is not Bayesian
• Sparsity regret bounds for individual sequences in online linear regression
• General nonexact oracle inequalities for classes with a subexponential envelope
• Sample average approximation with heavier tails II: localization in stochastic convex optimization and persistence results for the Lasso
• Concentrated Document Topic Model
• $L_1$-Penalization in Functional Linear Regression with Subgaussian Design