Math 595: Concentration Inequalities and Stein's Method (Fall 2019)

Goals and topics

Concentration inequalities bound the probability that a function of several random variables differs from its mean by more than a certain amount. The search for such 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, random matrices and others.

This course will cover several different approaches to answering the question of finding useful concentration bounds. In particular, we will study martingale method, entropy method, transportation method, isoperimetric method, Stein's method and will cover examples from current research, including dimension reduction, random matrices, Boolean analysis, spin glasses and statistical estimation. We will also look at distributional approximation techniques using Stein's method.

Logistics

Instructor Partha Dey
ContactBy email with subject line: "Math 595:"
Class TR 9:30am -10:50pm in 343 Altgeld Hall
Office341A Illini Hall
Office Hrs TBA and By appointment. I will be happy to answer your questions in my office anytime as long as I'm not otherwise engaged.
Textbook There is no required textbook. Here, is a list of books which are related to our material. I will make suggestions of more resources (books and papers) throughout the semester.
  • Boucheron, S., Lugosi, G., & Massart, P. (2013). Concentration inequalities: A nonasymptotic theory of independence. Oxford university press.
  • Vershynin, R. (2018). High-dimensional probability: An introduction with applications in data science (Vol. 47). Cambridge University Press.
  • Ledoux, M. (2001). The concentration of measure phenomenon (No. 89). American Mathematical Soc.
  • Talagrand, M. (1995). Concentration of measure and isoperimetric inequalities in product spaces. Publications Mathématiques de l'Institut des Hautes Etudes Scientifiques, 81(1), 73-205.
  • van Handle, R. (2016). Probability in High Dimension. Lecture Notes.
  • Neeman, J. (2016). Notes on Markov Diffusions. Lecture Notes.
  • Levin, D., Peres, Y., Wilmer, E. (2008). Markov Chains and Mixing Times (See Chapter 3)
Prerequisite Some familiarity with discrete mathematics and basic probability theory is necessary.
Grading Grades are based on class participation; solving exercises; and scribing lecture notes and/or presenting papers or research at the end of the semester.

Use this LaTeX template for scribing.

Tentative timeline:



08/27Overview. Moments to Tail bound. PDF (Greg Terlov)
08/29 Concentration function and Cramér-Chernoff bound. PDF (Kesav Krishnan)


09/03Sub Gamma Random variables. PDF (Amish Goel)
09/05Johnson-Lindenstrauss Lemma & Hansen-Wright Inequality. PDF (Qiang Wu)


09/10Concentration for Maximum. PDF (Hsin-Po Wang)
09/12Classical concentration inequalities. PDF (Hongqi Chen)


09/17McDiarmid's Inequality and its Applications. PDF (Sourya Basu)
09/19Gaussian Poincaré inequality. PDF (Xingyu Bai)


09/24Stein's method for concentration inequalities. PDF
09/26Efron-Stein and Poincaré inequalities. PDF (Siddhartha Satpathi)


10/01 Proofs of Efron-Stein inequality. PDF (Felix Clemen)
10/03 Further Applications of Efron-Stein inequality. PDF ( )


10/08 Gaussian Log-Sobolev inequality. PDF (Erchi Wang)
10/10Herbst's argument, and LSI to Poincare. PDF (Junchi Yang)


10/15Shannon and relative Entropy. PDF ( )
10/17Subadditivy of relative entropy and LSI for Uniform {0,1}^n. PDF (Hsin-Po Wang)


10/22 Application of LSI for for Uniform {0,1}^n. PDF ( )
10/24 Variational characterization for Entropy. PDF ( )


10/29 Another characterization of Entropy. PDF (Anamitra Chaudhuri)
10/31 Concentration for Self bounding functions. PDF (Bolton Bailey )


11/05 Mass Transportation Principle. PDF (Aditya Deshmukh)
11/07 Transportation cost inequality. PDF (Siddharta Satpathi )


11/12 Talagrand's convex distance inequality. PDF ( )
11/14Transportation cost inequality for Markov Chains. PDF (Felix Clemen)


11/19 Applications of Talagrand's convex distance inequality. PDF ( )
11/21 Hyper contractivity and Talagrand's L1-L2 inequality. PDF (Yifan Zhang)


11/26No classes. Thanksgiving break.
11/28


12/03 Noise operator and concentration for higher order polynomials. PDF (Xingyu Bai)
12/05 Sharp Threshold for Boolean functions. PDF ( )


Emergency information