Sparse recovery in convex hulls via entropy penalization TeX Export

@article{citeulike:4746961, 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\_jh\_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{\lambda}^{\varepsilon}:={\mathop {argmin}\_{\lambda\in \Lambda}}\Biggl[P\_n(\ell \bullet f\_{\lambda})+\varepsilon \sum\_{j=1}^N\lambda\_j\log \lambda\_j\Biggr]\end{eqnarray*} along with its distribution dependent version \begin{eqnarray*}\lambda^{\varepsilon}:={\mathop {argmin}\_{\lambda\in \Lambda}}\Biggl[P(\ell \bullet f\_{\lambda})+\varepsilon \sum\_{j=1}^N\lambda\_j\log \lambda\_j\Biggr],\end{eqnarray*} where \$\varepsilon\geq 0\$ is a regularization parameter. It is proved that the ``approximate sparsity'' of \$\lambda^{\varepsilon}\$ implies the ``approximate sparsity'' of \$\hat{\lambda}^{\varepsilon}\$ 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.}, archivePrefix = {arXiv}, author = {Koltchinskii, Vladimir}, citeulike-article-id = {4746961}, citeulike-linkout-0 = {http://arxiv.org/abs/0905.2078}, citeulike-linkout-1 = {http://arxiv.org/pdf/0905.2078}, day = {13}, eprint = {0905.2078}, keywords = {bounds, convexity, information, sparse, theory}, month = {May}, posted-at = {2009-06-05 04:53:37}, priority = {2}, title = {Sparse recovery in convex hulls via entropy penalization}, url = {http://arxiv.org/abs/0905.2078}, year = {2009} }

TY - JOUR ID - citeulike:4746961 L3 - citeulike-article-id:4746961 N2 - 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_jh_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{\lambda}^{\varepsilon}:={\mathop {argmin}_{\lambda\in \Lambda}}\Biggl[P_n(\ell \bullet f_{\lambda})+\varepsilon \sum_{j=1}^N\lambda_j\log \lambda_j\Biggr]\end{eqnarray*} along with its distribution dependent version \begin{eqnarray*}\lambda^{\varepsilon}:={\mathop {argmin}_{\lambda\in \Lambda}}\Biggl[P(\ell \bullet f_{\lambda})+\varepsilon \sum_{j=1}^N\lambda_j\log \lambda_j\Biggr],\end{eqnarray*} where $\varepsilon\geq 0$ is a regularization parameter. It is proved that the ``approximate sparsity'' of $\lambda^{\varepsilon}$ implies the ``approximate sparsity'' of $\hat{\lambda}^{\varepsilon}$ 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. TI - Sparse recovery in convex hulls via entropy penalization KW - bounds KW - convexity KW - information KW - sparse KW - theory AU - Koltchinskii, Vladimir PY - 2009/May/13/ UR - http://arxiv.org/abs/0905.2078 ER -