Coresets for Multiple ℓp Regression

David P. Woodruff, Taisuke Yasuda

Introduction

In the era of massive datasets, the computational cost of processing every data point often becomes prohibitive. Coresets have emerged as a fundamental tool in randomized numerical linear algebra and computational geometry to address this. A coreset is a small, weighted subset of the original data that serves as a high-fidelity proxy. By solving an optimization problem—such as regression—on the coreset, one can obtain a solution that is nearly as accurate as the one derived from the full dataset, but with significantly reduced computational overhead.

While coresets for standard $\ell_p$ regression (involving a single target vector) are well-understood, a significant gap has persisted for multiple response regression. In this setting, the goal is to predict many target variables simultaneously. Until recently, coreset sizes for these problems typically scaled linearly with the number of targets, rendering them inefficient for high-dimensional response data. A recent study by David P. Woodruff and Taisuke Yasuda from Carnegie Mellon University provides a breakthrough, offering the first coreset constructions where the size is independent of the number of target responses.

The Multiple Response Challenge

In a standard regression problem, we are given a matrix $A \in \mathbb{R}^{n \times d}$ and a target vector $b \in \mathbb{R}^n$. The objective is to find a vector $x$ that minimizes $\|Ax - b\|_p$. In multiple $\ell_p$ regression, the target is a matrix $B \in \mathbb{R}^{n \times m}$ containing $m$ different response vectors. The task is to find a matrix $X \in \mathbb{R}^{d \times m}$ that minimizes the entrywise $\ell_p$ norm:

$$\min_{X \in \mathbb{R}^{d \times m}} \|AX - B\|_p^p = \min_{X \in \mathbb{R}^{d \times m}} \sum_{i=1}^n \sum_{j=1}^m |(AX)_{i,j} - B_{i,j}|^p$$

Prior to this work, the size of coresets for this problem typically depended on $m$. If a dataset contained millions of target variables, the coreset would grow proportionally, defeating the purpose of data reduction. The authors sought to create "dimension-free" coresets, where the size depends only on the feature dimension $d$ and the error parameter $\epsilon$, regardless of the magnitude of $m$.

Technical Innovations

The authors introduce several key strategies to decouple the coreset size from the number of responses:

1. Partition by Sensitivity

The core innovation involves generalizing the "partition by sensitivity" framework. Sensitivity measures the maximum influence a single row can have on the total objective function. In the multiple response setting, the authors demonstrate that even without perfect knowledge of the target matrix $B$, one can preserve the difference between the objective value and a baseline. By focusing on the difference $\|AX - B\|_p^p - \|B\|_p^p$, they show that the sensitivities are primarily controlled by the features in $A$, allowing the columns of $B$ to be sampled collectively.

2. Strong vs. Weak Coresets

The paper distinguishes between two types of guarantees:

  • Strong Coresets: These provide a $(1 \pm \epsilon)$ approximation of the objective value for every possible solution $X$. The authors achieve this by considering multiple scales of the optimal value and using union bounds to extend single-response guarantees.
  • Weak Coresets: These only guarantee that the optimal solution found using the coreset is a $(1 + \epsilon)$ approximation for the original problem. To optimize these, the authors use an iterative size reduction argument, refining sampling probabilities based on the closeness of nearly optimal solutions.

3. Dvoretzky’s Theorem

To apply their regression results to other problems like Euclidean power means, the authors leverage Dvoretzky’s Theorem from functional analysis. This allows them to embed complex norms into the entrywise $\ell_p$ norm, facilitating the application of regression coresets to broader geometric problems.

Key Results and Bounds

The research establishes nearly tight upper and lower bounds for coreset sizes, significantly improving the state-of-the-art:

  • Strong Coresets: For $1 \le p < 2$, the size is $\tilde{O}(d/\epsilon^2)$. For $p > 2$, the size is $\tilde{O}(d^{p/2}/\epsilon^p)$.
  • Weak Coresets: For $1 < p < 2$, the size is $\tilde{O}(d/\epsilon)$. For $p > 2$, the size is $\tilde{O}(d^{p/2}/\epsilon^{p-1})$.
  • Euclidean Power Means: The authors settled a long-standing question regarding the sample complexity of finding a center that minimizes the sum of distances to the $p$-th power. They proved the required uniform samples are $\tilde{\Theta}(\epsilon^{-2})$ for $p=1$, $\tilde{\Theta}(\epsilon^{-1})$ for $1 < p < 2$, and $\tilde{\Theta}(\epsilon^{1-p})$ for $p > 2$.
  • Subspace Approximation: The paper provides the first nearly optimal "spanning coresets" for $1 < p < 2$, improving the dependence on the subspace dimension $k$.

Empirical Validation

While the contribution is primarily theoretical, the authors validated their claims using the MNIST handwritten digit dataset. By sampling random features to create $m$-dimensional response datasets, they empirically confirmed that the trade-off between sample size and approximation quality is indeed independent of the dimension $m$. This confirms that the theoretical "dimension-free" claims hold in practice.

Conclusion and Future Directions

This work bridges a major gap in coreset theory, providing the first efficient constructions for multiple response $\ell_p$ regression. However, some questions remain. For $p > 2$, a small gap persists between the known upper and lower bounds for single-response regression, and the current techniques for spanning coresets do not yet yield improvements in the $p > 2$ regime. Additionally, exploring "active" strong coresets—where the target matrix $B$ is not fully known upfront—presents an intriguing path for future research in active learning.

Summary updated

BibTeX
@inproceedings{woodruff2024coresets,
  author = {David P. Woodruff and Taisuke Yasuda},
  title = {{Coresets for Multiple ℓp Regression}},
  booktitle = {International Conference on Machine Learning},
  year = {2024},
}
Figure