# Fast Algorithms for ℓp-Regression

arXiv: https://arxiv.org/abs/2211.03963 · HTML: https://mlsanity.com/paper/2211.03963/

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 8 Nov 2022.

## Built on by (most cited first, 4 of 4)

- [Minimax Linear Regression under the Quantile Risk](https://mlsanity.com/paper/2406.12145/) (2024)
- [Optimal Excess Risk Bounds for Empirical Risk Minimization on p-Norm Linear Regression](https://mlsanity.com/paper/2310.12437/) (2023)
- [Guessing Efficiently for Constrained Subspace Approximation](https://mlsanity.com/paper/2504.20883/) (2025)
- [Planner-Admissible Graph-PDE Value Extensions for Sparse Goal-Conditioned Planning](https://mlsanity.com/paper/2605.19185/) (2026)

## Abstract (arXiv)

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.