Algorithms and Hardness for Attention and Kernel Density Estimation

A Google TechTalk, presented by Josh Alman , 2024-05-16 Google Algorithms Seminar. ABSTRACT: This talk will focus on two very related computational problems. The first is Attention, the task at the core of Transformer and other Large Language Models. The second is Kernel Density Estimation, a statistical task which has seen applications from machine learning to computational physics. Both of these problems have straightforward quadratic-time algorithms, and I'll discuss a recent line of work investigating when faster algorithms are possible. I'll survey two algorithmic techniques which lead to almost linear-time algorithms in different parameter regimes: the Fast Multipole Method, and the polynomial method. I'll then overview our new fine-grained hardness results, which prove that these techniques are essentially optimal in the parameter regimes where they apply, and highlight the situations where improvements may be possible. Based on joint work with Amol Aggarwal (in CCC 2022), Zhao Song (in NeurIPS 2023), and Yunfeng Guan (to appear in CCC 2024). About the Speaker: Josh Alman is an Assistant Professor of Computer Science at Columbia University. He works on algorithm design and complexity theory, focusing especially on algebraic tools for speeding up algorithms.