Readings will be mostly assigned from the following books:

36-788, Spring 2015
Class Schedule
Date Lecture Topic Readings Scribe Notes Notes
Tue Sep 1 Introduction and Examples pdf See the references for models with d increasing with n and without structural (sparsity) assumptions.
Thu Sep 3 Overview of concentration: concentration function and concentration of Lipschitz function
  • [L]: 1.1,1.2,1.3
  • [BLM]: 2.1, 2.2
  • [M]: 2.1
pdf HW1 is out.
Tue Sep 8 Sub-Gaussian random variables and Hoeffding Inequality
  • [BLM]: 2.3 and 2.6
  • [M]: 2.2.1
  • further references on sub-gaussian variables
  • references on multiplicative Chernoff bound (for Bernoulli variables).
pdf
Thu Sep 10 Sub-Exponential Variables and Bernstein Inequality
  • [BLM]: 2.4, 2.7, 2.8
  • Slides of Peter Bartlett's Lecture 4 and 5 in STAT 241B / EECS 281B.
pdf
Tue Sep 15
  • Bennet and general Bernstein Inequalities
  • Expected values of the maximum.
  • Concentration of Gaussian quadratic forms.
  • [BLM]: 2.5, 2.7, 2.8
  • [M]: 2.1, 2.2, 2.3
pdf
Thu Sep 17
  • Johnson_Lindenstrauss Lemma
  • Efron-Stein Inequality
  • [BLM]: 2.9, 3.1
pdf
Tue Sep 22 Efron-Stein iequality and examples.
  • [BLM]: 3.1, 3.2, 3.3, 3.4.
HW2 is out.
Thu Sep 24 Ale out of town.
Tue Sep 29
  • Efron Stein for self bounding and configuration functions.
  • Azuma inequality.
  • Definition of entropy.
  • [BLM]: 3.3, 3.4, 4.8
  • References on Azuma
pdf
Thu Oct 1
  • Entropy and its properties; sub-additivity.
  • The bounded difference inequality.
  • [BLM]: 4.8, 4.9, 4.13, 6.2, 6.2.
HW3 is out.
Tue Oct 6 The Chen-Stein Poisson Approximation, with applications to
  • an approximation on the birthday problem;
  • the maximum correlation between spherically distributed variables;
  • a simple scan statistics.
Guest lecture by Max G'Sell. 		pdf Ale out of town.
Thu Oct 8 More on the entropy method for concentration inequalities.
  • [BLM]: 6.3, 6.4, 6.6, 6.7, 6.9.
pdf
Tue Oct 13 Concentration of Lipschitz functions of Gaussian vectors
  • [BLM]: 5.3, 5.4, 5.5.
  • [M]: 3.1, 3.2, 3.3.
Thu Oct 15 Matrix concentration inequalities
  • Tropp, J. (2012). User-friendly tail bounds for sums of random matrices, Found. Comput. Math., Vol. 12, num. 4, pp. 389-434, 2012.
  • Tropp, J. (2015). An Introduction to Matrix Concentration Inequalities, Found. Trends Mach. Learning, Vol. 8, num. 1-2, pp. 1-230
Tue Oct 20 Matrix Bernestein inequality. Applications to covariance matrix estimation and graph Laplacian. Same as last lecture.
Thu Oct 22 Hoeffding inequality for U-statistics. Graphon estimation.



The scribe latex template is available here.


Sign up here.