Towards Evading the Limits of Randomized Smoothing: A Theoretical Analysis
Randomized smoothing is the dominant standard for provable defenses against
adversarial examples. Nevertheless, this method has recently been proven to
suffer from important information theoretic limitations. In this paper, we
argue that these limitations are not intrinsic, but merely a byproduct of
current certification methods. We first show that these certificates use too
little information about the classifier, and are in particular blind to the
local curvature of the decision boundary. This leads to severely sub-optimal
robustness guarantees as the dimension of the problem increases. We then show
that it is theoretically possible to bypass this issue by collecting more
information about the classifier. More precisely, we show that it is possible
to approximate the optimal certificate with arbitrary precision, by probing the
decision boundary with several noise distributions. Since this process is
executed at certification time rather than at test time, it entails no loss in
natural accuracy while enhancing the quality of the certificates. This result
fosters further research on classifier-specific certification and demonstrates
that randomized smoothing is still worth investigating. Although
classifier-specific certification may induce more computational cost, we also
provide some theoretical insight on how to mitigate it.