<html><head><style type='text/css'>p { margin: 0; }</style></head><body><div style='font-family: arial,helvetica,sans-serif; font-size: 10pt; color: #000000'>Haipeng Luo will present his research seminar/general exam on Monday May 13 at <br>2PM in Room 402.  The members of his committee are:  Rob Schapire, Sebastien <br>Bubeck (ORFE), and Moses Charikar.  Everyone is invited to attend his talk and <br>those faculty wishing to remain for the oral exam following are welcome to do so. <br>His abstract and reading list follow below.<br><br><hr id="zwchr"><div style="color:#000;font-weight:normal;font-style:normal;text-decoration:none;font-family:Helvetica,Arial,sans-serif;font-size:12pt;"><div dir="ltr"><br><div><div style="font-family:arial,sans-serif;font-size:13px"><b>Title</b>: Online Learning with Unknown Time Horizon</div><div style="font-family:arial,sans-serif;font-size:13px"><br></div><div style="font-family:arial,sans-serif;font-size:13px"><b>Abstract</b>: We consider online learning when the time horizon T is unknown. We apply a minimax analysis, beginning with the fixed horizon case, and then moving on to two unknown-horizon settings, one that assumes the horizon is chosen randomly according to some known distribution, and the other which allows the adversary full control over the horizon. For the random horizon setting with restricted losses, we derive a fully optimal minimax algorithm. And for the adversarial horizon setting, we prove a nontrivial lower bound which shows that the adversary obtains strictly more power than when the horizon is fixed and known. Based on the minimax solution of the random horizon setting, we then propose a new adaptive algorithm which “pretends” that the horizon is drawn from a distribution from a special family, but no matter how the actual horizon is chosen, the worst-case regret is bounded by O(sqrt(T*lnN)), where N is the number of actions. Furthermore, the constant in our regret bound approaches 1, which is better than the best previously known bound for this setting (as far as we know). Moreover, our algorithm can be generalized to other games, such as predicting with expert advice.</div>
<div style="font-family:arial,sans-serif;font-size:13px"><br></div><div style="font-family:arial,sans-serif;font-size:13px"><br></div><div style="font-family:arial,sans-serif;font-size:13px"><b>Reading List</b>:</div><div style="font-family:arial,sans-serif;font-size:13px">
Textbooks:</div><div style="font-family:arial,sans-serif;font-size:13px">1. Mehryar Mohri, Afshin Rostamizadeh and Ameet Talwalkar. Foundations of Machine Learning. MIT Press, 2012.</div><div style="font-family:arial,sans-serif;font-size:13px">
2. Nicolo Cesa-Bianchi and Gabor Lugosi. Prediction, Learning, and Games (Chapter 2,4,6,7). Cambridge University Press, 2006.</div><div style="font-family:arial,sans-serif;font-size:13px"><br></div><div style="font-family:arial,sans-serif;font-size:13px">
Papers:</div><div style="font-family:arial,sans-serif;font-size:13px">3. Jacob Abernethy and Manfred K. Warmuth. Repeated games against budgeted adversaries. In Advances in Neural Information Processing Systems 24, 2010.</div>
<div style="font-family:arial,sans-serif;font-size:13px">4. Jacob Abernethy, Manfred K. Warmuth, and Joel Yellin. Optimal strategies from random walks. In Proceedings of the 21st Annual Conference on Learning Theory, 2008.</div>
<div style="font-family:arial,sans-serif;font-size:13px">5. Jacob Abernethy, Alekh Agarwal, Peter L. Bartlett, Alexander Rakhlin. A Stochastic View of Optimal Regret through Minimax Duality. arXiv:0903.5328, 2009.</div><div style="font-family:arial,sans-serif;font-size:13px">
6. Peter Auer, Nicolo Cesa-Bianchi, and Claudio Gentile. Adaptive and self-confident on-line learning algorithms. Journal of Computer and System Sciences, 64(1):48–75, 2002.</div><div style="font-family:arial,sans-serif;font-size:13px">
7. Nicolo Cesa-Bianchi, Yoav Freund, David P. Helmbold, David Haussler, Robert E. Schapire, and Manfred K. Warmuth. How to use expert advice. Journal of the ACM, 44(3):427–485, May 1997.</div><div style="font-family:arial,sans-serif;font-size:13px">
8. Kamalika Chaudhuri, Yoav Freund, and Daniel Hsu. A parameter-free hedging algorithm. arXiv:0903.2851, 2009.</div><div style="font-family:arial,sans-serif;font-size:13px">9. Yoav Freund and Robert E. Schapire. Adaptive game playing using multiplicative weights. Games and Economic Behavior, 29:79–103, 1999.</div>
<div style="font-family:arial,sans-serif;font-size:13px">10. David Haussler, Jyrki Kivinen, and Manfred K. Warmuth. Sequential prediction of individual sequences under general loss functions. IEEE Transactions on Neural Networks, 10(6):1291–1304, 1999.</div>
<div style="font-family:arial,sans-serif;font-size:13px">11. Nick Littlestone and Manfred Warmuth. The weighted majority algorithm. In 30th Annual Symposium on Foundations of Computer Science, pages 256–261, 1989.</div><div style="font-family:arial,sans-serif;font-size:13px">
12. Alexander Rakhlin, Ohad Shamir, Karthik Sridharan. Relax and Randomize: From Value to Algorithms. arXiv:1204.0870, 2012.</div><div style="font-family:arial,sans-serif;font-size:13px">13. V. G. Vovk. A game of prediction with expert advice. Journal of Computer and System Sciences, 56(2):153–173, April 1998. </div>
</div></div>
</div><br></div></body></html>