Class Central is learner-supported. When you buy through links on our site, we may earn an affiliate commission.

YouTube

Strong Self-Concordance and Sampling

Association for Computing Machinery (ACM) via YouTube

Start learning Write review
Coursera Ad

Google AI Professional Certificate - Learn AI Skills That Get You Hired

Learn More → CodeSignal Ad

Learn the Skills Netflix, Meta, and Capital One Actually Hire For

Learn More →

Overview

Google, IBM & Meta Certificates — All 10,000+ Courses at 40% Off
One annual plan covers every course and certificate on Coursera. 40% off for a limited time.
Get Full Access
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)

Reviews

Start your review of Strong Self-Concordance and Sampling

Start learning

Never Stop Learning.

Get personalized course recommendations, track subjects and courses with reminders, and more.

Sign up for free
Someone learning on their laptop while sitting on the floor.