# Coresets for Multiple ℓp Regression

arXiv: https://arxiv.org/abs/2406.02432 · HTML: https://mlsanity.com/paper/2406.02432/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 13 of its 37 references that are in the map.
- First posted on arXiv 4 Jun 2024.

## Builds on (most cited first, 13 of 13)

- [Performance of Johnson-Lindenstrauss Transform for k-Means and k-Medians Clustering](https://mlsanity.com/paper/1811.03195/) (2018)
- [Optimal approximate matrix product in terms of stable rank](https://mlsanity.com/paper/1507.02268/) (2015)
- [Coresets for Clustering in Euclidean Spaces: Importance Sampling is Nearly Optimal](https://mlsanity.com/paper/2004.06263/) (2020)
- [Strong Coresets for k-Median and Subspace Approximation: Goodbye Dimension](https://mlsanity.com/paper/1809.02961/) (2018)
- [Query Complexity of Least Absolute Deviation Regression via Robust Uniform Convergence](https://mlsanity.com/paper/2102.02322/) (2021)
- [Online Lewis Weight Sampling](https://mlsanity.com/paper/2207.08268/) (2022)
- [L1 Regression with Lewis Weights Subsampling](https://mlsanity.com/paper/2105.09433/) (2021)
- [Input Sparsity and Hardness for Robust Subspace Approximation](https://mlsanity.com/paper/1510.06073/) (2015)
- [Improved Iteration Complexities for Overconstrained p-Norm Regression](https://mlsanity.com/paper/2111.01848/) (2021)
- [Dimensionality Reduction for Sum-of-Distances Metric](https://mlsanity.com/paper/1912.12003/) (2019)
- [Exponentially Improved Dimensionality Reduction for ℓ1: Subspace Embeddings and Independence Testing](https://mlsanity.com/paper/2104.12946/) (2021)
- [High-Dimensional Geometric Streaming in Polynomial Space](https://mlsanity.com/paper/2204.03790/) (2022)
- [Tight Bounds for the Subspace Sketch Problem with Applications](https://mlsanity.com/paper/1904.05543/) (2019)

## Abstract (arXiv)

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 ℓp linear regression with a single response are known in prior work. However, for multiple ℓ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-2d) for p<2 and tilde O(varepsilon-pdp/2) for p>2 independently of m (i.e., dimension-free) that approximate the multiple ℓp regression objective at every point in the domain up to (1±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 ℓp Euclidean power means up to a (1+varepsilon) factor, showing that tildeTheta(varepsilon-2) samples for p = 1, tildeTheta(varepsilon-1) samples for 1 < p < 2, and tildeTheta(varepsilon1-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-1k) rows which spans a (1+varepsilon)-approximately optimal k-dimensional subspace for ℓp subspace approximation, which is also nearly optimal.