Coresets for Multiple ℓp Regression

A coreset of a dataset with 𝑛 examples and 𝑑 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 ℓ 𝑝 linear regression with a single response are known in prior work. However, for multiple ℓ 𝑝 regression where there can be 𝑚 responses, there are no known constructions with size sublinear in 𝑚. In this work, we construct coresets of size Õ(𝜀 -2 𝑑) for 𝑝 < 2 and Õ(𝜀 -𝑝 𝑑 𝑝/2 ) for 𝑝 > 2 independently of 𝑚 (i.e., dimension-free) that approximate the multiple ℓ 𝑝 regression objective at every point in the domain up to (1 ± 𝜀) relative error. If we only need to preserve the minimizer subject to a subspace constraint, we improve these bounds by an 𝜀 factor for all 𝑝 > 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 ℓ 𝑝 Euclidean power means up to a (1 + 𝜀) factor, showing that Θ(𝜀 -2 ) samples for 𝑝 = 1, Θ(𝜀 -1 ) samples for 1 < 𝑝 < 2, and Θ(𝜀 1-𝑝 ) samples for 𝑝 > 2 is tight, answering a question of Cohen-Addad, Saulpic, and Schwiegelshohn. Second, we show that for 1 < 𝑝 < 2, every matrix has a subset of Õ(𝜀 -1 𝑘) rows which spans a (1+𝜀)-approximately optimal 𝑘-dimensional subspace for ℓ 𝑝 subspace approximation, which is also nearly optimal.