36-711 · Fall 2026

High-Dimensional Probability

Overview

Description

Understanding random vectors, matrices, and stochastic processes in high dimensions requires probabilistic tools that go beyond classical asymptotic analysis. This course will introduce non-asymptotic methods in high-dimensional probability that find widespread use across statistics, computer science, data science, and engineering. Topics will include tail bounds for sums of independent random variables and martingale differences, concentration inequalities for nonlinear functions, matrix concentration, and methods for controlling suprema of stochastic processes. Our primary focus will be on broadly applicable proof techniques and the geometric principles underlying them. This course will be theory-oriented.

Logistics

Instructor: Ankit Pensia
Email: ankitp@cmu.edu
Course number: 36-711 (Fall 2026)
Lectures: Monday and Wednesday, 9:30 AM–10:50 AM, Wean Hall 5316
Office hours: Wednesday, 2–3 PM, Baker Hall 232B
Course materials: Canvas

Schedule

The schedule will be updated as the course progresses. Topics and readings are tentative.

Date Topic Reading
Aug 24 Course overview and objectives; Sum of scalar random variables; Cramer-Chernoff method; Hoeffding's lemma [Ver26; Chapters 1 and 2] [Tal96; Section 1]
Aug 26 Sub-Gaussian random variables; General Hoeffding Inequality; Bernstein Inequalityl; Sub-Gamma random variables [Ver26; Chapter 2] [BLM13; Chapter 2]
Aug 31 Subexponential random variables; JL Sketch; Heavier-tailed random variables [Ver26; Chapter 2] [BLM13; Chapter 2]
Sep 02 Heavy-tailed random variables; mean estimation of (heavy-tailed) distributions [Tro23; Chapter 7] [Ver26; Chapter 2]
Sep 09 Non-linear functions; Efron-Stein inequality [BLM13; Chapter 3]
Sep 14 Poincare inequalities; Azuma-Hoeffding Inequality; Exponential concentration beyond bounded differences inequality [BLM13; Chapter 3]

Course Work

Lecture scribing

Students will take turns transcribing each lecture using the LaTeX template available on Canvas. The scribe must attend class, take accurate notes, check for mistakes and inconsistencies, write the notes in LaTeX, add references, and expand the material when appropriate after consulting with the instructor. The resulting PDF and LaTeX source files must be submitted for approval within one week. Approved PDFs will be posted on Canvas.

The scribe sign-up sheet will be accessible from Canvas.

Final reading project

Individually or in a group of two, students will choose a paper from the past ten years in high-dimensional probability, understood in a broad sense, and write a 5–10 page self-contained technical report. The report should clearly explain the paper’s main contribution and connection to the literature, and provide a streamlined proof sketch of its main results. Students are welcome to choose any paper of interest or discuss possible choices with the instructor. The report is due at the end of the seventh week, October 7, and should be emailed to the instructor.

References

Topics will be selected primarily from the following references. Additional references will be introduced as needed.