  Starting with Gilmer et al. (2018), several works have demonstrated the
inevitability of adversarial examples based on different assumptions about the
underlying input probability space. It remains unclear, however, whether these
results apply to natural image distributions. In this work, we assume the
underlying data distribution is captured by some conditional generative model,
and prove intrinsic robustness bounds for a general class of classifiers, which
solves an open problem in Fawzi et al. (2018). Building upon the
state-of-the-art conditional generative models, we study the intrinsic
robustness of two common image benchmarks under $\ell_2$ perturbations, and
show the existence of a large gap between the robustness limits implied by our
theory and the adversarial robustness achieved by current state-of-the-art
robust models. Code for all our experiments is available at
https://github.com/xiaozhanguva/Intrinsic-Rob.
