ECE 598MR: Statistical Learning Theory (Fall 2013)

About  |  Schedule  |  References  |  Coursework


The schedule will be updated and revised as the course progresses. Each topic will come with links to reference materials; key references will be highlighted.
Tue, Aug 27

Introduction, history, overview, and administrivia.

Thu, Aug 29
Tue, Sep 3
Thu, Sep 5

Concentration inequalities: Markov, Chebyshev, McDiarmid (bounded differences inequality), examples

Thu, Sep 05
Tue, Sep 10
Tue, Sep 17
Thu, Sep 19

Formulation of the learning problem: concept and function learning; agnostic (model-free) learning; consistency; Probably Approximately Correct (PAC) learning; Empirical Risk Minimization

Tue, Sep 24
Thu, Sep 26

Empirical Risk Minimization: abstract risk bounds and Rademacher averages -- stochastic inequalities for ERM; Rademacher averages (structural results, Finite Class Lemma); introduction to VC classes

Tue, Oct 01
Vapnik-Chervonenkis classes: shatter coefficients; VC dimension; examples of VC classes; Sauer-Shelah lemma; implication for Rademacher averages
Tue, Oct 08
Thu, Oct 10
Tue, Oct 15
Thu, Oct 17
Binary classification: bounds for simple VC classes (linear and generalized linear discriminant rules); margin-based bounds; reproducing kernel Hilbert spaces and kernel machines; convex risk minimization
Tue, Oct 22
Thu, Oct 24
Tue, Oct 29
Dimensionality reduction in Hilbert spaces: excess loss bounds for schemes with nonlinear (nearest-neighbor) encoders and linear decoders; applications to PCA, k-means, nonnegative matrix factorization, sparse coding; proof via Gaussian averages and comparison of Gaussian processes (Slepian's lemma)
Thu, Oct 31
Regression with quadratic loss
  • Presentation loosely based on Chapter 8 of Cucker and Zhou.
Tue, Nov 5
Matrix completion: guest lecture by Prof. Sewoong Oh
Tue, Nov 12
Thu, Nov 14
Tue, Nov 19
Minimax lower bounds: binary classification under a margin assumption; reduction to finite testing on a binary hypercube (Assouad's lemma); extra log factor for rich VC classes; information-theoretic methods (Fano's inequality)
Tue, Nov 26
Thu, Nov 28
No class: Thanksgiving break

Tue, Dec 3
Thue, Dec 5
Stochastic simulation via Rademacher bootstrap