Adventures with Randomized Algebra for Extreme-Scale Signal Processing

on YouTube ↗32m

" summary

Shows that locality-sensitive hashing (LSH) turns nearest-neighbor indexing into adaptive sampling with a known collision probability, enabling an unbiased estimator for softmax partition functions and gradients without computing all weights. Results on Penn Treebank/Text8 give near-full-softmax perplexity with far fewer samples at roughly 1.5× cost of SGD. Replaces dense forward/backprop by hashing neurons so training uses 5–10% sparsity with similar accuracy, supports asynchronous parallelism, and scales feature selection to 2.3 billion dimensions.

AI-written summary · about

" chapters (8)

1. 0:00Introduction and motivation
2. 2:25Locality sensitive hashing
3. 6:08LSH for adaptive sampling
4. 10:29Estimation in learning
5. 16:23Gradient estimation results
6. 19:01Sparse neural networks
7. 24:54Parallelism and memory
8. 28:55Conclusion and Q&A

" related talks

• 26mUsing Random Projections to Make Sense of High-Dimensional ...Stefan Savev · Berlin Buzzwords 2015
• 01h 02mImportance Sampling in High Dimensions via HashingMoses Charikar · Sublinear Algorithms and Nearest-Neighbor Search
• 01h 03mSampling for Linear Algebra, Statistics, and Optimization IMichael Mahoney · Foundations of Data Science Boot Camp 2018
• 39mProbabilistic Hashing Methods for Succinct Data Representations and ApplicationsPing Li · Workshop on Succinct Data Representations and Applications (Simons Institute Big Data 2013)
• 37mMin-Wise Hashing for Large-Scale Regression and ClassificationNicolai Meinshausen · Workshop on Succinct Data Representations and Applications (Simons Institute Big Data 2013)
• 33mRandomized Least Squares Optimization and its Incredible Utility for Large-Scale Tensor Decomp...Tamara Kolda · Extroverted Sublinear Algorithms 2024
• 11mFinding Friends in High Dimensions...Aaron Levin · !!Con 2017
• 24mSpeeding up search with locality sensitive hashingMaciej Kula · EuroPython 2015