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:
- 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$.
- 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.
- 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