The topic of this course will be the study of fluctuations of functions of many independent random variables. An archetypal example is the sum of independent identically distributed random variables. Concentration inequalities bound the probability that such a function differs from its expectation/median by more than a certain amount. The search for concentration inequalites has been a popular topic of research in the last deacades because of their importance in numeruos applications in discrete mathematics, statistical mechanics, information theory, high-dimensional geometry, and others.
In this course, which will closely follow the book of Boucheron, Lugosi, and Massart, we shall present several different approaches to answering the following general question: What kind of conditions should one impose on a function f of independent random variables X1, ..., Xn in order to obtain concentration bounds for f(X1, ..., Xn) around its mean or its median? In particular, we shall discuss: the martingale method, the entropy method, the transportation method, and concentration via isoperimetry.
Students enrolling in the course are expected to have working knowledge of basic probability theory.
S. Boucheron, G. Lugosi, and P. Massart, Concentration Inequalities: A Nonasymptotic Theory of Independence, Oxford University Press, 2013
D. P. Dubhashi and A. Panconesi, Concentration of Measure for the Analysis of Randomized Algorithms, Cambridge University Press, 2012
October 21
Markov's inequality; variance and Chebyshev's inequality; the log moment generating function and the Crámer–Chernoff method; Crámer transforms of normal, Poisson, and Bernoulli random variables and of sums of i.i.d. random variables; sub-Gaussian random variables
October 28
Lower bounds for tail probabilities of sums of i.i.d. random variables (Crámer's theorem); equivalent characterizations of sub-Gaussian random variables; Hoeffding's inequality; Bennett's inequality; Bernstein's inequality; the Johnson–Lindenstrauss lemma
November 4
Proof of the Johnson–Lindenstrauss lemma; Noga Alon's lower bound for the dimension in the Johnson–Lindenstraus lemma; conditional expectations and L
2-orthogonality of martingale differences; the Efron–Stein inequality; applications of the Efron–Stein bound for variance: functions with bounded differences, bin packing
November 11
Further applications of the Efron–Stein inequality: longest common subsequence, Rademacher averages, first passage percolation, the largest eigenvalue of a random symmetric matrix, minimum weight spanning tree; self-bounding functions
November 18
Examples of self-bounding functions: increasing subsequences, the number of distinct values in a discrete sample; a convex Poincaré inequality; the largest singular value of a random matrix; two approaches to obtaining exponential bounds on tail probabilities via the Efron–Stein inequality
November 25
Gaussian Poincaré inequality; self-information and Shannon's entropy; Kullback–Leibler divergence (relative entropy); basic properties of entropy; Han's inequality; edge-isoperimetry in the hypercube and influences
December 2
Edge-isoperimetry in the hypercube and influences: Han's inequality versus the Efron–Stein inequality; the entropy of a nonnegative random variable; entropy and concentration: a sketch of Herbst's argument; sub-additivity of entropy (discrete case); Han's inequality for relative entropies
December 9
Influences under non-uniform product distribution; dual characterization of entropy; sub-additivity of entropy (general case); logarithmic Sobolev inequality for the hypercube; Herbst's argument; concentration inequalities for functions of independent Rademacher variables
December 16
Shearer's lemma and the maximum number of independent sets in regular bipartite graphs (Kahn's theorem); Gaussian logarithmic Sobolev inequality; the Tsirelson–Ibragimov–Sudakov inequality; the bounded differenes inequality; Bregman divergence
December 23
The mean minimizes the expected Bregman divergence; the lenght of a sum of random vectors via bounded differences inequality; a modified logarithmic Sobolev inqequality; a strengthening of the bounded differences inequality; concentration of the largest eigenvalue of a symmetric random matrix; concentration inequalities for self-bounding functions; the maximum degree of G(n,p)
December 30
Isoperimetry and concentration of Lipschitz functions; Lévy's inequalities; the classical isoperimetric inequality in ℝ
n; the Brunn–Minkowski inequality; vertex isoperimetry in the hypercube (Harper's theorem, without full proof); Talagrand's convex distance inequality
January 6
Concentration inequalities for functions with (non-uniformly) bounded differences via Talagrand's inequality; traveling salesman problem for random points in the unit square; coupling distance between probability measures; transportation cost inequalities and isoperimetry
January 13
Pinsker's inequality; tensorization of transportation cost; bounded differences inequality revisited; quadratic transportation cost; logarithmic moment generating function and Kullback–Leibler divergence; Marton's theorem