Abstract
We present a minimax optimal learner for the problem of learning predictorsrobust to adversarial examples at test-time. Interestingly, we find that thisrequires new algorithmic ideas and approaches to adversarially robust learning.In particular, we show, in a strong negative sense, the suboptimality of therobust learner proposed by Montasser, Hanneke, and Srebro (2019) and a broaderfamily of learners we identify as local learners. Our results are enabled byadopting a global perspective, specifically, through a key technicalcontribution: the global one-inclusion graph, which may be of independentinterest, that generalizes the classical one-inclusion graph due to Haussler,Littlestone, and Warmuth (1994). Finally, as a byproduct, we identify adimension characterizing qualitatively and quantitatively what classes ofpredictors $\mathcal{H}$ are robustly learnable. This resolves an open problemdue to Montasser et al. (2019), and closes a (potentially) infinite gap betweenthe established upper and lower bounds on the sample complexity ofadversarially robust learning.