On the Convergence of IRLS and Its Variants in Outlier-Robust Estimation

Liangzu Peng, Christian Kümmerle, René Vidal

Introduction

In computer vision and robotics, outlier-robust estimation is critical for tasks like image stitching and autonomous navigation. While Iteratively Reweighted Least Squares (IRLS) has been a staple for decades, its most efficient variants—particularly those employing Graduated Non-Convexity (GNC)—have often been viewed as fast heuristics rather than mathematically grounded algorithms. This work provides the first rigorous convergence proofs for IRLS combined with GNC, establishing it as a provably correct and highly efficient framework.

Problem Statement

Robust estimation typically involves minimizing non-convex and non-smooth loss functions, such as $\ell_p$-loss or Truncated Least Squares (TLS). These functions present significant optimization challenges, often leading standard tools to stall in local minima. GNC addresses this by solving a sequence of smoothed problems that gradually approach the original objective. However, a general theory explaining the convergence properties and speed of GNC-IRLS has been missing.

Methodology: GNC-IRLS and Majorization

The proposed GNC-IRLS$_p$ algorithm integrates two core concepts:

  1. Two-Level Majorization: Instead of direct optimization of the non-smooth loss, the algorithm employs a "majorizer"—a surrogate function that upper-bounds the target loss and is easier to minimize. As shown in Figure 1, as the smoothing parameter $\epsilon$ approaches zero, the smooth majorizer $\rho_\epsilon(r)$ converges to the original robust loss $\rho(r)$.
  2. Superlinear GNC Schedule: Unlike traditional linear schedules that update smoothing parameters by a constant factor, this work introduces a superlinear schedule. This aggressive update mechanism significantly accelerates convergence.
Figure 1: The smooth majorizer $\rho_\epsilon(r)$ converges to the non-smooth robust loss $\rho(r)$ as the smoothing parameter $\epsilon$ decreases.

Key Insights

  • Theoretical Foundation for Truncation: Truncating small residuals in IRLS is proven to be a valid majorization strategy, ensuring convergence to stationary points rather than being a mere implementation "hack."
  • Convergence Phases: The authors identify a "burn-in" phase where error reduction is minimal while the smoothing parameter is large, followed by a rapid descent once a critical threshold is reached.
  • Quadratic Convergence: For robust regression, GNC-IRLS$_p$ can achieve quadratic convergence when initialized with standard least-squares estimates, effectively doubling the precision of the estimate with each iteration.

Experimental Results

The theory was validated through robust linear regression and point cloud registration tasks. In point cloud registration, the method maintained high accuracy even with 70-80% outliers.

Figure 2: Error decay showing the "burn-in" phase followed by rapid convergence, matching the theoretical bound.

As illustrated in Figure 2, the error follows a predictable decay path. Empirically, the proposed GNC-IRLS variant converged in just 5–10 iterations, a 3x speedup over the previous state-of-the-art GNC-TLS, which typically requires 30 or more iterations.

Conclusion

This research transforms GNC-IRLS from a heuristic into a well-founded optimization framework with provable convergence. By leveraging superlinear schedules and majorization theory, the authors achieve state-of-the-art speed and robustness in fundamental estimation tasks. Future work includes extending these proofs to a wider variety of robust losses and investigating automated threshold scheduling.

Implementation available at: GitHub

Summary updated

Abstract

Outlier-robust estimation involves estimating some parameters (e.g., 3D rotations) from data samples in the presence of outliers, and is typically formulated as a non-convex and non-smooth problem. For this problem, the classical method called iteratively reweighted least-squares (IRLS) and its variants have shown impressive performance. This paper makes several contributions towards understanding why these algorithms work so well. First, we incorporate majorization and graduated non-convexity (GNC) into the IRLS framework and prove that the resulting IRLS variant is a convergent method for outlier-robust estimation. Moreover, in the robust regression context with a constant fraction of outliers, we prove this IRLS variant converges to the ground truth at a global linear and local quadratic rate for a random Gaussian feature matrix with high probability. Experiments corroborate our theory and show that the proposed IRLS variant converges within 5–10 iterations for typical problem instances of outlier-robust estimation, while state-of-the-art methods need at least 30 iterations. A basic implementation of our method is provided: https://github.com/liangzu/IRLS-CVPR2023
BibTeX
@inproceedings{peng2023convergence,
  author = {Liangzu Peng and Christian Kümmerle and René Vidal},
  title = {{On the Convergence of IRLS and Its Variants in Outlier-Robust Estimation}},
  booktitle = {IEEE/CVF Conference on Computer Vision and Pattern Recognition},
  year = {2023},
  doi = {10.1109/cvpr52729.2023.01708},
}
Figure