Adventures with Randomized Algebra for Extreme-Scale Signal Processing

At extreme scale, even conventional sampling and projection methods can become too expensive. This talk treats locality-sensitive hashing as an amortized constant-time adaptive sampler, connecting probabilistic hash tables with efficient unbiased statistical estimators. A few hash lookups can support adaptive estimation at a cost close to uniform sampling. Applications include partition-function estimation for large natural-language models such as word2vec, adaptive gradient estimation for stochastic gradient descent, and sublinear deep learning with very large parameter spaces. The talk also considers memory reduction through a hashing method related to count-min sketches. An example trains a classifier with 100,000 classes and 400,000 features on a single Titan X while using at most five percent of the memory needed to store all weights; a conventional logistic-regression model for that dataset requires 320 GB.