Concentration Inequalities (2024)
Table of Contents
Welcome to EE5603/AI2200 (Concentration Inequalities).
This is the official webpage of the EE53100 course for 2024. All classes will be conducted in person. Online resources and references will be shared here. Much of our online interaction (homework submissions, announcements, off-classroom discussions, etc) will be on Google classroom. Invites will be sent to registered students by the first week of August. If you have not received an invite by the second class, please send me an email.
Concentration inequalities are mathematical techniques that are often used to derive bounds on the performance of various algorithms, or characterize random fluctuations of physical phenomena. These have applications in information theory, communications, statistics, machine learning, statistical physics and computer science (to name a few). We know that if we toss a fair coin many times, the fraction of heads is close to 0.5. Such phenomena occur in many applications, wherein we observe that most of the probability is ’concentrated’ in an event of small size (in the coin-tossing example, the distribution of the number of heads is concentrated close to 0.5). The focus of the course will be on obtaining quantitative bounds on the probability that a random variable deviates from its mean by a certain amount. We will also see applications of these inequalities in statistical learning theory, statistics and information theory.
The course will be mathematical in nature, and some of the assignment questions will involve programming. This course is also a prerequisite for statistical learning theory and kernel methods.
Prerequisites
- Strong foundation in probability and random processes
- Comfort with programming in python. We will mainly use the numpy library.
1. Assessment (tentative):
Each student will be expected to
- attend classes and participate actively
- solve homework assignments
- solve 2 exams
| Mid-term exam | 40% | Week of 12th Aug (tentative) |
| Final exam | 60% | 2nd September 2024 |
If you are planning to audit the course, you must secure a regular pass grade to be eligible for an AU grade.
2. Instructor:
| Name | Dr. Shashank Vatedka |
| shashankvatedka@ee.iith.ac.in | |
| Office | 446, Academic block C |
3. Class timings:
- Slot P: Mondays 14:30-16:00, Thursdays 16:00-17:30
- Class venue: A-221
4. Primary references:
We will primarily use the following material for the course:
- Concentration Inequalities by Stephane Boucheron, Gabor Lugosi and Pascal Massart
- High-dimensional Probability by Roman Vershynin
- “Introduction to statistical learning theory” by Olivier Bousquet, Stephane Boucheron and Gabor Lugosi
Other references
- Concentration of measure inequalities in information theory, communications, and coding by Maxim Raginsky and Igal Sason
To recap basics in probability and random processes:
- Probability, Random Variables and Stochastic Processes, Athanasios Papoulis and Unnikrishna Pillai
- Probability with Engineering Applications by Bruce Hajek
- Random Processes for Engineers by Bruce Hajek
5. Tentative list of topics
- Introduction, Review of basics on probability and random variables
- Sample space, probability measure - need for sample space for uncountable spaces
- Random variables, pmf, cdf and pdf, examples of common distributions
- Expectation, variance, higher moments and MGF
- Volume of n-ball and concentration, Stirling’s approximation, volume of hamming ball and l1 ball
- Sequences of random variables: iid and dependent sources
- Basic inequalities: Markov and Chebyshev inequalities
- Exponential concentration: Chernoff bound, log mgf and the best bounds
- Concentration for sums of iid random variables
- Examples: Gaussian, Poisson and Bernoulli
- Subgaussian random variables
- Bounded random variables: Hoeffding’s inequality
- Subgamma random variables
- Bennett’s inequality
- Bernstein’s inequality
- Example: Dimensionality reduction and the Johnson-Lindenstrauss lemma
- Bounding the variance: Efron-Stein inequality
- A concentration inequality for functions with bounded differences
- Empirical Risk Minimization
6. Class notes
Class notes will be uploaded regularly to this folder.
Recordings of most lectures will be uploaded to this YouTube playlist.
7. Academic honesty and plagiarism
Students are encouraged to discuss with each other regarding class material and assignments. However, verbatim copying in any of the assignments or exams (from your friends or books or an online sources) is not allowed. This includes programming assignments. It is good to collaborate when solving assignments, but the solutions and programs must be written on your own. Copying in assignments or exams will result in a fail grade.
See this page (maintained by the CSE department), this page, and this one to understand more about plagiarism.