Introduction, history, overview, and administrivia.
Concentration inequalities: Markov, Chebyshev, McDiarmid (bounded differences inequality), examples
Formulation of the learning problem: concept and function learning; agnostic (model-free) learning; consistency; Probably Approximately Correct (PAC) learning; 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