Learning Hurdles for Sleeping Experts

Varun Kanade, Thomas Steinke

Abstract: We study the online decision problem where the set of available actions varies over time, also called the sleeping experts problem. We consider the setting where the performance comparison is made with respect to the best ordering of actions in hindsight. In this paper, both the payoff function and the availability of actions is adversarial. Kleinberg et al. (2008) gave a computationally efficient no-regret algorithm in the setting where payoffs are stochastic. Kanade et al. (2009) gave an efficient no-regret algorithm in the setting where action availability is stochastic. However, the question of whether there exists a computationally efficient no-regret algorithm in the adversarial setting was posed as an open problem by Kleinberg et al. (2008). We show that such an algorithm would imply an algorithm for PAC learning DNF, a long standing important open problem. We also show that a related problem, the gambling problem, posed as an open problem by Abernethy (2010) is related to agnostically learning halfspaces, albeit under restricted distributions.

Published: ITCS 2012
Invited to special issue of ACM Transactions on Computation Theory
Conference Version: [ACM site]
Journal Version: [ACM site]
Draft: [ECCC]
Bibtex:  
@inproceedings{KanadeSteinke2012,
   author = {Varun Kanade and Thomas Steinke},
   title = {Learning Hurdles for Sleeping Experts},
   booktitle = {Proceedings of the 3rd Innovations in Theoretical Computer Science Conference},
   series = {ITCS '12},
   year = {2012},
   isbn = {978-1-4503-1115-1},
   location = {Cambridge, Massachusetts},
   pages = {11--18},
   numpages = {8},
   url = {http://doi.acm.org/10.1145/2090236.2090238},
   doi = {10.1145/2090236.2090238},
   acmid = {2090238},
   publisher = {ACM},
   address = {New York, NY, USA},
   keywords = {lower bounds, online learning, sleeping experts},
}
 

Last updated on 1 March 2012 by Thomas Steinke.