Overview
This paper provides a theoretical breakthrough for a classic numerical technique: Iteratively Reweighted Least Squares (IRLS). The authors propose a simple, natural version of IRLS for $\ell_1$ and $\ell_\infty$ regression that achieves a significantly faster, provable convergence rate. Notably, it features a term that is sublinear in the accuracy parameter ($1/\epsilon$), a rare and highly desirable property for non-smooth optimization.
The Gap Between Practice and Theory
Regression problems, specifically $\ell_1$ (minimizing the sum of absolute errors) and $\ell_\infty$ (minimizing the maximum error), are workhorses of scientific computing and signal processing. While they can be solved via standard Linear Programming, practitioners often prefer Iteratively Reweighted Least Squares (IRLS). IRLS is remarkably easy to implement, as it simply solves a sequence of weighted quadratic (least squares) problems.
However, a massive gap has historically existed between practice and theory. While IRLS works well in the real world, previous theoretical analyses either required perfect initialization, were highly sensitive to how "well-conditioned" the input data was, or had extremely slow convergence rates that depended heavily on the desired accuracy ($\epsilon$). This paper bridges that gap, providing an IRLS variant that is both simple and theoretically fast, regardless of the input's conditioning.
A New Approach to IRLS
The authors introduce a version of IRLS that uses a thresholding rule to update weights, moving away from traditional smooth weight updates.
- Electrical Network Analogy: The algorithm views the optimization through the lens of electrical flow. Minimizing the weighted least squares objective is equivalent to finding the flow that minimizes "electrical energy" in a network where the weights represent resistances (for $\ell_\infty$) or conductances (for $\ell_1$).
- Thresholded Updates: The algorithm checks if a specific coordinate's contribution to the total energy exceeds a certain threshold. If it does, the weight for that coordinate is scaled up.
- Potential Function Tracking: Unlike previous algorithms that combined multiple complex techniques (like multiplicative weights plus regularization), this method tracks a single potential function to prove convergence.
Key Insights and Theoretical Wins
The proposed method yields several major theoretical insights:
- Sublinear Convergence: The dominant term in the iteration count is $O(\epsilon^{-2/3})$. In the world of non-smooth optimization, dependencies are usually $O(\epsilon^{-1})$ or $O(\epsilon^{-2})$. Achieving sublinear dependency in $1/\epsilon$ is a massive theoretical win. Overall, the algorithms find a $(1+\epsilon)$-approximate solution in $\tilde{O}(m^{1/3} \epsilon^{-2/3} + \epsilon^{-2})$ iterations.
- Conditioning Independence: The running time does not depend on the "condition number" of the input matrix. This makes the algorithm robust for messy real-world data where traditional solvers might struggle.
- The "Slime Mold" Connection: The paper provides a rigorous theoretical justification for "Physarum dynamics." Biologists observed that the slime mold Physarum polycephalum can solve shortest-path problems in mazes; computer scientists later realized these dynamics are essentially a form of IRLS. This paper proves that these natural dynamics are actually highly efficient.
Empirical Performance
The authors evaluated their algorithms using synthetic datasets, varying the accuracy parameter $\epsilon$ and the problem dimension $m$.
In experiments, the number of iterations scaled even better than the $m^{1/3}$ theoretical bound, suggesting the algorithm might be even more powerful in practice than the proof guarantees. Furthermore, while the theory uses "short steps" for the proof, the authors found that a "long-step" strategy (doubling the step length as long as certain invariants hold) works even better empirically.
Limitations and Future Work
While a significant step forward, the approach has a few limitations:
- Decision vs. Optimization: The core algorithms are designed to solve a "decision problem" (e.g., is the objective value $\le M$?). To find the actual minimum, one must wrap the algorithm in an outer loop (like a binary search for $M$), which adds a small logarithmic overhead.
- Linear System Overhead: Each iteration requires solving a linear system ($ADA^\top x = b$). While efficient solvers exist, this remains the primary computational bottleneck per iteration.
Improving the $\epsilon$ dependence further, specifically for positive linear programs, remains an important open question in the field.
Summary updated