Fast Mixing Markov Chains for Strongly Rayleigh Measures, DPPs, and Constrained Sampling
We study probability measures induced by set functions with constraints. Such measures arise in a variety of real-world settings, where prior knowledge, resource limitations, or other pragmatic considerations impose constraints. We consider the task of rapidly sampling from such constrained measures, and develop fast Markov chain samplers for them. Our first main result is for MCMC sampling from Strongly Rayleigh (SR) measures, for which we present sharp polynomial bounds on the mixing time. As a corollary, this result yields a fast mixing sampler for Determinantal Point Processes (DPPs), yielding (to our knowledge) the first provably fast MCMC sampler for DPPs since their inception over four decades ago. Beyond SR measures, we develop MCMC samplers for probabilistic models with hard constraints and identify sufficient conditions under which their chains mix rapidly. We illustrate our claims by empirically verifying the dependence of mixing times on the key factors governing our theoretical bounds.
This paper presents and analyzes several Markov chains for sampling from various discrete probability distributions that allow for hard constraints. The authors analyze the mixing rate of the bases-exchange Gibbs sampler and the add-delete Gibbs sampler when the constraints are special types of matroid bases.   The authors then go on to show that a modification of the bases-exchange Gibbs sampler can be shown to mix rapidly when the target distribution satisfies the condition of being Strongly Rayleigh, a condition which is satisfied by Determinantal Point Processes.  Finally, experimental results are given which empirically demonstrate that the theoretical bounds presented depend on the correct quantities.
This paper is technically sound and addresses interesting questions relating to sampling and mixing rates. In fact, this paper generalizes two previous results:  (a) Section 2 can be considered an extension of Gotovos et al. (NIPS 2015). Unlike that paper, however, this paper allows for hard constraints. It is quite remarkable that even with these hard constraints, the authors are able to recover the same mixing rates as Gotovos et al.  (b) Section 3 can be thought of as an extension of Anari et al. (COLT 2016), but the difference is that Anari et al. could only handle homogeneous Strongly Rayleigh distributions, while this paper can handle any Strongly Rayleigh distribution. The proof, in which a Strongly Rayleigh distribution is viewed as the marginal distribution of a homogeneous Strongly Rayleigh distribution over a larger set of elements, is quite clever.    As best as I can tell, all the statements given in the paper and all the final bounds in the proofs presented in the supplementary material are essentially correct, modulo some constant factors. HOWEVER, there are some grave typos and undefined notation which make the intermediate steps in the proofs unintelligible.    Detailed comments:  1. In the proofs for Theorem 2, it appears that a factor of 2 is missing due to the fact that they are using the lazy version of the Markov chain. Thus, both of the mixing rate bounds should be increased by a factor of 2.  2. In the equations following lines 340 and 370, the factor of Z should appear in the denominator and not the numerator. Fortunately, this appears to be a typo and does not propagate through the rest of the proofs.  3. In equation (2.3) and all of appendix A, every occurrence of exp(\beta(F(\sigma_S(X,Y)) + F(\sigma_T(X,Y)))) should be replaced with exp(\beta F(\sigma_S(X,Y))) + exp(\beta F(\sigma_T(X,Y))). Similarly, every occurrence of exp(\beta(F(U_S) + F(U_T))) should be replaced with exp(\beta F(U_S)) + exp(\beta F(U_T)). This too appears to be a typo and does not propagate through the rest of the proofs.  4. In appendix A.2 and A.3, the quantity Z_F is never defined, although it seems to be taken as \sum_{U_S} exp(\beta F(U_S)).   5. In Theorem 4, it ought to be made explicit that \alpha_1 and \alpha_2 are functions of edges (S,T).  6. In Theorem 4 and the proof in appendix B, the notation |  |_+ and (  )_+ ought to be defined.  7. In the proof of Theorem 5, it should to be made clear that Theorem 10 is being instantiated with N := 2N and k := N.  8. In the figures of section 4 and appendix D, the meaning of the dashed lines ought to be made clear.