A unified analysis of convex and non-convex lp-ball projection problems

The task of projecting onto ℓp norm balls is ubiquitous in statistics and machine learning, yet the availability of actionable algorithms for doing so is largely limited to the special cases of p = left 0, 1,2, ∞ right. In this paper, we introduce novel, scalable methods for projecting onto the ℓp ball for general p>0. For p ≥1 , we solve the univariate Lagrangian dual via a dual Newton method. We then carefully design a bisection approach for p<1, presenting theoretical and empirical evidence of zero or a small duality gap in the non-convex case. The success of our contributions is thoroughly assessed empirically, and applied to large-scale regularized multi-task learning and compressed sensing.