Sun Dec 8th through Sat the 14th, 2019 at Vancouver Convention Center
The MCMC sampling is performed by homogenizing the distribution and using existing mixing results for the homogeneous case. This makes the argument simple and the bound is also weak, involving 2^d. This is the main weakness of the paper. Questions: * In which cases the assumptions of theorems 3,4 hold? In addition to SLC, they have some matroid related assumptions. Since these results intend to demonstrate the power of the SLC class, these should be discussed in more detail. * How the diversity related \alpha enters the mixing bounds? It seems that the bound depends very weakly on \alpha only through \nu(S_0). Edit following author's response: I'm inclined to keep my score of 6. This is due to following reasons: 1) I still find the theoretical contribution ok but not particularly strong, given existing results. As mentioned in the review, it is a weak, unpractical bound, and the proof, in itself, does not provide particular mathematical novelty. 2) The claims that "in practice the mixing time is even better" are not nearly sufficiently supported by the experiments, and therefore the evidence provided to practitioners is very limited. 3) My question regarding dependence on $\alpha$ was not answered in a satisfactory manner. I would expect a more explicit dependence on $\alpha$, since with higher diversity the problem should be more complicated. If this is not reflected in the bounds, it means the bounds are very loose.
Originality: The two algorithms presented in the paper are basically applications of the existing algorithms, namely, Metropolis Hastings sampler and distorted greedy algorithm. However, the paper presents nice new theoretical results which partly guarantee that the proposed algorithms work well. The paper clearly explains how this work is related to existing ones and provides an adequate number of citations of the related works. Quality: The quality of the paper is generally high. The authors have done careful work in terms of both theory and experiment. In particular, I think that the theoretical results of the paper are interesting and have a great value. Clarity: The paper is clearly written and well-organized. Although the paper includes some mathematical terminology which many participants of the conference might not be familiar with, I imagine that the nice presentation of the paper enables such participates to understand at least intuitively the contents of the paper. Regarding the presentation of the paper, I have only the following minor comments: (a) line 25: Is the word "conxevity" correct? (b) p.3, last line: The range of $y$ or the domain of $H_k f$ should be given. (c) line 175: ov ===> of (d) lines 222 and 223: It is not clear what 'all examples discussed above' refer to. (e) lines 250-252: The definition of OPT should be given. (f) line 255: appling ===> applying Significance: I think that the algorithms and theoretical results of the paper are important. The presented algorithms are based on the existing ones, but they are potentially useful for practitioners. The theoretical results related to the algorithms are very nice. The conclusions induced from the experimental results do not seem particularly significant, but it is helpful to find how one of the presented algorithms works under some settings of the size and parameters. EDIT: The authors have carefully responded to my comments, and I am satisfied with their responses. I think this is a nice paper and I will keep my good score.
• Originality: the authors are very clear on what is prior work and what their contributions are. Their algorithmic contributions are both (i) clearly novel and (ii) significant improvements over naïve baselines. • Quality: the theorems and proofs are written clearly and concisely. The authors cover all the natural sub-topics that ought to be covered when connecting two fields like this: both (i) on the algorithmic side, with sampling and mode-finding algorithms, and (ii) analyzing the theoretical properites thereof. • Clarity: the paper was very well-organized and clear. Significance: while strong empirical results are left to future work, the algorithmic and theoretical contributions are significant ant stand on their own.