A unified analysis of convex and non‑convex 𝓛p‑ball projection problems

Abstract

The task of projecting onto ${\ell }_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\in \text{{}0\text{,}1\text{,}2\text{,}\infty \text{}}$. In this paper, we introduce novel, scalable methods for projecting onto the ${\ell }_p$-ball for general $p>0$. For $p\ge 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.

Keywords: Compressed sensing; Large-scale optimization; Multitask learning; Projected gradient; Proximal operator; 𝓛p-norm ball.