Sparse Prediction with the $k$-Support Norm
This work addresses sparse prediction for machine learning practitioners, offering an incremental improvement over existing methods like the elastic net.
The paper tackles the problem of sparse prediction by deriving the $k$-support norm, a tighter convex relaxation than the elastic net, and shows it can replace Lasso or elastic net in such problems, while also bounding the looseness of the elastic net to justify its use.
We derive a novel norm that corresponds to the tightest convex relaxation of sparsity combined with an $\ell_2$ penalty. We show that this new {\em $k$-support norm} provides a tighter relaxation than the elastic net and is thus a good replacement for the Lasso or the elastic net in sparse prediction problems. Through the study of the $k$-support norm, we also bound the looseness of the elastic net, thus shedding new light on it and providing justification for its use.