Introduction, history, overview, and administrivia.
Concentration inequalities: Markov, Chebyshev, McDiarmid (bounded differences inequality), examples
Formulation of the learning problem: concept and function learning; realizable case; Probably Approximately Correct (PAC) learning.
Formulation of the learning problem, continued: agnostic (model-free) learning; consistency; Empirical Risk Minimization
Empirical Risk Minimization: abstract risk bounds and Rademacher averages -- stochastic inequalities for ERM; Rademacher averages (structural results, Finite Class Lemma); introduction to VC classes