A survey on Strongly Rayleigh measures and their mixing time analysis

Posted on:

Strongly Rayleigh measures are natural generalizations of measures that satisfy the notion of negative dependence. The Negative Dependence property reflects a repelling nature of items, a property that occurs across probability theory, combinatorial optimization, physics, and other fields. Negatively dependent probability measures provide a powerful tool for modeling non-i.i.d. data and thus can impact all aspects of learning and algorithm design like anomaly detection, information maximization, experimental design, fast MCMC sampling, interpretable learning etc. The class of Strongly Rayleigh measures provides the most useful characterization of Negative Dependence by grounding it in the theory of multivariate stable polynomials. This post attempts to throw some light on the origin of Strongly Rayleigh measures and Determinantal Point Processes and highlights the fast mixing time analysis of the natural MCMC chain in the support of a Strongly Rayleigh measure as shown by Anari, Gharan and Rezaei 2016.

This work has been done with Mitchell Wortsman as a part of our joint course project for Design and Analysis of Algorithms instructed by Prof. Shayan Oveis Gharan. The complete PDF post can be viewed here.

Leave a Comment