PaperlayerView exact revision on arXiv

Source-linked AI summary

Model Similarity Mitigates Test Set Overuse

Horia Mania, John Miller, Ludwig Schmidt, Moritz Hardt, Benjamin Recht

arXiv:1905.12580v1cs.LGstat.ML

TL;DR

Extensive reuse of holdout data strains standard statistical guarantees, particularly when model choices adapt to past results. This paper measures model similarity and develops generalization bounds that account for it. The authors report that model agreement exceeds what accuracy alone suggests, and that similarity can help explain test-set longevity.

  • Problem

    Practitioners reuse holdout data extensively, often choosing models based on past results, while standard guarantees assume models are selected independently of the test data.

    Source: §1 · p. 1

  • Method

    The paper empirically examines model agreement and develops generalization bounds that incorporate model similarity.

    Source: §1 · pp. 1–2, §1.1 · p. 2

  • Results

    Contemporary image-classification models are highly similar, and models 85% similar can differ by as much as 15% in accuracy.

    Source: §1 · p. 2, §6 · p. 11

  • Takeaways & Limitations

    When models are highly similar, similarity-aware bounds help explain why holdout data can remain useful longer than prior bounds suggest.

    Source: §1.1 · p. 2

    It remains open whether the similarity phenomenon extends beyond image classification and why classification models are so similar.

    Source: §6 · p. 11

Abstract

from arXiv · show

Excessive reuse of test data has become commonplace in today's machine learning workflows. Popular benchmarks, competitions, industrial scale tuning, among other applications, all involve test data reuse beyond guidance by statistical confidence bounds. Nonetheless, recent replication studies give evidence that popular benchmarks continue to support progress despite years of extensive reuse. We proffer a new explanation for the apparent longevity of test data: Many proposed models are similar in their predictions and we prove that this similarity mitigates overfitting. Specifically, we show empirically that models proposed for the ImageNet ILSVRC benchmark agree in their predictions well beyond what we can conclude from their accuracy levels alone. Likewise, models created by large scale hyperparameter search enjoy high levels of similarity. Motivated by these empirical observations, we give a non-asymptotic generalization bound that takes similarity into account, leading to meaningful confidence bounds in practical settings.

1 Introduction

Growing, adaptive reuse of holdout data strains the assumptions behind standard guarantees, even as popular benchmarks continue to support progress. The paper argues that model similarity helps explain this longevity and develops similarity-aware bounds alongside empirical analyses of ImageNet and CIFAR-10 models.

1 Introduction

  • Adaptive model reuse can bias holdout estimates, yet popular benchmarks have continued to support progress despite years of reuse [19].The usual log(k)/n guarantee assumes models are chosen independently of test data, while practitioners and adaptive searches use previous results.Source: §1 · p. 1

1.1 Our contributions

  • ImageNet and CIFAR-10 models agree in their predictions more than their accuracy levels alone would imply, motivating bounds that account for similarity.The paper presents empirical evidence and new generalization bounds as complementary contributions.Source: §1.1 · p. 2, §1 · p. 2
  • A refined union bound using representative ImageNet models’ mean similarity improves by 4× over an optimized baseline that ignores similarity.The paper also reports practical reuse guarantees and says an additional assumption on predictions can improve the similarity-based guarantee by multiple orders of magnitude.Source: §1.1 · p. 2
  • Similarity remained high during CIFAR-10 random hyperparameter and neural architecture searches, counterweighting many evaluations and limiting observed overfitting.The search procedures generated large classes of similar models.Source: §1.1 · pp. 2–3

1.2 Related work

  • Replication studies found limited or no adaptive overfitting on newly created ImageNet, CIFAR-10, and MNIST test sets [14, 19].Reevaluated models that performed better on the old test set also performed better on the new test set [14].Source: §1.2 · p. 3
  • Related explanations include selective reporting [2], restrictions on analysts’ use of past queries [20], and class-count effects [6]; the authors view them as potentially complementary.Prior work also studied noise-based holdout mechanisms [5] and tighter paired-test comparisons [19].Source: §1.2 · p. 3

2 Problem setup

The setup formalizes overfitting as a gap between a classifier’s test-set and population performance. It frames the problem as bounding the chance that any among several classifiers has a large gap, while accounting for dependencies between their errors.

2 Problem setup

  • A classifier overfits the test set when its test-set accuracy differs substantially from its population accuracy under the data distribution.The test set consists of n examples sampled independently from that distribution.Source: §2 · p. 3
  • Each classifier is represented by a 0-1 error query, whose empirical mean is test error and whose population mean is population error.The setup considers a set of classifiers, such as those obtained through hyperparameter search.Source: §2 · pp. 3–4
  • A standard union bound handles queries separately but cannot capture their dependencies; the paper studies whether query similarity yields tighter overfitting bounds.Similarity is measured by the probability that two queries agree on a data point.Source: §2 · p. 4

3 Non-adaptive classification

The section analyzes non-adaptively chosen classifiers and refines the union bound to account for similarity between their queries. A similarity cover can yield improved guarantees when queries are sufficiently similar.

3 Non-adaptive classification

  • The analysis considers classifiers fixed independently of the test set and seeks to keep the probability of inaccurate test estimates small.The motivating example is a hyperparameter grid fixed before any classifier is evaluated on the test set.Source: §3 · p. 4
  • The refined union bound exploits query similarity because similar queries make opposite-direction deviations less likely to occur together.The proof then applies a Chernoff concentration bound for random variables taking values −1, 0, and 1.Source: §3 · pp. 4–5
  • A similarity cover represents each query using two sufficiently similar queries whose population losses lie on either side of its own.Theorem 2 considers query collections independent of the test set.Source: §3 · p. 5
  • The bound can improve on the standard guarantee even when the cover similarity is much lower than 1 − ε.The supplied discussion says the requirement can be on the order of 1 − √ε and that the bound holds for similarity bounded away from one.Source: §3 · p. 5

4 Adaptive classification

The section extends similarity-based overfitting bounds to adaptive queries, focusing on the Trivial Mechanism and the analyst's possible-query set. Under a similarity-cover condition, the dependence on the number of queries can improve superlinearly.

4 Adaptive classification

  • Even when queries are chosen adaptively from earlier queries and test estimates, leveraging similarity can sharpen bounds on overfitting probability.The earlier non-adaptive result is described as applying when queries are fixed independently of the test set.Source: §4 · pp. 5–6
  • For the Trivial Mechanism, a deterministic analyst can ask at most (n + 1)^(k−1) possible queries over k rounds, forming the set to which the cover analysis is applied.The mechanism returns the empirical mean of each query on the test set.Source: §4 · p. 6
  • Corollary 4 applies a similarity-cover condition to the analyst's possible-query set to bound overfitting for adaptively chosen queries.The corollary's stated setting is the Trivial Mechanism with a test set of size n.Source: §4 · p. 6
  • When α = 0, Corollary 4 matches standard results for the Trivial Mechanism.The supplied passage does not include the remainder of the stated rate.Source: §4 · p. 6
  • A similarity-cover condition can yield a superlinear improvement in dependence on k; with α = 1/2, the result gives a quadratic improvement in query count for fixed sample size.The stated condition bounds the cover size of the possible-query set; the passage also says the technique extends to compression-based mechanisms such as the Ladder Mechanism [2].Source: §4 · p. 6

5 Empirical results

The experiments measure model similarity and the resulting increase in testable models on ImageNet and CIFAR-10. Across these settings, proposed models are more similar than accuracy-matched random predictions would suggest, and similarity-aware bounds improve reuse guarantees.

5.1 Similarities on Imagenet

  • The ImageNet models’ mean empirical similarity was 0.85 versus 0.62 for the random baseline, and DARTS similarity bounds offered one-to-four-order-of-magnitude gains over the standard union bound.For DARTS, the reported gains apply to both the similarity bound and the naive Bayes bound.Source: §5.1 · p. 7, §5.2 · p. 10, Table 1 · p. 10
  • The ImageNet models’ pairwise similarities are significantly higher than an accuracy-matched random baseline; the higher-order Naive Bayes analysis uses an assumption that is not exactly satisfied in practice.The authors say the observed violation of that assumption likely implies an even better lower bound on the number of testable models.Source: §5.1 · pp. 7–9
  • For 50,000 ImageNet examples and 75.6% population accuracy, the standard union bound guarantees 257,397 evaluations within 0.756 ± 0.01 with at least 95% probability.The paper compares this baseline with its refined similarity union bound, which it reports as a significant improvement for error rates 0.244 and pairwise similarity at least 0.85.Source: §5.1 · pp. 7–8
  • Under Assumption A1, the ImageNet analysis says 10^8 models can be evaluated without overfitting, while the guarantee improves over the standard union bound as similarity or ε increases.The passage describes the 10^8 scale as relevant because an adaptive search may involve a tree of possible models that large.Source: §5.1 · p. 9, Figure 2 · p. 9

5.2 Similarities on CIFAR-10

  • On CIFAR-10, 320 randomly searched ResNet110 models yielded 1,235 checkpoints with at least 50% accuracy, and their similarities exceeded random chance; Figure 3 reports pairwise similarities and covering-number bounds.The best model reached 96.6% accuracy.Source: §5.2 · pp. 9–10, Figure 3 · p. 10
  • The CIFAR-10 DARTS experiment found one-to-four-order-of-magnitude gains in testable-model counts from the similarity and naive Bayes bounds over the standard union bound.The comparison covers 20 randomly selected configurations and the top 20 configurations by DARTS internal score.Source: §5.2 · p. 10, Table 1 · p. 10

6 Conclusions and future work

The conclusion reports that model similarity extends test-set longevity without ruling out accuracy differences, and identifies unresolved questions about the phenomenon’s scope and how to use model structure for performance bounds.

  • Contemporary image-classification models are highly similar, and this similarity increases test-set longevity in theory and experiment.Models that are 85% similar can still differ by as much as 15% in accuracy.Source: §6 · p. 11
  • As practitioners explore models that are both more accurate and more similar, overfitting can become harder.The conclusion also notes that higher accuracy implies more test-set reuses without overfitting.Source: §6 · p. 11
  • Future work includes determining why classification models are similar and whether the phenomenon extends beyond image classification.The authors also point to possible structural dependencies and a statistical procedure that leverages model structure for reliable, accurate reuse bounds.Source: §6 · p. 11

A Proofs for Section 3

The proofs use Chernoff bounds and a similarity cover to control tail probabilities, then choose a bound parameter to meet the target confidence requirement.

A Proofs for Section 3

  • The lemma models each independent Xi as taking values −1, 0, and 1 with probabilities p−1, p0, and p1, and bounds its upper tail under a condition on t.Its expectation is p1 − p−1.Source: A Proofs for Section 3 · p. 13
  • Choosing a nonnegative λ through e^λ = z + 1 reduces the desired inequality to a condition on z and r.The proof uses Bernoulli’s inequality and requires z ≤ (p−1 − p1 + r)/p1.Source: A Proofs for Section 3 · p. 13
  • A minimal η-similarity cover partitions the query family so each query agrees with its representative with probability at least η.The proof applies a Chernoff bound and Lemma 3 within each partition, then sums over the cover.Source: A Proofs for Section 3 · p. 14
  • The final bound chooses ε to satisfy the required conditions, using log(1 + t) ≥ t/(t + 1) for t ≥ 0.The proof also requires the right-hand side to be at least log(4k/δ).Source: A Proofs for Section 3 · p. 15

B Tail probability of two dependent binomials

The appendix computes tail probabilities for two dependent binomials from the joint distribution of a query pair. It also gives a factorized representation under a stated condition and a separate Naive Bayes assumption.

B Tail probability of two dependent binomials

  • The similarity union-bound calculation derives pairwise outcome probabilities from the two marginal error rates and their agreement probability.Those probabilities are denoted p11, p10, p01, and p00.Source: B Tail probability of two dependent… · p. 15
  • The pair’s joint distribution is determined by its two error rates and agreement probability, and can be represented as (X1W, X2W) when p11 ≥ (p10 + p11)(p01 + p11).The tail probabilities for X1i and X2i can be computed efficiently with beta functions.Source: B Tail probability of two dependent… · pp. 15–16
  • The Naive Bayes calculation assumes equal query error rates and a common pairwise agreement probability η.It models the query vector using independent Bernoulli variables W and X1, …, Xk.Source: B Tail probability of two dependent… · p. 16

C Empirical distribution of image difficulty in ImageNet

Figure 4 measures ImageNet validation-image difficulty by counting how many classifiers misclassify each image. The distribution includes substantial groups classified correctly by all or nearly all models.

C Empirical distribution of image difficulty in ImageNet

  • About 27.8% of the 50,000 validation images are correctly classified by all models.The classifiers are those in the testbed from Recht et al. [14].Source: Figure 4 · p. 17
  • 55.9% of the images are correctly classified by 60 of the 66 models.The plot counts images misclassified by at most a given number of models.Source: Figure 4 · p. 17
  • 4.7% of the images are misclassified by all models.The passage describes a significant fraction as classified correctly by all or almost all models.Source: Figure 4 · p. 17

D CIFAR-10 random hyperparameter grid search

The CIFAR-10 random-search grid specifies sampled choices for model, optimizer, and data-augmentation settings, with other hyperparameters left at defaults unless stated otherwise.

D CIFAR-10 random hyperparameter grid search

Loading 1905.12580v1…