Globally-convergent Iteratively Reweighted Least Squares for Robust Regression Problems
This work addresses a foundational problem in machine learning by providing globally convergent methods for robust regression, which is crucial for applications like linear-armed bandits, though it builds incrementally on existing IRLS approaches.
The authors tackled the lack of global convergence guarantees for the iteratively reweighted least squares (IRLS) heuristic in robust regression by proposing augmented routines that ensure global model recovery and outperform state-of-the-art algorithms in practice.
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.