Coresets for Multiple $\ell_p$ Regression

David Woodruff, Taisuke Yasuda

Introduction

In modern data science, finding linear relationships between feature matrices and target variables is a foundational task. While standard least squares ($\ell_2$) regression is ubiquitous, $\ell_p$ regression (where $p \neq 2$) is frequently preferred for its robustness to outliers (e.g., $p=1$) or its flexibility in handling diverse noise distributions.

As datasets grow massive, researchers increasingly rely on coresets—tiny, weighted subsets of the original dataset that act as highly accurate proxies. Running a regression on a coreset yields nearly identical results to processing millions of original rows, drastically reducing computational overhead.

However, a major bottleneck exists in multiple $\ell_p$ regression, where the goal is to predict an entire matrix of targets with $m$ columns, rather than a single vector. Historically, coreset constructions for this problem scaled linearly with $m$. If a task required predicting a thousand different targets, the compressed coreset would be a thousand times larger.

This paper introduces a breakthrough: the first "dimension-free" coresets for multiple $\ell_p$ regression. The authors prove that it is possible to build a coreset whose size is entirely independent of the number of target variables $m$, settling long-standing open questions in the field.

Methodology: Overcoming the Non-Euclidean Divide

For standard least squares ($p=2$), creating coresets is relatively straightforward due to the Pythagorean theorem and orthogonality. For $p \neq 2$, these geometric conveniences vanish. To navigate this non-Euclidean landscape, the authors bridge techniques from active learning and coreset construction:

  • Sensitivity Sampling via Lewis Weights: The authors measure the geometric "importance" of each row using $\ell_p$ Lewis weights, a standard metric for understanding the overall geometry of the feature matrix.
  • Partition by Sensitivity: This is the core multi-scale innovation. The authors partition the entries of the target matrix into "big" and "small" components relative to their Lewis weights. By treating these components differently during sampling, they prevent approximation errors from accumulating as more columns are added to the target matrix.
  • Dvoretzky’s Theorem: To apply their findings to specific geometric problems like Euclidean power means, the authors leverage this classic functional analysis theorem. It allows them to embed complex geometric norms into standard entrywise $\ell_p$ norms.
  • Iterative Size Reduction: The paper distinguishes between "strong" coresets (which preserve the objective value for every possible solution) and "weak" coresets (which only need to preserve the optimal minimum). By using an iterative refinement argument, the authors shave off an extra factor of $\varepsilon$ from the size of weak coresets.

Key Results

The theoretical proofs of optimality are the paper's primary focus, though the authors also validated their findings empirically using the MNIST dataset. By sampling random features to create $m$-dimensional datasets, they demonstrated that the trade-off between sample size and approximation error remains stable regardless of $m$.

Major theoretical contributions include:

  • Optimal Coreset Sizes: The authors achieved coreset sizes of $\tilde{O}(\varepsilon^{-2}d)$ for $p < 2$ and $\tilde{O}(\varepsilon^{-p}d^{p/2})$ for $p > 2$. These are the first known bounds for multiple regression that do not depend on the number of responses $m$.
  • Settling Euclidean Power Means: The paper resolves the sample complexity required to approximate $\ell_p$ power means. For instance, they proved that exactly $\tilde{\Theta}(\varepsilon^{-2})$ samples are necessary and sufficient for $p=1$ (the geometric median), answering a prominent open question by Cohen-Addad, Saulpic, and Schwiegelshohn.
  • Subspace Approximation: For $1 < p < 2$, the authors proved that any matrix contains a subset of $\tilde{O}(\varepsilon^{-1}k)$ rows that spans a $(1+\varepsilon)$-approximately optimal $k$-dimensional subspace. This significantly improves upon previous bounds that suffered from a worse dependence on $k$.

Limitations and Future Directions

While the paper makes massive strides, a few theoretical gaps remain for future research:

  1. The $p > 2$ Gap: The bounds for $p < 2$ are exceptionally tight, but there remains a small gap between the best-known upper and lower bounds for strong coresets when $p > 2$.
  2. Spanning Coresets for $p > 2$: The techniques used to find a subset of rows that spans an optimal subspace work best in the $p < 2$ regime. Extending these nearly optimal bounds to $p > 2$ is an open challenge.
  3. Active Learning Lower Bounds: The authors suggest their weak coreset bounds are nearly optimal for active learning with an embedding. However, a formal, non-trivial lower bound for the most general weak coreset case has yet to be established.

Summary updated

Abstract

A *coreset* of a dataset with $n$ examples and $d$ features is a weighted subset of examples that is sufficient for solving downstream data analytic tasks. Nearly optimal constructions of coresets for least squares and $\ell_p$ linear regression with a single response are known in prior work. However, for multiple $\ell_p$ regression where there can be $m$ responses, there are no known constructions with size sublinear in $m$. In this work, we construct coresets of size $\tilde O(\varepsilon^{-2}d)$ for $p<2$ and $\tilde O(\varepsilon^{-p}d^{p/2})$ for $p>2$ independently of $m$ (i.e., dimension-free) that approximate the multiple $\ell_p$ regression objective at every point in the domain up to $(1\pm\varepsilon)$ relative error. If we only need to preserve the minimizer subject to a subspace constraint, we improve these bounds by an $\varepsilon$ factor for all $p>1$. All of our bounds are nearly tight. We give two application of our results. First, we settle the number of uniform samples needed to approximate $\ell_p$ Euclidean power means up to a $(1+\varepsilon)$ factor, showing that $\tilde\Theta(\varepsilon^{-2})$ samples for $p = 1$, $\tilde\Theta(\varepsilon^{-1})$ samples for $1 < p < 2$, and $\tilde\Theta(\varepsilon^{1-p})$ samples for $p>2$ is tight, answering a question of Cohen-Addad, Saulpic, and Schwiegelshohn. Second, we show that for $1<p<2$, every matrix has a subset of $\tilde O(\varepsilon^{-1}k)$ rows which spans a $(1+\varepsilon)$-approximately optimal $k$-dimensional subspace for $\ell_p$ subspace approximation, which is also nearly optimal.
BibTeX
@inproceedings{woodruff2024coresets,
  author = {David Woodruff and Taisuke Yasuda},
  title = {{Coresets for Multiple $\textbackslash\{\}ell\_p$ Regression}},
  booktitle = {International Conference on Machine Learning},
  year = {2024},
}
Figure