Algorithms Seminar

Oracle-efficient Online Learning and Applications to Auction Design

Speaker:Nika Haghtalab
Date: Thursday, November 16, 2017
Time: 12:00pm - 1:00pm
Location: D344 LSRC, Duke

Abstract

We consider the fundamental problem of learning from expert advice, a.k.a online no-regret learning, where we have access to an offline optimization oracle that can be used to compute, in constant time, the best performing expert at any point in time. We consider the design of no-regret algorithms that are computationally efficient using such an oracle. We present structural properties under which we show oracle-efficient no-regret algorithms exist, even when the set of experts is exponentially large in a natural representation of the problem. Our algorithm is a generalization of the Follow-The-Perturbed-Leader algorithm of Kalai and Vempala that at every step follows the best-performing expert subject to some perturbations. Our design uses a shared source of randomness across all experts that can be efficiently implemented by using an oracle on a random modification of the history of the play at every time step. Our second main contribution is showing that the structural properties required for our oracle-efficient online algorithm are present in a large class problems. As an examples, we discuss the applications of our oracle-efficient learning results to the adaptive optimization of truthful auctions.

This talk is based on a joint work with Miro Dudik, Haipeng Luo, Rob Schapire, Vasilis Syrgkanis, and Jenn Wortman Vaughan. To appear in FOCS'17.

Biography

Nika Haghtalab is a Ph.D. student at the Computer Science department of Carnegie Mellon University, co-advised by Avrim Blum and Ariel Procaccia. Her research is on the theoretical aspects of machine learning and economics. In her work, she is especially passionate about developing a foundations for machine learning that accounts for its interactions with people and organizations, and the wide variety of social and economical limitations, aspirations, and behaviors they demonstrate. Nika is a recipient of the IBM and Microsoft Research Ph.D. fellowships.