Global Linear and Local Superlinear Convergence of IRLS for Non-Smooth Robust Regression

Liangzu Peng, Christian Kümmerle, René Vidal

TL;DR

This paper breathes new life into Iteratively Reweighted Least Squares (IRLS), a classic optimization algorithm, by providing the first strong convergence guarantees for non-smooth robust regression. The authors prove that a specific IRLS variant converges globally at a linear rate for $p=1$ and locally at a superlinear rate for $p < 1$, outperforming state-of-the-art commercial solvers in both speed and outlier resilience.

Introduction: The Challenge of Robust Regression

In the world of data science, "robustness" usually means an algorithm won't break when the data is messy. Standard linear regression (least squares) is notoriously fragile; a single massive outlier can pull the entire model off track. To fix this, researchers use $\ell_p$-regression, where $p \leq 1$.

When $p=1$, the problem is convex but non-smooth (it has "kinks" that make standard calculus-based optimization difficult). When $p < 1$, the problem becomes non-convex and technically NP-hard, but it is even better at ignoring outliers. The challenge has been finding an algorithm that is both computationally efficient and theoretically guaranteed to find the right answer. While IRLS has been a popular heuristic for decades, its theoretical properties in this specific "robust regression" context remained surprisingly murky—until now.

Methods: A Dynamic Approach to IRLS

The authors focus on a variant called $\text{IRLS}_p$. The core idea of IRLS is to turn a difficult problem into a sequence of easy ones: it solves a series of weighted least squares problems, where the weights are updated at each step to down-weight the influence of large residuals (the outliers).

The "secret sauce" in this paper is the dynamic smoothing parameter ($\epsilon$).

  • The Old Way: Most IRLS implementations use a fixed, small $\epsilon$ to avoid dividing by zero. This limits accuracy because the algorithm only converges to an "approximate" neighborhood of the solution.
  • The New Way: The authors use a dynamic update rule for $\epsilon$ that shrinks toward zero as the algorithm progresses. This allows the algorithm to converge exactly to the global minimizer.
Convergence comparison of IRLS with dynamic vs. fixed smoothing parameters.

To prove this works, they rely on a condition called the Stable Range Space Property (RSP). This is a mathematical requirement on the feature matrix that essentially ensures the "good" data points provide enough signal to overcome the "bad" outliers.

Datasets and Evaluation

The paper validates the algorithm using:

  1. Synthetic Gaussian Data: Used to rigorously test convergence rates and sensitivity to the sparsity level ($k$).
  2. Extended Yale B Dataset: A standard computer vision benchmark containing face images of 38 individuals under various lighting conditions. This was used for the "Face Restoration" task, where images were intentionally corrupted with "salt and pepper" noise.

Key Insights

  • Bridging Two Fields: The authors successfully "transferred" theoretical insights from the field of Compressed Sensing (specifically basis pursuit) to the field of Robust Regression.
  • The Power of $p < 1$: One of the most striking "aha moments" is the proof of superlinear convergence for the non-convex case ($p < 1$). As $p$ gets closer to 0, the convergence rate approaches quadratic. In plain English: the more non-convex the objective, the faster the algorithm zooms in on the solution once it's in the right neighborhood.
  • Deterministic Guarantees: Unlike many modern papers that rely on purely probabilistic arguments, this work provides deterministic conditions (the RSP) under which the algorithm is guaranteed to succeed.

Key Results

  • Speed: In "regression without correspondences" tasks, $\text{IRLS}_{0.1}$ was 30x faster than the commercial Gurobi solver and 100x faster than Google’s PDLP solver.
Performance comparison showing IRLS outperforming Gurobi and PDLP solvers.
  • Outlier Handling: In phase retrieval experiments, $\text{IRLS}_{0.1}$ succeeded with the theoretical minimum number of samples ($m = 2n - 1$), while other state-of-the-art methods like Kaczmarz or Wirtinger Flow failed.
  • Face Restoration: The algorithm successfully restored face images heavily corrupted by sparse noise, producing visually faithful results where standard least squares simply produced a blurry average of the noise and the signal.

Limitations and Future Work

While the theory is a major step forward, there are a few caveats:

  • Conservative Constants: The theoretical convergence constant (1/294) is quite conservative. In practice, the algorithm often performs much better than the theory predicts.
  • Initialization for $p < 1$: The superlinear convergence for the non-convex case is local. You need a decent starting point to guarantee that "fast" finish. The authors suggest running $\text{IRLS}_1$ (which has global guarantees) first to get close, then switching to $\text{IRLS}_p$ to cross the finish line.
  • Computational Scaling: The current analysis shows a linear dependency on the number of samples ($m$). The authors conjecture this could be improved to $\sqrt{m} \log m$ in future work.
  • Inexact Solvers: Currently, each step requires solving a linear system exactly. Integrating "inexact" solvers (like Conjugate Gradient) could make the algorithm even faster for massive datasets.

Summary updated

Abstract

We advance both the theory and practice of robust $\ell_p$-quasinorm regression for $p \in (0,1]$ by using novel variants of iteratively reweighted least-squares (IRLS) to solve the underlying non-smooth problem. In the convex case, $p=1$, we prove that this IRLS variant converges globally at a linear rate under a mild, deterministic condition on the feature matrix called the stable range space property. In the non-convex case, $p\in(0,1)$, we prove that under a similar condition, IRLS converges locally to the global minimizer at a superlinear rate of order $2-p$; the rate becomes quadratic as $p\to 0$. We showcase the proposed methods in three applications: real phase retrieval, regression without correspondences, and robust face restoration. The results show that (1) IRLS can handle a larger number of outliers than other methods, (2) it is faster than competing methods at the same level of accuracy, (3) it restores a sparsely corrupted face image with satisfactory visual quality.
BibTeX
@inproceedings{peng2022global,
  author = {Liangzu Peng and Christian Kümmerle and René Vidal},
  title = {{Global Linear and Local Superlinear Convergence of IRLS for Non-Smooth Robust Regression}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2022},
  url = {https://openreview.net/forum?id=4i5gbFDgEc},
}
Figure