Sketching Linear Classifiers over Data Streams
arXiv:1711.02305
Abstract
We introduce a new sub-linear space sketch---the Weight-Median Sketch---for learning compressed linear classifiers over data streams while supporting the efficient recovery of large-magnitude weights in the model. This enables memory-limited execution of several statistical analyses over streams, including online feature selection, streaming data explanation, relative deltoid detection, and streaming estimation of pointwise mutual information. Unlike related sketches that capture the most frequently-occurring features (or items) in a data stream, the Weight-Median Sketch captures the features that are most discriminative of one stream (or class) compared to another. The Weight-Median Sketch adopts the core data structure used in the Count-Sketch, but, instead of sketching counts, it captures sketched gradient updates to the model parameters. We provide a theoretical analysis that establishes recovery guarantees for batch and online learning, and demonstrate empirical improvements in memory-accuracy trade-offs over alternative memory-budgeted methods, including count-based sketches and feature hashing.
arXiv commentFull version of paper appearing at SIGMOD 2018 with more detailed proofs of theoretical results. Code available at https://github.com/stanford-futuredata/wmsketch
References in corpus (11)
- Efficient Estimation of Word Representations in Vector Space
- Distilling the Knowledge in a Neural Network
- From Frequency to Meaning: Vector Space Models of Semantics
- Do Deep Nets Really Need to be Deep?
- HOGWILD!: A Lock-Free Approach to Parallelizing Stochastic Gradient Descent
- Federated Optimization:Distributed Optimization Beyond the Datacenter
- Federated Multi-Task Learning
- Theory of Dual-sparse Regularized Randomized Reduction
- Incremental Skip-gram Model with Negative Sampling
- Large-Scale Learning with Less RAM via Randomization
- Streaming Word Embeddings with the Space-Saving Algorithm