  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 = \left\{ 0, 1,2, \infty
\right\}$. In this paper, we introduce novel, scalable methods for projecting
onto the $\ell_p$ ball for general $p>0$. For $p \geq1 $, 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.
