Dikin Walk for Sampling Truncated Log-Concave Distributions

Abstract

In this thesis, we researched the interior point methods used in sampling from structuraldistributions. To be more specific, we studied the mixing times of two Metropolized Dikin walk algorithms with different local metrics, and it was applied to strongly log-concave and log-smooth distributions truncated on (possibily unbouneded) polytopes.To prove the correct mixing times, we rely on a classical technique by bounding the conductance of a reversible lazy Markov Chain. The proofs of mixing time have two major pillars:The isoperimetric inequality for log-concave distributions under certain metric; The transition overlap between nearby points. We improved upon previous work and dealt with these two issues correctly.As our result, the first algorithm using logarithmic metric achieved a mixing time of Õ((m+κ)n), where m is the number of faces of the polytope, n is the Euclidean dimension of the distribution, and κ is the “condition number” of the log-concave distribution. This result has already appeared in previous work, and we listed here only for completeness. The secondalgorithm using modifed Lewis weights metric achieved a mixing time of Õ((n + κ)n), which improves mixing time appearing in the previous work and can be considered as our main contribution.