Fast Algorithms for ℓp-Regression

The ℓp-norm regression problem is a classic problem in optimization with wide ranging applications in machine learning and theoretical computer science. The goal is to compute xstar =argminAx=b|x|pp, where xstar∈ ℝn, A∈ ℝd× n,b ∈ ℝd and d≤ n. Efficient high-accuracy algorithms for the problem have been challenging both in theory and practice and the state of the art algorithms require poly(p)· n^frac12-frac1p linear system solves for p≥ 2. In this paper, we provide new algorithms for ℓp-regression (and a more general formulation of the problem) that obtain a high-accuracy solution in O(p n^frac(p-2)(3p-2)) linear system solves. We further propose a new inverse maintenance procedure that speeds-up our algorithm to widetildeO(nω) total runtime, where O(nω) denotes the running time for multiplying n × n matrices. Additionally, we give the first Iteratively Reweighted Least Squares (IRLS) algorithm that is guaranteed to converge to an optimum in a few iterations. Our IRLS algorithm has shown exceptional practical performance, beating the currently available implementations in MATLAB/CVX by 10-50x.