acceptodds
Under review as a conference paper at ICLR 2027

The Sample Cost of Accurate Model Comparison in Total Variation

Abstract

Choosing between two generative models asks for one decision rather than an estimate of either model's error. How much data can this distinction save? We study two completely known distributions on an alphabet of size , with independent evaluation data from an unknown target distribution. A classical selector achieves a factor-3 approximation to the smaller total variation distance using a number of samples independent of . We show that every fixed improvement below factor 3 requires samples in the worst case, at sufficiently small fixed additive error. The known upper bound for estimating total variation gives a matching dependence on . Thus accurate comparison and numerical distance estimation have the same domain-size complexity, even with only two simple candidate distributions. The proof preserves a reversed model ranking while matching logarithmically many moments of the target probabilities. We give a general moment construction, a direct Poisson-thinning argument, and an explicit reduction between exact-factor comparison and distance estimation.

Primary area:
learning theory
Keywords:
model comparison, hypothesis selection, total variation distance, sample complexity, lower bounds, distribution testing, moment matching, generative model evaluation

Reviews

Among:
Shape:
1234this paper, Top 15%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 3.00 over 3 reviews, above 85% of the others.
Reviewer_kkpHOpenReview ↗
Rating
3(+1)
Confidence
2
Informativeness
2
Presentation
1
Soundness
3
Read review
Paper summary

Suppose we are given two probability distributions q0q_0 and q1q_1 on a set of size NN. We are further given mm samples from an unknown probability distribution pp on the same set. Let did_i denote the TV-distance from pp to qiq_i, and let i∗i^{*} be the index for which the TV distance is smaller. Given an approximation factor c>1c > 1, the goal is to output an index i^\hat{i} such that with probability at least 1−δ1 - \delta, over the choice of the samples and the randomness of the algorithm,

di^<cdi∗+ϵd_{\hat{i}} < c d_{i^{*}} + \epsilon,

where ϵ\epsilon is small positive. Ideally, mm should be independent of the universe size NN, and depend only on ϵ\epsilon and δ\delta. A classical algorithm due to Yatracos shows that c=3c = 3 is achievable in this setting. Bousquet et. al. (2019) showed that if mm is not to be a function of NN, then no constant c<3c < 3 is achievable. In the course of proving some other related results, Aamand aet al. (2026) showed that for any c<3c < 3, m=o((N))m = o(\sqrt(N)) samples do not suffice.

This paper proves that for any c<3c < 3, m=Ω(N/log⁡N)m = \Omega(N/\log N) 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
  1. The paper gives a tight sample complexity result for a very natural problem.

  2. 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.

  1. 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.

  2. lines 79-80. What does "subsequent work improves the organization of candidate comparisons" mean?

  3. 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.

  4. 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.

  5. This issue continues to the technical section. On line 210, it is not clarified whether the same weight U0U_0 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 rgoodr_{\mathrm{good}} and rbadr_{\mathrm{bad}} 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 U0/NU_0/N on each coordinate in [1,N/2][1, N/2] and mass V0/NV_0/N on each coordinate in [N/2+1,N][N/2 + 1, N], and the distributions q0q_0 and q1q_1 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.)

  6. 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 β=(3−c)/(1+c)\beta = (3-c)/(1+c) would cause the ratio rbad/rgoodr_{bad}/r_{good} to be exactly cc, so they choose β\beta to be smaller (in fact exactly half of this) so as to make this ratio strictly larger than cc.

  7. lines 242. "Conditional of visiting a given pair kk 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.

  8. 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.

  9. 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 SS and TT 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).

  10. Proof of Lemma 8, line 786. The random variable XX is used without definition. What are the "two joint laws" referred to in line 792? How do UU and VV enter the picture? (Presumably XX is either UU or VV, 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.

  11. 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 Q\mathcal{Q}), 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: D=∣qb(A)−qg(A)∣=2∣p^(A)−qg(A)D = |q_b(A) - q_g(A)| = 2|\hat{p}(A) - q_{g}(A), since, by definition b,g∈{0,1}b, g \in \{0, 1\} and b≠gb \neq g?

=======

Score increased to 3 after author response.

3 comments
AuthorsOpenReview ↗

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.

  • Sections 1 and 1.1 state the setting in the first paragraph and reword the motivation and the related work.
  • Section 2.2 writes out how the estimator of Jiao et al. gives the upper bound.
  • Sections 3 to 5 now define the weights, the raw discrepancies and their expectations explicitly, and the roadmap, now Figure 2, uses the terms of the text. The paired example moved to Appendix A.2.
  • The proof of Lemma 8, the paragraph on improper output in Section 6 and the reference list are revised.

Next, we provide our reponses as follows.


  1. Lines 37-38. "The task calls for a single choice" is not the reason why comparison might need less data.

We agree with your formulation and have removed that sentence. The introduction now says that when a factor c>1c>1 is allowed, choosing a model might need much less data than estimating both TV errors, with the Scheffé rule at c=3c=3 as the example (p. 1, in blue).

  1. Lines 79-80. What does "subsequent work improves the organization of candidate comparisons" mean?

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).

  1. Lines 160-171. "The known-reference estimator of Jiao et al." is the first hint that one distribution is known in full, and the rest of the argument is telegraphic.

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).

  1. Figure 1 against lines 175-184. The terms of the figure do not appear in the text, and vice versa.

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).

  1. Line 210. Does every coordinate of the first half get the same weight U0U_0, or its own sample? What are the "raw weights" and their "discrepancies"? rgoodr_{\rm good} and rbadr_{\rm bad} are defined only on page 8.

Each coordinate xx gets its own independent weight WxW_x. We have revised section 3 to make it explicit(p. 6, in blue). The same passage defines the raw discrepancy Di=12N∑x∣Wx−Nqi(x)∣D_i=\frac{1}{2N}\sum_x|W_x-Nq_i(x)| in Eq. (4) and then its expectations in world ++, rgood:=ED0r_{\rm good}:=\mathbb ED_0 and rbad:=ED1r_{\rm bad}:=\mathbb ED_1, in Eqs. (5)-(6).

The "raw weights" of the original are these weights WxW_x before the target is normalized, and DiD_i equals the TV error when the weights sum to NN. So, rgoodr_{\rm good} and rbadr_{\rm bad} 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).

  1. Eq. (6) of the original. The choice of β\beta would look less mysterious if the paper noted that β=(3−c)/(1+c)\beta=(3-c)/(1+c) gives ratio exactly cc and that half of this value is chosen.

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)\beta=(3-c)/(1+c) would make the ratio exactly cc, and that we take half of this value so that the ratio exceeds cc with a margin (p. 6, in blue).

  1. Line 242. "Conditional on visiting a given pair k times" refers to a random process that visits pairs, and none has been defined.

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 mm observations falls in it. Every pair has probability 2/N2/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.

AuthorsOpenReview ↗

Reply to Reviewer kkpH (2/2)

  1. 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 U0U_0 and V0V_0, can hold together. It has been replaced by a paragraph that explains this (p. 7, in blue). Moving a small probability ww from a point of [0,2][0,2] to a large value RR changes the law by at most wRwR in W1W_1, and hence each expected absolute error by at most wRwR, while it changes the kkth moment by about wRkwR^k. With wRwR small and RR large, this gives the freedom to match moments while preserving the ranking.

  1. Eq. (7) of the original. It has nothing to do with size biasing. It holds for every pair SS, TT 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 S,TS,T on an interval and any polynomial ψ\psi of degree at most L−1L-1. It follows from the definition of W1W_1, the mean value theorem and Markov's derivative inequality (p. 7, in blue). We need it because, once the interval has length of order L2/τL^2/\tau, it bounds the mismatch ETψ−ESψ\mathbb E_T\psi-\mathbb E_S\psi by a multiple of τ\tau times the supremum norm of ψ\psi on that interval. A correction of total mass of order τ\tau 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.

  1. Proof of Lemma 8. XX is used without definition. What are the "two joint laws", and how do UU and VV enter?

Yes, XX is either UU or VV. 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 X=UX=U in the first and X=VX=V in the second. The two joint laws are the laws PUP^U and PVP^V of (J,K)(J,K) in these experiments. UU and VV enter through their moments, which agree up to order LL, and this is why the two joint laws agree on the event {J≤L}\lbrace J\le L\rbrace.

  1. 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 NN 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, D=∣qb(A)−qg(A)∣=2∣p^(A)−qg(A)∣D=|q_b(A)-q_g(A)|=2|\hat p(A)-q_g(A)|?

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 p^(A)\hat p(A) at least as close to the selected candidate as to the other one, with equality only when p^(A)\hat p(A) is exactly at the midpoint.

Here is an example. Take q0(A)=0.8q_0(A)=0.8, q1(A)=0.2q_1(A)=0.2 and p^(A)=0.7\hat p(A)=0.7, and suppose q0q_0 is the worse candidate. The rule selects q0q_0 because 0.70.7 is above the midpoint 0.50.5, and D=0.6D=0.6 while 2∣p^(A)−q1(A)∣=1.02|\hat p(A)-q_1(A)|=1.0.


We hope the revised version is much easier to read, and we would be glad to answer any further questions.

Reviewer_kkpHOpenReview ↗

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.

Reviewer_oF9WOpenReview ↗
Rating
3
Confidence
3
Informativeness
2
Presentation
2
Soundness
3
Read review
Paper summary

This paper studies the sample complexity of hypothesis selection under Total Variation (TV) Distance when we have two models (represented as distributions over a finite space) describing the same population. They specifically study the sample complexity of obtaining approximation factors in [1,3)[1,3), which was left open by previous work such as Aiyer et. al (2026). Their main result (Theorem 1) establishes that for any fixed c∈[1,3)c \in [1,3), for sufficiently small accuracy ϵc\epsilon_c, we can choose a model close to the target distribution in TV distance with approximation factor cc and error (0,ϵc](0,\epsilon_c] using Θ(N/log⁡N)\Theta(N/\log N) samples from the target distribution. The main contribution relies in proving the lower bound here, which the authors do via a detailed moment-matching argument (Lemma 2).

Critical strengths
  1. The paper closes the gap between the earlier Ω(N)\Omega(\sqrt{N}) lower bound and O(N/log⁡N)O(N/\log N) upper bound, so the authors establishes a sharp characterization of sample complexity of TV density estimation for every approximation factor below 3. I think this is a nice contribution.
  2. I verified the proofs and the technical arguments all seem correct. In particular, I found Lemma 2 and the more general Lemma 6 to be interesting moment matching argument that could perhaps include techniques that can be applied in other problems.
  3. In general the paper is well-structured, and I really appreciated the detailed discussion of the lower bound argument in the main paper.
Critical weaknesses
  1. Although I found most of the paper to be well written, I think the introduction and discussion of related works can be improved. In particular, I think the authors can do a better job of describing their setting and why it is different from (or similar to) prior works (i.e do they consider finite N or can N be large, what is a population and what are models, etc...). As an example, the authors mention that Aiyer et al (2026) asks a similar question. I think they can make more clear the connection between the problem this paper is studying and the evaluability problem of Aiyer et al. In particular, how does the dichotomy between factor 1 and factor 3 from Aiyer et al. fit into this result. In general, I think the intro is slightly too informal in the way that it is written and can be difficult to follow for a non-technical reader. Maybe a bit more exposition would be nice.
Questions for authors
  1. Can this result be extended to general IPMs? The result from Bousquet, Kane, and Moran extends to general IPMs, and since the paper's construction extends theirs, does the same hold in this case?
  2. Is the value of ϵc\epsilon_c intrinsic to the problem or an artifact of the proof construction. More specifically, what is exact range of (c,ϵ)(c,\epsilon) for which the result in Theorem 1 is still valid?
2 comments

Dear Reviewer oF9W,

Thank you very much for taking the time to review our manuscript, for checking the proofs, and for the valuable suggestions. We respond to each point below.

Weakness. The introduction and related work should describe the setting and its relation to prior work more clearly, in particular the connection to the evaluability problem of Aiyer et al. and their dichotomy between factor 1 and factor 3.

Thank you for these suggestions. We have revised the introduction and the related work accordingly.

  • Setting. The first paragraph of Section 1 now states it (p. 1, in blue). The alphabet is finite with NN outcomes, the two models are known distributions q0,q1q_0,q_1 on it, the population is an unknown target pp, and the data are mm independent samples from pp. Our result concerns how the sample cost grows as N→∞N\to\infty.
  • Connection to Aiyer et al. Section 1.1 has a new paragraph on this (p. 3, in blue). For distances defined by binary tests, they prove a dichotomy on infinite domains. Factor 1 is achievable with a sample size independent of the domain when the tests have finite VC dimension. Otherwise, as for TV, factor 3 is achievable but no smaller factor is. Our result is a quantitative, finite-domain version of this dichotomy for TV. Factor 3 needs a number of samples independent of NN, whereas every factor below 3 costs as much as estimation at small additive error.
  • Exposition. We rewrote the introduction. It now states the main result as an informal theorem and has a new Figure 1 that draws the lower-bound construction (p. 2).

Question 1. Can the result be extended to general IPMs, as the result of Bousquet, Kane, and Moran can?

Thanks for raising this. Currently, we only focus on TV, and Section 6 lists the extension to other IPMs as an open question. The extension in Bousquet et al. (2019, Section 3.1) concerns their adaptive factor-2 algorithms, which give an upper bound. Our lower bound extends their construction for TV, and its proof uses that TV is a sum of absolute errors over the outcomes, so it does not carry over to general IPMs directly.

The lower bound also cannot hold for every IPM. Aiyer et al. (2026b) show that, with sample sizes independent of the domain, every bounded IPM is either estimable, which gives factor 1, or admits no guarantee with c<3c<3. An analogue of our result can therefore concern only IPMs of the second kind, such as TV.

Question 2. Is εc\varepsilon_c intrinsic or an artifact of the proof, and what is the exact range of (c,ε)(c,\varepsilon)?

Thank you for the question. The value εc\varepsilon_c comes from our construction, and it may not be optimal. It equals g0/4g_0/4, where g0g_0 is the ranking gap of the seed laws, and this choice leaves room for the gap to shrink during moment matching and normalization (Section 3, p. 6).

For the range, Theorem 1 covers every c∈[1,3)c\in[1,3) and every fixed ε∈(0,εc]\varepsilon\in(0,\varepsilon_c]. The range of cc cannot be extended, since at factor 3 a sample size independent of NN suffices. The restriction on ε\varepsilon is needed only for the lower bound, and the largest ε\varepsilon for which the lower bound holds is open. We now say this after Theorem 1 and in Section 6.

Thank you for the detailed rebuttal. I think this is a nice paper and will maintain my score.

Reviewer_izimOpenReview ↗
Rating
3
Confidence
2
Informativeness
2
Presentation
2
Soundness
3
Read review
Paper summary

This paper studies the sample complexity of Hypothesis Selection. Let [N]={1,…,N}[N]=\{1,\ldots,N\} be the universe and p,q0,q1∈ΔNp,q_0,q_1\in\Delta N be distributions. Assume we have explicit descriptions of q0,q1q_0,q_1 and we have sample access to pp; the goal is to select i^∈0,1\hat{i}\in\\{0,1\\} such that Pr⁡(TV(p,qi^)≤cmin⁡iTV(p,qi)+ε)≥1−δ\Pr\left(TV(p,q_{\hat{i}})\leq c \min_{i}TV(p,q_i)+\varepsilon\right)\geq1-\delta

A classical selector achieves c=3c=3 with sample complexity O(1ε2log⁡1δ)O\left(\frac{1}{\varepsilon^2}\log\frac{1}{\delta}\right). The authors focus on the regime c<3c<3. They prove for any c∈[1,3)c\in[1,3) for a sufficiently small εc>0\varepsilon_c>0 the sample complexity of this problem is asymptotically bounded by Ωc,ε(Nlog⁡N)\Omega_{c,\varepsilon}\left(\frac{N}{\log N}\right), this imrpoves upon the previous known lower bound of Ω(N)\Omega(\sqrt{N}). A matching upper bound follows from TV estimation of prior work.

Critical strengths

The authors prove a tight lower bound on sample complexity and resolve it for the entire regime c∈[1,3)c\in[1,3). They improved the bound from Ω(N)\Omega(\sqrt{N}) to Ω(Nlog⁡N)\Omega(\frac{N}{\log N}), which is now tight.

Critical weaknesses

The paper establishes a worst-case sample-complexity bound, but gives limited insight into how the difficulty varies across instances. Instance-dependent upper and lower bounds would help clarify which distributions require nearly linear sample complexity and which permit substantially fewer samples.

Questions for authors

Questions

The lower bound relies on carefully constructed target distributions. Is it possible to identify natural assumptions on the distributions so that an approximation factor c<3c<3 with o(Nlog⁡N)o(\frac{N}{\log N}) samples is achievable?

For example, can instance-dependent bounds be shown? e.g., suppose we knew the class of distributions for pp and q0,q1q_0,q_1 can we prove better upper bounds when c<3c<3?

Can a general lower bound on ε,δ,N,c\varepsilon,\delta,N,c be derived?

2 comments

Dear Reviewer izim,

Thank you very much for taking the time to review our manuscript and for providing insightful and valuable comments. We provide the reply in the following.

Weakness. The bound is worst-case. Instance-dependent upper and lower bounds would help.

That's correct. Currently, we don't have an instance-dependent result. We have added a new paragraph to Section 6, "Limitations and open questions" to explicitly state this limitation as an open question. Thanks for raising this.

Q1. Are there natural assumptions under which a factor c<3c<3 is achievable with o(N/log⁡N)o(N/\log N) samples?

Currently, we don't have such an assumption in our manuscript. We believe it should be important future work, we have added a new paragraph in Section 6 to list it as an open question. From our analysis, simple candidates are not enough by themselves, since the lower bound already holds for candidates that take only two probability values. We will explore other natural assumptions in the future.

Q2. Can instance-dependent bounds be shown, for example better upper bounds for c<3c<3 when the class of p,q0,q1p,q_0,q_1 is known?

Thank you for suggesting this direction. We don't have such bounds yet. Our current bounds are worst-case and do not use any knowledge of the class of pp, q0q_0, q1q_1. Better upper bounds for a known class are part of the open question listed in the same paragraph of Section 6, and we will study them in future work.

Q3. Can a general lower bound in ε,δ,N,c\varepsilon,\delta,N,c be derived?

Only in part. Theorem 10 in Appendix C.3 gives the lower bound for every fixed c∈[1,3)c\in[1,3), every δ∈(0,1/2)\delta\in(0,1/2) and every ε∈(0,εc]\varepsilon\in(0,\varepsilon_c]. It shows that m≥κN/log⁡Nm\ge\kappa N/\log N samples are needed for all large NN, where the constant κ\kappa is explicit in the proof and depends only on cc. This matches our upper bound in NN. However, it does not grow as ε→0\varepsilon\to0 or δ→0\delta\to0, whereas the upper bound in Section 2.2 grows as ε−2\varepsilon^{-2}. The sharp dependence on ε\varepsilon, δ\delta and cc is therefore still open, and we list it as an open question in Section 6. Thank you for the question.

Thank you for the response. My questions have been clarified, and I would like to keep my score.

Comments on the paper

1 comment
AuthorsOpenReview ↗

Summary of the revision

We thank the three reviewers for their careful reading. We have revised the manuscript accordingly. The main theorem is unchanged and we have made the following main changes to improve the readability.

  • The first paragraph of the introduction states the setting, and a new Figure 1 draws the lower-bound construction. Section 1.1 has a new paragraph on the dichotomy of Aiyer et al. and how our result relates to it.
  • Section 2.2 writes out how the estimator of Jiao et al. gives the upper bound.
  • Sections 3 to 5 follow the roadmap of Figure 2. The example with paired coordinates moved to Appendix A.2.
  • Section 6 has a rewritten paragraph on proper and improper selection and a new paragraph on limitations and open questions.
  • The appendices state how Lemmas 6, 8 and 9 relate to results of Jiao et al. and of Wu and Yang, and the reference list is corrected.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.