Pith. sign in

REVIEW 3 major objections 4 minor 20 references

Optimal multiclass overfitting by sequence reconstruction from Hamming queries

T0 review · 3 major / 4 minor · reviewed 2026-08-14 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read The paper resolves the open problem of how much adaptive accuracy queries can overfit an $m$-class test set, showing the maximum bias over the random-guessing baseline is $\tilde{\Theta}(\max\{\sqrt{k/(mn)}, k/n\})$ and that…

desk verdict Resolves the COLT 2019 open problem for the sequence-reconstruction model with clean, efficient algorithms, but the claimed full resolution for unknown test features rests on a distinctness assumption and one omitted proof. read the letter →

arxiv 1908.03156 v2 pith:RWYKRWWI submitted 2019-08-08 cs.LG cs.ITmath.ITstat.ML

Jayadev Acharya , Ananda Theertha Suresh This is my paper · ORCID
classification cs.LGcs.ITmath.ITstat.ML
keywords adaptivedataanalysistestsetreusemulticlassclassificationoverfittingbiasHammingqueriessequencereconstructionaccuracyoraclemastermindproblem
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

The paper establishes the worst-case overfitting bias for multiclass classification when an algorithm can make $k$ adaptive queries to the accuracy of classifiers on a fixed test set of $n$ examples with $m$ labels. It proves that the maximum expected accuracy over the random-guessing baseline $1/m$ is, up to logarithmic factors, $\tilde{\Theta}(\max\{\sqrt{k/(mn)}, k/n\})$. This closes the open problem left by the earlier upper bound for multiclass test-set reuse and shows that multiclass problems are more resistant to overfitting than binary ones: in the small-query regime the bias shrinks by a factor of $\sqrt{m}$. The algorithms that achieve this bias run in polynomial time, whereas previous matching approaches required brute-force search.

What carries the argument

The central reduction replaces worst-case label sequences with uniformly random ones: composing each position's labels with an independent random permutation of $[m]$ turns any algorithm's average accuracy on uniform labels into a guaranteed worst-case accuracy, so the problem becomes sequence reconstruction from Hamming distance queries. For small $k$, the algorithm splits the $n$ positions into $k-1$ blocks, queries each block with a constant label, and predicts the block's majority by comparing two adjacent query accuracies; the excess over $1/m$ comes from the expected maximum of two multinomial counts, which exceeds $n/m$ by a $\Theta(\sqrt{n/m})$ term per block. For large $k$, the first $t$ positions are queried with columns containing exactly $k/m$ copies of each label, and each position is predicted by the label whose average over its $k/m$ query accuracies is largest; negative association among the counts and Chernoff bounds make each such prediction correct with probability at least $3/4$.

What would settle it

Enumerate all label sequences in $[m]^n$ for small parameters (for example $n=3$, $m=2$, $k=1$ or $k=2$), run the proposed $A_{\mathrm{small}}$ algorithm on each, and compute the minimum expected accuracy over sequences. If that minimum is below $1/m + (1/8)\sqrt{k/(mn)}$, the lower bound is false. Conversely, for $k=1$, if any algorithm overfits a sequence to an accuracy above $1/m + (1/2)\sqrt{1/(n(m-1))}$, the matching upper bound is false.

Watch

Extended reading notes

Core claim

The paper's central claim is that after $k$ accuracy queries, the best worst-case expected accuracy on any $m$-class test set of size $n$ is $1/m + \tilde{\Theta}(\max\{\sqrt{k/(mn)}, k/n\})$. In the small-query regime $k=O(n/m)$, the bias over the baseline is $\tilde{\Theta}(\sqrt{k/(mn)})$; this resolves the quadratic gap in the dependence on $m$ left open by previous work. In the large-query regime $k=\Omega(n/m)$, the bias is $\tilde{\Theta}(k/n)$, independent of $m$. The paper gives explicit polynomial-time algorithms for both regimes and shows that adaptivity does not increase the achievable bias: all $k$ queries can be fixed ahead of time, and only the final classifier depends on the answers. For $k=1$ the logarithmic factor is removed, determining the optimal single-query bias up to constant factors.

Load-bearing premise

The feature-space version of the result assumes the $n$ test features are all distinct; the randomized partition of the feature space can place duplicated features in ways that break the concentration argument, so the stated guarantees may fail if duplicates are present.

Editorial extensions

If this is right

  • For $k=O(n/m)$, the overfitting bias is $\tilde{\Theta}(\sqrt{k/(mn)})$: multiplying the number of classes by four cuts the bias in half, so multiclass benchmarks are intrinsically harder to overfit than binary ones.
  • For $k=\Omega(n/m)$, the bias is $\tilde{\Theta}(k/n)$ and no longer depends on $m$; once the number of queries is large, adding classes stops helping.
  • All queries in the optimal algorithms are non-adaptive, so an analyst who chooses queries based on previous answers gains no extra overfitting power.
  • The polynomial runtime of the algorithms means the optimal bias is achievable without brute-force searching over labelings, which was the obstacle in the prior matching construction.
  • If the test features are unknown but distinct, the same bounds hold up to constant factors by randomly partitioning the feature space, so the characterization applies beyond the known-features sequence model.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • The exact constant for $k=1$ suggests the true leading constant for general $k$ may be derivable with a sharper multinomial analysis; the paper leaves this as an open direction.
  • The block-comparison idea effectively converts accuracy feedback into pairwise comparisons between labels, so the same bias rates may extend to other feedback models such as thresholded, noisy, or top-1 accuracies.
  • The result gives a quantitative explanation for the empirical difficulty of overfitting large-label benchmarks through test-set reuse: the $\sqrt{m}$ denominator in the small-query regime makes many-class problems substantially harder to game.
  • A natural next step is to analyze the duplicate-feature case directly, since the distinctness assumption is the only place where the feature-space extension can deteriorate.
Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

3 major / 4 minor

Summary. The paper studies the maximum overfitting bias achievable by an algorithm that makes k adaptive accuracy queries on a multiclass test set of n examples with m classes, formalized as the value acc(k,n,m). The main result claims acc(k,n,m) - 1/m = tilde-Theta(max{sqrt(k/(mn)), k/n}), matching upper bounds of Feldman, Frostig, and Hardt. In the known-features/sequence-reconstruction model, the paper proves this lower bound with explicit efficient algorithms: Theorem 3 covers k = O(n/m) and Theorem 6 covers k = Omega(n/m), both non-adaptive. Section 3 gives an average-case reduction showing that worst-case labels can be assumed uniform. Section 7 extends the algorithms to the unknown-features setting under the assumption that all n test features are distinct; the proof for small k is sketched in Appendix B.2 and the proof for large k is omitted. Theorem 9 gives a constant-factor-optimal analysis for k = 1.

Significance. If the central characterization holds in full generality, this is a significant result: it resolves the COLT 2019 open problem, removes the quadratic gap in m left by previous work, and provides computationally efficient and non-adaptive algorithms matching the information-theoretic upper bounds up to logarithmic factors. The reduction in Section 3 is elegant, the algorithms are simple and parameter-free, and the main proofs for the sequence model are complete and use standard tools. The claimed tight dependence on m is the key conceptual contribution, and the paper gives proper credit to the earlier upper bounds. The main weakness is that the bridge from the sequence model to the original feature-unknown problem is incomplete: the stated distinct-features assumption is not part of the original worst-case definition, and the large-k extension is only sketched.

major comments (3)
  1. [Section 7 / Table 1] The headline claim in the abstract and Table 1 is for acc(k,n,m), defined in Section 2 as inf over all S in (X x [m])^n with no distinctness condition on features. The only bridge from the sequence-reconstruction lower bounds to the feature-unknown setting is Section 7, which explicitly assumes all n test features in S_X are distinct. A lower bound proved for a restricted subclass does not imply the worst-case lower bound over all datasets. This is not a purely cosmetic restriction: under the uniform-function distribution u_m, duplicated features make the counts N_l weighted sums rather than Bin(n;1/m), and the concentration argument in Appendix B.2 relies on |B_i| ~ Bin(n;1/(k-1)). Please either prove the general case, prove a reduction showing that duplicate features cannot reduce the worst-case bias, or explicitly restrict the theorem statements and abstract to the distinct-features setting.
  2. [Section 7.2 / Appendix B.2] The analysis of Alarge_unknown is not supplied: the text says 'the rest of the analysis is similar to that of Theorem 6 and we omit it.' This algorithm is needed for the k = Omega(n/m) regime in the unknown-features setting, so the omission is load-bearing. A complete proof must account for the randomness of X_t, concentration of the number of test examples in X_t, the per-example error probability in the presence of the random set, and the contribution of examples outside X_t. The current sketch is insufficient to support the claimed extension.
  3. [Appendix B.2] The proof sketch for Asmall_unknown uses Pr(|B_i| >= n/(2(k-1))) >= 1/2, which follows from |B_i| ~ Bin(n;1/(k-1)). With duplicate features, all copies of the same feature fall in the same block, so |B_i| is a sum of weighted Bernoulli variables and the binomial median bound can fail. The paper does not show that duplicate features cannot make the dataset harder, so the distinctness assumption is not a minor technicality but a gap between the proven theorems and the abstract's claim to resolve the original problem over all datasets.
minor comments (4)
  1. [Appendix C] The notation in the proof of Theorem 9 is inconsistent: 'r = h(q,z)' treats the accuracy fraction h as an integer count, and the statement 'r ~ Bin(n-1;1/m)' does not match the later variance computation E[(r - n/m)^2] = n(1/m)(1-1/m). Please rewrite the proof with an integer count R and clarify the conditioning step.
  2. [Section 2.1] The equality h(k,n,m) = acc(k,n,m) is asserted in the sequence-reconstruction discussion, but it depends on the feature-known assumption. The text does clarify this later, but the statement as written could mislead; please add an explicit qualifier at that point.
  3. [Theorem 6 / Figure 2] The proof assumes k is an integer multiple of m, with a footnote saying the same results hold without the assumption, but the theorem statement does not mention this. Please state the divisibility condition in the theorem or give the rounding argument in the proof.
  4. [Introduction] There is a typo: 'This line of word broadly falls' should be 'This line of work broadly falls.'

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the lower bounds are proved from first principles and matched against independent information-theoretic upper bounds.

full rationale

The paper's central result, acc(k,n,m)-1/m = Theta_tilde(max{sqrt(k/(mn)), k/n}), is established by direct algorithmic constructions (Asmall in Figure 1 and Alarge in Figure 2) whose analyses use only elementary multinomial concentration tools (Lemmas 4 and 5) and Chernoff bounds. The worst-case to average-case reductions (Theorem 2, Corollary 1, Theorem 7, Corollary 8) are proven from first principles and do not assume the target bound. The claimed rates are compared against the independent information-theoretic upper bounds of Feldman et al. (2019a), which is an external benchmark rather than a self-citation. The paper contains no fitted parameters renamed as predictions, and no load-bearing self-citation chain. The sequence-reconstruction model is introduced as a simplification of the accuracy-query model, and Section 7 provides a separate bridge to the unknown-features setting; whether that bridge fully covers all datasets is a correctness/scoping concern, not a circularity, because the distinctness assumption does not smuggle in the theorem's conclusion. Theorems 3 and 6 do not reduce by construction to their inputs: the query schemes and final predictions are explicit, and the accuracy gains are derived from variance/concentration calculations rather than from the quantity being predicted. Overall, the derivation chain is self-contained on the circularity axis.

Assumptions & free parameters 0 free parameters · 6 assumptions · 0 invented entities

The central claims rest on standard probability tools (binomial/Berend-Kontorovich, Chernoff, Jensen) and on the modeling assumption that the oracle returns exact accuracies. No free parameters are fitted to data. The only introduced entity is the conceptual reduction to sequence reconstruction from Hamming queries, which is a framing, not a new physical entity.

assumptions (6)
  • domain assumption Accuracy oracle returns exact empirical accuracy on the test set for each queried classifier.
    The entire model of adaptive overfitting assumes the oracle is exact and reveals h(q,z) = fraction of correct predictions; Section 2.
  • domain assumption All n test features are distinct in the unknown-features extension.
    Section 7 states this 'natural assumption' is required for the algorithms that partition X into blocks; duplicate features would break the concentration arguments.
  • standard math Berend-Kontorovich lower bound on binomial mean absolute deviation: for Y ~ Bin(n;p), E|Y-np| >= sqrt(np(1-p)/2).
    Used in Lemma 4 and Lemma 5 (Appendix A) to lower-bound the overfitting bias.
  • standard math Chernoff bounds hold for negatively associated variables.
    Used in Theorem 6 to bound M_l; the paper states 'basic balls and bins results' and quotes equation (5).
  • standard math Jensen's inequality applied to conditional expectations.
    Used in Lemma 5 proof to assert E[|N1 - N'2|] >= E[|N1 - n'/m|].
  • domain assumption Symmetry reduction via random permutations per coordinate.
    Theorem 2 constructs A' by permuting labels independently per coordinate; requires the query space to be closed under these permutations.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Optimal multiclass overfitting by sequence reconstruction from Hamming queries." pith.science (2026). https://pith.science/paper/RWYKRWWI

@misc{pith2026190803156,
  author       = {Pith},
  title        = {Pith review of: Optimal multiclass overfitting by sequence reconstruction from Hamming queries},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/RWYKRWWI}},
  note         = {Machine review of arXiv:1908.03156}
}
abstract

A primary concern of excessive reuse of test datasets in machine learning is that it can lead to overfitting. Multiclass classification was recently shown to be more resistant to overfitting than binary classification. In an open problem of COLT 2019, Feldman, Frostig, and Hardt ask to characterize the dependence of the amount of overfitting bias with the number of classes $m$, the number of accuracy queries $k$, and the number of examples in the dataset $n$. We resolve this problem and determine the amount of overfitting possible in multi-class classification. We provide computationally efficient algorithms that achieve overfitting bias of $\tilde{\Theta}(\max\{\sqrt{{k}/{(mn)}}, k/n\})$, matching the known upper bounds.

Figures

Figures reproduced from arXiv: 1908.03156 by the authors.

Figure 1
Figure 1. Algorithm for small values of k. (n; 1 m , . . . , 1 m ). Our query is to predict all the labels as ‘1’, namely q 1 j = 1 for 1 ≤ j ≤ n. The accuracy observed is then N1/n. If N1 ≥ n/m, then we predict all labels as ‘1’, namely zˆj = 1 for all j, otherwise we output all the labels as ‘2’. The pseudocode is provided in [PITH_FULL_IMAGE:figures/full_fig_p008_1.png] view at source ↗
Figure 2
Figure 2. Algorithm for large values of k. at least 3/4. Consider the jth example, for 1 ≤ j ≤ t. For a label ` ∈ [m], consider the k/m queries such that q i j = `, and consider the average of the accuracies returned for these queries. Our prediction for the jth example is the label for which this average accuracy is the largest, namely zˆj = arg max `∈[m] X i:q i j=` h(¯q i , z¯). The queries and predictions are described in… view at source ↗
Figure 3
Figure 3. Algorithm for small values of k without the test features. Algorithm A large unknown Queries 1. Let t := 1 + k 9 log m , and Xt ⊂ X is defined in Section 7.2. 2. For 1 ≤ i ≤ k and x /∈ Xt , f i (x) = 1. 3. Independently for each x ∈ Xt , let f 1 (x), . . . , f k (x) be uniformly chosen from all sequences in [m] k that have each label in [m] appearing exactly k/m times. Predict 1. For x ∈ X t, ˆf(x) = arg max`∈[m] P … view at source ↗
Figures from the paper (1 more)
Figure 4
Figure 4. Figure 4: Algorithm for large values of k without the test features. examples in Bi . Hence, summing over the blocks the total expected number of correct 17 [PITH_FULL_IMAGE:figures/full_fig_p017_4.png]

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

20 extracted references · 15 canonical work pages

  1. [1]

    Algorithmic stability for adaptive data analysis

    Raef Bassily, Kobbi Nissim, Adam Smith, Thomas Steinke, Uri Stemmer, and Jonathan Ullman. Algorithmic stability for adaptive data analysis. In Proceedings of the forty-eighth annual ACM symposium on Theory of Computing, pages 1046--1059, 2016

    work page 2016

  2. [2]

    A sharp estimate of the binomial mean absolute deviation with applications

    Daniel Berend and Aryeh Kontorovich. A sharp estimate of the binomial mean absolute deviation with applications. Statistics & Probability Letters, 83 0 (4): 0 1254--1259, 2013

    work page 2013

  3. [3]

    The ladder: a reliable leaderboard for machine learning competitions

    Avrim Blum and Moritz Hardt. The ladder: a reliable leaderboard for machine learning competitions. In Proceedings of the 32nd International Conference on International Conference on Machine Learning-Volume 37, pages 1006--1014. JMLR.org, 2015

    work page 2015

  4. [4]

    Optimal algorithms for the coin weighing problem with a spring scale

    Nader H Bshouty. Optimal algorithms for the coin weighing problem with a spring scale. In COLT, volume 2009, page 82. Citeseer, 2009

    work page 2009

  5. [5]

    Mastermind

    Vasek Chv \'a tal. Mastermind. Combinatorica, 3 0 (3-4): 0 325--329, 1983

    work page 1983

  6. [6]

    Playing mastermind with many colors

    Benjamin Doerr, Carola Doerr, Reto Sp \"o hel, and Henning Thomas. Playing mastermind with many colors. Journal of the ACM (JACM), 63 0 (5): 0 42, 2016

    work page 2016

  7. [7]

    Generalization in adaptive data analysis and holdout reuse

    Cynthia Dwork, Vitaly Feldman, Moritz Hardt, Toni Pitassi, Omer Reingold, and Aaron Roth. Generalization in adaptive data analysis and holdout reuse. In Advances in Neural Information Processing Systems, pages 2350--2358, 2015 a

    work page 2015

  8. [8]

    The reusable holdout: Preserving validity in adaptive data analysis

    Cynthia Dwork, Vitaly Feldman, Moritz Hardt, Toniann Pitassi, Omer Reingold, and Aaron Roth. The reusable holdout: Preserving validity in adaptive data analysis. Science, 349 0 (6248): 0 636--638, 2015 b

    work page 2015

Show all 20 references
  1. [9]

    Preserving statistical validity in adaptive data analysis

    Cynthia Dwork, Vitaly Feldman, Moritz Hardt, Toniann Pitassi, Omer Reingold, and Aaron Leon Roth. Preserving statistical validity in adaptive data analysis. In Proceedings of the forty-seventh annual ACM symposium on Theory of computing, pages 117--126. ACM, 2015 c

    2015

  2. [10]

    os and Alfred R \'e nyi. On two problems of information theory. Magyar Tud. Akad. Mat. Kutat\'o K\

    Paul Erd\"os and Alfred R \'e nyi. On two problems of information theory. Magyar Tud. Akad. Mat. Kutat\'o K\"ozl, 8, 1963

    1963

  3. [11]

    The advantages of multiple classes for reducing overfitting from test set reuse

    Vitaly Feldman, Roy Frostig, and Moritz Hardt. The advantages of multiple classes for reducing overfitting from test set reuse. In International Conference on Machine Learning, 2019 a

    2019

  4. [12]

    Vitaly Feldman, Roy Frostig, and Moritz Hardt. Open problem: How fast can a multiclass test set be overfit? In Alina Beygelzimer and Daniel Hsu, editors, Proceedings of the Thirty-Second Conference on Learning Theory, volume 99 of Proceedings of Machine Learning Research, page...

    2019

  5. [13]

    An introduction to statistical learning, volume 112

    Gareth James, Daniela Witten, Trevor Hastie, and Robert Tibshirani. An introduction to statistical learning, volume 112. Springer, 2013

    2013

  6. [14]

    Do cifar-10 classifiers generalize to cifar-10? arXiv preprint arXiv:1806.00451, 2018

    Benjamin Recht, Rebecca Roelofs, Ludwig Schmidt, and Vaishaal Shankar. Do cifar-10 classifiers generalize to cifar-10? arXiv preprint arXiv:1806.00451, 2018

    2018 arXiv

  7. [15]

    Do imagenet classifiers generalize to imagenet? arXiv preprint arXiv:1902.10811, 2019

    Benjamin Recht, Rebecca Roelofs, Ludwig Schmidt, and Vaishaal Shankar. Do imagenet classifiers generalize to imagenet? arXiv preprint arXiv:1902.10811, 2019

    1902 arXiv

  8. [16]

    Cold case: The lost mnist digits

    Chhavi Yadav and L \'e on Bottou. Cold case: The lost mnist digits. arXiv preprint arXiv:1905.10498, 2019

    1905 arXiv

  9. [17]

    Natural analysts in adaptive data analysis

    Tijana Zrnic and Moritz Hardt. Natural analysts in adaptive data analysis. In International Conference on Machine Learning, pages 7703--7711, 2019

    2019

  10. [18]

    @esa (Ref

    \@ifxundefined[1] #1\@undefined \@firstoftwo \@secondoftwo \@ifnum[1] #1 \@firstoftwo \@secondoftwo \@ifx[1] #1 \@firstoftwo \@secondoftwo [2] @ #1 \@temptokena #2 #1 @ \@temptokena \@ifclassloaded agu2001 natbib The agu2001 class already includes natbib coding, so you should ...

  11. [19]

    \@lbibitem[] @bibitem@first@sw\@secondoftwo \@lbibitem[#1]#2 \@extra@b@citeb \@ifundefined br@#2\@extra@b@citeb \@namedef br@#2 \@nameuse br@#2\@extra@b@citeb \@ifundefined b@#2\@extra@b@citeb @num @parse #2 @tmp #1 NAT@b@open@#2 NAT@b@shut@#2 \@ifnum @merge>\@ne @bibitem@firs...

  12. [20]

    We first consider the case k=O(n/m)

    @open @close @open @close and [1] URL: #1 \@ifundefined chapter * \@mkboth \@ifxundefined @sectionbib * \@mkboth * \@mkboth\@gobbletwo \@ifclassloaded amsart * \@ifclassloaded amsbook * \@ifxundefined @heading @heading NAT@ctr thebibliography [1] @ \@biblabel @NAT@ctr \@bibset...

Pith tools

Reviewed August 14, 2026 · model on record in the stance chip above.