| Announcement(s): |
|
|
Syllabus:
Probabilistic and adversarial models of machine learning. Development and analysis of machine learning principles and algorithms, their computational complexity, data complexity and convergence properties. Computational and cryptographic limitations on algorithms for machine learning. Core results and recent developments in this field.
Prerequisites: COMP 160; EE 104 or MATH 162; COMP 170 recommended but not required. Or permission of instructor.
Times and Location:
Tuesday/Thursday 10:30-11:45, Halligan Hall 106
Instructor:
Roni Khardon
Office: Halligan 230
Office Hours: Mon 4-5 or by arrangement
Phone: 1-617-627-5290
Email: roni@cs.tufts.edu
What is this course about?
Machine learning algorithms aim to "make sense of data", often
developing some generalizations that are useful for
future tasks, for example in classification, prediction, and control.
Computational Learning Theory investigates such tasks and algorithms
in a formal framework. The focus is to identify performance guarantees
for algorithms in terms of computational complexity (how long it takes
to run), data complexity (how much data is required), and convergence
properties (how well does the result/output of the learning algorithm
perform).
Alternatively, for some machine learning
problems we seek lower bounds on the amount of resources for any
potential algorithm.
Models vary from adversarial worst case scenarios,
to statistical settings where a random process generates the data, and
to interactive settings where the learner can control the flow of
data.
The course will mix taught classes with seminar type reading of
research papers of recent topics.
This semester: In addition to a review of core topics,
this semester we will explore online convex optimization, bandit
problems, PAC-Bayes theorems, learning theory for pattern recognition
models (GMM, HMM), matrix completion problems, and maybe other topics.
For reference
see
details from 2008 offering
Policy on collaboration on homework assignments: You may discuss the problems and general ideas about their solutions with other students, and similarly you may consult other textbooks or the web. However, you must work out the details on your own and write the solution on your own. Every such collaboration (either getting help of giving help) and every use of text or electronic sources must be clearly cited and acknowledged in the submitted homework. Failure to follow these guidelines will result in disciplinary action for all parties involved. Any questions? for this and other issues concerning academic integrity please consult the booklet available from the office of the Dean of Student Affairs.
. The assignment writeup linked below has been
updated.