Skip to main content
eScholarship
Open Access Publications from the University of California

Vaidya walk: A sampling algorithm based on the volumetric barrier

  • Author(s): Chen, Yuansi
  • Dwivedi, Raaz
  • Wainwright, Martin J
  • Yu, Bin
  • et al.

Published Web Location

https://ieeexplore.ieee.org/document/8262876
No data is associated with this publication.
Abstract

© 2017 IEEE. The problem of sampling from the uniform distribution over a polytope arises in various contexts. We propose a new random walk for this purpose, which we refer to as the Vaidya walk, since it is based on the volumetric-logarithmic barrier introduced by Vaidya in the context of interior point methods for optimization. We show that the Vaidya walk mixes in significantly fewer steps compared to the Dikin walk, a random walk previously studied by Kannan and Narayanan. In particular, we prove that for a polytope in Rd defined by n constraints, the Vaidya walk mixes in O (√n/d) fewer steps than the Dikin walk. The per iteration cost for our method is at most twice that of the Dikin walk, and hence the speed up is significant for polytopes with nd. Furthermore, the algorithm is also faster than the Ball walk and Hit-And-Run for a large family of polytopes. We illustrate the speed-up of the Vaidya walk over the Dikin walk via several numerical examples and discuss possible new and faster algorithms for sampling from polytopes.

Item not freely available? Link broken?
Report a problem accessing this item