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.
翻译:本文从游戏理论角度处理对抗性实例问题。 我们研究攻击者和分类者组成的零和游戏中是否存在混合的纳什平衡的开放问题。 虽然先前的作品通常只允许一个玩家使用随机化策略, 但我们显示有必要考虑分类者和攻击者随机化。 我们证明这个游戏没有双重性差距, 意思是它总是接受大约纳什平衡。 我们还提供了第一批优化算法, 以学习混合的分类者, 大致了解这个游戏的价值, 即 emph{i. e.} 程序, 以构建一个最强的随机化分类者。