  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.

Machine Learning