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.

该研究提出了对 IRLS 鲁棒回归问题的全球模型恢复结果，建议加强基本 IRLS 例程，提供全球恢复的保证，可更好地抵御基本回归任务和应用任务的超参数错误，使用加权强凸和平稳性的新概念来理论分析。