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

Add to your list(s) Download to your calendar using vCal

• Martin Wainwright (UC Berkeley)
• Friday 24 November 2017, 15:30-16:30
• MR12.

If you have a question about this talk, please contact Quentin Berthet.

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

This talk is part of the Statistics series.

This talk is included in these lists:

• All CMS events
• All Talks (aka the CURE list)
• CMS Events
• Cambridge Forum of Science and Humanities
• Cambridge Language Sciences
• Cambridge talks
• Chris Davis' list
• DPMMS Lists
• DPMMS info aggregator
• DPMMS lists
• Guy Emerson's list
• Hanchen DaDaDash
• Interested Talks
• MR12
• Machine Learning
• School of Physical Sciences
• Statistical Laboratory info aggregator
• Statistics
• Statistics Group
• bld31
• custom
• rp587

Note that ex-directory lists are not shown.