Topic: Concentration Inequalities and their Applications in Computer Science

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.

- [BLM16] S. Boucheron, G. Lugosi, P. Massart,
*Concentration Inequalities: A Nonasymptotic Theory of Independence*, Oxford University Press, 2016.

- [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.

- 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.

- 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