Exponentiated Strongly Rayleigh Distributions
Strongly Rayleigh (SR) measures are discrete probability distributions over the subsets of a ground set. They enjoy strong negative dependence properties, as a result of which they assign higher probability to subsets of diverse elements. We introduce in this paper Exponentiated Strongly Rayleigh (ESR) measures, which sharpen (or smoothen) the negative dependence property of SR measures via a single parameter (the exponent) that can be intuitively understood as an inverse temperature. We develop efficient MCMC procedures for approximate sampling from ESRs, and obtain explicit mixing time bounds for two concrete instances: exponentiated versions of Determinantal Point Processes and Dual Volume Sampling. We illustrate some of the potential of ESRs, by applying them to a few machine learning problems; empirical results confirm that beyond their theoretical appeal, ESR-based models hold significant promise for these tasks.
### Post-Rebuttal ###  I have read the rebuttal and would like to thank you for the clarifications.  ##################  # Summary The paper introduces a concept of exponentiated strongly Rayleigh (ESR) measure motivated by the trade-offs between diversity and quality of items in a selected subset of a ground set with n items. A measure \mu over the subsets of a ground set of n items is called strongly Rayleigh (SR) if its generating polynomial  P_{\mu}(z_1, ..., z_n) = \sum_S \mu(S) \prod_{i \in S} z_i is `real stable'. The authors take the definition of a `real stable' polynomial from [10] and define it as a polynomial without complex roots. An exponentiated strongly Rayleigh measure \mu is defined as a measure such that there exists a strongly Rayleigh measure \nu satisfying \mu(S) \prop \nu(S)^p for some p >= 0. Now, for p >1 the ESR measure promotes diversity whereas for p < 1 it allows less diverse items at the expense of their quality. For p=0 the ESR measure is uniform and for p=\infty it concentrates at the mode.  # Comments/Details - The first theoretical result is Proposition 1 which states that there exists an ESR measure which is not a SR measure. This is a key result for establishing the `novelty' of ESR measures, showing that they are not contained in the class of SR measures. The proof of this proposition might need a clarification. In particular, if in the proof of this proposition one sets z=-l_{22}^p + u and w=-l_{11}^p + \overline{u} with u \in C such that || u ||^2 = l_{11}l_{22} - det(L^p) then one obtains a complex root of the polynomial p(z, w). In my understanding this then does not align with Definition 1. Moreover, the proof of Proposition 1 contains a number of claims without a proper mathematical derivation. If these results are from other papers, then those should be cited accordingly. Otherwise, a complete proof of the proposition is required.  - The second theoretical result is Theorem 1, where it is shown that there exists a choice of p and a non-trivial matrix for which its exponent defines a determinantal point process that is an SR measure. This result is novel and establishes that some ESR measures remain SR.  - To sample from an ESR measure the authors consider two algorithms. The first algorithm is an independent Metropolis--Hastings sampler with a proposal distribution given by a SR measure. It is quite strange that the authors do not cite the paper by Metropolis or some survey on MCMC methods because there is nothing novel about this algorithm. The second algorithm is pretty much the one published in [29]. I do not see any significant novelty in this part of the paper.  - In order to study the mixing properties of the chains for sampling ESR measures the authors introduce a concept of closeness of measures (Definition 3) and provide a bound for the parameter defining it in Proposition 3. Following this, the main theoretical results are given which provide the mixing bounds for chains defined by Algorithms 1 and 2. Parts of these proofs can be obtained by mimicking previous derivations such as [5].  - In the concluding part of the section on ESR measures the authors focus on determinantal point processes and ESR measures defined by exponentiating a positive definite matrix defining such a process. For this specific case, the authors provide bounds on the parameter defining the closeness of distributions in mixing bounds for the considered sampling algorithms (see the comment on Definition 3).  - The approach is evaluated empirically via three experiments: i) an experiment illustrating the mixing properties of the chain, ii) anomaly detection problem, and iii) Nystroem method with ESR landmarks (this experiment is replicated from the paper on DPP-Nystroem from [30]). The experiments illustrate the utility of the exponent in trade-offs between quality and diversity among items from a selected subset.  ### Overall the main part of the paper is well written and easy to follow. In the appendix, it is quite difficult to follow the proof of Proposition 1 because of the claims that are expected to be accepted without a proof. In the summary of the contributions, it might be beneficial to be more explicit and state that the proposed algorithms are not novel contributions of the paper. The theoretical results providing mixing bounds for these samplers in combination with ESR measures are novel and interesting. Still the impression is that these are just minor adaptations of the previous work. I do, however, appreciate the flexibility introduced via the exponent p in ESR measures. It would be nice if the authors provided an ESR measure that is not in the context of determinantal point processes. The focus on determinantal point processes precludes other contributions and the utility of general ESR measures. ###