Prerequisites
· A
solid background in algorithm design is necessary.
CPSC 420 or CPSC 500
would be ideal. CPSC 320
might not be adequate.
· A
solid background in probability or randomized algorithms would be very helpful.
MATH 418, STAT 547C
or CPSC 536N would be ideal. MATH 302
or STAT 302 might be
adequate.
· A
solid grasp of linear algebra would be very helpful.
MATH 310 would be
ideal. MATH 223 or MATH 307 might be adequate.
· Some
familiarity with complexity theory may be useful.
CPSC 421/501 may be may be
useful background, but it is not required.
· No
background in machine learning is required.
CPSC 540 and CPSC 340 have little overlap with
this course, but they may be useful background knowledge.
· No
background in statistics is required.
STAT 447B has some
overlap with this course, and it may be useful background knowledge.
To
determine whether your background is appropriate for this class, please look at
the lecture notes here,
here, here or here. This course will
be quite similar. If you can follow those notes, then your background is a good
fit for this course.
In
exceptional circumstances, undergraduate students may also be admitted into the
class.
Textbooks
The
primary text is:
· Shalev-Shwartz,
Ben-David. “Understanding
Machine Learning: From Theory to Algorithms”
Other
books relevant to portions of the course include:
· Mohri,
Rostamizadeh, Talwalkar “Foundations
of Machine Learning”
· Shalev-Shwartz
“Online Learning
and Online Convex Optimization”
· Hazan
“Introduction to Online Convex
Optimization”
· Kearns,
Vazirani “An
Introduction to Computational Learning Theory”
· Cesa-Bianchi,
Lugosi “Prediction,
Learning and Games”
· Schapire,
Freund “Boosting:
Foundations and Algorithms”
· Devroye,
Gyorfi, Lugosi “A
Probabilistic Theory of Pattern Recognition”
Evaluation
Roughly
4-5 problem-solving assignments and a final project.