Search | Directories | Reference Tools
UW Home > Discover UW > Student Guide > Course Catalog 

Instructor Class Description

Time Schedule:

Ofer Dekel
CSE 522
Seattle Campus

Design and Analysis of Algorithms II

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.

Class description

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

Recommended preparation

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


The information above is intended to be helpful in choosing courses. Because the instructor may further develop his/her plans for this course, its characteristics are subject to change without notice. In most cases, the official course syllabus will be distributed on the first day of class.
Last Update by Ofer Dekel
Date: 12/15/2010