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.
Problem sets:
Problem Set 1
Problem Set 2
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.