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

Liangzu Peng, Christian Kümmerle, Renè Vidal

TL;DR

This paper introduces novel variants of Iteratively Reweighted Least Squares (IRLS) for robust $\ell_p$-regression, particularly for non-smooth cases ($p \in (0, 1]$). They provide theoretical guarantees for global linear convergence (for $p=1$) and local superlinear convergence (for $p \in (0,1)$) under a new "stable range space property" assumption, demonstrating superior performance in applications like phase retrieval and face restoration.

What Problem Does This Paper Address?

Robust regression aims to find a model that fits data well, even in the presence of outliers. The $\ell_p$-regression problem, minimizing the $p$-th power of residuals, is a common formulation. While $\ell_2$-regression (least squares) is sensitive to outliers, $\ell_1$-regression (least absolute deviations) is more robust but non-smooth and convex. For $p < 1$, the problem becomes non-convex and even more challenging to solve. Existing methods often struggle with theoretical guarantees for convergence, especially for non-smooth and non-convex $\ell_p$-regression, and can be slow or inaccurate in practice when dealing with many outliers or specific data structures. This paper addresses the need for theoretically sound and practically efficient algorithms for $\ell_p$-regression, particularly for $p \in (0, 1]$, which offers better sparsity-promoting properties than $\ell_1$.

Methods

The core of the paper is the development and analysis of an Iteratively Reweighted Least Squares (IRLS) algorithm, denoted as IRLSp, for solving the $\ell_p$-regression problem. The standard IRLS approach alternates between solving a weighted least-squares problem and updating the weights. The novelty here lies in:

  • Dynamic Smoothing Parameter: Instead of using a fixed small parameter $\epsilon$ (which can lead to approximate solutions), they employ a dynamic update rule for $\epsilon$ (Equation (7)) that adaptively decreases it, ensuring convergence to the true minimizer.
  • Stable Range Space Property (RSP): They introduce and utilize the "stable range space property" (Definition 1) as a key assumption on the feature matrix $A$. This property is shown to be a necessary and sufficient condition for exact recovery of the underlying sparse solution and is demonstrated to hold with high probability for random Gaussian matrices.
  • Theoretical Convergence Guarantees:
    • For $p=1$ (convex case), they prove global linear convergence under the stable RSP. This is significant because many first-order methods for $\ell_1$-regression only achieve sub-linear rates.
  • For $p \in (0, 1)$ (non-convex case), they prove local superlinear convergence (specifically, order $2-p$, which becomes quadratic as $p \to 0$) under the stable RSP, provided the initial guess is sufficiently close to the true solution. This is a novel theoretical result for non-convex $\ell_p$-regression.

Datasets

The paper uses standard datasets for evaluation:

  • Real Phase Retrieval: Synthetic data generated to mimic real-world phase retrieval scenarios.
  • Linear Regression without Correspondences: Synthetic data generated to simulate this specific regression problem.
  • Face Restoration: The Extended Yale B dataset is used for face restoration experiments.

Key Insights and Ideas

  • Bridging Theory and Practice for Non-Smooth $\ell_p$-Regression: The paper provides a strong theoretical foundation (global linear and local superlinear convergence) for IRLS methods applied to $\ell_p$-regression, especially for the challenging non-smooth and non-convex cases ($p < 1$).
  • The Power of Dynamic $\epsilon$: Using a dynamically updated smoothing parameter $\epsilon$ is crucial for achieving exact convergence to the global minimizer, unlike fixed $\epsilon$ methods that only find approximate solutions.
  • Stable Range Space Property as a Key Assumption: This property elegantly connects the structure of the feature matrix to the solvability of the $\ell_p$-regression problem and is shown to be a practical condition for random matrices.
  • Superlinear Convergence for Non-Convex $\ell_p$ is Achievable: The result of local superlinear convergence for $p < 1$ is a significant theoretical advancement, showing that even non-convex problems can be solved efficiently in a neighborhood of the solution.
  • $\ell_p$ for $p<1$ Offers Advantages: The empirical results suggest that using $p < 1$ can lead to better accuracy and faster convergence than $\ell_1$ in certain robust regression scenarios, particularly when dealing with structured noise or specific problem formulations like phase retrieval.

Key Results

  • Theoretical Guarantees:
    • Global Linear Convergence: IRLSp for $p=1$ converges linearly to the true solution from any initialization, under the stable RSP.
  • Local Superlinear Convergence: IRLSp for $p \in (0, 1)$ converges at a rate of order $2-p$ (quadratic for $p=0$) to the true solution, provided the initial guess is within a specific neighborhood.
  • Empirical Performance:
    • Real Phase Retrieval: IRLS with $p=0.1$ recovers the solution with $m=2n-1$ measurements, outperforming other state-of-the-art methods that fail in this extreme case.
  • Linear Regression without Correspondences: IRLS0.1 is shown to be significantly more accurate and faster (20-100x) than competing solvers like PDLP and Gurobi.
  • Face Restoration: IRLS0.1 demonstrates robustness to sparse corruptions (salt-and-pepper noise), providing better restoration quality than standard least-squares methods.
  • Error Decay: Experiments confirm the predicted linear decay for $p=1$ and superlinear decay for $p < 1$, with faster convergence as $p$ decreases.

Limitations and Future Work

  • Assumptions: The theoretical results rely on the "stable range space property." While shown to hold for random Gaussian matrices, exploring weaker assumptions (e.g., sub-Gaussian distributions) is a future direction.
  • Constant Factors: The convergence rates have constant factors that might be conservative. Improving these constants and understanding their dependence on parameters like $m$ is an open question.
  • Global Convergence for $p < 1$: While local superlinear convergence is proven for $p < 1$, proving global convergence rates for this non-convex case remains an open challenge.
  • Inexact Solvers: Investigating the use of inexact solvers for the inner weighted least-squares problem could further accelerate the IRLS algorithm.
  • Broader Applications: The authors suggest that IRLSp could be valuable for other outlier-robust estimation tasks beyond regression.
  • Balanced Data in Phase Retrieval: Handling cases with balanced inliers and outliers in real phase retrieval with minimum samples is identified as a future research direction.

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 \textit{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. https://github.com/liangzu/IRLS-NeurIPS2022
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