Sparse Recovery in Convex Hulls of Infinite Dictionaries

Abstract

Let S be an arbitrary measurable space, $T \subset R$ and (X, Y ) be a random couple in $S \times T$ with unknown distribution P. Let (X1, Y1), . . . , (Xn, Yn) be i.i.d. copies of (X, Y ). Denote by Pn the empirical distribution based on the sample (Xi, Yi), i = 1, . . . , n. Let H be a set of uniformly bounded functions on S. Suppose that H is equipped with a σ-algebra and with a finite measure $\mu$. Let D be a convex set of probability densities with respect to $\mu$. For $\lambda$ ∈D, define the mixture f$\lambda$(·) = R H h(·)$\lambda$(h)d$\mu$(h). Given a loss function $\ell: T \times \mathbb{R} \to \mathbb{R}$ such that, for all $y \in T$, $\ell$(y, ·) is convex, denote ($\ell \circ$ f)(x, y) = $\ell$(y; f(x)). We study the following penalized empirical risk minimization problem $\hat{\lambda}_\varepsilon$ := argmin $\lambda$∈D Pn($\ell \circ$ f$\lambda$) + $\varepsilon$ Z $\lambda$ log $\lambda$d$\mu$ along with its distribution dependent version $\lambda_\varepsilon$ := argmin $\lambda$∈D P($\ell \circ$ f$\lambda$) + $\varepsilon$ Z $\lambda$ log $\lambda$d$\mu$ . We prove that the "approximate sparsity" of $\lambda_\varepsilon$ implies the "approximate sparsity" of $\hat{\lambda}_\varepsilon$ and study connections between the sparsity and the excess risk of empirical solutions $\hat{\lambda}_\varepsilon$.