Coresets for Multiple ℓp Regression

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.