We prove an exponential separation for the sample complexity between the
standard PAC-learning model and a version of the Equivalence-Query-learning
model. We then show that this separation has interesting implications for
adversarial robustness. We explore a vision of designing an adaptive defense
that in the presence of an attacker computes a model that is provably robust.
In particular, we show how to realize this vision in a simplified setting.

In order to do so, we introduce a notion of a strong adversary: he is not
limited by the type of perturbations he can apply but when presented with a
classifier can repetitively generate different adversarial examples. We explain
why this notion is interesting to study and use it to prove the following.
There exists an efficient adversarial-learning-like scheme such that for every
strong adversary $mathbf{A}$ it outputs a classifier that (a) cannot be
strongly attacked by $mathbf{A}$, or (b) has error at most $epsilon$. In both
cases our scheme uses exponentially (in $epsilon$) fewer samples than what the
PAC bound requires.

Go to Source of this post
Author Of this post: <a href="http://arxiv.org/find/cs/1/au:+Gluch_G/0/1/0/all/0/1">Grzegorz G&#x142;uch</a>, <a href="http://arxiv.org/find/cs/1/au:+Urbanke_R/0/1/0/all/0/1">R&#xfc;diger Urbanke</a>

By admin