University of Cambridge > Talks.cam > Statistics > From linear programming to statistics: Fast algorithms for sampling based on interior point methods

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

  • UserMartin Wainwright (UC Berkeley)
  • ClockFriday 24 November 2017, 15:30-16:30
  • HouseMR12.

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.

Tell a friend about this talk:

This talk is included in these lists:

Note that ex-directory lists are not shown.

 

© 2006-2017 Talks.cam, University of Cambridge. Contact Us | Help and Documentation | Privacy and Publicity