High-dimensional sampling has applications in many fields, and efficient algorithms for sampling and integration have become part of the standard algorithmic toolkit. The past three decades have witnessed remarkable improvements in the worst-case complexity of these problems and resulted in a rich set of algorithmic and analytic tools. This tutorial will be an in-depth exposition of the state-of-the-art in sampling algorithms, their applications, and relevant developments in asymptotic convex geometry. Only a basic knowledge of linear algebra, probability and algorithms will be assumed. The tutorial will conclude with a discussion of open problems and research directions on all three major aspects: algorithms, probability/Markov chains and geometry.
Slides from the tutorial: Part I, Part II
Here is an outline of topics covered:
| 1. Introduction | Model, problems, structure of high-dimensional convexity |
| 2. Algorithms | Integration, optimization, learning via sampling; simulated annealing |
| Demo/exercise | Experiments with a MATLAB implementation |
| 3. Asymptotic Convex Geometry | Concentration; Isoperimetry; KLS, thin-shell and slicing conjectures |
| 4. Probability | Geometric Markov chains, conductance. |