Fast Mixing for Discrete Point Processes

author: Patrick Rebeschini, Yale Institute for Network Science, Yale University
published: Aug. 20, 2015,   recorded: July 2015,   views: 1943


Related Open Educational Resources

Related content

Report a problem or upload files

If you have found a problem with this lecture or would like to send us extra material, articles, exercises, etc., please use our ticket system to describe your request and upload the data.
Enter your e-mail into the 'Cc' field, and we will keep you updated with your request's status.
Lecture popularity: You need to login to cast your vote.


We investigate the systematic mechanisms for designing fast mixing Markov chains Monte Carlo algorithms to sample from discrete point processes. Such processes are defined as probability distributions $\mu(S)\propto \exp(f(S))$ over all subsets $S\subseteq 2^V$ of a finite set $V$ through a bounded set function $f:2^V\rightarrow \mathbb{R}$. In particular, a subclass of discrete point processes characterized by submodular functions (which include determinantal point processes, log-submodular distributions, and submodular point processes) has recently gained a lot of interest in machine learning and shown to be effective for modeling diversity and coverage. We show that if the set function (not necessarily submodular) displays a natural notion of decay of correlation, then it is possible to design fast mixing Markov Chain Monte Carlo methods that provide size-free error bounds on marginal approximations. The conditions that we introduce involve a control on the second order (discrete) derivatives of set functions. We then provide sufficient conditions for fast mixing when the set function is submodular, and specialize our results for canonical examples.

See Also:

Download slides icon Download slides: colt2015_rebeschini_point_processes_01.pdf (212.0┬áKB)

Help icon Streaming Video Help

Link this page

Would you like to put a link to this lecture on your homepage?
Go ahead! Copy the HTML snippet !

Write your own review or comment:

make sure you have javascript enabled or clear this field: