PaperlayerView exact revision on arXiv

Source-linked AI summary

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

Vitaly Feldman, Roy Frostig, Moritz Hardt

arXiv:1905.10360v1cs.LGcs.DSstat.ML

TL;DR

Adaptive reuse of test-set accuracy can overfit, while heavily reused multiclass benchmarks have shown little concrete evidence of significant overfitting. The paper analyzes this problem with multiclass bias bounds and attacks, finding that more classes increase the query cost of overfitting. Its experiments also find that residual uncertainty over multiple classes makes overfitting harder than in the binary case.

  • Problem

    Adaptive reuse of holdout accuracy risks overfitting, yet popular multiclass benchmarks have shown little concrete evidence of significant overfitting despite extensive reuse.

    Source: §1 · pp. 1–2

  • Method

    The paper develops worst-case multiclass bias bounds and attacks, and evaluates practical attacks using classifier information and test-set accuracy queries.

    Source: §1.1 · pp. 2–3, §5 · p. 20

  • Results

    The worst-case query requirement for a fixed bias grows at least linearly with class count, and the best reported attack overfits by about 3% with 5000 queries.

    Source: §1 · p. 2, §1.1 · p. 5

  • Takeaways & Limitations

    The authors find that uncertainty among multiple possible labels makes overfitting harder even when an attacker uses prior information from a strong model.

    Source: §1.1 · p. 5

    The upper and lower bounds leave a gap in their dependence on the number of classes, and the proposed asymptotic optimality of the point-wise attack remains a conjecture.

    Source: §1.1 · p. 3

Abstract

from arXiv · show

Excessive reuse of holdout data can lead to overfitting. However, there is little concrete evidence of significant overfitting due to holdout reuse in popular multiclass benchmarks today. Known results show that, in the worst-case, revealing the accuracy of $k$ adaptively chosen classifiers on a data set of size $n$ allows to create a classifier with bias of $\Theta(\sqrt{k/n})$ for any binary prediction problem. We show a new upper bound of $\tilde O(\max\{\sqrt{k\log(n)/(mn)},k/n\})$ on the worst-case bias that any attack can achieve in a prediction problem with $m$ classes. Moreover, we present an efficient attack that achieve a bias of $\Omega(\sqrt{k/(m^2 n)})$ and improves on previous work for the binary setting ($m=2$). We also present an inefficient attack that achieves a bias of $\tilde\Omega(k/n)$. Complementing our theoretical work, we give new practical attacks to stress-test multiclass benchmarks by aiming to create as large a bias as possible with a given number of queries. Our experiments show that the additional uncertainty of prediction with a large number of classes indeed mitigates the effect of our best attacks. Our work extends developments in understanding overfitting due to adaptive data analysis to multiclass prediction problems. It also bears out the surprising fact that multiclass prediction problems are significantly more robust to overfitting when reusing a test (or holdout) dataset. This offers an explanation as to why popular multiclass prediction benchmarks, such as ImageNet, may enjoy a longer lifespan than what intuition from literature on binary classification suggests.

1 Introduction

The paper asks why heavily reused multiclass benchmarks can remain useful despite the risks of adaptive test-set reuse. It analyzes how class count affects overfitting, develops bounds and attacks, and tests practical attacks on ImageNet.

1 Introduction

  • The paper addresses the contrast between extensive benchmark reuse and evidence that leading ImageNet models transfer gracefully to a newly collected test set.Adaptive test-set feedback can affect future model and hyperparameter choices, motivating analysis beyond query counts alone.Source: §1 · pp. 1–2

1.1 Our contributions

  • The paper finds that achieving a fixed bias in the worst case requires at least linearly more queries as the number of classes grows.The authors identify class count as a factor that mitigates overfitting, both theoretically and experimentally.Source: §1 · p. 2, §1.1 · p. 3

1.2 Related work

  • The authors position their work as extending adaptive-data-analysis results to multiclass prediction, whose accuracy measurements lack the simple linear structure of binary prediction.They also distinguish prediction bias from related reconstruction work, which focuses on partial reconstruction.Source: §1.1 · p. 2, §1.2 · p. 5

1.1 Our contributions

  • Theoretical contributions include upper and lower bounds on bias from adaptive accuracy queries, including an efficient point-wise attack and an inefficient reconstruction-based attack.The point-wise attack is optimal within a broad class of attacks; the reconstruction-based attack requires access to test points, but not their labels.Source: §1.1 · pp. 3–4
  • In prior-free simulations, overfitting becomes substantially harder as class count grows, and the binary attack improves on the attack in [BH15].On ImageNet, the best reported attack overfits by about 3% with 5000 queries.Source: §1.1 · pp. 4–5
  • On ImageNet, attacks using model logits as prior information gave only a minor improvement over prior-free attacks; selecting the lowest-confidence points gave modest improvements, while restricting each point to its top R predicted classes exploits top-R accuracy.Source: §1.1 · p. 4

2 Preliminaries

The preliminaries define the accuracy-query model for test-set overfitting and distinguish point-wise attacks from attacks that may access test points. They also specify prior-based average-case accuracy and introduce concentration results used later.

2 Preliminaries

  • A test-set overfitting attack makes at most k adaptive queries to test-set accuracy and outputs a classifier; queries may depend on earlier accuracy responses.The attack’s performance is measured against its accuracy on the underlying population.Source: §2 · p. 6
  • A point-wise attack generates queries and its output separately for each point, using query predictions and observed accuracies; it can be implemented without access to test points.Its achieved accuracy depends only on the target-label vector.Source: §2 · p. 6
  • For point-wise attacks or attacks with point access, a prior can specify an independent label distribution for each test point, and average-case accuracy is evaluated over labels sampled from it.For every prior, the stated average-case accuracy is at least the worst-case accuracy.Source: §2 · p. 7

2.1 Random variables and concentration

  • The concentration subsection states the Chernoff bound and a Bernoulli Berry–Esseen result for later use.The Berry–Esseen statement compares a Bernoulli average with a Gaussian having mean p and variance p(1 − p).Source: §2.1 · p. 7

3 Upper bound

Under a uniform prior over labelings, this section establishes an upper bound on the bias any attack can achieve, including attacks with access to the test points. Its analysis uses a description-length argument and also applies to access models that limit the information revealed.

3 Upper bound

  • The bound applies even when an attacker can access the test points, under the uniform-prior setting with no prior knowledge of the test labels.Source: §3 · p. 7
  • For k ≥ n/m, the highest bias achieved is ~O(1/m); in this regime, roughly one query buys one additional correctly labeled point, up to logarithmic factors.The bound has a transition at k=n/m.Source: §3 · p. 8
  • A description-length argument underlies the upper bound: finding a classifier with non-negligible success probability requires learning many bits about the target labels.Source: §3 · p. 8
  • The upper bound also applies to access models limiting information to t bits, using b=t+ln(1/δ), and extends to bounded approximate max-information.Source: §3 · p. 9

4 Test set overfitting attacks

This section analyzes point-wise and reconstruction-based attacks that use query accuracies to induce bias or recover labels. It describes the point-wise bias lower bound and unique-recovery guarantee, as well as full or partial reconstruction depending on whether the query set suffices.

4.1 Point-wise attack

  • For any prior, NBπ achieves at least the expected accuracy of every point-wise attack using k uniformly random queries; without a prior, NB is optimal.The attack scores each possible label using its prior probability times the likelihood of the observed query labels given the returned accuracies, then predicts a maximizing label.Source: §4.1 · pp. 10–12
  • Theorem 4.4 establishes a bias lower bound for the point-wise attack when m≥2 and n≥k≥kmin=O(ln n + m ln m).The analysis compares NB with a simpler attack that selects the plurality among query labels whose accuracies exceed the mean by a threshold; Poissonization makes label counts independent.Source: §4.1 · pp. 13–14

4.2 Reconstruction-based attack

  • For random query matrices, the reconstruction theorem guarantees unique recovery from shifted accuracies with probability at least 1/2; the attack exactly reconstructs part of the test-set labels.The shifted-accuracy condition extends the uniqueness argument of Erdos and Rényi [ER63] and Chvátal [Chv83]; the attack is not computationally efficient.Source: §4 · p. 9, §4.2 · p. 14
  • A fixed query set can distinguish labelings by their accuracies, enabling full label reconstruction and an attack with accuracy 1 when enough queries are available.The attack can recover the unknown labeling by trying candidate labelings and selecting one whose accuracy matches the observed accuracy.Source: §4.2 · p. 17
  • For k ≥40m ln(m), Corollary 4.6 gives an attack that reconstructs a subset of labels and predicts the rest uniformly at random.The proof extends queries over the recovered subset to the full set of n labels.Source: §4.2 · pp. 17–18

5 Experimental evaluation

The experiments test the point-wise attack on synthetic multiclass labels and compare it with a binary attack and an analytical baseline. On ImageNet, restricting the attack to less-confident points and fewer candidate labels yields larger accuracy gains in the reported 5,200-query examples.

Class-count experiments

  • Figure 3 reports NB attack bias over 10 trials on uniformly random test labels across class counts and test-set sizes of 10,000 and 50,000.The maximum possible bias differs by class count and is 1 − 1/m.Source: §5 · p. 19, Figure 3 · p. 20

Binary comparison

  • For uniformly random binary labels, Figure 5 compares NB’s observed relative advantage with Blum and Hardt’s majority-based attack.The two attacks differ in that NB weights queries by their observed accuracies, whereas the majority function uses only ±1 weights.Source: §5 · p. 19

ImageNet attacks

  • 0.42% accuracy boost after 5200 queries resulted from using the model’s predictive distribution as the NB prior, averaged over 10 attack simulations.Source: §5 · p. 20
  • 1.44% accuracy boost after 5200 queries followed culling to the 10K least-confident points, leaving errors on the other 40K points intact.The heuristic reduces the attacked test-set size to one fifth of the original.Source: §5 · p. 20
  • 3.0% accuracy boost after 5200 queries was observed with R = 2 when the top-R and confidence-culling heuristics were combined.The top-R restriction trades fewer effective classes for a ceiling set by the model’s top-R accuracy.Source: §5 · p. 20

Analytical baseline

  • The linear-scan baseline starts from a random query and changes one point’s label per successive query, revealing its true label when accuracy increases.Figure 2 compares this baseline’s expected performance with the average accuracies in Figure 1 at the same query count.Source: Figure 2 · p. 19, §5 · p. 20

Class-count experiments

  • For fixed advantage over 1/m, query counts rose superlinearly with class count m; Figure 4’s endpoint slopes were roughly 1.2 and 1.3.The text also says maintaining the Theorem 4.4 bound requires a quadratic increase in queries as m increases.Source: §5 · p. 19, Figure 4 · p. 21

A Proof of Lemma 4.3

The proof uses Poissonization to analyze label-count maxima under a perturbed categorical distribution. It compares the true label’s count with the largest competing count using symmetry, Poisson tail bounds, and quantiles.

Poissonization

  • Poissonization replaces a fixed multinomial sample count with a Poisson-distributed count, yielding independent Poisson counts for the classes.For independent Poisson variables, their sum is Poisson with parameter equal to the sum of their parameters.Source: A Proof of Lemma 4.3 · p. 24

Count comparison

  • Under ργ, the true label m has probability 1/m + γ, while each other label has probability 1/m − γ/(m−1).The proof splits the true-label count into a baseline Poisson count and an independent increment, leaving an i.i.d. vector for comparison.Source: A Proof of Lemma 4.3 · p. 25
  • The argmax analysis compares the true-label count with the largest rival count, using symmetry of the baseline counts and bounding ties by a one-half chance of selecting m.An increment in the true-label count can make it exceed the rival maximum; the proof bounds the probability of such an increment.Source: A Proof of Lemma 4.3 · pp. 25–26

Tail bounds

  • Poisson quantiles and a union bound constrain the rival maximum, while a tail-to-mass bound controls the probability across the relevant count interval.The proof defines quantiles u and v for Pois(λ′), then bounds the probability that the maximum rival count exceeds v.Source: A Proof of Lemma 4.3 · pp. 24, 26
Loading 1905.10360v1…