Reviews: PAC-learning in the presence of adversaries

This paper develops a PAC framework for learning binary functions in the presence of evasion adversaries. Let X be the domain, and suppose we have an unknown function f: X - {0,1} to be learned, and we also have a hypothesis class H. Moreover, there is a "closeness" relationship defined on pairs in X, so any pair of points in X are either "close" or "far." We also have an unknown distribution P on X. For a hypothesis h, its loss is defined as follows: first we pick a data point x in X according to P. The true label of this point is f(x).