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.
- See chapter 2 of Tsybakov, 2009.
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.
- Notes
2019-09-09. Analysis of clustering after projection to the principal component (contd.); \(\varepsilon\)-nets. Issues with conditioning on the observed data and fixes.
- See also Vempala and Wang, JCSS 80(4), 2004.
2019-09-05. Analysis of clustering after projection to the principal component (contd.). Properties of the principal component.
- See also Vempala and Wang, JCSS 80(4), 2004.
2019-08-29. Analysis of distance based clustering. Possibilities for improvement. The singular value decomposition.
- julia notebook.
2019-08-26. Properties of Gaussian vectors. Distance-based clustering of Gaussian mixtures.
- julia notebook. Needs to be run as an IJulia notebook environment for the julia programming language.
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.

References

Foundations of Data Science . A. Blum, J. E. Hopcroft, R. Kannan. To be published by Cambridge University Press.
Introduction to Nonparametric Estimation. Alexandre B. Tsybakov. Springer Series in Statistics, 2009.