Home » Publication » 19885

Dettaglio pubblicazione

2018, NIPS'18: Proceedings of the 32nd International Conference on Neural Information Processing Systems, Pages 6561-6570

On coresets for logistic regression (04b Atto di convegno in volume)

Munteanu A., Sohler C., Schwiegelshohn C., Woodruff D. P.

Coresets are one of the central methods to facilitate the analysis of large data. We continue a recent line of research applying the theory of coresets to logistic regression. First, we show the negative result 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 ± ε)-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.
Gruppo di ricerca: Algorithms and Data Science
© Università degli Studi di Roma "La Sapienza" - Piazzale Aldo Moro 5, 00185 Roma