Faster Sampling Algorithms for Polytopes with Small Treewidth

Sampling is a fundamental problem in optimization, machine learning and theoretical computer science. A common region of interest for sampling is the polytope, which is defined by a set of linear inequalities. The algorithm that is sampling from polytopes usually requires heavy matrix algebra, including matrix multiplication, matrix inversion and matrix determinant. In this work, we show how to implement the heavy matrix algebra in the area of sampling in nearly linear time for the polytope that has small treewidth. In particular, given a polytope defined by a matrix A ∈ ℝ<sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">n×d</sup> with treewidth τ, we improve the running time of each iteration for three typical sampling algorithms for polytopes such as Dikin Walk, Soft-Threshold Dikin Walk and Vaidya Walk from O(nd<sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">2</sup>) to O(nτ<sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">2</sup>) by exploiting the small treewidth structures of the matrices.