# Iterative Refinement for ℓp-norm Regression

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

## Key facts

- Cited by 6 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 21 Jan 2019.

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

- [Private Convex Optimization in General Norms](https://mlsanity.com/paper/2207.08347/) (2022)
- [Complementary Composite Minimization, Small Gradients in General Norms, and Applications](https://mlsanity.com/paper/2101.11041/) (2021)
- [The Complexity of Dynamic Least-Squares Regression](https://mlsanity.com/paper/2201.00228/) (2022)
- [Optimal Excess Risk Bounds for Empirical Risk Minimization on p-Norm Linear Regression](https://mlsanity.com/paper/2310.12437/) (2023)
- [Optimal Algorithms for Stochastic Complementary Composite Minimization](https://mlsanity.com/paper/2211.01758/) (2022)
- [Sharper Bounds for ℓp Sensitivity Sampling](https://mlsanity.com/paper/2306.00732/) (2023)

## Abstract (arXiv)

We give improved algorithms for the ℓp-regression problem, minx |x|p such that A x=b, for all p ∈ (1,2) cup (2,∞). Our algorithms obtain a high accuracy solution in tildeOp(m^frac|p-2|2p + |p-2|) ≤ tildeOp(m^frac13) iterations, where each iteration requires solving an m × m linear system, m being the dimension of the ambient space. By maintaining an approximate inverse of the linear systems that we solve in each iteration, we give algorithms for solving ℓp-regression to 1 / poly(n) accuracy that run in time tildeOp(m^maxω, 7/3), where ω is the matrix multiplication constant. For the current best value of ω > 2.37, we can thus solve ℓp regression as fast as ℓ2 regression, for all constant p bounded away from 1. Our algorithms can be combined with fast graph Laplacian linear equation solvers to give minimum ℓp-norm flow / voltage solutions to 1 / poly(n) accuracy on an undirected graph with m edges in tildeOp(m^1 + frac|p-2|2p + |p-2|) ≤ tildeOp(m^frac43) time. For sparse graphs and for matrices with similar dimensions, our iteration counts and running times improve on the p-norm regression algorithm by [Bubeck-Cohen-Lee-Li STOC`18] and general-purpose convex optimization algorithms. At the core of our algorithms is an iterative refinement scheme for ℓp-norms, using the smoothed ℓp-norms introduced in the work of Bubeck et al. Given an initial solution, we construct a problem that seeks to minimize a quadratically-smoothed ℓp norm over a subspace, such that a crude solution to this problem allows us to improve the initial solution by a constant factor, leading to algorithms with fast convergence.