Existence and Minimax Theorems for Adversarial Surrogate Risks in Binary Classification

Natalie S. Frank; Jonathan Niles-Weed

We prove existence, minimax, and complementary slackness theorems for adversarial surrogate risks in binary classification. These results extend recent work that established analogous minimax and existence theorems for the adversarial classification risk. We show that such statements continue to hold for a very general class of surrogate losses; moreover, we remove some of the technical restrictions present in prior work. Our results provide an explanation for the phenomenon of transfer attacks and inform new directions in algorithm development.

Existence and Minimax Theorems for Adversarial Surrogate Risks in Binary Classification

Abstract