Academics / Courses / DescriptionsCOMP_SCI 496: Computational Learning Theory
VIEW ALL COURSE TIMES AND SESSIONS
Prerequisites
COMP_SCI 335 COMP_SCI 336 AND COMP_SCI 349 (or email the instructor if you have done upper level math courses)Description
This course will introduce some of the central topics in computational learning theory, a field which approaches the question "whether machines can learn" from the perspective of theoretical computer science. We will study well defined and rigorous mathematical models of learning where it will be possible to give precise and rigorous analysis of learning problems and algorithms. A big focus of the course will be the computational efficiency of learning in these models. We will develop some provably efficient algorithms and explain why such provable algorithms are unlikely for other models.
We will only cover topics which permit a mathematically rigorous analysis and hence mathematical maturity is absolutely necessary. In particular, some familiarity with basic probability (such as linearity of expectation) and basic linear algebra will be necessary. Also, the emphasis of the course will be on proofs, so if you are in this course, you should enjoy proofs and math.
- This course satisfies the Theory Depth Requirement.
INSTRUCTOR: Prof. Lev Reyzin
LIST OF COURSE TOPICS:
- Query learning
- PAC learning and VC theory
- Occam's razor
- Online learning
- Boosting
- Support vector machines
- Bandit algorithms
- Statistical queries
- Rademacher complexity
- Neural networks