notesum.ai

Published at December 9

PolytopeWalk: Sparse MCMC Sampling over Polytopes

stat.CO

cs.LG

stat.ML

Released Date: December 9, 2024

Authors: Benny Sun¹, Yuansi Chen²

Aff.: ¹Duke University; ²ETH Zurich

Arxiv: http://arxiv.org/pdf/2412.06629v1

Refer to caption

Random Walk	Mixing Rate	Computational Complexity
Ball Walk f14f	$\tau(d^{2}R^{2}/r^{2})$	The Ball Walk includes minimal matrix multiplication and gaussian vector calculations.
Hit-and-Run f11f	$\tau(d^{2}R^{2}/r^{2})$	The Hit-and-Run computes binary search calculate a random chord in the polytope.
Dikin Walk f12f	$\tau(nd)$	The Dikin Walk uses sparse linear solvers and sparse Cholesky decomposition for computing determinant and inverse square root of Hessian matrix.
Vaidya Walk f3f	$\tau(n^{1/2}d^{3/2})$	The Vaidya Walk builds upon Dikin Walk and uses sparse Cholesky decomposition and sparse inverse algorithm from f9f to compute leverage scores.
John Walk f3f	$\tau(d^{2.5})$	The John Walk builds upon the Vaidya Walk to solve an optimization task with fixed-point iteration, computing a weighted leverage score each iteration.
Lee Sidford Walk f10f	$\tau(d^{2})$	The Lee Sidford Walk also solves an optimization task using gradient descent, computing a weighted leverage score each iteration.