- Instructor: Avrim Blum
- Time: MW 1:30-2:50
- Place: Wean 4615A
- 12 Units, 1 CU

**Text:**
*
An Introduction to Computational Learning Theory* by Michael Kearns
and Umesh Vazirani, plus papers and notes for topics not in the book.

**Office hours:** Just stop by my office or make an appointment.

Some ideas for presentations and projects.

- General Course Information
- Homework 1. Due January 21. Solutions.
- Homework 2. Due Feb 4. Some clarifications. Solutions.
- Homework 3. Due Feb 16. Solutions.
- Homework 4. Due March 4. Some clarifications. Solutions.
- Homework 5. Due March 18. Solutions.
- Homework 6: do exercise 6.2 (p.141) in the book. Due April 8. Solutions.
- Probabilistic inequalities.

- 01/12:Overview, basic definitions, the consistency model
- 01/14:Consistency for simple neural net is NP-hard. Intro to Mistake-Bound model
- 01/19:Decision lists, Halving alg, Std Opt, Perceptron Alg
- 01/21:The Weighted-Majority Algorithm, Randomized Weighted Majority
- 01/26:Randomized WM contd, 2-player games, the Winnow algorithm
- 01/28:Learning from string-valued features, intro to PAC model
- 02/02:MB==>PAC, Occam's razor
- 02/04:Occam's razor cont, intro to VC-dim and C[m]. See also the slides.
- 02/09:VC-dim and splitting number: upper and lower bound proofs.
- 02/11:Probabilistic inequalities and proof of Chernoff, intro to weak-learning.
- 02/16:Weak and strong learning, Adaboost. Here are Yoav Freund's slides
- 02/18:Learning with noise.
- 02/23:The Statistical Query model.
- 02/25:Characterizing SQs with Fourier analysis.
- 03/04:Fourier analysis, intro to Memb queries, weak-learning DNF.
- 03/09:Finding large Fourier coeffs, Bshouty's alg for learning XOR of terms.
- 03/11:Learning deterministic finite-state environments. Text and Slides.
- 03/16:Learning finite-state environments contd, Intro to HMMs.
- 03/18:HMMs and weak learning of monotone functions.
- 03/30:Hardness results for learning based on cryptography and vice versa.
- 04/01:Query-by-Committee [Kamal]. Paper by Freund et al.
- 04/06:Probabilistic concepts [Haiqin]. Paper by Kearns & Schaipre.
- 04/08:The EM algorithm [Dimitris]. Paper by Xu and Jordan.
- 04/13:VC-dimension and "margins" [Goran]. Paper by Schapire et al.
- 04/15:Bias and variance [Chuck].
- 04/20:Piecemeal exploration [Michael].
- 04/22:Intro to Reinforcement Learning [Jovan].
- 04/27:Combining Reinforcement Learning with function approximation [Bryan]. Papers by Geoff Gordon: 1, 2, 3.
- 04/29:Projects [Paul, Jason, John].

- Blum and Rivest: "Training a 3-node neural net is NP-complete"
- Selection from Minsky and Papert,
*Perceptrons*. - Littlestone, "Learning Quickly when Irrelevant Attributes abound..."
- Littlestone and Warmuth, "The Weighted Majority Algorithm"
- Blum: "On-Line Algorithms in Machine Learning" (a survey).
- Blum, Furst, Kearns, Lipton: Cryptographic Primitives Based on Hard Learning Problems.