Reducing Adversarially Robust Learning to Non-Robust PAC Learning

On the uniform convergence of relative frequencies of events to their probabilities

V. Vapnik and A. Chervonenkis · 1971

Earlier work this paper cites.

Theory of Pattern Recognition

V. Vapnik and A. Chervonenkis · 1974

Earlier work this paper cites.

Densité et dimension

P. Assouad · 1983

Earlier work this paper cites.

Learnability and the Vapnik-Chervonenkis dimension

A. Blumer, A. Ehrenfeucht, D. Haussler, and M. Warmuth · 1989

Earlier work this paper cites.

A general lower bound on the number of examples needed for learning

A. Ehrenfeucht, D. Haussler, M. Kearns, and L. Valiant · 1989

Earlier work this paper cites.

A decision-theoretic generalization of on-line learning and an application to boosting

Yoav Freund and Robert E. Schapire · 1997

Earlier work this paper cites.

Potential-based agnostic boosting

Adam Kalai and Varun Kanade · 2009

Earlier work this paper cites.

Lecture notes - machine learning theory, January 2010

Maria-Florina Balcan · 2010

Earlier work this paper cites.

Boosting

R. E. Schapire and Y. Freund · 2012

Cited alongside, same era.

Evasion attacks against machine learning at test time

Battista Biggio, Igino Corona, Davide Maiorca, Blaine Nelson, Nedim Šrndić, Pavel Laskov, Giorgio Giacinto, and Fabio Roli · 2013

Cited alongside, same era.

Intriguing properties of neural networks

Original

Christian Szegedy, Wojciech Zaremba, Ilya Sutskever, Joan Bruna, Dumitru Erhan, Ian Goodfellow, and Rob Fergus · 2013

Cited alongside, same era.

Explaining and harnessing adversarial examples

Original

Ian J Goodfellow, Jonathon Shlens, and Christian Szegedy · 2014

Cited alongside, same era.

Learning and inference in the presence of corrupted inputs

Uriel Feige, Yishay Mansour, and Robert E. Schapire · 2015

Cited alongside, same era.

Robust inference for multiclass classification

Uriel Feige, Yishay Mansour, and Robert E. Schapire · 2018

Later among the works it cites.

Towards deep learning models resistant to adversarial attacks

Aleksander Madry, Aleksandar Makelov, Ludwig Schmidt, Dimitris Tsipras, and Adrian Vladu · 2018

Later among the works it cites.

Improved generalization bounds for robust learning

Idan Attias, Aryeh Kontorovich, and Yishay Mansour · 2019

Later among the works it cites.

Adversarial examples from computational constraints

Sebastien Bubeck, Yin Tat Lee, Eric Price, and Ilya Razenshteyn · 2019

Later among the works it cites.

Vc classes are adversarially robustly learnable, but only improperly

Omar Montasser, Steve Hanneke, and Nathan Srebro · 2019

Later among the works it cites.

Efficiently learning adversarially robust halfspaces with noise

Omar Montasser, Surbhi Goel, Ilias Diakonikolas, and Nati Srebro · 2020