Abstract

In this talk, I'll provide a brief overview of "Learning-augmented algorithms": online algorithms that have access to predictions made by a machine learning oracle. The goal in this setting is to design an algorithm that can utilize good predictions to obtain near-optimal performance in practical instances, while simultaneously guaranteeing robust worst-case guarantees (even when the predictions are of a poor quality).

I'll then present a specific application of this framework to the classical online learning problem where the online player receives a "hint'' regarding the upcoming cost vector before choosing the action for that round. Our goal is to design a learning algorithm that utilizes "good'' hints to obtain regret that grows only logarithmically with the number of time steps (thus circumventing well known lower bounds), while at the same time being resilient to bad hints. We develop a general framework for online learning with hints that obtains near-optimal regret bounds with respect to the quality of the hints. We also discuss extensions to settings where the algorithm has access to multiple, possibly conflicting, hints at each round and must also pay for switching actions between rounds.

Biography

Manish is a Research Scientist at Google Research, Mountain View. He obtained his PhD from the University of Maryland, College Park under the supervision of Samir Khuller. He is broadly interested in the design and analysis of approximation algorithms as well as machine learning.