Analysis of algorithms more sophisticated than those treated in CSE 521. Content varies and may include such topics as algebraic algorithms, combinational algorithms, techniques for proving lower bounds on complexity, and algorithms for special computing devices such as networks or formulas. Prerequisite: CSE major and CSE 521.
The title of this course is Learning Theory.
In this course, we will study the theoretical foundations of modern machine learning. We will analyze the inherent difficulty of learning problems and study the theoretical guarantees one can prove about a learning algorithm's ability to generalize. We will address these issues using tools from probability, statistics, game theory, and convex analysis. Most importantly, we will see how a formal understanding of learning problems and algorithms facilitates the design of better learning techniques. Topics include sample complexity (VC theory, Rademacher complexity), PAC-Bayes bounds, online regret minimization, online-to-batch conversion techniques, with applications to support vector machines, boosting, and online learning algorithms.
Student learning goals
General method of instruction
Prerequisites: This course assumes background in basic probability theory and linear algebra. Key mathematical concepts will be reviewed before they are used, but a certain level of mathematical maturity is expected.
Class assignments and grading
Grades will be based on homework and class participation