• View
• Edit
• History
• Print

Oracle-efficient Online Learning And Applications To Auction Design

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 example, we discuss applications of our oracle-efficient learning results to the adaptive optimization of a large class of auctions, including (1) VCG auctions with bidder-specific reserves in single-parameter settings, (2) envy-free item pricing in multi-item auctions, and (3) Myerson-like auctions for single-item settings.

Bio:

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 interests include machine learning theory, computational aspects of economics, and algorithms. Nika is a recipient of the IBM and Microsoft Research Ph.D. fellowships.