- Rating
- 3(+1)
- Confidence
- 3
- Informativeness
- 2
- Presentation
- 1
- Soundness
- 3
Read review
Paper summary
The paper proposes Uniform Race (UR) approximate sample rejection algorithm with a simple stochastic scoring scheme to reject the samples. The method leads to omission of the rejection threshold, a parameter that requires some knowledge of target-proposal density ratio, and has guaranteed total variation error lower than limited-budget RS upper bound. This bounds holds with any budget N and threshold M, without dependence on the importance weight envelope, tuning a threshold or other parameters. While simple in principle the algorithm is accompanied with supporting theory and empirical results showing its superiority in budget-efficient sampling error in comparison the baselines SIR and budget calibrated RS.
Critical strengths
The proposed method has several interesting properties: it eliminates the need to know the importance weight envelope for RS, or adjust a rejection threshold M for each sampling target/budget. The paper presents a rather detailed theoretical study on the efficiency of the UR method in relation to limited-N RS total variation upper bounds, providing a minimax bound over the sample selection procedure over any proposal-target pairs, and proving the uniqueness of a stochastic sample selection procedure satisfying this bound up to a constant factor. The paper further studies the induced total variance error of UR algorithm relevant to budget-bounded RS and SIR. (I did not go over the proofs in the Appendix.) And provides an appealing real world experiment to support the theoretical material.
Critical weaknesses
The writing is focused too much on the details of proofs and examples that appear unnecessary to convey the message of the paper. While the UR idea and the supporting theory are fundamentally interesting, it is difficult to follow the paper through the the technical details. I would recommend restructuring and polishing the material and moving unnecessary examples and details to the appendix. And maybe use the related work in the main text to setup the motivation for the proposed method.
Some of the sentences are too long and not completely clear when read the first time: e.g. line 90: "Consequently, the threshold giving the best guarantee hinges on the unknown target–proposal pair, including importance weights that may never appear among the N observed candidates. " Such sentences need more elaboration.
The introduction of the propositions and binary examples seem to be out of order. Proposition 1 is introduced without sufficiently motivating the results. Corollary 1 seems logically preceding Corollary 2 and Theorem 4. While Theorem 4 is directly relevant to the UR algorithm and Corollary 2 is a peripheral development. Theorem 2 and 3 are testament to the validity of the claims mentioned in the introduction but intervened with arbitrary details of special cases several times. making it necessary to reread several sections.
Some of the more urgent and interesting properties of UR are left unstudied or explicitly mentioned. With UR sample distribution converges to the exact target? If not what is the discrepancy in the limit? Is this a trivial property deduced from the rest of the paper?
While the paper is more focused on theoretical analysis of toy binary examples, it lacks more rigorous empirical study.
Minor typos:
132: , and even when -> omit and
171: is not defined
Questions for authors
Can the authors prove the asymptotic properties of the UR method, as e.g. convergence rate?
Is the uniform scaling sample selection also a good approach for resampling?
Comparing the proposed algorithm to other sampling method other than simple baselines seems appropriate to show if the method is indeed performing well in the considered experiment. Also addition of more synthetic benchmarks that are used for evaluation of sampling algorithms in high-dimensional multi-modal scenarios seems appropriate.
How is the accuracy gap total variation bound derived on line 484?
Why are all sampling methods with converging to values worse than perfect?
As the UR idea is novel and interesting I would consider reevaluating the rating if any of the proposed modification are made to improve the paper.
Common response to the reviewers
We thank the reviewers for their thoughtful comments. We have revised the manuscript in response to the reviewers' comments. Key revisions are highlighted in blue. Unless otherwise noted, all references to the manuscript below refer to the revised version. Below, we first clarify the contribution and its relationship to existing sampling methods, then address each review.
We study how closely a selected sample follows the target distribution when only a fixed number of proposal samples are available. The selection rule is the classical priority sampling rule used to retain one candidate (Duffield et al., 2007). We call its use for this sampling problem uniform race (UR). Our contribution is to establish UR as a parameter-free method for approximate sampling with a fixed budget, with three main results.
The marginal output distribution includes the randomness in both generating the candidates and selecting the returned sample. The updated Table 1 summarizes the error bounds and required inputs.
Here F(M,N):=2EM(π,μ)+exp(−N/M), where EM(π,μ):=Eμ[(w−M)+] and w:=dπ/dμ. Write Cπ:=Eμ[w2] and C∞π:=esssupμw. The table omits fixed numerical factors and the additional minimum with 1. Calibrated RS uses N≥3 and chooses δcal∈(0,1) before drawing the samples used to estimate the normalizing constant.
Contribution to approximate sampling
We agree that the connection to priority sampling should be stated when UR is introduced in the main text. The original submission acknowledged this connection in Appendix A. Classical priority sampling uses selected items to estimate sums of weights. We study how closely one selected sample follows a target distribution. To our knowledge, this use of the one-item priority rule for fixed budget approximate sampling had not been studied before our work. The rule also arises naturally from the finite budget RS problem. Rather than selecting a threshold in advance, UR chooses the largest threshold that still accepts at least one observed candidate. In particular, with the candidate batch and independent acceptance uniforms Ui fixed, candidate i is accepted at threshold τ if and only if τ≤wu(Yi)/Ui. Therefore, the largest such threshold is maxiwu(Yi)/Ui, which directly gives the UR selection rule. However, this threshold depends on the observed candidates and uniforms, so the fixed threshold RS bound does not directly apply. We establish Theorem 1 by characterizing UR's conditional output distribution and comparing its error with RS at every fixed threshold. We now make the attribution and distinction explicit when introducing UR in Section 1, with further discussion in Appendix A. We provide a more detailed explanation of the design motivation and theoretical contributions in our follow-up response to Reviewer ZEwq.
Connection to Metropolis-Hastings
We also establish an exact connection to independent Metropolis-Hastings (IMH), which processes candidates one at a time. If IMH starts from one draw from the proposal and processes N−1 further independent draws, its final output has the same distribution as UR with N proposals. UR realizes this distribution through a one-shot batch selection based on independent randomized scores, without constructing intermediate Markov states. Our response to Reviewer i7q7 explains why this holds and which existing IMH bounds therefore apply to UR. The connection is summarized in Section 5, with Theorem 5 and its proof in Appendix J of our revised manuscript.