# Globally-convergent Iteratively Reweighted Least Squares for Robust Regression Problems

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

## Key facts

- Cited by 15 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 25 Jun 2020.

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

- [Robust and Differentially Private Mean Estimation](https://mlsanity.com/paper/2102.09159/) (2021)
- [On Tilted Losses in Machine Learning: Theory and Applications](https://mlsanity.com/paper/2109.06141/) (2021)
- [Efficient List-Decodable Regression using Batches](https://mlsanity.com/paper/2211.12743/) (2022)
- [Imbalanced Mixed Linear Regression](https://mlsanity.com/paper/2301.12559/) (2023)
- [Near Optimal Heteroscedastic Regression with Symbiotic Learning](https://mlsanity.com/paper/2306.14288/) (2023)
- [Linear Regression using Heterogeneous Data Batches](https://mlsanity.com/paper/2309.01973/) (2023)
- [Recovering Simultaneously Structured Data via Non-Convex Iteratively Reweighted Least Squares](https://mlsanity.com/paper/2306.04961/) (2023)
- [AGGLIO: Global Optimization for Locally Convex Functions](https://mlsanity.com/paper/2111.03932/) (2021)
- [Corruption-tolerant Algorithms for Generalized Linear Models](https://mlsanity.com/paper/2212.05430/) (2022)
- [Iterative thresholding for non-linear learning in the strong varepsilon-contamination model](https://mlsanity.com/paper/2409.03703/) (2024)
- [A Smoothing Newton Method for Rank-one Matrix Recovery](https://mlsanity.com/paper/2507.23017/) (2025)
- [Language-guided Recursive Spatiotemporal Graph Modeling for Video Summarization](https://mlsanity.com/paper/2509.05604/) (2025)
- [Interlaced dynamic XCT reconstruction with spatio-temporal implicit neural representations](https://mlsanity.com/paper/2510.08641/) (2025)
- [Provably Outlier-resistant Semi-parametric Regression for Transferable Calibration of Low-cost Air-quality Sensors](https://mlsanity.com/paper/2511.19810/) (2025)
- [Outlier-robust Autocovariance Least Square Estimation via Iteratively Reweighted Least Square](https://mlsanity.com/paper/2603.08158/) (2026)

## Abstract (arXiv)

We provide the first global model recovery results for the IRLS (iteratively reweighted least squares) heuristic for robust regression problems. IRLS is known to offer excellent performance, despite bad initializations and data corruption, for several parameter estimation problems. Existing analyses of IRLS frequently require careful initialization, thus offering only local convergence guarantees. We remedy this by proposing augmentations to the basic IRLS routine that not only offer guaranteed global recovery, but in practice also outperform state-of-the-art algorithms for robust regression. Our routines are more immune to hyperparameter misspecification in basic regression tasks, as well as applied tasks such as linear-armed bandit problems. Our theoretical analyses rely on a novel extension of the notions of strong convexity and smoothness to weighted strong convexity and smoothness, and establishing that sub-Gaussian designs offer bounded weighted condition numbers. These notions may be useful in analyzing other algorithms as well.