Concentration Inequalities (2025)
Table of Contents
Welcome to EE5603/AI2200 (Concentration Inequalities).
This is the official webpage of the EE53100 course for 2025. 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.
Prerequisites
- Strong foundation in probability and random processes
1. Assessment (tentative):
Each student will be expected to
- attend classes and participate actively
- solve 2 exams
| Mid-term exam | 40% | |
| Final exam | 60% |
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 | EE616, EECS building |
3. Class timings:
- Slot R:
- Class venue: LHC-04
4. Primary references:
We will primarily use the following material for the course:
- High-dimensional Probability by Roman Vershynin
- Concentration Inequalities by Stephane Boucheron, Gabor Lugosi and Pascal Massart
- “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.
Recorded lectures will be posted here.
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.