Convergence bounds for the Random Walk Metropolis algorithm - Perspectives from Isoperimetry

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

• Sam Power, University of Bristol
• Thursday 11 May 2023, 11:00-12:00
• Cambridge University Engineering Department, CBL Seminar room BE4-38..

If you have a question about this talk, please contact Hong Ge.

Abstract: When carrying out inference in probabilistic models, a recurring task is to examine high-dimensional probability measures with complex structure and ‘make sense of’ them in a suitable way. By now, a wide range of practical solutions for this task exist, each offering their own tradeoffs between computational efficiency, statistical accuracy, practical robustness, and beyond. By analogy with fields such as optimisation, we might now seek to answer questions like “which classes of probability measure can be understood efficiently?”, as well as quantitative, algorithm-specific versions of this question. This encourages the rigorous comparison of existing methods, and can guide the design of improved methods.

In recent work, we study this question in the context of the Random Walk Metropolis algorithm, a simple Markov chain-based iterative algorithm for sampling from probability measures, given only access to an unnormalised density. Our analysis highlights the key role of ‘isoperimetry’, a geometric notion for probability measures which appears to robustly capture the complexity of understanding probability measures with local algorithms.

In this talk, I will present our theoretical results about the convergence behaviour of the Random Walk Metropolis algorithm (as well as related results for the Preconditioned Crank-Nicolson algorithm for sampling from GP posteriors), and contextualise the role which isoperimetry plays in enabling these results. If time permits, I will also offer high-level comments on some potential implications of isoperimetry for related approximate inference methodologies (e.g. VI, NFs, DDMs).

(joint work with Christophe Andrieu, Anthony Lee, and Andi Wang; preprint available at https://arxiv.org/abs/2211.08959)

Bio: Sam Power is a postdoctoral research associate at the University of Bristol. His research centres around the design and analysis of stochastic algorithms, with applications to problems in modern statistics and machine learning. Some particular interests include Markov chain Monte Carlo and Sequential Monte Carlo algorithms, and how theoretical studies of these methods can enable their robust, automatic, and efficient deploymeent.

This talk is part of the Machine Learning @ CUED series.

This talk is included in these lists:

• Seminar
• All Talks (aka the CURE list)
• Biology
• CBL important
• Cambridge Centre for Data-Driven Discovery (C2D3)
• Cambridge Forum of Science and Humanities
• Cambridge Language Sciences
• Cambridge Neuroscience Seminars
• Cambridge University Engineering Department, CBL Seminar room BE4-38.
• Cambridge talks
• Chris Davis' list
• Creating transparent intact animal organs for high-resolution 3D deep-tissue imaging
• Featured lists
• Guy Emerson's list
• Hanchen DaDaDash
• Inference Group Summary
• Information Engineering Division seminar list
• Interested Talks
• Joint Machine Learning Seminars
• Life Science
• Life Sciences
• ML
• Machine Learning @ CUED
• Machine Learning Summary
• Neuroscience
• Neuroscience Seminars
• Neuroscience Seminars
• Required lists for MLG
• Simon Baker's List
• Stem Cells & Regenerative Medicine
• Trust & Technology Initiative - interesting events
• bld31
• dh539
• kt532's list
• ndk22's list
• ob366-ai4er
• rp587
• yk373's list

Note that ex-directory lists are not shown.