PENN CIS 620, FALL 2008: COMPUTATIONAL LEARNING THEORY

Prof. Michael Kearns and Dr. Koby Crammer
mkearns@cis.upenn.edu, crammer@cis.upenn.edu
Tuesdays 12-3 PM (First meeting Sep 9)
315 Levine Hall (note change of room)

URL for this page: www.cis.upenn.edu/~mkearns/teaching/COLT

COURSE DESCRIPTION

This course is an introduction to Computational Learning Theory, a field which attempts to provide algorithmic, complexity-theoretic and statistical foundations to modern machine learning.

The first part of the course will closely follow portions of An Introduction to Computational Learning Theory, by M. Kearns and U. Vazirani (MIT Press). We will cover perhaps 6 or 7 of the chapters in K&V over (approximately) the first half of the course, often supplementing with additional readings and materials. Copies of K&V will be available at the Penn bookstore. The second portion of the course will focus on a number of more recent but still fundamental topics in learning theory not covered in K&V.

The course will give a broad overview of the kinds of problems and techniques typically studied in Computational Learning Theory, and provide a basic arsenal of powerful mathematical tools for analyzing machine learning problems.

Topics to be covered include:

  • Basics of the Probably Approximately Correct (PAC) Learning Model
  • Occam's Razor, Compression and Learning
  • Uniform Convergence and the Vapnik-Chervonenkis Dimension
  • Learning in the Presence of Noise and Statistical Query Learning
  • Learning and Cryptography
  • Query Models
  • Boosting
  • Online and No-Regret Learning
  • Discrete Fourier Methods in Learning
  • Active Learning
  • Agnostic Learning
  • PAC-style Analyses in Reinforcement Learning
  • PAC-style Analyses in Probabilistic Inference

    Notes on related courses:

  • There will sufficiently little overlap that interested students should be able to fruitfully (and if you're really a zealot, simultaneously) take both this course and the graduate machine learning course CIS 520, which has a somewhat more applied flavor. CIS 520 is not a prerequisite for this course.
  • There are several nice related courses at other instituions, including those of Avrim Blum at CMU,   Rocco Servedio at Columbia,   Rob Schapire at Princeton   Adam Klivans at UT Austin, and Adam Kalai at the Weizmann.

    COURSE FORMAT, REQUIREMENTS, AND PREREQUISITES

    Much of the course will be in fairly traditional "chalk talk" lecture format, but with ample opportunity for discussion, participation, and critique. The course will meet once a week on Mondays from 12 to 3. Lunch will be served.

    There are no official prerequisites, but participants should be comfortable with the basics of the design and analysis of algorithms, computational complexity, statistics and probability theory. The level of the material is such that the typical graduate student in computer science or statistics would have an appropriate background; strong undergraduates are also encouraged to join. Auditors and occasional participants are welcome.

    The course requirements for registered students are active in-class participation, an occasional problem set, possibly leading a class discussion, and a final project.

    DETAILED MEETING/TOPIC SCHEDULE
    The exact timing and set of topics below will depend on our progress and will be updated as we proceed. "[MK]" indicates lecture by Prof. Kearns; "[KC]" by Dr. Crammer.

    Tue Sep 9
    [MK] In the first meeting, we will go over course mechanics and present a course overview, then immediately begin investigating the Probably Approximately Correct (PAC) model of learning.

    READING: K&V Chapter 1.

    Tue Sep 16
    [MK] Introduction to PAC learning, continued; Occam's Razor, sample complexity and learning curves.

    READING: K&V Chapters 1 and 2.

    HOMEWORK #1, DUE AS HARDCOPY IN CLASS SEP 23: Solve the following problems from K&V: 1.1, 1.3, 2.3, 2.4. You are free to collaborate on the homework assignments, but please turn in separate write-ups and acknowledge your collaborations. Please do not attempt to look up solutions in the literature.

    Tue Sep 23
    [MK] Occam's Razor, continued; VC dimension.

    READING: K&V Chapters 2 and 3.

    Tue Sep 30
    [MK] VC dimension, continued; Structural Risk Minimization; generalizations.

    READING: K&V Chapter 3.

    Tue Oct 7
    [KC] Better generalization bounds: Rademacher complexity, PAC-Bayes.

    READING: Supplementary readings:

  • Stability and Generalization, Bousquet and Elisseeff.
  • Rademacher and Gaussian Complexities: Risk Bounds and Structural Results. Bartlett and Mendelson.

    Tue Oct 14
    Fall break, no class.

    Tue Oct 21
    [MK] Learning with noise and errors; SQ learning.

    READING: K&V Chapter 5; supplementary reading:

  • Weakly Learning DNF and Characterizing Statistical Query Learning Using Fourier Analysis. Blum, Furst, Jackson, Kearns, Mansour, Rudich.

    HOMEWORK #2, DUE AS HARDCOPY IN CLASS NOV 7: Solve the following problems from K&V: 3.1, 3.5, 5.1, 5.3. You are free to collaborate on the homework assignments, but please turn in separate write-ups and acknowledge your collaborations. Please do not attempt to look up solutions in the literature.

    Tue Oct 28
    [KC] Boosting

    READING: K&V Chapter 4; supplementary readings.

    CHANGE OF DATE: Tue Nov 4 ===> Fri Nov 7
    [MK] In honor of Election Day, this week's class has been MOVED from Tuesday to Friday, Nov 7 from 12-2PM in Room 337 Moore (we only have the room for two hours). We will cover a complementary pair of results, first showing that finite state automata cannot be learned in the PAC model (under standard cryptographic assumptions), then showing that they can be learned if the model is augmented with membership queries. HW2 will be due in class Nov 7.

    READING: K&V Chapters 6,7,8.

    Tue Nov 11
    [KC] Online and no-regret learning.

    READING: Supplementary readings.

    INFORMATION ON COURSE PROJECTS.
    For those of you registered for credit in the course, your final assignment will be a course project, for which you have three choices:

  • Research Paper. For a research paper, you should either choose an open problem related to the models we have examined in the class and write up your attempts to solve it; or you should write a paper introducing a new model of learning that extends or modifies those we examined in class, and ideally motivate and illustrate your model with some initial results. For those going the "open problem" route, you must both choose your own problem (don't ask me for problems --- that's part of doing research), and do enough of a literature search to make sure it hasn't been solved already. Ditto for finding and researching your own new model.
  • Final Problem Set. Here you can choose and solve any 8 problems from K&V that were not already assigned in the homeworks. Try to pick a mix of difficulty levels.
  • Literature Survey/Synthesis. Here you may pick a few related papers from the learning theory literature, and do a write-up surveying their models and results, and relating the papers to each other. Try not to simply regurgitate what's in the papers themselves.

    The deadline for final projects will be December 20, via email to Prof Kearns.

    Tue Nov 18
    [KC] Online and no-regret learning, continued.

    READING: Supplementary readings.

    Tue Nov 25
    [MK] COLT methods in reinforcement learning.

    READING: Supplementary readings.

    Tue Dec 2
    [MK] Topic TBD.

    READING: Supplementary readings.