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 \( {x} = min _{ {A} {x}= {b}} {x} _p^p\) , where \( {x}∈ R^n, {A}∈ Rd× n, {b}∈ R^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)· n1/2-1/p\) linear system solves for \(p≥ 2\) . In this article, 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^{ {(p-2)}{(3p-2)}})\) linear system solves. We further propose a new inverse maintenance procedure that speeds-up our algorithm to \({O}(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–50×.