{"id":"7488f52a-b0dc-4bdd-995b-12a8523cbbd8","arxiv_id":"1908.03156","paper_version":2,"verdict":"ACCEPT","confidence":"HIGH","novelty_score":8.0,"correctness_risk":"low","formal_verification":"none","parameter_count":0,"one_line_summary":"The optimal overfitting bias for multiclass classification with k accuracy queries is Theta_tilde(max(sqrt(k/(mn)), k/n)), and the paper gives polynomial-time algorithms achieving it.","lead":"The paper determines, up to logarithmic factors, how much a model can overfit a multiclass test set when it only receives the overall accuracy after each query. It provides efficient algorithms that achieve this maximal overfitting bias, closing an open problem from COLT 2019.","discovery_kind":"first_principles","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Unknown-features lower bound is proved only for distinct test features, so the claimed resolution of the original problem over all datasets is not fully established.","rationale":"The sequence-reconstruction results are rigorous and the reduction in Section 3 is sound; the stress-test concern is specifically about the scope of the central claim. The paper's abstract and Table 1 state that the amount of overfitting possible in multiclass classification is determined, i.e., acc(k,n,m) over all datasets. Theorems 3 and 6 give lower bounds for the Hamming-query sequence problem, which is equivalent to the original model only when the adversary knows the test features. Section 7 extends the algorithms to unknown features, but only under an explicit distinctness assumption. The reader flagged this assumption as the weakest point but considered it minor; the stress-test view is that it is load-bearing because without it the lower bound for acc(k,n,m) is not established for datasets with repeated features. The Appendix B.2 proof relies on block sizes being Bin(n,1/(k-1)), which fails for arbitrary multiplicities, and the Alarge_unknown proof is omitted. A conditional verdict is appropriate: accept the sequence-reconstruction contribution and the distinct-features case, but require either a proof that duplicate features are no harder or a scoping of the claimed resolution to distinct test features.","tokens_in":14228,"tokens_out":31775,"duration_ms":351904,"concrete_test":"Prove or disprove that duplicating test features cannot decrease the worst-case expected accuracy of the Section 7 algorithms. Concretely, redo the Appendix B.2 block-size analysis for an arbitrary multiplicity pattern w_1,...,w_d (d distinct features, sum w_i = n): the block sizes are |Bi| = sum_j w_j * Bernoulli_j(1/(k-1)), not Bin(n,1/(k-1)). Check whether Pr(|Bi| >= n/(2(k-1))) >= 1/2 still holds for all valid w. If it fails, exhibit the violating multiplicity pattern (e.g., one feature with multiplicity c n) and compute the expected accuracy of Asmall_unknown for k=2, m=10, n=1000; if it is below 1/m + (1/8) sqrt(k/(mn)) ≈ 0.10125, the lower bound in the original model is false. If it holds, prove the monotonicity lemma and update Section 7 to remove the distinctness restriction.","verdict_should_be":"CONDITIONAL","load_bearing_attack":"The central claim, acc(k,n,m) - 1/m = Theta_tilde(max{sqrt(k/(mn)), k/n}), concerns the original accuracy-query model over all test sets S subseteq (X x [m])^n. Theorems 3 and 6 establish the lower bound only in the sequence-reconstruction model, which is equivalent to the original model when the adversary knows the test features SX. The transfer to the feature-unknown setting (Section 7) is the only bridge to acc(k,n,m), and it explicitly assumes all n test features in SX are distinct. If features are duplicated, the random feature-space partitions used by Asmall_unknown and Alarge_unknown assign all copies of the same feature to the same block, so example assignments to blocks are not independent. The concentration argument in Appendix B.2 uses |Bi| ~ Bin(n; 1/(k-1)) and the median bound Pr(|Bi| >= n/(2(k-1))) >= 1/2; with arbitrary multiplicities, |Bi| is a sum of weighted Bernoulli variables and this bound can fail. The paper does not show that duplicate features cannot make the dataset harder, nor does it provide a counterexample. The proof of Alarge_unknown is also only a sketch ('rest of the analysis is similar to that of Theorem 6 and we omit it'), so the distinctness assumption is not a minor technicality but a gap between the proven theorems and the abstract's claim to resolve the open problem. If duplicates are genuinely easier, the gap is closable, but that monotonicity lemma is absent.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","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.","tokens_in":14546,"tokens_out":9118,"duration_ms":103166,"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":[{"comment":"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.","section":"Section 7 / Table 1"},{"comment":"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.","section":"Section 7.2 / Appendix B.2"},{"comment":"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.","section":"Appendix B.2"}],"minor_comments":[{"comment":"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.","section":"Appendix C"},{"comment":"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.","section":"Section 2.1"},{"comment":"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.","section":"Theorem 6 / Figure 2"},{"comment":"There is a typo: 'This line of word broadly falls' should be 'This line of work broadly falls.'","section":"Introduction"}],"recommendation":"major_revision","confidential_remarks":"The core sequence-reconstruction results appear sound and are likely publishable, but the paper currently overclaims in the abstract and Table 1 because the unknown-features section assumes distinct test features and omits the large-k proof. If the authors can either close the gap or restate the results with the assumption, I would support acceptance. The distinctness issue should be resolved before publication rather than left as a caveat."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"The real news here: the paper closes the quadratic gap in m for small k, gives the first computationally efficient algorithms for large k, and proves a sharp k=1 upper bound. The main theorems (3 and 6) are solid, with standard tools and complete proofs. The reduction to the uniform case (Theorem 2) is clean and important, and the k=1 analysis that removes the sqrt(log n) factor is genuinely nice. There are no fitted parameters, no self-citations, and the lower bounds are proved from first principles, benchmarked against Feldman et al.'s independent upper bounds. This is a serious, well-executed theory paper that does what it claims for the Hamming-query sequence-reconstruction model.\n\nThe soft spot is Section 7, and it is real, not manufactured. The abstract and introduction claim to resolve the original problem over arbitrary test sets, but the unknown-features extension explicitly assumes all n test features are distinct. That assumption is stated, not hidden, but it is load-bearing: the random partitions of feature space concentrate only when features are not duplicated, and the proof for Alarge_unknown is sketched, not given. So the claimed resolution of the problem in its full generality is not fully established. A serious referee should ask for either a proof that handles duplicate features or a revised claim that limits the result to datasets with distinct features. This is a patchable gap, not a fatal flaw in the central argument.\n\nThe citation pattern is appropriate. The relation to mastermind and to Feldman et al. is properly acknowledged, and the novelty claim checks out. The paper is written clearly enough that the structure is easy to follow, and the appendices contain the necessary details for the main theorems.\n\nWho should read this: anyone working on adaptive data analysis, test-set reuse, or multiclass overfitting. It is a within-field result that settles a stated open problem and gives algorithms that match information-theoretic bounds up to log factors; it does not change practice directly, but it is the kind of result that belongs in COLT or a similar venue.\n\nMy recommendation: send it to peer review. The main theorems are worth refereeing even though Section 7 needs work. I would not desk-reject it, and I expect the referee reports to focus on closing the distinctness gap and filling in the omitted proof.","headline":"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.","tokens_in":15023,"tokens_out":1111,"would_cite":true,"duration_ms":14364,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"deepseek-v4-flash","headline":"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…","keywords":["adaptive data analysis","test set reuse","multiclass classification","overfitting bias","Hamming queries","sequence reconstruction","accuracy oracle","mastermind problem"],"falsifier":"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.","tokens_in":14082,"feed_emoji":"🎯","tokens_out":13415,"duration_ms":122491,"temperature":0.7,"pith_summary":"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.","feed_headline":"Multiclass test-set overfitting bias pinned down","feed_subtitle":"More classes make test-set reuse safer; the exact overfitting rate is now known.","key_machinery":"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$.","core_discovery":"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.","pith_inferences":["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."],"forward_implications":["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."],"supporting_citations":[{"why":"Supplies the information-theoretic upper bound $1/m + \\tilde{O}(\\max\\{\\sqrt{k/(mn)}, k/n\\})$ that the paper's lower bounds match, and the prior suboptimal algorithms it improves.","marker":"Feldman et al. 2019a"},{"why":"States the open problem of characterizing the overfitting bias as a function of $k,n,m$.","marker":"Feldman et al. 2019b"},{"why":"Establishes the binary baseline $\\Theta(\\sqrt{k/n})$ overfitting bias that the multiclass result generalizes.","marker":"Dwork et al. 2015c"},{"why":"Provides the binomial mean-absolute-deviation lower bound used in the small-$k$ multinomial analysis.","marker":"Berend and Kontorovich 2013"},{"why":"Resolves perfect sequence reconstruction from Hamming queries, the problem variant that anchors the large-$k$ regime.","marker":"Chvátal 1983"}],"fun_headline_variants":["Exact overfitting rate for multiclass test-set reuse","More classes cut overfitting bias: tight bound shown","Test-set reuse risk: multiclass overfitting exactly pinned","Adaptivity irrelevant: optimal multiclass overfitting rate","Open problem resolved: multiclass overfitting bias known"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"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.","fun_headline_variants_meta":{"raw":{"variants":["Exact overfitting rate for multiclass test-set reuse","More classes cut overfitting bias: tight bound shown","Test-set reuse risk: multiclass overfitting exactly pinned","Adaptivity irrelevant: optimal multiclass overfitting rate","Open problem resolved: multiclass overfitting bias known"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000202,"raw_usage":{"total_tokens":1338,"prompt_tokens":855,"completion_tokens":483,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":471,"completion_tokens_details":{"reasoning_tokens":405}},"tokens_in":471,"tokens_out":483,"duration_ms":5739,"temperature":1.0,"reasoning_tokens":405,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-14T14:22:31.223523+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"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.","supporting_citations":[{"cited_title":"A sharp estimate of the binomial mean absolute deviation with applications","cited_arxiv_id":null,"evidence_quote":"Provides the binomial mean-absolute-deviation lower bound used in the small-$k$ multinomial analysis."}],"review_version":1}