Thumbnail

Mixed Nash Equilibria in the Adversarial Examples Game

Meunier, Laurent; Scetbon, Meyer; Pinot, Rafael; Atif, Jamal; Chevaleyre, Yann (2021), Mixed Nash Equilibria in the Adversarial Examples Game. https://basepub.dauphine.psl.eu/handle/123456789/22145

View/Open
Type
Document de travail / Working paper
Date
2021
Series title
Preprint Lamsade
Published in
Paris
Metadata
Show full item record
Author(s)
Meunier, Laurent
Laboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
Scetbon, Meyer
Centre de Recherche en Économie et Statistique [CREST]
Pinot, Rafael
Ecole Polytechnique Federale de Lausanne [EPFL]
Atif, Jamal
Laboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
Chevaleyre, Yann
Laboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
Abstract (EN)
This paper tackles the problem of adversarial examples from a game theoretic point of view. We study the open question of the existence of mixed Nash equilibria in the zero-sum game formed by the attacker and the classifier. While previous works usually allow only one player to use randomized strategies, we show the necessity of considering randomization for both the classifier and the attacker. We demonstrate that this game has no duality gap, meaning that it always admits approximate Nash equilibria. We also provide the first optimization algorithms to learn a mixture of classifiers that approximately realizes the value of this game, \emph{i.e.} procedures to build an optimally robust randomized classifier.
Subjects / Keywords
game theory