Fast Attention Requires Bounded Entries

on YouTube ↗46m

" summary

Shows attention computation has a sharp threshold: if all Q,K,V entries satisfy B ≤ √log n a polynomial-approximation method yields a low-rank decomposition and an nearly linear time algorithm (n1+o(1)); if B is a constant·√log n then a reduction from approximate closest pair gives a SETH-based lower bound ruling out truly subquadratic time. Tools: Chebyshev/poly truncation, polynomial method, low-rank sketching; construction and bounds match up to log factors.

AI-written summary · about

" chapters (7)

1. 0:00Introduction to attention in machine learning
2. 4:18Attention computation problem
3. 9:21Kernel density estimation link
4. 11:13Lower bound via closest pair
5. 24:31Polynomial approximation algorithm
6. 35:24Chebyshev polynomials & approximation
7. 41:59Q&A

" related talks

• 44mSomething for Almost Nothing: Advances in Sub-Linear Time AlgorithmsRonitt Rubinfeld · Workshop on Succinct Data Representations and Applications (Simons Institute Big Data 2013)
• 30mOn Approximation Guarantees for Greedy Low Rank OptimizationSahand Negahban · Optimization, Statistics and Uncertainty
• 11mUnderstanding Statistical-to-Computational Gaps via Low-Degree PolynomialsAlex Wein · Meet the Fellows Welcome Event
• 29mRecent Advances in Positive Semidefinite Matrix ApproximationCameron Musco · Randomized Numerical Linear Algebra and Applications 2018
• 01h 01mNearest Neighbor Methods IIIlya Razenshteyn · Foundations of Data Science Boot Camp 2018
• 47mSuccinct Representations and Efficient Algorithms Based on Linear ProgrammingSudipto Guha · Workshop on Succinct Data Representations and Applications (Simons Institute Big Data 2013)
• 21mLucky Talk: Chebyshev Polynomials, Moment Matching and Optimal Estimation of the UnseenYihong Wu · Information Theory, Learning and Big Data (Simons Institute, 2015)
• 01h 10mSketching for Linear Algebra: Basics of Dimensionality Reduction and CountSketch IIDavid P. Woodruff · Foundations of Data Science Boot Camp 2018