  Coresets are one of the central methods to facilitate the analysis of large
data sets. We continue a recent line of research applying the theory of
coresets to logistic regression. First, we show a negative result, namely, that
no strongly sublinear sized coresets exist for logistic regression. To deal
with intractable worst-case instances we introduce a complexity measure
$\mu(X)$, which quantifies the hardness of compressing a data set for logistic
regression. $\mu(X)$ has an intuitive statistical interpretation that may be of
independent interest. For data sets with bounded $\mu(X)$-complexity, we show
that a novel sensitivity sampling scheme produces the first provably sublinear
$(1\pm\varepsilon)$-coreset. We illustrate the performance of our method by
comparing to uniform sampling as well as to state of the art methods in the
area. The experiments are conducted on real world benchmark data for logistic
regression.
