Abstract
Linear regression in $\ell_p$-norm is a canonical optimization problem that arises in several applications, including sparse recovery, semi-supervised learning, and signal processing. Generic convex optimization algorithms for solving $\ell_p$-regression are slow in practice. Iteratively Reweighted Least Squares (IRLS) is an easy to implement family of algorithms for solving these problems that has been studied for over 50 years. However, these algorithms often diverge for $p > 3$, and since the work of Osborne (1985), it has been an open problem whether there is an IRLS algorithm that is guaranteed to converge rapidly for $p > 3$. We propose $p$-IRLS, the first IRLS algorithm that provably converges geometrically for any $p \in [2,\infty).$ Our algorithm is simple to implement and is guaranteed to find a $(1+\varepsilon)$-approximate solution in $O(p^{3.5} m^{\frac{p-2}{2(p-1)}} \log \frac{m}{\varepsilon}) \le O_p(\sqrt{m} \log \frac{m}{\varepsilon} )$ iterations. Our experiments demonstrate that it performs even better than our theoretical bounds, beats the standard Matlab/CVX implementation for solving these problems by 10--50x, and is the fastest among available implementations in the high-accuracy regime.
Introduction
Linear regression is a fundamental tool in data science, typically solved using the $L_2$ norm (least squares). However, many modern applications—such as sparse recovery, signal processing, and semi-supervised learning (SSL)—require minimizing the $p$-norm: $\min \|Ax - b\|_p$.
While $L_2$ problems are computationally straightforward, $p$-norms for $p > 2$ present significant challenges. As $p$ increases, the gradient of the objective function vanishes rapidly near the optimum, causing first-order methods like gradient descent to converge extremely slowly. For decades, practitioners have favored Iteratively Reweighted Least Squares (IRLS) for its simplicity: it transforms a complex $p$-norm problem into a sequence of standard weighted $L_2$ problems.
Despite its popularity, standard IRLS is notoriously unstable and often diverges when $p > 3$. Since 1985, a major open question in the field has been whether an IRLS variant exists that can guarantee fast convergence for large $p$.
The $p$-IRLS Algorithm
The authors introduce $p$-IRLS, a refined version of the classic algorithm designed to overcome historical instability. A standard IRLS step calculates a weight matrix $R$ based on current residuals and solves the resulting linear system. $p$-IRLS incorporates three critical modifications:
- Weight Padding: A small, systematic identity term ($sI$) is added to the weight matrix $R$. This prevents the matrix from becoming ill-conditioned, a primary cause of divergence in traditional IRLS.
- Line Search: Rather than taking a full step to the next "ideal" point, the algorithm employs a line search to determine the optimal step size along the descent direction.
- Progress Check: An internal monitoring mechanism adaptively adjusts the padding parameter if the algorithm fails to make sufficient progress.
By analyzing the problem through a "Residual Problem" framework, the authors prove that $p$-IRLS achieves geometric convergence. This means the number of iterations required scales with $\log(1/\epsilon)$, a significant improvement over the $1/\epsilon$ scaling of many alternative methods.
Experimental Evaluation
The performance of $p$-IRLS was evaluated on two distinct problem types: random dense matrices and $p$-Laplacian graphs used for semi-supervised learning.
Key Results
- Superior Speed: $p$-IRLS is 10–50x faster than standard Interior Point methods (e.g., Matlab/CVX).
- High Accuracy: In high-accuracy regimes, $p$-IRLS is the fastest available implementation. For large $p$ (e.g., $p=50$), it maintains high precision where competing IRLS-homotopy methods fail.
- Scalability: While theoretical complexity suggests a dependence on the number of rows $m$, experiments show iteration counts remain nearly constant regardless of problem size and grow only slowly with $p$.
Discussion and Future Work
$p$-IRLS successfully bridges the gap between the practical simplicity of IRLS and the theoretical rigor required for guaranteed convergence. It acts as a "locally greedy" solver, often taking much larger steps in practice than the conservative theoretical bounds suggest.
However, some challenges remain. A gap exists between the theoretical worst-case iteration bound (dependent on $m$) and the observed empirical performance (independent of $m$). Future work may explore "acceleration" techniques to further optimize theoretical bounds for $L_1$ or $L_\infty$ regression. Additionally, refining the analysis for the "very large $p$" regime could yield even tighter performance guarantees.
Summary updated