Sparse Prediction with the k-Support Norm

We derive a novel norm that corresponds to the tightest convex relaxation of sparsity combined with an ℓ2 penalty. We show that this new norm provides a tighter relaxation than the elastic net, and is