2019/05/24 by Vitaly Feldman, Roy Frostig, Feldman, Vitaly +3 · 6 citations
Computer Science · #Adversarial Robustness in Machine Learning #Data Structures and Algorithms (cs.DS) #Domain Adaptation and Few-Shot Learning #FOS: Computer and information sciences #Imbalanced Data Classification Techniques #Machine Learning (cs.LG) #Machine Learning (stat.ML)
paper · pdf · doi:10.48550/arxiv.1905.10360
openalex publication_date 2019/05/24 · openalex created_date 2019/06/27 · openalex updated_date 2026/07/28
Excessive reuse of holdout data can lead to overfitting. However, there is\nlittle concrete evidence of significant overfitting due to holdout reuse in\npopular multiclass benchmarks today. Known results show that, in the\nworst-case, revealing the accuracy of k adaptively chosen classifiers on a\ndata set of size n allows to create a classifier with bias of\n\Θ(\√(k/n)) for any binary prediction problem. We show a new upper\nbound of O(\max \√(k\log(n)/(mn)),k/n ) on the worst-case bias\nthat any attack can achieve in a prediction problem with m classes. Moreover,\nwe present an efficient attack that achieve a bias of \Ω(\√(k/(m2\nn))) and improves on previous work for the binary setting (m=2). We also\npresent an inefficient attack that achieves a bias of Ω(k/n).\nComplementing our theoretical work, we give new practical attacks to\nstress-test multiclass benchmarks by aiming to create as large a bias as\npossible with a given number of queries. Our experiments show that the\nadditional uncertainty of prediction with a large number of classes indeed\nmitigates the effect of our best attacks.\n Our work extends developments in understanding overfitting due to adaptive\ndata analysis to multiclass prediction problems. It also bears out the\nsurprising fact that multiclass prediction problems are significantly more\nrobust to overfitting when reusing a test (or holdout) dataset. This offers an\nexplanation as to why popular multiclass prediction benchmarks, such as\nImageNet, may enjoy a longer lifespan than what intuition from literature on\nbinary classification suggests.\n