In many probabilistic settings the distribution of random variables can be shown to be highly concentrated about about their mean or median value. Spurred by the pioneering work of Talagrand and his isoperimetric inequality, this `concentration of measure’ phenomenon been an intensive topic of research over the last decade. The course will examine a number of methods whereby concentration of measure can be proved, including the use of martingales, entropy and information, transportation inequalities, self bounding functions and Stein couplings. Applications will be considered in areas spanning statistics, combinatorics, information theory, randomized algorithms and high dimensional geometry.
Instructor: Larry Goldstein
Main Text:
Concentration Inequalities: A Nonasymptotic Theory of Independence
Stephane Boucheron, Gabor Lugosi and Pascal Massart, Oxford University Press.
Supplementary references:
The Concentration of measure phenomenon
Michel Ledoux
Concentration of Measure Inequalities in Information Theory, Communications and Coding
Maxim Raginsky, Igal Sason
Applications to Machine Learning
Stéphane Boucheron
A list of open problems.
First meeting on Monday, August 26th, 9:00am, KAP 414, Regular course meetings Mondays and Wednesdays 8:35-9:50AM, KAP 414.
Course material will be drawn from selections of the first eight chapters of the text of Boucheron et al. listed above, and additonal supplementary sources.
Readings
Talagrand’s convex distance inequality: Notes by Cook, and Chapter 6 in the book by Steele.
Chapter 1 of text, skim for preview.
Chapter 2 of text, see Theorem 2.8 in particular for Hoeffding’s inequality.
Chapter 3, Sections 1,2 and 3 of text, Efron-Stein Inequality.
Chapter 4, Sections 1-11
Chapter 5, Sections 1,2
Chapter 6, Sections 1,2,3,4,5,11, certifiable functions from the ‘Self Bounding’ paper by McDiarmid and Reed
Chapter 8, Sections 1,2,4
Grading
30% Midterm Exam Friday, October 25th.
30% Presentation
10% Participation
30% Final Project, Due Dec 11th
Students will choose a topic in collaboration with the instructor, and, depending its extent, may work as part of a group of students. Many suggested readings can be found in the content section of the course Blackboard page, and students should feel free to suggest potential areas of interest. Students will give a presentation on their topic during the last five weeks of the course, and provide a summary writeup as their final project. Students receive credit for course participation by attending and submitting questions and comments on the presentation topics through the Blackboard discussion board for that topic. Students should strive to choose a topic and have it approved as early as possible in the semester; presentation dates will be assigned to those with approved topics on a first come first served basis.
The Final Project consists of a writeup that accompanies, augments and records your presentation. The writeup can be of any length you choose, with a minimum of three to five pages, preferably a pdf file generated by LaTeX, consisting of an introduction to the topic, the results and applications presented, and how the material you studied fits into, and is related to, the framework for concentration inequalities presented in class. Portions of the relevant works may be repeated verbatim only when absolutely necessary, such as for noting result statements or proofs, leaving the remainder of your report expressed in your own words. The document should serve as a substitute, and essentially equivalent source, for attendance at your presentation.