COL863: Special Topics in Theoretical Computer Science
Topic: Concentration Inequalities and their Applications in Computer Science
I semester: 2025-26
Amitabha Bagchi
Class Timings: M Th 3:30PM-5PM.
Venue: TBA
Course objectives
The purpose of this course is to discuss various inequalities that help bound the probability that a random variable, or sum of random variables, is far from its expected value. We will show how these inequalities are used in various area of computer science like algorithms, networks, and machine learning.
Topics
Background required: Elementary probability, some linear algebra.
- Some examples of finding tail bounds using elementary methods.
- Markov's inequality and the first moment method; Chebyshev's inequality and the second moment method.
- The Cramer-Chernoff Method; a direct application to approximating Personalized Page Rank.
- The independent Bernuolli variable case; some applications, e.g., randomised rounding etc.
- Hoeffding's inequality; application to random Fourier approximation in Machine Learning.
- Martingales and the Azuma-Hoeffding inequality; application to reachability algorithms for graphs using random walks.
- McDiarmid's inequality; application to proving generalization error bounds in Machine Learning.
- Bernstein's inequality; application to proving the Johnson-Lindenstrauss Lemma.
- The Matrix Bernstein inequality; random Fourier approximation revisited.
If we have time left, and based on interest, we may also cover other topics. A dscussion of other possibilities will be held around the midpoint of the class.
Text
- [BLM16] S. Boucheron, G. Lugosi, P. Massart, Concentration Inequalities: A Nonasymptotic Theory of Independence, Oxford University Press, 2016.
Other references
- [MR04] Rajeev Motwani and Prabhakar Raghavan, Randomized Algorithms, Cambridge University Press, 2004.
- [Roch22] Sebastien Roch, Modern Discrete Probability: An Essential Toolkit (Lecture Notes), University of Wisconsin, 2022.
- [Bagchi04] Amitabha Bagchi, Lecture notes for a simple proof (due to Satish Rao) for the "power of two choices" result, 2004.
- [Harvey14] Nicholas Harvey, Lecture Notes for CPSC 536N: Randomized algorithms, University of British Columbia, 2014-15.
- [MU05] Michael Mitzenmacher and Eli Upfal, Probability and Computing, Cambridge University Press, 2005.
- [Tu16] Stephen Tu, Class notes on Random Fourier Features (locally mirrored since the original has gone offline), Univesity of California, Berkeley, 2016.
- [FRCS05] D. Fogaras, B. Racz, K. Csalogany, and T. Sarlos, Towards Scaling Fully Personalized PageRank: Algorithms, Lower Bounds, and Experiments, Internet Mathematics 2(3):333-358, 2005.
- [BE02] Olivier Bousquet, André Elisseeff, Stability and Generalization. J. Mach. Learn. Res. 2: 499-526 (2002).
- [Tropp2015] Joel A. Tropp, An Introduction to Matrix Concentration Inequalities, Foundations and Trends in Machine Learning, Vol 8, No. 1-2, pp 1-230, 2015. doi:10.1561/2200000048.
Also available at: arXiv:1501.01571 [math.PR].
- [Bhatia07] Rajendra Bhatia, Positive Definite Matrices, Princeton University Press, 2007.
Course calendar
TBA
Evaluation
Evaluation will be on the basis of 3-4 take-home exams, each of equal weight.
Attendance policy
If your attendance is below 75% then your 4th take-home exam will not be graded. If your attendance at the time of the institute midterm exams is < 50% of the classes held you will be withdrawn from the class and none of your remaining papers will be graded.
Plagiarism policy
If you copy even a single line from anyone else's paper or any book, website, or any other source (including AI assistants of any kind) your score for the entire course will be set to 0.
Audit policy
Audit pass will be given if
- you have 75% attendance and
- you score marks that would get you to B- or above if you were crediting the course.
Amitabha
Bagchi