
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.
Machine learning has matured and expanded over the last two decades
and is now used extensively as a tool in many application areas.
Increasingly, theory and analysis are used to guide the development of successful algorithms and systems.
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,
when such guarantees do not exist, we might
aim to show that learning is impossible by proving
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.
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:
(D+ Block)
TR 10:3011:45,
Lane Hall 100A
Instructor:
Roni Khardon
Office: Halligan 230
Office Hours: TBA
Phone: 16176275290
Email: roni@cs.tufts.edu
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.
Type  What  Due Date 
Lecture 1  Introduction to CLT 