- Rating
- 2
- Confidence
- 2
- Informativeness
- 2
- Presentation
- 2
- Soundness
- 3
Read review
Paper summary
The paper considers the problem of separating an original dataset sampled from a two-component mixture using a reference dataset sampled from one component. It greedily selects observations without replacement from the two-component dataset (until a stopping criterion is met) aiming to minimize the MMD to the distribution of the reference dataset. Observations from the original dataset that have not been selected, constitute the remainder subset that is representative of the other component. The paper presents an extensive theoretical analysis of how the selection of candidate instances affects approximation error and how stopping size determines remainder quality, with convergence guarantees under geometric assumptions. Experiments on synthetic data and three real datasets examine selection quality and stopping rules.
Critical strengths
S1. The main strength of the paper is theoretical analysis. It provides an analysis of greedy selection without replacement, specifying how candidate selection affects approximation quality. It establishes an exact decomposition of remainder error and provides error bounds.
S2. Empirical evidence is provided that the approach performs better in approximating the target distribution.
Critical weaknesses
W1. The contribution and novelty is not clear from an aglorithmic point of view. The method is simple combining incremental greedy MMD minimization with existing stopping procedures. Its distinction from MMD-Critic and related approaches, and why it should perform better, remain insufficiently clear. The theoretical bounds do not guide selection or stopping, while the strongest guarantees require restrictive assumptions and are developed for the energy kernel.
W2. Empirical evidence is insufficient: experiments cover only three real datasets and comparison is made with only two competitors and using only the specific kernel. Improved results in positive-distribution matching do not consistently improve remainder recovery. Moreover, An application of the method to a real problem would illustrate practical significance.
Questions for authors
Q1. To clarify the algorithmic novelty, could you briefly describe the closest greedy MMD approaches and explicitly specify their objectives, selection rules, and stopping procedures illustrating the differences to the proposed method?
Q2. What practical guidance do the theoretical bounds provide? Are they exploited in the algorithm?
Q3. Which theoretical results extend beyond the energy kernel, and how sensitive is performance to kernel choice?
Q4. Given the small number of datasets and narrow range of baselines, could you expand the experimental evaluation to establish whether the improvements generalize, particularly for approximation of the remainder?
Q5. Are there real-world applications of the proposed method?
3 comments
I thank the authors for their response and the additional experiments. I remain concerned about the limited novelty of the proposed methodology relative to existing methods, its real-world impact and the practical value of the theoretical results.
We thank the reviewer for the follow-up and address the concerns as follows.
Novelty. We agree that the greedy update rule is not new and do not claim it as our contribution. Our contribution is the analysis of this rule in a setting that, to our knowledge, prior work has not combined: an external target, selection without replacement, and recovery of the unselected remainder. Teymur et al. (2021) and Pronzato (2023) consider external targets, but the set of available points stays the same at every step, so depletion does not arise. MMD-Critic and Shao et al. (2024) select without replacement, but their target is the candidate pool itself, so it always lies within the initial candidate hull, and no second distribution is recovered from the remainder. Our bounds explicitly account for depletion, i.e., the remaining candidate hull moving away from the target as candidates are removed.
Practical value. The results lead to concrete practical conclusions.
- Theorem 2 shows that, given an accurate selected set, the remainder is consistent if and only if the stopping fraction converges to . Selected-set error alone therefore cannot certify separation, which is why we report both and in the experiments, and a stopping rule should be judged by how accurately it estimates .
- Equation (12) splits the remainder error into selection and stopping terms. This explains, for example, why PathMin gives a smaller remainder error than KM2 on Page Blocks with : it stops closer to .
Real-world impact. The setting arises whenever a trusted reference sample exists but pooled data mix sources whose labels are lost, as in the production line example in our earlier response. In such applications, individual labels often cannot be recovered reliably where components overlap, but group-level distributions, which our paper targets, can still be recovered and suffice for downstream tasks. Following your suggestion, we added more real-world datasets for experiments; the results agree with our theoretical analysis.
We thank the reviewer for the positive assessment of our analysis and experiments. We respond to each concern below.
W1 & Q1: On Algorithmic Novelty and Differences from Existing Greedy MMD Methods
We agree that the update rule is closely related to existing methods and do not claim it as our innovation. We summarize the main differences from the closest related works in Section 5 and Table 24 in Appendix G.1, which we reproduce below
In contrast, Theorem 1 establishes a path-wise error bound for arbitrary external targets in a Hilbert space, separating the initial convex hull error, removal loss, and one-step greedy approximation cost. Theorem 2 shows that, given selected-set consistency, convergence of the stopping fraction to θ is both necessary and sufficient for remainder consistency. This question does not arise in representative subset selection,. Thus, our novelty lies in the theoretical characterization of an existing greedyrule in a distinct statistical setting, not the update rule itself.
W1 & Q2: On the Practical Implications of the Theoretical Error Bounds
We agree that our error bounds explain greedy selection; they are not used to choose the next point or the stopping time. Their practical value is to identify the mechanisms behind the error (depletion v. stopping), give conditions for consistency, and justify evaluating selection and stopping separately, as our experiments do.
W1 & Q3: Which Theoretical Results Extend to Other Kernels?
W2 & Q4: On Baselines, Experimental Scope, Kernel, and Remainder Recovery
We have expanded the evaluation to five real-world datasets, adding Dry Bean and Spambase, and have added the Gaussian RBF kernel. The added content (blue text) is in the section 4 (Experiments, Page 8) and Appendix F.4 (Page 30). We compared Min-MMD Greedy (the same greedy strategy as EG), Kernel Herding, R-GKHR, and LabelOracle. All methods were evaluated at the same selection budget k=θN2, allowing us to isolate selection-order effects from stopping errors. The new results show that the improvement can be generalized to another kernel and the advantage holds in remainder recovery.
We do not claim that EG always gives the best remainder. Our claim is that EG selects accurately and, with accurate stopping, also recovers the remainder well. Let $ e_P =MMD ( \hat{P}_S,P) $ and $ e_Q = MMD(\hat{P}_R,Q) $. When the stopping fraction equals θ, Equation (12) implies ∣eQ−1−θθeP∣≤1−θMMD(M^,M), where $ \hat{M} $ is the empirical distribution of the candidate pool. Thus, the two errors are tied, but a smaller $ e_P $ does not mean a smaller $ e_Q $ in finite samples due to mixture-pool sampling error. This is why we report both errors rather than $ e_P $ alone.
W2 & Q5: On Real-World Applications.
Our framework fits data curation where a reliable reference sample exists, but the candidate data mix sources. For example, a factory has two production lines A and B, whose sensor measurements follow distributions P and Q, respectively. The factory maintains a set of verified reference samples from line A, but source labels were lost during historical data integration, making it impossible to determine which production line generated each observation. Nevertheless, production logs still provide the overall mixture proportion θ. The pooled data can thus be modeled as M=θP+(1−θ)Q. Our method splits the poolinto two groups approximate P and Q, enabling production-line-level quality monitoring and distributional analysis without recovering individual labels.