• Announcements,Reading and Homework
• Overview and Prerequisites
• Grading and Requirements
• Schedule of Lectures

The question "Can machines learn from experience?" is one that has fascinated people for a long time. Over the past few decades, many researchers in computer science have studied this question from a range of applied and theoretical perspectives. This course will give an introductiion to some of the central topics in computation learing theory. We will study well-defined mathematical models of learning in which it is possible to give precise and rigorous analyses of learning problems and learning algorithms. A big focus of the course will be the computational efficiencey of learning in these models. We'll develop computationally efficient algorithms for certain learning problems, and will show why efficient algorithms are not likely to exist for other problems.

This is a preliminary list of "core" topics. Other topics may be covered as well depending on how the semester progresses. Some topics will take more than one lecture.

• Introduction: what is computational learning theory (and why)?
• The online mistake-bound learning model. Online algorithms for simple concept classes.
• General algorithms for online learning. Lower bounds for online learning.
• The Probably Approximately Correct (PAC) learning model: definition and examples. Online to PAC conversions.
• Occam's Razor: learning by finding a consistent hypothesis.
• The VC dimension and uniform convergence.
• Weak versus strong learning: boosting algorithms.
• Hardness results for efficient learning based on cryptography.
• PAC learning for noisy data. Malicious noise and classificatioin noise. Learning from Statistical Queries.
• Exact learning from membership and equivalence queries. Learning monotone DNF and learning finite automata.

You should be familiar with the following topics.