MATH 233A: Concentration of measure

Stanford University, Autumn 2018

Lectures: Mon/Wed/Fri 9:30 - 10:20 PM, McCullough 115
Instructor: Jan Vondrak (jvondrak@stanford.edu)

Textbook: Boucheron, Lugosi, Massart: Concentration of measure (a nonasymptotic theory of independence) .
Lecture notes: maintained by Yuval Wigderson
Additional material: Lecture notes with Jiri Matousek : Check Chapter 8 for additional information on martingales and concentration of Lipschitz functions.

Course description:

Classical inequalities: Chernoff-Hoeffding, Bernstein's inequality, Martingales, Azuma's inequality
Functions of independent r.v.'s: Effron-Stein, bounded differences, self-bounding functions
Information inequalities: properties of entropy, Han's inequality, isoperimetry on the hypercube
Log-Sobolev inequalities, hypercontractivity, Bonami-Beckner inequality
The entropy method for self-bounding functions, Talagrand's inequality
etc. depending on how far we get

Prerequisites: Basic probability background.