Probability and Statistics in Computing

Lecture notes

• 2019-09-23. Preliminaries 3 (contd.): The Cramér-Rao inequality and lower bounds on the variance of estimators. Interlude and revision: Randomized rounding for MAX-CUT.

• 2019-09-19. Preliminaries 3 (contd.): Relative-entropy based minimax lower bounds for testing multiple hypotheses: examples. Excursion: Equivalence of Pinkser’s inequality and Hoeffding’s lemma.

• See chapter 2 of Tsybakov, 2009.

• Notes on connections between Pinsker’s inequality and concentration.

• 2019-09-16. Preliminaries 3 (contd.): Minimax lower bounds with multiple hypotheses.

• 2019-09-12. Preliminaries 3: Discussion of $$\varepsilon$$-nets; example: operator norm of a random matrix. Minimax lower bounds. Information theoretic lower bounds for distinguishing Bernoulli distributions.

• 2019-09-09. Analysis of clustering after projection to the principal component (contd.); $$\varepsilon$$-nets. Issues with conditioning on the observed data and fixes.

• 2019-09-05. Analysis of clustering after projection to the principal component (contd.). Properties of the principal component.

• 2019-08-29. Analysis of distance based clustering. Possibilities for improvement. The singular value decomposition.

• 2019-08-26. Properties of Gaussian vectors. Distance-based clustering of Gaussian mixtures.

• 2019-08-22. Preliminaries 2: Some probability estimates for spheres and balls in $$\mathbb{R}^d$$.

• Animation of the variation of relative volume of an infinitesimal cross-sectional ‘slice’ of the Euclidean unit ball with the distance of the slice from the equator. Code for the animation (in julia, requires the Plots and PyPlot packages).
• 2019-08-19. Preliminaries 1: Basic hypothesis testing terminology. The Neyman-Pearson lemma.

General information

Instructor: Piyush Srivastava

Schedule: Mondays and Thursdays, 1400-1530, A-201.

• Homework 4. Due December 10, 2100IST. Last updated version hash: ca4c390, December 2. Files required for Q2 are here.

• Homework 3. Due November 11, before class. Last updated version hash: 354a930, October 28.

• Homework 2. Due October 7, before class. Last updated version hash: de0ba01, September 23.

• Homework 1. Due September 5, before class. Last updated version hash: 7093495, August 30.

References

1. Foundations of Data Science . A. Blum, J. E. Hopcroft, R. Kannan. To be published by Cambridge University Press.

2. Introduction to Nonparametric Estimation. Alexandre B. Tsybakov. Springer Series in Statistics, 2009.