E2 207 Concentration Inequalities (Aug-Dec 2017)

Instructor: Himanshu Tyagi

Latest Announcements

  • Homework 3 posted. Due on December 4.
  • Suggested list of course projects is available here. Please confirm your choice by October 23.
  • Homework 2 posted. Due in the class on November 1.
  • Homework 1 posted. Due in the class on September 11.
  • First class on Monday, August 7 at 2:00pm in ECE 1.08

Time & Venue

  • Class: Monday and Wednesday 2pm-3:30pm in ECE 1.08

Homework

Agenda

(Notes for some of the lectures have been provided below. These notes have been lifted mostly verbatim from the textbook of the course or other resources mentioned in the class. Perhaps the arrangement of the topics is slightly different. The only reason to make them available here is to supplement the reading material for the students. These notes have been prepared jointly with Aditya Gopalan. However, HT must be given the credit for all the typos, spelling mistakes, and other Freudian slips.)
  • Lecture 1: Introduction to the course: Law of large numbers, central limit theorem (with Berry-Esseen correction), large deviation; Markov and Chebyshev inequalities; course overview; numerical evidence of concentration.
  • 1. Cramér-Chernoff method for tail bounds
  • Lecture 2: The Cramér-Chernoff method; properties of Cramér transform; Examples: Gaussian, Poisson, Bernoulli, Chi squared.
  • Lecture 3: Sums of iid rvs; Application: Johnson-Lindenstrauss Lemma; sub-Gaussian rvs; variance of bounded rvs and Hoeffding inequality.
  • 2. Martingale differences and bounded differences
  • Lecture 4: Concentration bounds for sums of iid: Hoeffding inequality (covered in lecture 3), Bennett inequality, Bernstein inequality, sum of mulitplicative family and Azuma's inequality; concentration for maximum of martingale noise; the bounded difference property and McDiarmid's inequality. [pdf]
  • Lecture 5: Applications1: A bound on maximum of subGaussian random variables; longest common subsequence, chromatic number of Erdös-Rényi random graph; balls and bins setup -- number of empty bins. [pdf]
  • Lecture 6: Applications2: Empirical process and uniform convergence; Glivenko-Cantelli Theorem; VC bound for deviation of empirical processes. [pdf]
  • Lecture 7: Applications2: Chaining method to bound the deviation of empirical process; introduction of Efron-Stein inequality. [pdf]
  • 3. The Efron-Stein method
  • Lecture 8: The Efron-Stein inequality (contd.). [pdf]
  • Lecture 9: Exponential concentration around median and mean via Efron-Stein; Gaussian Poincaré inequality [pdf]
  • Lecture 10: Variance bound of self-bounding functions; Introduction to Entropy method: Herbst's argument. [pdf]
  • 4. The Entropy method
  • Lecture 11: Subadditivity of entropy for discrete rvs; Variational formula for entropy; Gibbs variational principle. [pdf]
  • Lecture 12 (short lecture): Subadditivity of entropy for general rvs; Introduction to Sobolev and log-Sobolev inequality; binary log-Sobolev inequality.
  • Lecture 13: Gaussian log-Sobolev inequality; Gaussian concentration; concentration of supremum of Gaussian processes. [pdf]
  • Lecture 14: A modified log-Sobolev inequality (valid for general rvs); Upper and lower tail bounds via entropy method; upper tail bound for weakly self-bounding functions. [pdf]
  • Lecture 15: Lower tail bound for weakly self-bounding functions. [pdf]
  • Lecture 16: Lower tail bound proof (contd.); Review of the course till date; Introduction to the Threshold Phenomenon. [pdf]
  • 5. Application to binary and Gaussian random variables
  • Lecture 17: Russo's Lemma; formalizing threshold phenomenon; a strengthening of log-Sobolev inequality. [pdf]
  • Lecture 18: Threshold phenomenon for symmetric monotone sets. [pdf]
  • 6. Isoperimetric Inequalities and Concentration
  • Lecture 19: Classical isoperimetric theorem; Levy's inequalities (connection b/w concentration and isoperimetry). [pdf]
  • Lecture 20: Bounded difference property and isoperimetry; Blowing-up lemma; Talagrand's convex distance inequality and Talagrand's concentration inequality. [pdf]
  • Lecture 21: Proof of Talagrand's convex distance inquality; examples. [pdf]
  • 7. The Transportation Method
  • Lecture 22: Examples (contd.): Suprema of Rademacher processes; Introducetion to transportation cost inequalities and coupling. [pdf]
  • Lecture 23: Tranportation lemma (connection between concentration and transportation cost inequality); McDiarmid inequality via transportation lemma; proof of Pinsker's inequality; Marton's transportation cost inequlity. [pdf]
  • Lecture 24: Concentration of functions beyond those satisfying the bounded difference property [pdf]
  • Lecture 25: Marton's conditional transportation cost inequality. [pdf]

Course description

It is well-known that functions of large numbers of random quantities tend to behave rather predictably and `less randomly’ than their constituents. For instance, the laws of large numbers tell us that the average of many independendent random variables is asymptotically the expected value; higher-order refinements such as the central limit theorem and large deviations techniques uncover the asymptotic rate at which this reduction in randomness takes place. However, if one is interested in sharper estimates, for the probability of deviation from the typical value, for a fixed number of observations, for functions other than the average, or for functions of dependent random variables, one must take recourse to more specific measure concentration bounds. Perhaps the most basic, nontrivial examples in this regard are the Markov and Chebyshev inequalities, which are encountered in a first course on probability. This graduate-level course on concentration inequalities will cover the basic material on this classic topic as well as introduce several advanced topics and techniques. The utility of the inequalities derived will be illustrated by drawing on applications from electrical engineering, computer science and statistics.

  1. Introduction & motivation: Limit results and concentration bounds
  2. Chernoff bounds: Hoeffding’s inequality, Bennett’s inequality, Bernstein’s inequality
  3. Variance bounds: Efron-Stein inequality, Poinca ́re inequality
  4. The entropy method and bounded difference inequalities
  5. Log-Sobolev inequalities and hypercontractivity
  6. Isoperimetric inequalities (Talagrand's convex distance inequality)
  7. The transportation method
  8. Influences and threshold phenomena

Textbook Stephane Boucheron, Gabor Lugosi, and Pascal Massart, ``Concentration Inequalities,” Oxford University Press, 2013.

Prerequisites

A course on either probability, random processes or measure theory. Basic mathematical maturity and working familiarity with probability calculations.

Grading

Homework (2-4)   60%
Literature review (to be done in groups of size 2)   30%
Class Participation   10%