Oracle-efficient online learning and auction design

Miroslav Dudik, Nika Haghtalab, Haipeng Luo, Robert E. Schapire, Vasilis Syrgkanis, Jennifer Wortman Vaughan

Research output: Chapter in Book/Report/Conference proceedingConference contribution

32 Scopus citations


We consider the design of computationally efficient online learning algorithms in an adversarial setting in which the learner has access to an offline optimization oracle. We present an algorithm called Generalized Followthe- Perturbed-Leader and provide conditions under which it is oracle-efficient while achieving vanishing regret. Our results make significant progress on an open problem raised by Hazan and Koren [1], who showed that oracle-efficient algorithms do not exist in full generality and asked whether one can identify conditions under which oracle-efficient online learning may be possible. Our auction-design framework considers an auctioneer learning an optimal auction for a sequence of adversarially selected valuations with the goal of achieving revenue that is almost as good as the optimal auction in hindsight, among a class of auctions. We give oracle-efficient learning results for: (1) VCG auctions with bidder-specific reserves in singleparameter settings, (2) envy-free item-pricing auctions in multiitem settings, and (3) the level auctions of Morgenstern and Roughgarden [2] for single-item settings. The last result leads to an approximation of the overall optimal Myerson auction when bidders valuations are drawn according to a fast-mixing Markov process, extending prior work that only gave such guarantees for the i.i.d. setting.We also derive various extensions, including: (1) oracleefficient algorithms for the contextual learning setting in which the learner has access to side information (such as bidder demographics), (2) learning with approximate oracles such as those based on Maximal-in-Range algorithms, and (3) no-regret bidding algorithms in simultaneous auctions, which resolve an open problem of Daskalakis and Syrgkanis [3].

Original languageEnglish (US)
Title of host publicationProceedings - 58th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2017
PublisherIEEE Computer Society
Number of pages12
ISBN (Electronic)9781538634646
StatePublished - Nov 10 2017
Externally publishedYes
Event58th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2017 - Berkeley, United States
Duration: Oct 15 2017Oct 17 2017

Publication series

NameAnnual Symposium on Foundations of Computer Science - Proceedings
ISSN (Print)0272-5428


Other58th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2017
Country/TerritoryUnited States

All Science Journal Classification (ASJC) codes

  • General Computer Science


  • Follow-the-Perturbed-Leader
  • auction design
  • online learning
  • revenue maximization


Dive into the research topics of 'Oracle-efficient online learning and auction design'. Together they form a unique fingerprint.

Cite this