Definition: In this task, you are given a part of an article. Your task is to generate headline (title) for this text. Preferred headlines are under fifteen words.
Input: We consider the design of online learning algorithms in a general learning setting, with the goal of obtaining computationally efficient no-regret algorithms, when given access to an oracle for the offline optimization version of the problem. We present an algorithm that we call Generalized Follow-thePerturbed-Leader (Generalized FTPL) and provide conditions under which it achieves vanishing regret and is efficiently implementable with an oracle. Our second main contribution is the introduction of a new online adversarial auction-design framework for revenue maximization and an application of our oracle-efficient learning results to the adaptive optimization of auctions. Our learning algorithm is a generalization of the classic FTPL algorithm of Kalai and Vempala [27], playing at every iteration the historically best-performing action after adding some perturbation to the performance of each of its actions. The crux of our design is adding perturbations in a manner that leads to oracle-efficiency. We reduce this to designing a translation matrix, which translates a low dimensional vector with independent noise components into a high dimensional vector of perturbations on the learner’s action space. Our approach generalizes prior work on oracle-efficient online learning [11, 22, 27, 35], ranging from online combinatorial optimization, learning in simultaneous auctions, and contextual learning. Our auction-design framework considers an auctioneer learning an optimal auction rule in an online manner, every day observing an adversarially chosen vector of valuations. The auctioneer’s goal is to achieve revenue that competes with the revenue of the optimal auction in hindsight among those in some target class. We give oracle-efficient learning results for: (1) VCG auctions with bidder-specific reserves in single-parameter settings with matroid constraints, (2) envy-free item pricing in multi-item auctions with unlimited supply, and (3) s-level auctions of Morgenstern and Roughgarden [28] for singleitem settings. The last result implies good regret against the optimal overall auction when valuations are coming from a fast mixing Markov chain, that is independent across bidders. We also extend our results to the case when the learner observes side information on the bidders before running the auction (contextual learning). We present additional extensions to contextual learning and learning with approximate oracles, implemented by FPTAS or Maximal-in-Range algorithms. We provide further applications in online welfare maximization in multi-unit auctions and in no-regret learning in simultaneous item auctions, answering an open question from prior work. ∗Microsoft Research, New York, mdudik@microsoft.com †Computer Science Department, Carnegie Mellon University, nhaghtal@cs.cmu.edu ‡Microsoft Research, New York, haipeng@microsoft.com §Microsoft Research, New York, schapire@microsoft.com ¶Microsoft Research, New England, vasy@microsoft.com ‖Microsoft Research, New York, jenn@microsoft.com ar X iv :1 61 1. 01 68 8v 1 [ cs .L G ] 5 N ov 2 01 6

Oracle-Efficient Learning and Auction Design