On the Self-Penalization Phenomenon in Feature Selection

Abstract

We describe an implicit sparsity-inducing mechanism based on minimization over a family of kernels: \begin{equation*} \min_{β, f}~\widehat{\mathbb{E}}[L(Y, f(β^{1/q} \odot X)] + λ_n \|f\|_{\mathcal{H}_q}^2~~\text{subject to}~~β\ge 0, \end{equation*} where $L$ is the loss, $\odot$ is coordinate-wise multiplication and ${\mathcal{H}}_q$ is the reproducing kernel Hilbert space based on the kernel $k_q(x,x^{\prime })=h(\Vert x-x^{\prime }{\Vert }_q^q)$, where $\Vert \cdot {\Vert }_q$ is the ${\ell }_q$ norm. Using gradient descent to optimize this objective with respect to $\beta$ leads to exactly sparse stationary points with high probability. The sparsity is achieved without using any of the well-known explicit sparsification techniques such as penalization (e.g., ${\ell }_1$), early stopping or post-processing (e.g., clipping). As an application, we use this sparsity-inducing mechanism to build algorithms consistent for feature selection.

54 pages

References in corpus (2)

• Margins, Shrinkage, and Boosting
• A Self-Penalizing Objective Function for Scalable Interaction Detection