Concentration inequalities in learning theory (tutorial)

Concentration inequalities estimate deviations of functions of independent random variables from their expectation. Such inequalities have countless applications and they play a fundamental role in the analysis of learning algorithms and statistical procedures. In these lectures we present some of the basic ideas and some useful inequalities. We discuss in detail the so-called “entropy method” for deriving general concentration inequalities. We discuss applications to empirical processes and learning theory.