Oracle-Efficient Online Learning and Auction Design
  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
Follow-the-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, who showed that
oracle-efficient algorithms do not exist in general and asked whether one can
identify properties 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 single-parameter settings, (2)
envy-free item pricing in multi-item auctions, and (3) s-level auctions of
Morgenstern and Roughgarden 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.
  Finally, we derive various extensions, including: (1) oracle-efficient
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 in simultaneous auctions, resolving an open problem of
Daskalakis and Syrgkanis.
