Class number 054–39482R
Class meetings: MW, 9:30am-12:30pm, KAP 147.
Information on this and related pages changes frequently.
Instructor: Sergey Lototsky.
Office: KAP 248D.
Phone: 213 740 2389
E-mail: lototsky usc edu.
Office Hours: MW after the class. Appointments at other time are welcome.
Course objective: to learn basic tools for deriving explicit non-asymptotic exponential bounds on probabilities of certain events and to explore some applications of such bounds.
More general goal: to learn something interesting, new, and/or useful.
Official grading scheme: 20% class participation, 40% homework assignments, 40% final presentation.
Main reference: Bernard Bercu, Bernard Delyon, and Emmanuel Rio. Concentration inequalities for sums and martingales. SpringerBriefs in Mathematics. Springer, Cham, 2015. x+120 pp. ISBN: 978-3-319-22098-7; 978-3-319-22099-4
The book is available in electronic form from the USC Libraries
Homework problems and more
My notes
- General summary of probability
- Random variables: general definitions and an easy diagram
- Basic inequalities
- More on probability inequalities
- Fundamental Theorems of Various Branches of Mathematics
- Gamma and Beta functions
- Exact relations among probability distributions
- Gaussian objects: Normal random variables, CLT, and more
- A summary of Gaussian inequalities
- Asymptotic integration
- A summary of large deviations
- Glivenko-Cantelli theorem
- Elementary and Intermediate notes on linear algebra
Other notes
- (Almost) everything you need to know about probability distributions
- About Vysochansky-Petunin inequality
- Martingale inequalities [from Shiryaev’s book]
- Asymptotic notations 1
- Asymptotic notations 2
- Examples of binomial confidence intervals
- The original paper by Clopper and Pearson
- The Abel Prize interview with M. Talagrand [AMS Notices]
- The original paper by Hanson and Wright
- Modern extensions of Hanson and Wright, with a USC connection
- Quantifying the difference between probability measures
- The original paper on KL divergence [Kullback, S.; Leibler, R.A. (1951). “On information and sufficiency”. Annals of Mathematical Statistics. 22 (1): 79–86.]
Our Progress
May 21: Course overview; Elementary inequalities in probability; Some bounds on the normal tail.
May 26: No class (Memorial Day).
May 28: Inequalities of Bernshtein and Hoeffding.
June 2: Sub-Gaussian random variables and Orlicz spaces.
June 4: Gamma and sub-Gamma random variables; conditional expectation and McDiarmid’s inequality.
June 9: Roots of random (Kac) polynomials; martingales and the Azuma-Hoeffding inequality.
June 11: Other martingale inequalities.
June 16: Applications from the book (statistical inference in ARMA models, combinatorial CLT, random matrices).
June 18: Concentration of measure from the analysis point of view (Sobolev, log Sobolev, Poincare, and isoperimetric inequalities, as well as Levy on the sphere and convex Talagrand).
June 23: Hanson-Wright inequality; intro to coupling and related ideas; the Efron-Stein inequality, with applications to LCS and KDE, and entropy extensions.
June 25: From the Boltzmann entropy to KL divergence, Pinsker’s inequality, and optimal transport.
June 30: From concentration inequalities to “with high probability” statements; a first look at uniform limit theorems and VC theory.
July 2: Dimension reduction (Dvoretzky-Milman and Johnsson-Lindenstrauss); matrix versions of Bernshtein, Hoeffding, and Cramer-Chernoff.
July 7: Concluding discussion.