There has been much recent interest in adversarially robust learning – where the goal is to learn a classifier which can accurately classify, not just data from the underlying distribution, but also small perturbations thereof. In this talk, we will look at this phenomenon from the point of view of non-parametric methods, such as nearest neighbors and decision trees.
For non-parametric methods, Stone in 1977 proved a consistency theorem that shows that when the training data size goes to infinity, the accuracy of many methods approach that of the Bayes optimal classifier. In this talk, we will establish a robustness analogue of the Bayes optimal, called the r-optimal, and show an analogue of Stone’s theorem for robustness for the case when data from different classes is well-separated. We will then briefly discuss what happens when this is not the case.
Talk based on joint work with Robi Bhattacharjee.