  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.
