## 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 By email with subject line: "Math 595:" TR 9:30am -10:50pm in 343 Altgeld Hall 341A Illini Hall TBA and By appointment. I will be happy to answer your questions in my office anytime as long as I'm not otherwise engaged. 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) Some familiarity with discrete mathematics and basic probability theory is necessary. 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/27 Overview. Moments to Tail bound. PDF (Greg Terlov) 08/29 Concentration function and Cramér-Chernoff bound. PDF (Kesav Krishnan) 09/03 Sub Gamma Random variables. PDF (Amish Goel) 09/05 Johnson-Lindenstrauss Lemma & Hansen-Wright Inequality. PDF (Qiang Wu) 09/10 Concentration for Maximum. PDF (Hsin-Po Wang) 09/12 Classical concentration inequalities. PDF (Hongqi Chen) 09/17 McDiarmid's Inequality and its Applications. PDF (Sourya Basu) 09/19 Gaussian Poincaré inequality. PDF (Xingyu Bai) 09/24 Stein's method for concentration inequalities. PDF 09/26 Efron-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/10 Herbst's argument, and LSI to Poincare. PDF (Junchi Yang) 10/15 Shannon and relative Entropy. PDF ( ) 10/17 Subadditivy 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/14 Transportation 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/26 No 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 ( )