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:
- 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.
- 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.
- 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.
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$.
- 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