Continuous Algorithms - Sampling and Optimization in High Dimension

Explore continuous algorithms for sampling and optimization in high dimensions in this 33-minute lecture by Santosh Vempala from Georgia Tech, presented at the Simons Institute 10th Anniversary Symposium. Delve into topics such as the Cutting Plane method, Rounding and Integration, Interior-Point Method 2.0, and Riemannian Hamiltonian Monte Carlo. Learn about the challenges of optimization, the complexity of solving linear systems, and discover a template for continuous algorithms. Gain insights into finding the right space and path for effective problem-solving in high-dimensional contexts.

Syllabus

Intro
Sampling and Optimization
Optimization Cutting Plane method (building on Blipsoidalgorithm)
Rounding and Integration (Volume)
The difficulty of optimization
Interior-Point Method 2.0
Linear systems, LP, and Basic open problem in optimization Complexity of solving a linear system!
Back to Sampling
Riemannian Hamiltonian Montian Carlian
Template for continuous algorithms Find the right space 2. Find the right path