- Rating
- 3(+1)
- Confidence
- 2
- Informativeness
- 2
- Presentation
- 1
- Soundness
- 3
Read review
Paper summary
Suppose we are given two probability distributions and on a set of size . We are further given samples from an unknown probability distribution on the same set. Let denote the TV-distance from to , and let be the index for which the TV distance is smaller. Given an approximation factor , the goal is to output an index such that with probability at least , over the choice of the samples and the randomness of the algorithm,
,
where is small positive. Ideally, should be independent of the universe size , and depend only on and . A classical algorithm due to Yatracos shows that is achievable in this setting. Bousquet et. al. (2019) showed that if is not to be a function of , then no constant is achievable. In the course of proving some other related results, Aamand aet al. (2026) showed that for any , samples do not suffice.
This paper proves that for any , samples are needed, and further, that these many samples are enough via the known minimax optimal algorithms for TV-distance estimation (Jiao at al., 2018).
The paper starts with the lower bound construction of Bousquet et al. (2019), as corrected by Aamand et al. (2026). However, to boost the sample complexity, the paper brings to bear upper bounds on TV distance of between mixtures of Poisson distributions with a number of matching moments. Here the paper use ideas from a paper of Wu and Yang (2015). Similar ideas were also used by Jiao et al. (2018) in the analysis of their minimax optimal algorithm for TV distance estimation (e.g. compare their Lemmas 32 and 33 with Lemmas 8 and 6 in this paper).
Critical strengths
-
The paper gives a tight sample complexity result for a very natural problem.
-
It brings together interesting techniques to do so.
Critical weaknesses
At several places, the writing is very unclear. Sometimes, the logical flow of arguments is not clear. Elsewhere, various quantities and objects are not properly defined and I had to reverse-engineer what the paper might have meant. This makes the paper extremely hard to read. Some examples are given below.
Given these issues, I think whether the paper should be accepted depends largely upon ICLR's focus. If the focus is to accept an interesting result even if the paper is almost unreadable for a human, then this paper should be accepted. Otherwise, it should probably be accepted only after a substantial rewriting. Since I am not sure which way the ICLR guidelines lean, I am currently registering a score of "weak reject". Please feel free to update it in either direction based on the focus of the conference. With clearer writing, my confidence in the correctness would probably also have been much higher.
-
lines 37-38. "The task calls for a single choice. This suggests that comparison might need much less data than estimating the discrepancy of each model." It is not that comparisons might need much less data because the task calls for a single choice. The point is that comparing which of two choices is better on a metric might potentially require less data than estimating the same metric accurately for each of the choices.
-
lines 79-80. What does "subsequent work improves the organization of candidate comparisons" mean?
-
line 160. "The known-reference estimator of Jiao et al." This is the first reference in the paper, I think, to the fact that the estimator of Jiao et al. assumes that one of the two probability distributions it considers is known fully (I suspect that is what "known-reference" means) while the other is available through samples. Needless to say, this is a very reader-unfriendly way to cite a result that underlies the main sample complexity upper bound argument of the paper. The rest of this argument, as written out in lines 160-171 is also very telegraphic. Given this argument is central to the paper's main upper bound result, I would have expected a cleaner description of how exactly the approach of Jiao et al. is being used.
-
Another glaring example of this is Figure 1 that claims to summarize the construction in lines 175-184. The technical terms appearing in the figure appearing in the figure ("rankings", "moment lifting" etc.) don't appear in the text description, and the terms appearing in the text description ("world", "prior" etc.) do not appear in the figure. It is not even clear if there is any correspondence whatsoever between the figure and the description in the text in lines 175-184.
-
This issue continues to the technical section. On line 210, it is not clarified whether the same weight is placed on each coordinate of the first half, or on the first half as a while. What are the "raw weights" whose "discrepancies" are being calculated here? A proper definition of the quantities and is not even given here (they are given much later, on page 8, lines 385-386).
It requires some reverse engineering to figure out that they are the expected TV distance between a "random" distribution that puts mass on each coordinate in and mass on each coordinate in , and the distributions and respectively. But the paper does not make it clear at all at this point, and in fact the expressions are consistent with the random distribution being defined alternatively as the one where the mass of the each coordinate is a different sample from the same distribution as in the above description. Again, the paper does not clarify which case it is at this point. (Discussions at the beginning of the next section, on lines 239-240, and much later, on lines 374-375, seem to suggest that this latter situation is closer to what the paper wants.)
-
This is a relatively smaller issue compared to many of the others, but the choice in eq. (6) would appear much less mysterious, if the paper had noted that choosing would cause the ratio to be exactly , so they choose to be smaller (in fact exactly half of this) so as to make this ratio strictly larger than .
-
lines 242. "Conditional of visiting a given pair times..". I don't think till this point the paper has defined which random process is "visiting" these pairs. I am not sure how one can even talk about the probability in the next display without specifying what the underlying random process is.
-
line 287. I am not sure what the relevance of the sentence "Small transport cost is compatible with a growing support." is to the rest of the paragraph.
-
Again, a relatively minor issue compared to many of those above: unlike what the description in the paper makes it sound, eq. (7) has nothing to do with the specifics of "size-biasing", and holds for every pair and of probability distributions: it is a direct and easy consequence of "Markov's derivative inequality" and the definition of the Wasserstein distance (as given on line 283).
-
Proof of Lemma 8, line 786. The random variable is used without definition. What are the "two joint laws" referred to in line 792? How do and enter the picture? (Presumably is either or , but this is the kind of technical detail that a reader of an ICLR paper can, I think, reasonably expect the paper to specify, rather than leaving it for the reader to conduct an exegesis of what the paper might have meant.) A few such typos/missed explanations are fine, but unfortunately this paper seems to have too many of them.
-
I had a hard time following what the paragraph on lines 478-485 was trying to say. Compare for example the following sentence from the paper in these lines: "When the output can be a newly constructed distribution, aggregation achieves factor 2 with a sample bound independent of N for a fixed candidate family, precision, and confidence (Bousquet et al., 2019; 2021). These results make the permitted output a consequential part of the validation problem." It was not very clear to me what this means, but what I think this probably means is the following (quoted from the abstract of Bousquet et al. 2019): "if one allows the algorithm to output arbitrary densities (e.g. a mixture of densities from ), then the approximation factor can be reduced to 2, which is optimal. In particular this demonstrates an advantage of improper learning over proper in this setup." I think the latter is both much simpler and much clearer.
My evaluation of this paper would be far higher if the paper paid some attention to such clarity of exposition.
Questions for authors
My main concern is with the readability of the paper, and these are described in detail in the "Weaknesses" section. Some other minor suggestions are given below.
-
The techniques of Wu and Yang (2015) is crucial for this paper, but the paper only cites the arxiv version of their paper "Chebyshev polynomials, moment matching, and optimal estimation of the unseen", and not the published journal version in Annals of Statistics.
-
No references (links/conference proceedings or journal issue details etc.) are provided for the citations to Aiyer et al. (2026a, 2026b).
-
Isn't the first inequality on line 143 an equality: , since, by definition and ?
=======
Score increased to 3 after author response.
3 comments
Reply to Reviewer kkpH (2/2)
- Line 287. What is the relevance of "Small transport cost is compatible with a growing support"?
The sentence was meant to say why the two requirements of Section 4, matching many moments and staying close to the seed laws and , can hold together. It has been replaced by a paragraph that explains this (p. 7, in blue). Moving a small probability from a point of to a large value changes the law by at most in , and hence each expected absolute error by at most , while it changes the th moment by about . With small and large, this gives the freedom to match moments while preserving the ranking.
- Eq. (7) of the original. It has nothing to do with size biasing. It holds for every pair , of probability distributions and follows from Markov's derivative inequality and the definition of the Wasserstein distance.
Thanks for the comment. Section 4.1 introduces the inequality, now Eq. (8), as a general fact for any two probability laws on an interval and any polynomial of degree at most . It follows from the definition of , the mean value theorem and Markov's derivative inequality (p. 7, in blue). We need it because, once the interval has length of order , it bounds the mismatch by a multiple of times the supremum norm of on that interval. A correction of total mass of order then removes the mismatch, and the matched laws stay close to the seed laws. Size biasing enters only in the next paragraph, where Eq. (8) is applied.
- Proof of Lemma 8. is used without definition. What are the "two joint laws", and how do and enter?
Yes, is either or . Thanks for the pointing it out. We have revised the proof (Appendix C.1, pp. 19-20, in blue) accordingly. We define two experiments, with in the first and in the second. The two joint laws are the laws and of in these experiments. and enter through their moments, which agree up to order , and this is why the two joint laws agree on the event .
- Lines 478-485. The paragraph on improper output is hard to follow, and the abstract of Bousquet et al. (2019) says it more simply and clearly.
Yes, that is what the paragraph was trying to say. Thank you for the clearer formulation. We have revivsed it following the sentence you quote from Bousquet et al. (p. 10, in blue). It now says that in our problem the selector outputs one of the two candidates (proper selection), and that if the output may be an arbitrary distribution, for example a mixture of the candidates (improper selection), then with a sample size independent of the approximation factor can be reduced to 2, which is optimal.
Q1. The paper cites only the arXiv version of Wu and Yang (2015), and not the published journal version in the Annals of Statistics.
Thank you for pointing it out. We now cite the journal version in The Annals of Statistics, so the citation reads Wu & Yang (2019).
Q2. No references (links/conference proceedings or journal issue details etc.) are provided for the citations to Aiyer et al. (2026a, 2026b).
Thank you. We have added the publication details. Aiyer et al. (2026a) is now cited with its ICML proceedings, and Aiyer et al. (2026b) with its arXiv number and a note that it is to appear at NeurIPS 2026.
Q3. Line 143. Isn't the first inequality an equality, ?
The first relation in the chain is an equality, and the second is an inequality in general. The original display merged the two, and Section 2.1 now separates them and explains the second (p. 4, in blue). The Scheffé rule puts at least as close to the selected candidate as to the other one, with equality only when is exactly at the midpoint.
Here is an example. Take , and , and suppose is the worse candidate. The rule selects because is above the midpoint , and while .
We hope the revised version is much easier to read, and we would be glad to answer any further questions.
Response
Thank you for the detailed response. I could not read through all the changes fully, but the parts that I checked do seem much more readable now. I will revise my score upwards.
Reply to Reviewer kkpH (1/2)
Dear Reviewer kkpH,
Thank you very much for your careful reading and for the detailed comments. We have significantly revised the whole paper to improve the presentation. We first summarize the main revisions made in response to the comments.
Next, we provide our reponses as follows.
We agree with your formulation and have removed that sentence. The introduction now says that when a factor c>1 is allowed, choosing a model might need much less data than estimating both TV errors, with the Scheffé rule at c=3 as the example (p. 1, in blue).
It meant that later work reduces the computation needed for large families of candidates. The phrase was vague, so Section 1.1 now explains what each of the cited papers achieves (p. 3, in blue).
Thanks for pointing it out. "Known-reference" meant that one distribution is known in full while the other is sampled, and we removed the term. The setting is now stated where the estimator is first cited (p. 1, in blue) and again in Section 2.2 (p. 4, in blue). Section 2.2 now writes out the argument step by step. It describes the estimator of Jiao et al., takes the bound on its mean squared error from their Theorem 2, applies Markov's inequality and a union bound, and then simulates Poisson sampling with a fixed number of samples (pp. 4-5).
Thanks for the comments. We have revised the roadmap (now it is Fig.2) to make it consistent with the main body. Specifically, the first paragraph of Section 3 defines a prior, its sample law, the two worlds and the ranking gap, and the second paragraph walks through the three boxes of the figure (p. 5, in blue).
Each coordinate x gets its own independent weight Wx. We have revised section 3 to make it explicit(p. 6, in blue). The same passage defines the raw discrepancy Di=2N1∑x∣Wx−Nqi(x)∣ in Eq. (4) and then its expectations in world +, rgood:=ED0 and rbad:=ED1, in Eqs. (5)-(6).
The "raw weights" of the original are these weights Wx before the target is normalized, and Di equals the TV error when the weights sum to N. So, rgood and rbad are the expected TV errors of the two candidates, up to the normalization of the target.
Only the paired example (lines 239-240 of the original) draws one weight per pair of coordinates, and Appendix A.2 states this difference (p. 14, in blue).
Thank you for this suggestion. We have revised our manuscript accordingly. The text before the equation, now Eq. (7), says that β=(3−c)/(1+c) would make the ratio exactly c, and that we take half of this value so that the ratio exceeds c with a margin (p. 6, in blue).
Sorry that the original did not define this process. The paired example is now in Appendix A.2 (pp. 14-15). There, a pair is visited when one of the m observations falls in it. Every pair has probability 2/N, so the visited pairs form an IID uniform sequence that is independent of the weights. Given this sequence and the weight of a pair, each observation in that pair falls on its coordinate in the first half independently, and the display you ask about averages the resulting probability over the weight (p. 14, in blue). Proposition 5 gives the full statement and proof.