Varför är klassificerare i hög dimension sårbara för "adversariella" störningar? Vi visar att det sannolikt inte beror på information teoretiska begränsningar, utan snarare på beräkningsmässiga begränsningar. För det första bevisar vi att för en bred uppsättning klassificeringsuppgifter innebär blotta existensen av en robust klassificering att den kan hittas av en möjligen exponentiellt tidsalgoritm med relativt få träningsexempel. Då ger vi en särskild klassificeringsuppgift där att lära sig en robust klassificering är beräkningsmässigt oåtkomlig. Mer exakt konstruerar vi en binär klassificering uppgift i högdimensionellt utrymme som är (i) information teoretiskt lätt att lära sig robust för stora perturbationer, (ii) effektivt lärbar (icke-robustly) av en enkel linjär separator, (iii) men är inte effektivt robust lärbar, även för små perturbationer, av någon algoritm i den statistiska frågan (SQ) modell. Detta exempel ger en exponentiell separation mellan klassiskt lärande och robust lärande i den statistiska frågemodellen. Det tyder på att kontradiktoriska exempel kan vara en oundviklig biprodukt av beräkningsbegränsningar av inlärningsalgoritmer.
REF analyserar beräkningshårdheten i utbildningen av en robust klassificering i den statistiska frågemodellen.
Adversarial examples from computational constraints
{'venue': 'ArXiv', 'journal': 'ArXiv', 'mag_field_of_study': ['Mathematics', 'Computer Science']}