COL866: Special Topics in Algorithms
Topic: Concentration Inequalities and their Applications in Computer Science
II semester: 2022-23
Amitabha Bagchi
Class Timings: M Th 3:30PM-5PM.
Venue: SIT 006.
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
Evaluation
Evaluation will be on the basis of 3-4 take-home exams.
- Minor 1. Due on gradescope by 11:59PM on Friday, 3 February 2023.
- Minor 2. Due on gradescope by 11:59PM on Friday, 3 March 2023.
- Minor 3. Due on gradescope by 11:59PM on Saturday, 4 April 2023.
- Minor 4. Due on gradescope by 11:59PM on Friday, 28 April 2023.
Attendance policy
If your attendance is below 75% then your 4th take-home exam will not be graded.
Plagiarism policy
If you copy even a single line from anyone else's paper or any book, website, or any other source your score for the entire course will be set to 0.
Audit policy
Audit pass will be given if
- you have 75% attendance (L1 was not held so it won't be counted. For L2 everyone will be marked present. From L3 attendance will be taken), and
- you score marks that would get you to B- or above if you were crediting the course.
Amitabha
Bagchi