Vasilis Syrgkanis: Oracle efficient Learning and Auction Design

Abstract. We consider the design of online no-regret algorithms that are computationally efficient, given access to an offline optimization oracle. We present an algorithm we call Generalized Follow-the-Perturbed-Leader and provide conditions under which it achieves vanishing regret and is oracle-efficient. Our second main contribution is introducing a new adversarial auction-design framework for revenue maximization and applying our oracle-efficient learning results to the adaptive optimization of auctions. Our work extends to oracle-efficient algorithms with contextual information, learning with Maximal-in-Range approximation algorithms, and no-regret bidding in simultaneous auctions.

Joint with: Miroslav Dudik, Nika Haghtalab, Haipeng Luo, Robert E. Schapire and Jennifer Wortman Vaughan