CSC 696H-001: Topics in Concentration of Measure - Fall 2023

This course introduces the concentration of measure phenomenon. Students will learn various techniques to control tail bounds of popular mean estimators and estimators for the minimum value of a function. The course will consist of three part:

  1. The basic concentration of measure bounds such as subgaussian random variable, sub-exponential random variable, empirical Bernstein, robust mean estimators, and McDiarmid’s inequality,
  2. Numerically tight confidence bounds including time-uniform bounds, bounds for linear models, PAC-Bayes bounds, and their applications to machine learning problems, and
  3. Advanced tools for the deviation of functions including covering and packing, the concentration of Rademacher/Gaussian complexities, metric entropy, and chaining.

Throughout, students will not only learn fundamental tools upholding the current understanding of concentration of measure but also develop skills for adapting these techniques to their own research needs such as developing and analyzing new algorithms for interactive machine learning problems like multi-armed bandits and A/B testing.

Syllabus

Here is the syallabus updated on 08/14/2023. Further adjustments will be available in D2L.

Logistics info

  • Mondays and Wednesdays, 12:30pm - 1:45pm, Gould-Simpson 701
  • D2L: https://d2l.arizona.edu/d2l/home/1347795
  • Please find other information from the D2L and the syllabus.

Instructor

Textbook

Textbooks:

  • [W] Martin J. Wainwright, High-Dimensional Statistics: A Non-Asymptotic Viewpoint, 2019.
  • [BLM] Stéphane Boucheron, Gábor Lugosi, and Pascal Massart. Concentration inequalities: A nonasymptotic theory of independence, 2012.

Both are available through UA library. The main textbook will be [W], but we will occasionally use [BLM] and other materials. The instructor will announce other related materials in D2L.

There is no designated textbook for this course. Much of the course materials will be based on these books:

Other useful resources

Evaluation

  • Two homeworks (20+20=40)
  • Participation (5)
  • Weekly discussion (5)
  • Pop quiz (10): weekly
  • Paper critique (10)
  • Presentation (30)

There will be no exams, but each student must do an independent presentation for 60 minutes + rebuttal based on the paper critique. More on the rebuttal: for each presentation, approximately two students will have to write their own paper critiques (in the standard ML conference paper review format), and the presenter must show a rebuttal against those critiques.

Schedule

The following is a rough schedule. Please see D2L for a more detailed and calibrated schedule.

#   Topics Readings Homework
1: 08/21 intro
2: 08/23 (part 1) sub-gaussian random variables
3: 08/28 Sub-exponential random variables (1)
4: 08/30 Sub-exponential random variables (2)
5: 09/04 labor day; no lecture
5: 09/06 robust mean estimators
6: 09/11 empirical Bernstein inequality
7: 09/13 martingale-based methods and McDiarmid’s inequality
8: 09/18 lipschitz functions of Gaussian variables
9: 09/20 (part 2) Time-uniform bounds and applications in multi-armed bandits
10: 09/25 bounds for linear models and linear bandits (1)
11: 09/27 bounds for linear models and linear bandits (2)
12: 10/02 numerically tight bounds: KL-divergence and betting-based bounds
13: 10/04 pac-bayes bounds (1)
14: 10/09 pac-bayes bounds (2)
15: 10/11 (part 3) uniform law of large numbers.
16: 10/16 upper bounds on the rademacher complexity
17: 10/18 covering and packing
18: 10/23 gaussian and rademacher complexity
19: 10/25 metric entropy and sub-gaussian processes
20: 10/30 sudakov’s lower bound
21: 11/01 chaining
22: 11/06 student paper presentation
23: 11/08 student paper presentation
24: 11/13 student paper presentation
25: 11/15 student paper presentation
26: 11/20 student paper presentation
27: 11/22 student paper presentation
28: 11/27 student paper presentation
29: 11/29 student paper presentation
30: 12/04 student paper presentation
31: 12/06 student paper presentation

Potential presentation topics