2018

On Coresets for Logistic Regression

Munteanu, Alexander, Schwiegelshohn, Chris, Sohler, Christian et al.

Understand

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.

Built on

A general purpose unequal probability sampling plan
Chao, M. T · 1982
Earlier work this paper cites.
Extensions of Lipschitz mappings into a Hilbert space
Johnson, William B and Lindenstrauss, Joram · 1984
Earlier work this paper cites.
Learnability and the Vapnik-Chervonenkis dimension
Blumer, Anselm, Ehrenfeucht, Andrzej, Haussler, David, and Warmuth, Manfred K · 1989
Earlier work this paper cites.
Generalized Linear Models
McCullagh, P. and Nelder, J. A · 1989
Earlier work this paper cites.
An Introduction to Computational Learning Theory
Kearns, Michael J. and Vazirani, Umesh V · 1994
Earlier work this paper cites.
Exact logistic regression: Theory and examples
Mehta, Cyrus R. and Patel, Nitin R · 1995
Earlier work this paper cites.
The Nature of Statistical Learning Theory
Vapnik, Vladimir N · 1995
Earlier work this paper cites.
On randomized one-round communication complexity
Kremer, Ilan, Nisan, Noam, and Ron, Dana · 1999
Earlier work this paper cites.
A solution to the problem of separation in logistic regression
Heinze, Georg and Schemper, Michael · 2002
Earlier work this paper cites.
Approximating extent measures of points
Agarwal, Pankaj K., Har-Peled, Sariel, and Varadarajan, Kasturi R · 2004
Earlier work this paper cites.
Subgradient and sampling algorithms for ℓ 1 \ell_{1} regression
Clarkson, Kenneth L · 2005
Earlier work this paper cites.
Sampling algorithms for ℓ 2 \ell_{2} regression and applications
Drineas, Petros, Mahoney, Michael W., and Muthukrishnan, S · 2006
Earlier work this paper cites.
k-means++: the advantages of careful seeding
Arthur, David and Vassilvitskii, Sergei · 2007
Earlier work this paper cites.
Relative-error CUR matrix decompositions
Drineas, Petros, Mahoney, Michael W., and Muthukrishnan, S · 2008
Earlier work this paper cites.

Similar

Sampling algorithms and coresets for ℓ p \ell_{p} regression
Dasgupta, Anirban, Drineas, Petros, Harb, Boulos, Kumar, Ravi, and Mahoney, Michael W · 2009
Cited alongside, same era.
Universal ε \varepsilon -approximators for integrals
Langberg, Michael and Schulman, Leonard J · 2010
Cited alongside, same era.
A unified framework for approximating and clustering data
Feldman, Dan and Langberg, Michael · 2011
Cited alongside, same era.
Scalable training of mixture models via coresets
Feldman, Dan, Faulkner, Matthew, and Krause, Andreas · 2011
Cited alongside, same era.
Subspace embeddings for the L 1 L_{1} -norm with applications
Sohler, Christian and Woodruff, David P · 2011
Cited alongside, same era.
Fast approximation of matrix coherence and statistical leverage
Drineas, Petros, Magdon-Ismail, Malik, Mahoney, Michael W., and Woodruff, David P · 2012
Cited alongside, same era.
Low rank approximation and regression in input sparsity time
Clarkson, Kenneth L. and Woodruff, David P · 2013
Cited alongside, same era.
Turning big data into tiny data: Constant-size coresets for k -means, PCA and projective clustering
Feldman, Dan, Schmidt, Melanie, and Sohler, Christian · 2013
Cited alongside, same era.
Matrix computations (4. ed.)
Golub, Gene H. and van Loan, Charles F · 2013
Cited alongside, same era.
Iterative row sampling
Li, Mu, Miller, Gary L., and Peng, Richard · 2013
Cited alongside, same era.
Subspace embeddings and ℓ p \ell_{p} -regression using exponential random variables
Woodruff, David P. and Zhang, Qin · 2013
Cited alongside, same era.
Sketching as a tool for numerical linear algebra
Woodruff, David P · 2014
Cited alongside, same era.

Then

Uniform sampling for matrix approximation
Cohen, Michael B., Lee, Yin Tat, Musco, Cameron, Musco, Christopher, Peng, Richard, and Sidford, Aaron · 2015
Later among the works it cites.
Communication efficient coresets for empirical loss minimization
Reddi, Sashank J., Póczos, Barnabás, and Smola, Alexander J · 2015
Later among the works it cites.
k k -means for streaming and distributed big sparse data
Barger, Artem and Feldman, Dan · 2016
Later among the works it cites.
New frameworks for offline and streaming coreset constructions
Original
Braverman, Vladimir, Feldman, Dan, and Lang, Harry · 2016
Later among the works it cites.
The fast Cauchy transform and faster robust linear regression
Clarkson, Kenneth L., Drineas, Petros, Magdon-Ismail, Malik, Mahoney, Michael W., Meng, Xiangrui, and Woodruff, David P · 2016
Later among the works it cites.
Coresets for scalable Bayesian logistic regression
Huggins, Jonathan H., Campbell, Trevor, and Broderick, Tamara · 2016
Later among the works it cites.
Strong coresets for hard and soft Bregman clustering with applications to exponential family mixtures
Lucic, Mario, Bachem, Olivier, and Krause, Andreas · 2016
Later among the works it cites.
Input sparsity time low-rank approximation via ridge leverage score sampling
Cohen, Michael B., Musco, Cameron, and Musco, Christopher · 2017
Later among the works it cites.
Random projections for Bayesian regression
Geppert, Leo N., Ickstadt, Katja, Munteanu, Alexander, Quedenfeld, Jens, and Sohler, Christian · 2017
Later among the works it cites.
Recursive sampling for the Nyström method
Musco, Cameron and Musco, Christopher · 2017
Later among the works it cites.
Beyond worst-case analysis, 2017
Roughgarden, Tim · 2017
Later among the works it cites.
Scalable k k -means clustering via lightweight coresets
Bachem, Olivier, Lucic, Mario, and Krause, Andreas · 2018
Closest in time.
Core dependency networks
Molina, Alejandro, Munteanu, Alexander, and Kersting, Kristian · 2018
Closest in time.
Coresets for monotonic functions with applications to deep learning
Original
Tolochinsky, Elad and Feldman, Dan · 2018
Closest in time.

Beyond the bibliography

alphaXiv searches the wider corpus for related work and actual follow-ups.

Open on alphaXiv

alphaXiv is searching for related work…

Reading the bibliography…