Sparse Prediction with the $k$-Support Norm

Abstract

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.

Cited by in corpus (21)

• Fixed Point Strategies in Data Science
• Oracle Based Active Set Algorithm for Scalable Elastic Net Subspace Clustering
• PySAP: Python Sparse Data Analysis Package for Multidisciplinary Image Processing
• Variable Selection and Task Grouping for Multi-Task Learning
• Estimating Structured Vector Autoregressive Model
• Sparsity Constrained Minimization via Mathematical Programming with Equilibrium Constraints
• An Inequality with Applications to Structured Sparsity and Multitask Dictionary Learning
• Hidden Convexity in the l0 Pseudonorm
• Unified View of Matrix Completion under General Structural Constraints
• Streaming Symmetric Norms via Measure Concentration
• Structured Matrix Recovery via the Generalized Dantzig Selector
• Compression of Deep Convolutional Neural Networks under Joint Sparsity Constraints
• Finding the largest low-rank clusters with Ky Fan $2$-$k$-norm and ${\ell }_1$-norm
• Approximate Near Neighbors for General Symmetric Norms
• Orthant-Strictly Monotonic Norms, Generalized Top-k and k-Support Norms and the L0 Pseudonorm
• Efficient Proximal Mapping Computation for Unitarily Invariant Low-Rank Inducing Norms
• The Nonconvex Geometry of Linear Inverse Problems
• Fitting Spectral Decay with the $k$-Support Norm
• Learning with Optimal Interpolation Norms
• Regularized Loss Minimizers with Local Data Perturbation: Consistency and Data Irrecoverability
• Convexification of Permutation-Invariant Sets and an Application to Sparse PCA