Fast, Provably convergent IRLS Algorithm for p-norm Linear Regression

Deeksha Adil, Richard Peng, Sushant Sachdeva

This paper, presented at NeurIPS 2019, tackles a long-standing challenge in optimization: making a simple, classic algorithm both fast and mathematically "guaranteed" for a broad class of regression problems.

TL;DR

The authors introduce $p$-IRLS, the first Iteratively Reweighted Least Squares algorithm that is provably guaranteed to converge geometrically for any $\ell_p$-norm linear regression where $p \ge 2$. By adding simple padding and a line search to the classic IRLS framework, they achieved 10–50x speedups over standard solvers like CVX while solving a 30-year-old open problem in numerical optimization.

What Problem Does This Paper Address?

Linear regression is usually associated with the $\ell_2$-norm (least squares), but many modern applications—like sparse recovery, signal processing, and semi-supervised learning (SSL)—require the $\ell_p$-norm. For example, in graph-based SSL, using a large $p$ (the "$p$-Laplacian") helps prevent "degeneracy," where labels don't propagate correctly across a graph.

However, solving $\ell_p$-regression for $p > 2$ is difficult. Standard gradient descent is sluggish because the gradient vanishes near the optimum. Interior-point methods (the "gold standard" for convex optimization) are robust but very slow for large-scale problems.

For over 50 years, researchers have used Iteratively Reweighted Least Squares (IRLS). It’s popular because it’s easy to code: it simply solves a sequence of weighted least squares problems. The catch? Since the mid-1980s, it’s been known that standard IRLS often diverges or becomes unstable when $p > 3$. Finding a version of IRLS that is guaranteed to be fast for large $p$ has been an open problem for decades.

Methods

The authors propose two critical modifications to the standard IRLS iterate to ensure stability and speed:

  1. Systematic Padding: They add a small diagonal "padding" matrix ($sI$) to the weights in each iteration. This prevents the weight matrix from becoming ill-conditioned (singular) when the residuals of the regression approach zero.
  2. Line Search: Instead of jumping directly to the solution of the weighted least squares problem, the algorithm treats that solution as a direction. It then performs a line search to find the optimal step size along that path.
  3. The "Residual Problem" Framework: They use a novel theoretical framework to check progress at each step. If the objective doesn't decrease enough, the algorithm automatically adjusts the padding ($s$) to ensure the next step is productive.

Mathematically, they prove that this algorithm achieves geometric convergence. This means the error decreases by a constant factor in each step, leading to a total iteration count that depends only logarithmically on the desired accuracy ($\log 1/\epsilon$).

Datasets

The authors evaluated $p$-IRLS on two types of problems:

  • Random Dense Matrices: Synthetic $\ell_p$-regression instances of various sizes (up to $1000 \times 850$) to test raw optimization performance.
  • Graph-based Semi-Supervised Learning: They used low-dimensional nearest-neighbor graphs (1000 nodes, ~5000 edges) to solve $p$-Laplacian problems, which are common in data clustering and label propagation.

Key Insights and Ideas

  • Simplicity is Powerful: The core of the algorithm remains a weighted least squares solver. This means it can leverage highly optimized linear algebra libraries (like Matlab's backslash operator), making it much faster in practice than complex interior-point machinery.
  • Bridging Theory and Practice: While the theoretical proof requires a specific "progress check," the authors found that in practice, the algorithm is incredibly stable even with simpler implementations.
  • The "m" Factor: Theoretically, the number of iterations scales with the number of rows in the matrix ($m$). However, the experiments revealed a surprising "aha moment": the iteration count stays almost constant regardless of problem size, suggesting the algorithm is even more efficient than the current theory can prove.
Performance of p-IRLS across varying error tolerances, problem sizes, and p values.

Key Results

  • Massive Speedups: $p$-IRLS outperformed the standard Matlab/CVX solver by 10x to 50x.
  • High Precision: In the "high-accuracy" regime (where you need an error of $10^{-8}$ or smaller), $p$-IRLS is significantly faster than heuristic "homotopy" methods, which often struggle to reach high precision for large $p$.
Error comparison between IRLS and Newton with Homotopy as parameter p increases.
  • Robustness to $p$: Even for very large values (like $p=50$), the algorithm converged in just 60–80 iterations on a standard desktop.

Limitations and Future Work

  • Acceleration: The current algorithm is fast, but it is not "accelerated" in the sense of Nesterov’s momentum. The authors suggest that incorporating acceleration could further improve the theoretical iteration bounds.
  • The $p < 2$ Regime: This paper focuses on $p \ge 2$. While IRLS is also used for $p < 2$ (like $\ell_1$ minimization for sparsity), the specific proofs and padding strategies used here would need to be adapted for that regime.
  • Theoretical Gap: There is still a gap between the "worst-case" theoretical complexity and the much faster performance seen in real-world experiments. Closing this gap remains an open challenge for theorists.

Summary updated

Abstract

Linear regression in L<em>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 L</em>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 &gt; 3, and since the work of Osborne (1985), it has been an open problem whether there is an IRLS algorithm that converges for p &gt; 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 high accuracy solution in a sub-linear number of 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.
BibTeX
@inproceedings{adil2019fast,
  author = {Deeksha Adil and Richard Peng and Sushant Sachdeva},
  title = {{Fast, Provably convergent IRLS Algorithm for p-norm Linear Regression}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2019},
  url = {https://openreview.net/forum?id=NanU0ry17ax},
}

Loading related content...

Figure