Source-linked AI summary
Monte Carlo Markov Chain Algorithms for Sampling Strongly Rayleigh Distributions and Determinantal Point Processes
Nima Anari, Shayan Oveis Gharan, Alireza Rezaei
TL;DR
Markov-chain sampling of k-DPPs remained an open question. The paper analyzes the natural MCMC for homogeneous strongly Rayleigh distributions and proves rapid mixing, extending the sampling result to k-DPPs.
Problem
Whether the natural Markov chain mixes rapidly for k-DPPs remained open, despite prior attempts to bound its mixing time.
Source: §1.1 · p. 4Method
The paper analyzes the natural MCMC on homogeneous strongly Rayleigh distributions by lower-bounding its spectral gap.
Source: §1 · p. 2, §1.2 · p. 5Results
The natural MCMC rapidly mixes on homogeneous strongly Rayleigh supports, and the result applies to k-DPPs.
Source: §1 · pp. 2–3Takeaways & Limitations
The chain can efficiently generate approximate samples of k-DPPs.
Source: §1 · p. 2, §1.1 · p. 4The log-Sobolev constant and L2 mixing time may be unbounded because the bound depends on the minimum probability of a supported state.
Source: §1.2 · p. 5
Abstract
from arXiv · showhide
Strongly Rayleigh distributions are natural generalizations of product and determinantal probability distributions and satisfy strongest form of negative dependence properties. We show that the "natural" Monte Carlo Markov Chain (MCMC) is rapidly mixing in the support of a {\em homogeneous} strongly Rayleigh distribution. As a byproduct, our proof implies Markov chains can be used to efficiently generate approximate samples of a $k$-determinantal point process. This answers an open question raised by Deshpande and Rademacher.
1 Introduction
The paper proves rapid mixing for the natural MCMC on supports of homogeneous strongly Rayleigh distributions and uses this result to address approximate sampling of k-DPPs. It also outlines a weighted matroid-based proof and explains why a comparable log-Sobolev bound may not follow.
1 Introduction
- The natural MCMC rapidly mixes on the support of a homogeneous strongly Rayleigh distribution.The main theorem applies from a starting state in the support and yields an approximate sample.Source: §1 · pp. 2–3
- The chain proposes exchanging one element of the current set for one outside it, and is reversible, irreducible, and lazy.It stays in each state with probability at least 1/2; irreducibility follows from the matroid-bases support result for homogeneous strongly Rayleigh distributions.Source: §1 · p. 2
- Given a sufficiently probable supported starting set and an evaluation oracle, the theorem yields approximate samples with poly(n, k, log(1/ε)) oracle calls.The stated starting-set condition is µ(S) ≥ exp(−n).Source: §1 · p. 3
1.1 Determinantal Point Processes and the Volume Sampling Problem
- The result addresses the open question of using Markov chains to sample k-DPPs, which are strongly Rayleigh measures closed under truncation.The paper states that the chain can efficiently generate approximate k-DPP samples.Source: §1.1 · p. 4
- For k-DPPs, the paper gives an approximate-sampling algorithm from the ensemble matrix and uses a greedy algorithm to select its starting state.Each chain transition takes time polynomial in k.Source: §1.1 · p. 4
1.2 Proof Overview
- The proof lower-bounds the chain’s spectral gap using negative association and chain decomposition, but the log-Sobolev constant may be unbounded.The stated bound depends on the minimum probability of a supported state, which need not be bounded in terms of n and k.Source: §1.2 · p. 5
2 Background
This background sets up mixing-time analysis through the Poincaré constant and introduces negative association and chain decomposition as tools for bounding it.
2.1 Markov Chains and Mixing Time
- A chain is lazy when each state has self-transition probability at least 1/2; reversibility means the stationary flow between each pair of states balances.Source: §2.1 · p. 6
- For reversible, irreducible, lazy chains, the Diaconis–Stroock theorem turns a Poincaré-constant lower bound into an upper bound on total-variation mixing time.Source: §2.1 · pp. 6–7
- Theorem 2.3 lower-bounds the Poincaré constant of Mµ, and the text says this result together with the mixing-time bound yields Theorem 1.1.Source: §2.1 · p. 7
2.2 Strongly Rayleigh Measures
- Strongly Rayleigh measures are negatively associated, and conditioning preserves strong Rayleigh; negative association is identified as key to the chain’s Poincaré lower bound.Source: §2.2 · p. 7
- The theorem applies more broadly to homogeneous measures when the measure and all its conditional measures are negatively associated.Source: §2.2 · p. 7
2.3 Decomposable Markov Chains
- The decomposition technique analyzes a two-block projection chain and within-block restriction chains, bounding the original chain’s Poincaré constant by the minimum of their constants.Source: §2.3 · p. 8
3 Inductive Argument
The proof inducts on the support size, splitting states according to whether a chosen element is present. It constructs a modified kernel using a fractional matching to obtain the bounds needed to complete the induction.
3 Inductive Argument
- A coordinate with probability strictly between zero and one partitions the support into states where that element is absent or present; the restricted chains are again strongly Rayleigh.The proof applies induction to these two nonempty parts of the support.Source: §3 · p. 8
- The replacement kernel preserves µ and is bounded above by the original transition probabilities, while agreeing with the original chain within each part.These properties make its Poincaré constant a lower bound for the original chain’s, enabling the decomposition argument.Source: §3 · p. 9
- The inductive step completes by applying the decomposition theorem to a modified chain whose restriction and projection chains have Poincaré constants bounded below by Cµ.The modified chain agrees with the original on each restriction chain, and its projection chain has the required bound.Source: §3 · pp. 8–9
3.1 Proof of Lemma 3.1
- A fractional perfect matching between the two parts supplies weights only on pairs connected by transitions of the original chain.The matching is used to construct the replacement kernel and establish its required cross-partition property.Source: §3.1 · pp. 9–10
- The constructed kernel’s projection has Poincaré constant Cµ, and the proof completes the remaining cross-partition condition of Lemma 3.1.Together, these establish the projection bound and finish the lemma used in the induction.Source: §3.1 · pp. 10–11
- Negative association yields Hall’s condition for the transition support graph, and a max-flow/min-cut argument produces the required unit flow.The flow out of each state in one part is proportional to its µ-mass; the capacities are normalized by the masses of the two parts.Source: §3.1 · p. 11