Strong self concordance and sampling

ACO Student Seminar
Friday, March 6, 2020 - 1:05pm for 1 hour (actually 50 minutes)
Skiles 005
Aditi Laddha – CS, Georgia Tech – aladdha6@gatech.edu
He Guo

Motivated by the Dikin walk, we develop aspects of an interior-point

theory for sampling in high dimensions. Specifically, we introduce symmetric

and strong self-concordance. These properties imply that the corresponding

Dikin walk mixes in $\tilde{O}(n\bar{\nu})$ steps from a warm start

in a convex body in $\mathbb{R}^{n}$ using a strongly self-concordant barrier

with symmetric self-concordance parameter $\bar{\nu}$. For many natural

barriers, $\bar{\nu}$ is roughly bounded by $\nu$, the standard

self-concordance parameter. We show that this property and strong

self-concordance hold for the Lee-Sidford barrier. As a consequence,

we obtain the first walk to mix in $\tilde{O}(n^{2})$ steps for an

arbitrary polytope in $\mathbb{R}^{n}$. Strong self-concordance for other

barriers leads to an interesting (and unexpected) connection ---

for the universal and entropic barriers, it is implied by the KLS