Mixed Nash Equilibria in the Adversarial Examples Game

Laurent Meunier, Meyer Scetbon, Rafael B Pinot, Jamal Atif, Yann Chevaleyre
Proceedings of the 38th International Conference on Machine Learning, PMLR 139:7677-7687, 2021.

Abstract

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.

Cite this Paper

BibTeX
@InProceedings{pmlr-v139-meunier21a, title = {Mixed Nash Equilibria in the Adversarial Examples Game}, author = {Meunier, Laurent and Scetbon, Meyer and Pinot, Rafael B and Atif, Jamal and Chevaleyre, Yann}, booktitle = {Proceedings of the 38th International Conference on Machine Learning}, pages = {7677--7687}, year = {2021}, editor = {Meila, Marina and Zhang, Tong}, volume = {139}, series = {Proceedings of Machine Learning Research}, month = {18--24 Jul}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v139/meunier21a/meunier21a.pdf}, url = {https://proceedings.mlr.press/v139/meunier21a.html}, abstract = {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.} }
Endnote
%0 Conference Paper %T Mixed Nash Equilibria in the Adversarial Examples Game %A Laurent Meunier %A Meyer Scetbon %A Rafael B Pinot %A Jamal Atif %A Yann Chevaleyre %B Proceedings of the 38th International Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2021 %E Marina Meila %E Tong Zhang %F pmlr-v139-meunier21a %I PMLR %P 7677--7687 %U https://proceedings.mlr.press/v139/meunier21a.html %V 139 %X 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.
APA
Meunier, L., Scetbon, M., Pinot, R.B., Atif, J. & Chevaleyre, Y.. (2021). Mixed Nash Equilibria in the Adversarial Examples Game. Proceedings of the 38th International Conference on Machine Learning, in Proceedings of Machine Learning Research 139:7677-7687 Available from https://proceedings.mlr.press/v139/meunier21a.html.

Related Material