TY - GEN
T1 - Oracle-efficient online learning and auction design
AU - Dudik, Miroslav
AU - Haghtalab, Nika
AU - Luo, Haipeng
AU - Schapire, Robert E.
AU - Syrgkanis, Vasilis
AU - Vaughan, Jennifer Wortman
N1 - Publisher Copyright:
© 2017 IEEE.
PY - 2017/11/10
Y1 - 2017/11/10
N2 - 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].
AB - 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].
KW - Follow-the-Perturbed-Leader
KW - auction design
KW - online learning
KW - revenue maximization
UR - http://www.scopus.com/inward/record.url?scp=85041112989&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85041112989&partnerID=8YFLogxK
U2 - 10.1109/FOCS.2017.55
DO - 10.1109/FOCS.2017.55
M3 - Conference contribution
AN - SCOPUS:85041112989
T3 - Annual Symposium on Foundations of Computer Science - Proceedings
SP - 528
EP - 539
BT - Proceedings - 58th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2017
PB - IEEE Computer Society
T2 - 58th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2017
Y2 - 15 October 2017 through 17 October 2017
ER -