# Scalable Optimal Classifiers for Adversarial Settings under Uncertainty

arXiv: https://arxiv.org/abs/2106.14702 · HTML: https://mlsanity.com/paper/2106.14702/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 7 of its 56 references that are in the map.
- First posted on arXiv 28 Jun 2021.

## Builds on (most cited first, 7 of 7)

- [Explaining and Harnessing Adversarial Examples](https://mlsanity.com/paper/1412.6572/) (2014)
- [Distillation as a Defense to Adversarial Perturbations against Deep Neural Networks](https://mlsanity.com/paper/1511.04508/) (2015)
- [Towards the Science of Security and Privacy in Machine Learning](https://mlsanity.com/paper/1611.03814/) (2016)
- [Randomization matters. How to defend against strong adversarial attacks](https://mlsanity.com/paper/2002.11565/) (2020)
- [Randomized Prediction Games for Adversarial Machine Learning](https://mlsanity.com/paper/1609.00804/) (2016)
- [Robust Attacks against Multiple Classifiers](https://mlsanity.com/paper/1906.02816/) (2019)
- [A Game-Theoretic Analysis of Adversarial Classification](https://mlsanity.com/paper/1610.04972/) (2016)

## Abstract (arXiv)

We consider the problem of finding optimal classifiers in an adversarial setting where the class-1 data is generated by an attacker whose objective is not known to the defender -- an aspect that is key to realistic applications but has so far been overlooked in the literature. To model this situation, we propose a Bayesian game framework where the defender chooses a classifier with no a priori restriction on the set of possible classifiers. The key difficulty in the proposed framework is that the set of possible classifiers is exponential in the set of possible data, which is itself exponential in the number of features used for classification. To counter this, we first show that Bayesian Nash equilibria can be characterized completely via functional threshold classifiers with a small number of parameters. We then show that this low-dimensional characterization enables to develop a training method to compute provably approximately optimal classifiers in a scalable manner; and to develop a learning algorithm for the online setting with low regret (both independent of the dimension of the set of possible data). We illustrate our results through simulations.