E1 341: Probabilistic Foundations for Sequential Learning

Instructor: Shubhada Agrawal
Time: Tuesdays and Thursdays, 10:00 - 11:30 am
Room: EC 1.08
Teams group: If you have an IISc email ID, you can join the Teams group using the code: u0bhb7v

Course description: This course develops a rigorous mathematical foundation for analyzing adaptive and sequential decision-making systems. The focus is on core probabilistic tools, such as martingale theory, martingale concentration inequalities, convergence of random variables, and large deviations, which form the backbone of modern theoretical research in sequential learning.

The first part of the course introduces martingales in discrete time. Topics include filtrations, conditional expectation, stopping times, Doob decompositions, optional stopping theorems, maximal inequalities, martingale convergence theorems, discrete quadratic variation, and uniformly integrable martingales. 

In the second part, we explore applications of martingale theory to concentration and sequential analysis. Topics include Ville’s inequality, time-uniform bounds, mixture martingales, and confidence sequences. We will cover a unified derivation of a wide variety of new and old time-uniform concentration inequalities using martingales. We will also touch upon self-normalized exponential concentration inequalities.

The third part will introduce the theory of large deviations. We will examine Cramer’s and Chernoff bounds, rate functions, tilted distributions, Gartner-Ellis theory, and Sanov-type principles.

Pre-requisite: Random Processes (E2 202) and Analysis-1 (MA 221), or equivalent background.

Evaluation (tentative): 40% mid sem, 40% end sem, 20% student presentations.

References:

1. Probability with Martingales, David Williams

2. Large Deviations Techniques and Applications, Dembo and Zeitouni