Concentration inequalities

By Prof. Himanshu Tyagi, Prof. Aditya gopalan   |   IISc Bangalore
Learners enrolled: 110
It is well-known that functions of large numbers of random quantities tend to behave rather predictably and ‘less randomly’ than their constituents. For instance, the laws of large numbers tell us that the average of many independent random variables is asymptotically the expected value; higher-order refinements such as the central limit theorem and large deviations techniques uncover the asymptotic rate at which this reduction in randomness takes place. However, if one is interested in sharper estimates, for the probability of deviation from the typical value, for a fixed number of observations, for functions other than the average, or for functions of dependent random variables, one must take recourse to more specific measure concentration bounds. Perhaps the most basic, nontrivial examples in this regard are the Markov and Chebyshev inequalities, which are encountered in a first course on probability.

This graduate-level course on concentration inequalities will cover the basic material on this classic topic as well as introduce several advanced topics and techniques. The utility of the inequalities derived will be illustrated by drawing on applications from electrical engineering, computer science and statistics. A tentative list of topics is given below.

1. Introduction & motivation: Limit results and concentration bounds
2. Chernoff bounds: Hoeffding’s inequality, Bennett’s inequality, Bernstein’s inequality
3. Variance bounds: Efron-Stein inequality, Poincáre inequality
4. The entropy method and log Sobolev inequality
5. The transportation method
6. Isoperimetric inequalities
7. Other special topics

PREREQUISITES  :  A course on either probability, random processes or measure theory. Basic mathematical maturity and working familiarity with probability calculations.
Summary
 Course Status : Upcoming Course Type : Elective Duration : 8 weeks Start Date : 23 Aug 2021 End Date : 15 Oct 2021 Exam Date : 24 Oct 2021 Enrollment Ends : 02 Aug 2021 Category : Electrical, Electronics and Communications Engineering Communication and Signal Processing Credit Points : 3 Level : Postgraduate

Course layout

Week 1: Chernoff bounds
Week 2: Concentration bounds for sums and other functions of independent random variables
Week 3: Variance bounds for functions of independent random variables
Week 4: The Entropy method for concentration inequalities
Week 5: Entropy method (contd.) and Transportation method
Week 6: Transportation method, isoperimetry and concentration
Week 7: Log-Sobolev inequalities revisited
Week 8: Concentration inequalities for sequential data

Books and references

• Stéphane Boucheron, Gábor Lugosi, and Pascal Massart, “Concentration Inequalities,” Oxford University Press, 2013.
• Maxim Raginsky and Igal Sason, “Concentration of Measure Inequalities in Information Theory, Communications and Coding (Second Edition),” Foundations and Trends in Communications and Information Theory, vol. 10, no 1-2, pp. 1-248, 2013. (available at on https://arxiv.org/abs/1212.4663v8)

Prof. Himanshu Tyagi

IISc Bangalore
Associate Professor Department of Electrical Communication Engineering Participating Faculty Robert Bosch Center for Cyber Physical Systems Member Faculty Analysis and Probability Research Group (APRG)

Department of Electrical Communication Engineering (ECE)
IISc Bangalore

Course certificate

The course is free to enroll and learn from. But if you want a certificate, you have to register and write the proctored exam conducted by us in person at any of the designated exam centres.
The exam is optional for a fee of Rs 1000/- (Rupees one thousand only).
Date and Time of Exams: 24 October 2021 Morning session 9am to 12 noon; Afternoon Session 2pm to 5pm.
Registration url: Announcements will be made when the registration form is open for registrations.
The online registration form has to be filled and the certification exam fee needs to be paid. More details will be made available when the exam registration form is published. If there are any changes, it will be mentioned then.
Please check the form for more details on the cities where the exams will be held, the conditions you agree to when you fill the form etc.

CRITERIA TO GET A CERTIFICATE

Average assignment score = 25% of average of best 6 assignments out of the total 8 assignments given in the course.
Exam score = 75% of the proctored certification exam score out of 100

Final score = Average assignment score + Exam score

YOU WILL BE ELIGIBLE FOR A CERTIFICATE ONLY IF AVERAGE ASSIGNMENT SCORE >=10/25 AND EXAM SCORE >= 30/75. If one of the 2 criteria is not met, you will not get the certificate even if the Final score >= 40/100.

Certificate will have your name, photograph and the score in the final exam with the breakup.It will have the logos of NPTEL and IISc Bangalore.It will be e-verifiable at nptel.ac.in/noc.

Only the e-certificate will be made available. Hard copies will not be dispatched.

Once again, thanks for your interest in our online courses and certification. Happy learning.

- NPTEL team