From ResearchWiki

Contents 1 CS7941: Online Learning 1.1 Participants 1.2 Schedule 1.3 Possible Papers 1.4 Paper Summaries 1.5 Past Semesters

CS7941: Online Learning

Time: Fridays, 2-3:20

Location: MEB 3105, except as noted

Topic: Online learning

Participants

• Hal Daumé III, Assistant Professor, School of Computing
• Seth Juarez, PhD Student, School of Computing
• Piyush Rai, PhD Student, School of Computing
• Youngjun Kim, PhD Student, School of Computing
• Arvind Agarwal, PhD Student, School of Computing
• Jiarong Jiang, PhD Student, School of Computing
• Avishek Saha, PhD Student, School of Computing
• Amit Goyal, PhD Student, School of Computing
• Ruihong Huang, PhD Student, School of Computing
• Ramesh Pinnamaneni, MS Student, School of Computing
• Jagadeesh Jagarlamudi, PhD Student, School of Computing
• Lalindra De Silva, PhD Student, School of Computing
• Abhishek Kumar, PhD Student, School of Computing
• Mike Cason, PhD Student, School of Computing

Schedule

Date	Papers	Presenter
Sep 04	Online Learning Survey by Avrim Blum	Hal
Sep 11	Learning Quickly when Irrelevant Attributes Abound: A New Linear-threshold Algorithm by Nick Littlestone	Sandeep and Shuying
Sep 18	The Weighted Majority Algorithm by Littlestone and Warmuth	Jagadeesh
Sep 25	Efficient algorithms for the online decision problem by Adam Kalai and Santosh Vempala	Seth
Oct 02	Online convex programming and generalized infinitesimal gradient ascent by M. Zinkevich	Jiarong and Mike
Oct 23	Confidence-Weighted Linear Classification by Mark Dredze, Koby Crammer and Fernando Pereira	Amit and Lalindra
Oct 30	Step Size-Adapted Online Support Vector Learning by Karatzoglou, Vishwanathan, Schraudolph, and Smola	Ramesh
Nov 06	A New Perspective on an Old Perceptron Algorithm by Shai Shalev-Shwartz and Yoram Singer	Youngjun and anyone who wants to be his team
Nov 13	Data-Driven Online to Batch Conversions by Ofer Dekel and Yoram Singer	Ruihong and Adam
Nov 20	[some bandit paper] by [some bandit paper author(s)] - kindly leave the bandit papers for me :)	Amrish & Avishek
Dec 04	Sparse Online Learning via Truncated Gradient by John Langford, Lihong Li and Tong Zhang	Abhishek and Piyush
Dec 11	[xxx] by xxx

Possible Papers

• Nick Littlestone, Learning Quickly when Irrelevant Attributes Abound: A New Linear-threshold Algorithm. Machine Learning 2:285--318, 1987. (The version pointed to here is the tech report UCSC-CRL-87-28.)

• Littlestone and Warmuth, The Weighted Majority Algorithm. Information and Computation 108(2):212-261, 1994.

• Nicolo Cesa-Bianchi, Yoav Freund, David Haussler, David Helmbold, Robert Schapire, and Manfred Warmuth, How to use expert advice, Journal of the ACM, 44(3):427-485, May 1997.

• Yoav Freund and Robert Schapire, Adaptive game playing using multiplicative weights, Games and Economic Behavior, 29:79-103, 1999.

• Adam Kalai and Santosh Vempala, Efficient algorithms for the online decision problem, COLT '03.

• Peter Auer, Nicolo Cesa-Bianchi, Yoav Freund, Robert Schapire: The Nonstochastic Multiarmed Bandit Problem, SIAM J. Comput. 32(1): 48-77 (2002).

• Online Geometric Optimization in the Bandit Setting Against an Adaptive Adversary. By Brendan McMahan and Avrim Blum. COLT '04.

• Abie Flaxman, Adam Tauman Kalai, and Brendan McMahan. Online Convex Optimization in the Bandit Setting: Gradient Descent Without a Gradient. In Proceedings of the Sixteenth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 385-394, 2005.

• M. Zinkevich. Online convex programming and generalized infinitesimal gradient ascent. In Twentieth International Conference on Machine Learning, 2003.

• Online Passive-Aggressive Algorithms. Koby Crammer, Ofer Dekel, Joseph Keshet, Shai Shalev-Shwartz, Yoram Singer

• Confidence-Weighted Linear Classification Mark Dredze, Koby Crammer and Fernando Pereira. Proceedings of the 25th International Conference on Machine Learning (ICML), 2008

• John Langford, Lihong Li and Tong Zhang. Sparse Online Learning via Truncated Gradient. Journal of Machine Learning Research, 10:777-801, 2009.

• Alexandros Karatzoglou, S.V.N. Vishwanathan, Nicol N. Schraudolph, and Alex J. Smola. Step Size-Adapted Online Support Vector Learning. In Proc. 8th Intl. Symp. Signal Processing & Applications, IEEE, 2005.

• Risk-Sensitive Online Learning. With E. Even-Dar and J. Wortman. ALT 2006.

• Ofer Dekel and Yoram Singer. Data-Driven Online to Batch Conversions NIPS*05

• Shai Shalev-Shwartz and Yoram Singer. A New Perspective on an Old Perceptron Algorithm. COLT*05

• Exponentiated Gradient versus Gradient Descent for Linear Predictors. Kivenen and Warmuth, information and computation 132, 163 (1997).

• The Epoch-Greedy Algorithm for Contextual Multi-armed Bandits John Langford and Tong Zhang, NIPS 2007.

Paper Summaries

Past Semesters

• Summer 2009 (Assorted Topics)
• Spring 2009 (Learning Theory)
• Fall 2008 (Graphical Models)
• Summer 2008 (Multitask Learning)
• Spring 2008 (Kernel Methods)
• Fall 2007 (Unsupervised Bayes)
• Summer 2007 (Manifolds)