Georgia Institute of Technology College of Sciences

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

conjecture.