Learning-Augmented Algorithms

In recent years there has been increasing interest in using machine learning to improve the performance of classical algorithms in computer science, by fine-tuning their behavior to adapt to the properties of the input distribution. Many applications involve processing streams of data (video, data logs, customer activity etc) by executing the same algorithm on an hourly, daily or weekly basis. These data sets are typically not "random" or "worst-case"; instead, they come from some distribution which does not change rapidly from execution to execution. This makes it possible to design better algorithms tailored to the specific data distribution, trained on past instances of the problem. Using this “data-driven” or “learning-augmented” approach to algorithm design, our group members design better data structures, online algorithms, streaming and sublinear algorithms, algorithms for similarity search and inverse problems.
 

Faculty: Costis Daskalakis, Piotr Indyk, Ronitt Rubinfeld

Postdocs: Talya Eden, Anders Aamand

Students: Justin Y Chen, Shyam Narayanan, Sandeep Silwal, Nicholas Schiefer

Alumni: Tal Wagner, Ali Vakilian, Ilya Razenshteyn, Yang Yuan

 

Learning-based Support Estimation in Sublinear Time

T Eden, P Indyk, S Narayanan, R Rubinfeld, S Silwal, T Wagner

International Conference on Learning Representations (ICLR), 2021.

 

Learning Sublinear-Time Indexing for Nearest Neighbor Search

Y Dong, P Indyk, I Razenshteyn, T Wagner

International Conference on Learning Representations (ICLR), 2020.

 

Learning-based low-rank approximations

P Indyk, A Vakilian, Y Yuan

Advances in Neural Information Processing Systems (NeurIPS), 2019.

 

Learning-Based Frequency Estimation Algorithms

CY Hsu, P Indyk, D Katabi, A Vakilian

International Conference on Learning Representations (ICLR), 2019.

 

Learning-augmented algorithms course lecture notes

https://stellar.mit.edu/S/course/6/sp19/6.890/materials.html

 

FODSI Workshop on Machine Learning for Algorithms

https://fodsi.us/ml4a.html