Timezone: »

 
Poster
The advantages of multiple classes for reducing overfitting from test set reuse
Vitaly Feldman · Roy Frostig · Moritz Hardt

Wed Jun 12 06:30 PM -- 09:00 PM (PDT) @ Pacific Ballroom #197
in Posters Wed »
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.
Keywords: Computational Learning Theory · Statistical Learning Theory

Author Information

Vitaly Feldman (Google Brain)
Roy Frostig (Google Brain)
Moritz Hardt (Google Brain)

Related Events (a corresponding poster, oral, or spotlight)

More from the Same Authors