Sparse Regression Faster than dω

Mehrdad Ghadiri, Richard Peng, Santosh S. VempalaarXiv 2021 · arXiv · OpenReview

Abstract

For a matrix $A\in \mathbb{R}^{n\times d}$ with $n\geq d$, we consider the dual problems of $\min \|Ax-b\|_p^p, \, b\in \mathbb{R}^n$ and $\min_{A^\top x=b} \|x\|_p^p,\, b\in \mathbb{R}^d$. We improve the runtimes for solving these problems to high accuracy for every $p>1$ for sufficiently sparse matrices. We show that recent progress on fast sparse linear solvers can be leveraged to obtain faster than matrix-multiplication algorithms for any $p > 1$, i.e., in time $\tilde{O}(pn^\theta)$ for some $\theta < \omega$, the matrix multiplication constant. We give the first high-accuracy input sparsity $p$-norm regression algorithm for solving $\min \|Ax-b\|_p^p$ with $1 < p \leq 2$, via a new row sampling theorem for the smoothed $p$-norm function. This algorithm runs in time $\tilde{O}(\text{nnz}(A) + d^4)$ for any $1<p\leq 2$, and in time $\tilde{O}(\text{nnz}(A) + d^\theta)$ for $p$ close to $2$, improving on the previous best bound where the exponent of $d$ grows with $\max\{p, p/(p-1)\}$.

Introduction

In numerical optimization, $p$-norm regression is a fundamental problem with applications ranging from robust statistics ($p=1.5$) to classical least squares ($p=2$) and network flow problems ($p \approx \infty$). For high-accuracy solutions, the computational bottleneck has historically been tied to the complexity of matrix multiplication, denoted as $O(d^\omega)$ where $\omega \approx 2.37$. While Interior Point Methods (IPMs) and Homotopy Methods provide high precision, they typically require solving dense linear systems in each iteration, making them computationally expensive for large-scale data.

A recent breakthrough by Mehrdad Ghadiri, Richard Peng, and Santosh S. Vempala overcomes this barrier for sparse matrices. By integrating state-of-the-art sparse linear solvers with novel sampling techniques, the authors demonstrate that $p$-norm regression can be solved faster than the theoretical limit for dense matrix multiplication.

Algorithmic Innovations

The core of the new approach lies in a "sketch-and-precondition" framework tailored for sparsity. The authors introduce several key technical contributions:

  1. Leveraging Sparse Linear Solvers: The research utilizes recent advancements in sparse linear algebra that solve specific linear systems faster than $d^\omega$, provided the input matrix is sufficiently sparse.
  2. Quadratic Smoothing ($\gamma$-Function): To address the non-differentiability and varying curvature of $p$-norms, the authors employ a smoothed version known as the $\gamma$-function. This function acts as a quadratic ($p=2$) near the origin and transitions to a $p$-norm further out, facilitating more stable optimization.
  3. Iterative Row Sampling via Leverage Scores: A significant contribution is a new sampling theorem. The authors prove that leverage scores—traditionally associated with $L_2$ problems—can be used to sample a small subset of rows that accurately approximates the $\gamma$-function of the entire matrix for $1 < p \le 2$. This preserves the matrix's sparsity, unlike traditional sketching methods that densify the data.
  4. Efficient Inverse Maintenance: To handle the evolving matrix within optimization loops, the authors use the Sherman-Morrison-Woodbury formula for efficient updates, carefully managing numerical stability and bit complexity.

Complexity Results

The resulting algorithms establish new benchmarks for $p$-norm regression. Notably, for $1 < p \le 2$, the authors achieve a runtime of $\tilde{O}(\text{nnz}(A) + d^4)$. This "input sparsity time" is particularly significant for "tall" matrices ($n \gg d$), as the $d^4$ term is independent of the number of rows $n$. Furthermore, for general $p > 1$, the runtime is reduced to $n^\theta$ with $\theta < \omega$ for sufficiently sparse matrices.

Summary of algorithmic complexities for $p$-norm regression problems across different ranges of $p$.

As shown in the table above, the improvements are most pronounced when $p$ is close to 2, where the problem's structure allows for more aggressive optimization, reaching runtimes of $\tilde{O}(\text{nnz}(A) + d^\theta)$.

Conclusion

This work represents a major step forward in high-accuracy optimization. By breaking the matrix multiplication barrier for sparse $p$-norm regression, it opens new possibilities for large-scale robust estimation. While the current $d^4$ term and specific sparsity requirements present opportunities for further refinement, the theoretical foundation for "input sparsity" high-accuracy solvers is now firmly established. Future work may focus on reducing the polynomial dependence on $d$ and exploring practical implementations of these sparse solvers.

Summary updated

Abstract

For a matrix $A\in \mathbb{R}^{n\times d}$ with $n\geq d$, we consider the dual problems of $\min \|Ax-b\|_p^p, \, b\in \mathbb{R}^n$ and $\min_{A^\top x=b} \|x\|_p^p,\, b\in \mathbb{R}^d$. We improve the runtimes for solving these problems to high accuracy for every $p>1$ for sufficiently sparse matrices. We show that recent progress on fast sparse linear solvers can be leveraged to obtain faster than matrix-multiplication algorithms for any $p > 1$, i.e., in time $\tilde{O}(pn^\theta)$ for some $\theta < \omega$, the matrix multiplication constant. We give the first high-accuracy input sparsity $p$-norm regression algorithm for solving $\min \|Ax-b\|_p^p$ with $1 < p \leq 2$, via a new row sampling theorem for the smoothed $p$-norm function. This algorithm runs in time $\tilde{O}(\text{nnz}(A) + d^4)$ for any $1<p\leq 2$, and in time $\tilde{O}(\text{nnz}(A) + d^\theta)$ for $p$ close to $2$, improving on the previous best bound where the exponent of $d$ grows with $\max\{p, p/(p-1)\}$.
BibTeX
@misc{ghadiri2021sparse,
  author = {Mehrdad Ghadiri and Richard Peng and Santosh S. Vempala},
  title = {{Sparse Regression Faster than dω}},
  year = {2021},
  eprint = {2109.11537},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2109.11537},
}
Figure