On the Self-Penalization Phenomenon in Feature Selection

We describe an implicit sparsity-inducing mechanism based on minimization over a family of kernels: beginequation* minβ, f~widehatmathbbE[L(Y, f(β1/q odot X)] + λn |f|Hq2~~subject to~~β ≥ 0, endequation* where L is the loss, odot is coordinate-wise multiplication and Hq is the reproducing kernel Hilbert space based on the kernel kq(x, x') = h(|x-x'|qq), where |·|q is the ℓq norm. Using gradient descent to optimize this objective with respect to β 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., ℓ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.