Improved Estimation of Concentration Under $\ell_p$-Norm Distance
  Metrics Using Half Spaces
  Concentration of measure has been argued to be the fundamental cause of
adversarial vulnerability. Mahloujifar et al. presented an empirical way to
measure the concentration of a data distribution using samples, and employed it
to find lower bounds on intrinsic robustness for several benchmark datasets.
However, it remains unclear whether these lower bounds are tight enough to
provide a useful approximation for the intrinsic robustness of a dataset. To
gain a deeper understanding of the concentration of measure phenomenon, we
first extend the Gaussian Isoperimetric Inequality to non-spherical Gaussian
measures and arbitrary $\ell_p$-norms ($p \geq 2$). We leverage these
theoretical insights to design a method that uses half-spaces to estimate the
concentration of any empirical dataset under $\ell_p$-norm distance metrics.
Our proposed algorithm is more efficient than Mahloujifar et al.'s, and our
experiments on synthetic datasets and image benchmarks demonstrate that it is
able to find much tighter intrinsic robustness bounds. These tighter estimates
provide further evidence that rules out intrinsic dataset concentration as a
possible explanation for the adversarial vulnerability of state-of-the-art
classifiers.
