On Coresets for Regularized Loss Minimization
  We design and mathematically analyze sampling-based algorithms for
regularized loss minimization problems that are implementable in popular
computational models for large data, in which the access to the data is
restricted in some way. Our main result is that if the regularizer's effect
does not become negligible as the norm of the hypothesis scales, and as the
data scales, then a uniform sample of modest size is with high probability a
coreset. In the case that the loss function is either logistic regression or
soft-margin support vector machines, and the regularizer is one of the common
recommended choices, this result implies that a uniform sample of size $O(d
\sqrt{n})$ is with high probability a coreset of $n$ points in $\Re^d$. We
contrast this upper bound with two lower bounds. The first lower bound shows
that our analysis of uniform sampling is tight; that is, a smaller uniform
sample will likely not be a core set. The second lower bound shows that in some
sense uniform sampling is close to optimal, as significantly smaller core sets
do not generally exist.
