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

通过构建核心集，我们实现了对多个响应的多元回归目标的近似，并得到了关于样本数量和子空间逼近的几乎最优的界限。

多重 $\ell_p$ 回归的核心集

Coresets for Multiple $\ell_p$ Regression

In the subspace approximation problem, we seek a k-dimensional subspace F of
R^d that minimizes the sum of p-th powers of Euclidean distances to a given set
of n points a_1, ..., a_n in R^d, for p >= 1. More generally than minimizing
sum_i dist(a_i,F)^p,we may wish to minimize sum_i M(dist(a_i,F)) for some loss
function M(), for example, M-Estimators, which include the Huber and Tukey loss
functions. Such subspaces provide alternatives to the singular value
decomposition (SVD), which is the p=2 case, finding such an F that minimizes
the sum of squares of distances. For p in [1,2), and for typical M-Estimators,
the minimizing $F$ gives a solution that is more robust to outliers than that
provided by the SVD. We give several algorithmic and hardness results for these
robust subspace approximation problems.
We think of the n points as forming an n x d matrix A, and letting nnz(A)
denote the number of non-zero entries of A. Our results hold for p in [1,2). We
use poly(n) to denote n^{O(1)} as n -> infty. We obtain: (1) For minimizing
sum_i dist(a_i,F)^p, we give an algorithm running in O(nnz(A) +
(n+d)poly(k/eps) + exp(poly(k/eps))), (2) we show that the problem of
minimizing sum_i dist(a_i, F)^p is NP-hard, even to output a
(1+1/poly(d))-approximation, answering a question of Kannan and Vempala, and
complementing prior results which held for p >2, (3) For loss functions for a
wide class of M-Estimators, we give a problem-size reduction: for a parameter
K=(log n)^{O(log k)}, our reduction takes O(nnz(A) log n + (n+d) poly(K/eps))
time to reduce the problem to a constrained version involving matrices whose
dimensions are poly(K eps^{-1} log n). We also give bicriteria solutions, (4)
Our techniques lead to the first O(nnz(A) + poly(d/eps)) time algorithms for
(1+eps)-approximate regression for a wide class of convex M-Estimators.

研究了多维欧氏空间中寻找一个 k 维子空间 F，使得一组 n 个点到该子空间的 p 次方欧氏距离和最小的问题。进一步探讨了在某些损失函数 M ()（如 Huber 和 Tukey 损失函数）下此问题的最优解。这些鲁棒子空间可替代奇异值分解（SVD）提供更有效的解决方案，对于典型的 M-Estimators，对离群值的鲁棒性更强。本文给出了一些这些鲁棒子空间逼近问题的算法和难度结果。