Comp 250-CLT: Computational Learning Theory
Department of Computer Science
Tufts University
Spring 2006

Syllabus:

Prerequisites:

Times and Location:

Instructor:

Activities & Grading

• Lecture notes: students will take turns writing formal lecture notes that will be handed back to the class. Note will be written using the Latex package.
  Latex templates for lecture notes template.tex and 250clt-style.tex
• Paper presentations: students will read papers from recent literature and present these to the class; 2-4 presentations are expected. A report (1-2 pages) on the paper is due with the presentation. The presentation and report should explain the main results, and highlights from proofs or constructions in the papers.
• There will be 3-4 assignments involving problem solving and proofs.
• A take home exam will take place at the end of the semester.
• Each of the 4 activities contributes 25% to the grade.

Texts/Reference

• We will be using different sources from the first two texts below and articles.
• M.J. Kearns and U.V. Vazirani. An Introduction to Computational Learning Theory , MIT Press, Cambridge, MA, 1994.
• N. Cristianini and J. Shawe-Taylor. An introduction to support vector machines : and other kernel-based learning methods. Cambridge University Press, 2000.
• M. Anthony and N. Biggs. Computational Learning Theory, Cambridge University Press, 1992.

Papers for presentations and Discussion

• PAC Learning
  • The following papers are avilable from Warmuth
    Sample Compression, Learnability, and the Vapnik-Chervonenkis Dimension, Machine Learning, Vol.21 (3), pp. 269--304, December 1995. Floyd and Warmuth.
  • A decision-theoretic generalization of on-line learning and an application to boosting. Yoav Freund and Robert E. Schapire. Journal of Computer and System Sciences, 55(1):119-139, 1997.
  • The following papers are avilable from Klivans
    Learnability and Automatizability Misha Alekhnovich, Mark Braverman, Vitaly Feldman, Adam Klivans, Toniann Pitassi. Proceedings of the 45th Foundations of Computer Science (FOCS), 2004.
  • The following papers are avilable from COLT 05 LNAI 3559
    On Attribute Efficient and Non-adaptive Learning of Parities and DNF Expressions, Vitaly Feldman.
  • The following papers are avilable from COLT 04 LNAI 3120
    Polynomial time Prediction Strategy with almost Optimal Mistake Probability, Nader Bshouty.
    PExact = Exact Learning, Dmitry Gavinsky and Avi Owshanko.
    Toward Attribute Efficient Learning of Decision Lists and Parities, Adam R. Klivans and Rocco A. Servedio.
    Learning Intersections of Halfspaces with a Margin, Adam R. Klivans and Rocco A. Servedio.
    A New PAC Bound for Intersection-Closed Concept Classes, Peter Auer and Ronald Ortner.
• On line Learning and Active Learning COLT 05 LNAI 3559
  • A New Perspective on an Old Perceptron Algorithm, Shai Shalev-Shwartz and Yoram Singer.
  • Analysis of Perceptron-Based Active Learning, by Sanjoy Dasgupta, Adam Tauman Kalai, Claire Monteleoni.
• Learning for Ranking COLT 05 LNAI 3559
  • Learnability of Bipartite Ranking Functions, by Shivani Agarwal and Dan Roth.
  • Margin-Based Ranking Meets Boosting in the Middle Cynthia Rudin, Corinna Cortes, Mehryar Mohri, Robert E. Schapire
• Unsupervised learning, and semi-supervised learning
  • A Framework for Statistical Clustering with a Constant Time Approximation Algorithms for K-Median Clustering, by Shai Ben-David. COLT 04 LNAI 3120
  • A PAC-Style Model for Learning from Labeled and Unlabeled Data, by Maria-Florina Balcan and Avrim Blum. COLT 05 LNAI 3559
  • Generalization Error Bounds Using Unlabeled Data, by Matti Kääriäinen. COLT 05 LNAI 3559
• Kernels Methods
  • Maximum Margin Algorithms with Boolean Kernels, by Roni Khardon and Rocco Servedio. Journal of Machine Learning Research (JMLR) Volume 6 pp 1405--1429, 2005.
  • On Kernels, Margins, and Low-Dimensional Mappings, by Maria-Florina Balcan, Avrim Blum, Santosh Vempala ALT 04 LNAI 3224
  • General Polynomial Time Decomposition Algorithms, by Nikolas List and Hans Ulrich Simon COLT 05 LNAI 3559
  • Leaving the Span, by Manfred K. Warmuth and S.V.N. Vishwanathan COLT 05 LNAI 3559