Improved $\ell_{p}$ Regression via Iteratively Reweighted Least Squares
Abstract
We introduce fast algorithms for solving $\ell_{p}$ regression problems using the iteratively reweighted least squares (IRLS) method. Our approach achieves state-of-the-art iteration complexity, outperforming the IRLS algorithm by Adil-Peng-Sachdeva (NeurIPS 2019) and matching the theoretical bounds established by the complex algorithm of Adil-Kyng-Peng-Sachdeva (SODA 2019, J. ACM 2024) via a simpler lightweight iterative scheme. This bridges the existing gap between theoretical and practical algorithms for $\ell_{p}$ regression. Our algorithms depart from prior approaches, using a primal-dual framework, in which the update rule can be naturally derived from an invariant maintained for the dual objective. Empirically, we show that our algorithms significantly outperform both the IRLS algorithm by Adil-Peng-Sachdeva and MATLAB/CVX implementations.
Cite
Text
Ene et al. "Improved $\ell_{p}$ Regression via Iteratively Reweighted Least Squares." International Conference on Learning Representations, 2026.Markdown
[Ene et al. "Improved $\ell_{p}$ Regression via Iteratively Reweighted Least Squares." International Conference on Learning Representations, 2026.](https://mlanthology.org/iclr/2026/ene2026iclr-improved/)BibTeX
@inproceedings{ene2026iclr-improved,
title = {{Improved $\ell_{p}$ Regression via Iteratively Reweighted Least Squares}},
author = {Ene, Alina and Nguyen, Ta Duy and Vladu, Adrian},
booktitle = {International Conference on Learning Representations},
year = {2026},
url = {https://mlanthology.org/iclr/2026/ene2026iclr-improved/}
}