Probability in High Dimension WS 2016/17
Lectures: Tuesday 10-12 and Thursday, 14-16, room N0.003
Examination: The examination will be oral. There are two options: a "standard" exam and a "homework" exam. The homework exam is only available if you have completed 8 out of 10 problem sets; it will be shorter than the standard exam, and it will be focused on the problem sets.
Standard exam: You will start by explaining to me a topic of your choice (that was covered in the course). Then I will ask questions about that topic, and about other topics that were covered in class.
Homework exam: I will ask you questions about homework problems that you handed in. I will probably focus on problems that you had difficulty with.
The first examinations will be on February 20 and 21. The second examinations will be on March 30 and 31.
Problem sets:
- Due 3.11: problems 2.2 and 2.4.
- Due 10.11: problems 3.1 and 3.7.
- Due 17.11: problems 3.14 and 3.18.
- Due 29.11: problems 4.4 and 4.10.
- Due 8.12: problem 5.10.
- Due 15.12: problem 5.11.
- Due 12.1: problems 6.3 and 6.6.
- Due 19.1: problem 7.9, parts a-d.
- Due 26.1: problem 7.12, parts a and c.
Content: This is a course about probabilistic tools that have applications in "high-dimensional" problems. The methods we will study have applications to many fields: random matrices, machine learning, high-dimensional convex geometry, and more. We will use problems from some of these applications as running examples throughout the course.
There will be two main topics. The first is concentration, in particular the phenomenon that a nice function of many almost-independent random variables tends to be close to its mean with high probability. Examples of this phenomenon range from very classical ones (e.g. the weak law of large numbers) to well-known open problems (e.g. those in this book).
The second part of the course will be about suprema of stochastic processes. We will see techniques for bounding the supremum of a stochastic process in terms of combinatorial or geometric properties of its index set.
The course will be based around these lecture notes by Ramon van Handel. To get a better idea of the course content and its motivation, see the introduction of those notes.
Additional material: here is a list of sources for material that we covered but was not in the notes by van Handel.
- Dvoretzky's theorem is covered in the book "Concentration of Measure," section 3.5, by Michel Ledoux
- Self-bounding functions are covered in these notes (section 3.5) by Boucheron, Lugosi, and Bousquet.