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