# Consistent Non-Parametric Methods for Maximizing Robustness

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

## Key facts

- Cited by 7 papers in the map (data through 14 Oct 2026).
- Builds on 17 of its 47 references that are in the map.
- First posted on arXiv 18 Feb 2021.

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

- [Towards Deep Learning Models Resistant to Adversarial Attacks](https://mlsanity.com/paper/1706.06083/) (2017)
- [Intriguing properties of neural networks](https://mlsanity.com/paper/1312.6199/) (2013)
- [Towards Evaluating the Robustness of Neural Networks](https://mlsanity.com/paper/1608.04644/) (2016)
- [The Limitations of Deep Learning in Adversarial Settings](https://mlsanity.com/paper/1511.07528/) (2015)
- [Distillation as a Defense to Adversarial Perturbations against Deep Neural Networks](https://mlsanity.com/paper/1511.04508/) (2015)
- [Delving into Transferable Adversarial Examples and Black-box Attacks](https://mlsanity.com/paper/1611.02770/) (2016)
- [Certifying Some Distributional Robustness with Principled Adversarial Training](https://mlsanity.com/paper/1710.10571/) (2017)
- [Certified Defenses against Adversarial Examples](https://mlsanity.com/paper/1801.09344/) (2018)
- [Formal Guarantees on the Robustness of a Classifier against Adversarial Manipulation](https://mlsanity.com/paper/1705.08475/) (2017)
- [MMA Training: Direct Input Space Margin Maximization through Adversarial Training](https://mlsanity.com/paper/1812.02637/) (2018)
- [Large Margin Deep Networks for Classification](https://mlsanity.com/paper/1803.05598/) (2018)
- [CAT: Customized Adversarial Training for Improved Robustness](https://mlsanity.com/paper/2002.06789/) (2020)
- [Rates of Convergence for Nearest Neighbor Classification](https://mlsanity.com/paper/1407.0067/) (2014)
- [Analyzing the Robustness of Nearest Neighbors to Adversarial Examples](https://mlsanity.com/paper/1706.03922/) (2017)
- [Towards Proving the Adversarial Robustness of Deep Neural Networks](https://mlsanity.com/paper/1709.02802/) (2017)
- [When are Non-Parametric Methods Robust?](https://mlsanity.com/paper/2003.06121/) (2020)
- [On the Robustness of Deep K-Nearest Neighbors](https://mlsanity.com/paper/1903.08333/) (2019)

## Built on by (most cited first, 7 of 7)

- [Probabilistically Robust Learning: Balancing Average- and Worst-case Performance](https://mlsanity.com/paper/2202.01136/) (2022)
- [Robust Empirical Risk Minimization with Tolerance](https://mlsanity.com/paper/2210.00635/) (2022)
- [The Adversarial Consistency of Surrogate Risks for Binary Classification](https://mlsanity.com/paper/2305.09956/) (2023)
- [On the Computability of Robust PAC Learning](https://mlsanity.com/paper/2406.10161/) (2024)
- [The Consistency of Adversarial Training for Binary Classification](https://mlsanity.com/paper/2206.09099/) (2022)
- [Adversarial Attack and Defense for Non-Parametric Two-Sample Tests](https://mlsanity.com/paper/2202.03077/) (2022)
- [Generalization Properties of Adversarial Training for ℓ0-Bounded Adversarial Attacks](https://mlsanity.com/paper/2402.03576/) (2024)

## Abstract (arXiv)

Learning classifiers that are robust to adversarial examples has received a great deal of recent attention. A major drawback of the standard robust learning framework is there is an artificial robustness radius r that applies to all inputs. This ignores the fact that data may be highly heterogeneous, in which case it is plausible that robustness regions should be larger in some regions of data, and smaller in others. In this paper, we address this limitation by proposing a new limit classifier, called the neighborhood optimal classifier, that extends the Bayes optimal classifier outside its support by using the label of the closest in-support point. We then argue that this classifier maximizes the size of its robustness regions subject to the constraint of having accuracy equal to the Bayes optimal. We then present sufficient conditions under which general non-parametric methods that can be represented as weight functions converge towards this limit, and show that both nearest neighbors and kernel classifiers satisfy them under certain conditions.