Learning-Based Sketching Algorithms

Abstract: Classical algorithms typically provide "one size fits all" performance, and do not leverage properties or patterns in their inputs. A recent line of work aims to address this issue by developing algorithms that use machine learning predictions to improve their performance. In this talk I will present two examples of this type, in the context of streaming and sketching algorithms. In particular, I will show how to use machine learning predictions to improve the performance of (a) low-memory streaming algorithms for frequency estimation, and (b) generating space partitions for nearest neighbor search.

The talk will cover material from papers co-authored with Y Dong, CY Hsu, D Katabi, I Razenshteyn, T Wagner and A Vakilian.

bioinformaticsgame theoryinformation theorymachine learningneural and evolutionary computingclassical analysis and ODEsoptimization and controlstatistics theory

Audience: researchers in the topic

IAS Seminar Series on Theoretical Machine Learning

Series comments: Description: Seminar series focusing on machine learning. Open to all.

Register in advance at forms.gle/KRz8hexzxa5P4USr7 to receive Zoom link and password. Recordings of past seminars can be found at www.ias.edu/video-tags/seminar-theoretical-machine-learning