Explore an algorithm for sampling a polytope that mixes in Õ(n^2) steps from a warm start using strong self-concordance in this 25-minute ACM conference talk. Discover the connection between strong self-concordance of well-known barrier functions and the KLS isoperimetry conjecture. Learn about sampling techniques, including the Ball Walk and Generalized Dikin Walk, and delve into main results, conductance bounding, and proof outlines. Examine the Lee Sidford Barrier and its properties, and consider open problems in the field.
Overview
Syllabus
Intro
Sampling
Ball Walk
Alternatives
Barriers to Ellipsoids
Drawbacks
Question
Genralized Dikin Walk
Main Results
Bounding Conductance
Proof Outline of Lemma
Bounding Rejection Probability
Bounding Second term
Lee Sidford Barrier (Lee and Sidford, 2019)
Convexity and Symmetry of LS Matrix LS Barrier satisfies the following properties Lee and Sidford, 2019
Open Problems
Taught by
Association for Computing Machinery (ACM)
