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

By Vitaly Feldman, Roy Frostig, Moritz Hardt. 2019

36 citations recorded by the source corpus.

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.

Subfields: Artificial Intelligence, Evaluation & Benchmarks

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Evaluation & Benchmarks

Citations in the corpus

The Effect of Natural Distribution Shift on Question Answering Models (2020, background): “A number of works have proffered explanations for why adaptive overﬁtting does not occur in machine learning (Blum & Hardt, 2015; Mania et al., 2019; Feldman et al., 2019; Zrnic & Hardt, 2019).”
Are We Learning Yet? A Meta Review of Evaluation Failures Across Machine Learning (2021, background): “An active line of research investigates the question of overﬁtting from test set reuse, also known as adaptive overﬁtting [5, 9, 14, 37, 42, 91, 175].”
A Meta-Analysis of Overfitting in Machine Learning (2019, background): “The adaptive data analysis literature [6, 17] provides a range of theoretical explanations for how the common machine learning workflow may implicitly mitigate overfitting [3, 8, 12, 23].”
The Benchmark Lottery (2021, background): “For instance, [Feldman et al., 2019b,a] show that in multi-class classiﬁcation, the large number of classes makes it substantially harder to overﬁt due to test set reuse.”
Model Similarity Mitigates Test Set Overuse (2019, background): “[6] gave evidence that the number of classes in a classification problem helps mitigate overfitting in benchmarks.”