ECE 598MR: Statistical Learning Theory (Fall 2014)

About  |  Schedule  |  References  |  Coursework


Schedule

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 26
[notes]

Introduction, history, overview, and administrivia.

Thu, Aug 28
Tue, Sep 2
Thu, Sep 4
[notes]

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

Tue, Sep 9
[notes]

Formulation of the learning problem: concept and function learning; realizable case; Probably Approximately Correct (PAC) learning.

Thu, Sep 11
[notes]

Formulation of the learning problem, continued: agnostic (model-free) learning; consistency; Empirical Risk Minimization

Tue, Sep 16
Thu, Sep 18
[notes]

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, Sep 23
[notes]
Vapnik-Chervonenkis classes: shatter coefficients; VC dimension; examples of VC classes; Sauer-Shelah lemma; implication for Rademacher averages

RIP Alexey Chervonenkis

Thu, Sep 25
[notes]
Binary classification: bounds for simple VC classes (linear and generalized linear discriminant rules); surrogate loss functions; margin-based bounds
Tue, Sep 30
Tue, Oct 7
Thu, Oct 9
[notes]
Binary classification, continued: reproducing kernel Hilbert spaces and kernel machines; convex risk minimization
Thu, Oct 2
No class: Allerton Conference
Tue, Oct 14
Thu, Oct 16
Tue, Oct 21
Thu, Oct 23
[notes]
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)
Tue, Oct 28
Thu, Oct 30
[notes]
Regression with quadratic loss
  • Presentation loosely based on Chapter 8 of Cucker and Zhou.

Tue, Nov 4
Thu, Nov 6
[notes]
Regression with quadratic loss: learning without concentration
Tue, Nov 18
Thu, Nov 20
Tue, Dec 2
Thu, Dec 4
[notes]
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 25
Thu, Nov 27
No class: Thanksgiving break