A unified analysis of convex and non‑convex 𝓛 p ‑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 ∈ { 0 ,   1 ,   2 ,   ∞ } . 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. The code implementing our methods is publicly available on Github.