Iterative Refinement for ℓp-norm Regression

Deeksha Adil, Rasmus Kyng, Richard Peng, Sushant SachdevaSODA 2019 · arXiv · OpenReview

TL;DR

This paper introduces a new iterative refinement algorithm for $\ell_p$-norm regression that achieves significantly faster convergence, especially for high accuracy solutions. The method achieves near-optimal iteration counts and, by incorporating inverse maintenance, can solve $\ell_p$-norm regression problems as fast as $\ell_2$-norm regression for many values of $p$.

What Problem Does This Paper Address?

The paper tackles the $\ell_p$-norm regression problem: minimizing $\|x\|_p$ subject to $Ax = b$. This is a fundamental problem in optimization and machine learning, with $\ell_2$-norm regression being equivalent to solving a linear system and $\ell_1$ and $\ell_\infty$ norms being related to linear programming. However, for general $p$, obtaining high-accuracy solutions has historically been computationally expensive, with iteration counts scaling poorly with the problem size and desired accuracy. Existing methods often require a large number of iterations, each involving solving a linear system, or offer only approximate solutions in polynomial time. This paper aims to bridge this gap by providing algorithms that achieve geometric convergence and significantly improve upon existing iteration counts and running times, particularly for high-accuracy solutions.

Methods

The core of the paper's contribution lies in an iterative refinement scheme for $\ell_p$-norms. This scheme leverages quadratically-smoothed $\ell_p$-norms, introduced by Bubeck et al., to construct a sequence of "residual problems." The key idea is that solving these smoothed problems to a crude accuracy allows for a constant factor improvement of the current solution to the original problem. This iterative process leads to geometric convergence.

To further accelerate the process, the authors incorporate a technique for maintaining an approximate inverse of the linear systems that arise during the iterations. This "inverse maintenance" speeds up the solution of these systems, leading to overall faster running times. The algorithms are also adapted to leverage fast solvers for graph Laplacians, enabling efficient solutions for related graph problems like $\ell_p$-norm flows.

Datasets

Not discussed in the paper.

Key Insights and Ideas

  • Iterative Refinement for $\ell_p$-norms: The core insight is that by solving a sequence of "easier" smoothed $\ell_p$-norm problems, one can iteratively refine an initial solution to achieve high accuracy in the original problem. This is a departure from methods that directly aim for high accuracy in a single pass.
  • Bridging the Gap between $\ell_2$ and General $\ell_p$: The paper demonstrates that for many $p$, $\ell_p$-norm regression can be solved as efficiently as $\ell_2$-norm regression (which is equivalent to solving linear systems), especially when using state-of-the-art matrix multiplication algorithms. This is a significant theoretical advancement.
  • The Power of Smoothed Norms: Using quadratically-smoothed $\ell_p$-norms as intermediate problems is crucial. It allows for local approximations that are amenable to iterative refinement, effectively turning a difficult non-linear problem into a sequence of more manageable subproblems.
  • Inverse Maintenance for Speed: Applying inverse maintenance techniques, typically used for linear systems, to the iterative refinement framework for $\ell_p$-norms is a key algorithmic innovation that leads to improved overall time complexity.

Key Results

  • Improved Iteration Counts: The algorithms achieve iteration counts of $\tilde{O}_p(m^{\frac{|p-2|}{2p+|p-2|}})$, which is bounded by $\tilde{O}_p(m^{1/3})$. This is a significant improvement over previous methods, especially for high accuracy.
  • Near $\ell_2$ Regression Time: By incorporating inverse maintenance and using fast matrix multiplication (with exponent $\omega$), the algorithms achieve a total running time of $\tilde{O}_p(m^{\max\{\omega, 7/3\}})$. For the current best $\omega \approx 2.37$, this means $\ell_p$-norm regression can be solved as fast as $\ell_2$-norm regression for constant $p$ bounded away from 1.
  • Efficient Graph Algorithms: The methods are extended to solve $\ell_p$-norm flow and voltage problems on graphs in $\tilde{O}_p(m^{4/3})$ time, improving upon prior results.
  • Generalization: The techniques can be applied to solve a broader class of $\ell_p$-norm optimization problems with affine constraints.

Limitations and Future Work

  • Constant $p$ Assumption: The speedup to $\ell_2$ regression time is achieved for "constant $p$ bounded away from 1." The paper notes that their results do not directly give anything for $p=1$ or $p=\infty$ due to the nature of the dual norms and the complexity of the smoothing functions.
  • Sparsity: The current analysis does not explicitly account for matrix sparsity, although the authors suggest that extensions might be possible by combining their methods with $\ell_p$ row sampling.
  • Generalization to $p=1, \infty$: Extending the current iterative refinement framework to cover the $p=1$ and $p=\infty$ cases remains an open challenge.
  • Practical Performance: While theoretical improvements are significant, the practical performance of these algorithms compared to existing solvers on real-world datasets would be an interesting area for future research.

Summary updated

Abstract

We give improved algorithms for the ℓp-regression problem, minx ‖x‖p such that Ax = b, for all p ∊ (1, 2) ∪ (2, ∞). Our algorithms obtain a high accuracy solution in iterations, where each iteration requires solving an m × m linear system, with m being the dimension of the ambient space. Incorporating a procedure for maintaining an approximate inverse of the linear systems that we need to solve at each iteration, we give algorithms for solving ℓp-regression to 1/poly(n) accuracy that runs in time Õp(mmax{ω, 7/3}), where ω is the matrix multiplication constant. For the current best value of ω > 2.37, this means that we can solve ℓp regression as fast as ℓ2 regression, for all constant p bounded away from 1. Our algorithms can be combined with nearly-linear time solvers for linear systems in graph Laplacians to give minimum ℓp-norm flow / voltage solutions to 1/poly(n) accuracy on an undirected graph with m edges in time. For sparse graphs and for matrices with similar dimensions, our iteration counts and running times improve upon the p-norm regression algorithm by [Bubeck-Cohen-Lee-Li STOC'18], as well as general purpose convex optimization algorithms. At the core of our algorithms is an iterative refinement scheme for ℓp-norms, using the quadratically-smoothed ℓp-norms introduced in the work of Bubeck et al. Formally, given an initial solution, we construct a problem that seeks to minimize a quadratically-smoothed ℓp norm over a subspace, such that a crude solution to this problem allows us to improve the initial solution by a constant factor, leading to algorithms with fast convergence.
BibTeX
@inproceedings{adil2019iterative,
  author = {Deeksha Adil and Rasmus Kyng and Richard Peng and Sushant Sachdeva},
  title = {{Iterative Refinement for ℓp-norm Regression}},
  booktitle = {SODA},
  year = {2019},
  url = {https://openreview.net/forum?id=Z1axSz_Vljt},
}
Figure