The question "Can machines think?" is one that has fascinated people for a long time (see here for an amusing non-technical perspective on this question by E.B. White). This is pretty close to the question "Can machines learn?", which has been studied from different points of view by many researchers in computer science.
This course will give an introduction to some of the central topics in computational learning theory, a field which approaches the above question from a theoretical computer science perspective. We will study well-defined mathematical and computational 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 efficiency of learning in these models. We'll develop computationally efficient algorithms for certain learning problems, and will see why efficient algorithms are not likely to exist for other problems.
Instructor: Rocco Servedio
Instruction modality: On campus, in Computer Science Building room 451; however, lectures will be recorded and recordings will be made available to all enrolled students through Courseworks.
Time: Mon/Wed 8:40am-9:55am Eastern Time
Course email (for administrative issues; use Ed Discussion for subject matter questions): coms4252columbiaf21 at gmail dot com
This is a preliminary list of core topics. Other topics may be covered depending on how the semester progresses. Most topics will take several lectures. For more information, click on the "Lectures" tab above.