On Coresets for Logistic Regression
This work provides theoretical and practical advances for efficient data compression in logistic regression, though it is incremental as it builds on prior coreset research.
The paper addresses the challenge of constructing coresets for logistic regression, proving that strongly sublinear coresets are impossible in general but introducing a complexity measure μ(X) to quantify compression difficulty and developing a novel sensitivity sampling scheme that yields provably sublinear coresets for data with bounded μ(X)-complexity, with experiments on real-world benchmarks.
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 $μ(X)$, which quantifies the hardness of compressing a data set for logistic regression. $μ(X)$ has an intuitive statistical interpretation that may be of independent interest. For data sets with bounded $μ(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.