From linear programming to statistics: Fast algorithms for sampling based on interior point methods

Sampling from distributions is a core challenge in
statistics, computer science and operations research. An evolving
body of work is showing how algorithms from optimization can be
modified so as to sample from distributions. In this talk, we describe and analyze some novel algorithms, based on modifications of
interior point methods used in linear programming, for sampling points
uniformly from polytopes. Such sampling algorithms are useful for
volume computation, contigency table analysis, post selection
inference, and the hard disk problem in statistical physics, among
other applications. We propose and analyze the mixing times of two new Markov chain methods, referred as the Vaidya and John walks, both of which
yield substantial improvements over the state-of-the-art Dikin walk.

Based on joint work with: Yuansi Chen, Raaz Dwivedi, and Bin Yu
Pre-print: https://arxiv.org/abs/1710.08165

• Speaker: Martin Wainwright (UC Berkeley)
• Friday 24 November 2017, 15:30–16:30
• Venue: MR12.
• Series: Statistics; organiser: Quentin Berthet.