Sparsity by Worst-Case Quadratic Penalties

This paper proposes a new robust regression interpretation of sparse penalties such as the elastic net and the group-lasso. Beyond providing a new viewpoint on these penalization schemes, our approach results in a unified optimization strategy. Our evaluation experiments demonstrate that this strategy, implemented on the elastic net, is computationally extremely efficient for small to medium size problems. Our accompanying software solves problems at machine precision in the time required to get a rough estimate with competing state-of-the-art algorithms.