Nearest Neighbor Based Greedy Coordinate Descent

on YouTube ↗31m

" summary

Shows that greedy coordinate selection reduces to a nearest neighbor query on the residual, so using approximate nearest neighbor data structures (LSH or quadtrees with random projections) makes each greedy step sublinear, giving overall runtime sublinear in P while preserving the 1/T convergence up to a constant. Preprocessing and storage are quasi‑linear in P; approximation factors trade accuracy for speed. Empirical tests on logistic regression beat cyclic and vanilla greedy modestly, confirming the reduction works but needing LSH tuning for better gains.

AI-written summary · about

" chapters (12)

1. 0:00Intro
2. 1:41Modem Big Data
3. 6:30Convex Optimization
4. 9:27Coordinate Descent (CD)
5. 12:14Greedy Coordinate Descent (GCD)
6. 13:09Greedy Coordinate Descent: Analysis
7. 16:19Fast Greedy and Nearest Neighbor
8. 19:18Approximate Greedy CD: Analysis
9. 20:55Fast Greedy: Comoutational Complexity
10. 23:15Fast Greedy: Computational Complexity
11. 27:26Modified Greedy for non-smooth objectives
12. 29:28Summary

" related talks

• 01h 05mNearest Neighbor Methods IIlya Razenshteyn · Foundations of Data Science Boot Camp 2018
• 40mEfficient Reductions for k-Nearest Neighbor SearchRasmus Pagh · Sublinear Algorithms and Nearest-Neighbor Search
• 01h 01mNearest Neighbor Methods IIIlya Razenshteyn · Foundations of Data Science Boot Camp 2018
• 30mParallelization by ApproximationKanat Tangwongsan · Parallel and Distributed Algorithms for Inference and Optimization (Simons Institute, Oct. 21–24, 2013)
• 01h 18mOptimization IBen Recht · Big Data Boot Camp 2013
• 26mUsing Random Projections to Make Sense of High-Dimensional ...Stefan Savev · Berlin Buzzwords 2015
• 44mParsimonious Learning-Augmented AlgorithmsRavi Kumar · Quantifying Uncertainty: Stochastic, Adversarial, and Beyond
• 24mSpeeding up search with locality sensitive hashingMaciej Kula · EuroPython 2015