In the year of 2021, the course is divided into three parts:
1. Basic Tools in Probabilistic Analysis.
I will talk about concentration inequalities, martingales, and optional stopping theorem.
Starting from some motivating problems in online decision-making, I will cover some basic concepts and tools in convex optimization, online learning, and most importantly, the connection between optimization algorithms and the geometry of the underlying problem.
I will introduce Markov chains and the Markov chain Monte Carlo (MCMC) algorithm. Based on this, a few applications in theoretical computer science and data science will be discussed. Finally, I will talk about the connection between the convergence of Markov chains and geometry as well.
If time permits, I will discuss some close connections between optimization and sampling algorithms, mainly from the perspective of discretizing certain differential equations.