Sparse Prediction with the $k$-Support Norm

Andreas Argyriou, Rina Foygel, Nathan Srebro

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 tig…