Strong Self-Concordance and Sampling
Offered By: Association for Computing Machinery (ACM) via YouTube
Course Description
Overview
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.
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)
Related Courses
Information TheoryThe Chinese University of Hong Kong via Coursera Intro to Computer Science
University of Virginia via Udacity Analytic Combinatorics, Part I
Princeton University via Coursera Algorithms, Part I
Princeton University via Coursera Divide and Conquer, Sorting and Searching, and Randomized Algorithms
Stanford University via Coursera