# Improved Estimation of Concentration Under ℓp-Norm Distance Metrics Using Half Spaces

arXiv: https://arxiv.org/abs/2103.12913 · HTML: https://mlsanity.com/paper/2103.12913/

## Key facts

- Cited by 4 papers in the map (data through 13 Oct 2026).
- Builds on 15 of its 26 references that are in the map.
- First posted on arXiv 24 Mar 2021.

## Builds on (most cited first, 15 of 15)

- [Explaining and Harnessing Adversarial Examples](https://mlsanity.com/paper/1412.6572/) (2014)
- [Towards Deep Learning Models Resistant to Adversarial Attacks](https://mlsanity.com/paper/1706.06083/) (2017)
- [Intriguing properties of neural networks](https://mlsanity.com/paper/1312.6199/) (2013)
- [Theoretically Principled Trade-off between Robustness and Accuracy](https://mlsanity.com/paper/1901.08573/) (2019)
- [Certified Adversarial Robustness via Randomized Smoothing](https://mlsanity.com/paper/1902.02918/) (2019)
- [Distillation as a Defense to Adversarial Perturbations against Deep Neural Networks](https://mlsanity.com/paper/1511.04508/) (2015)
- [Provable defenses against adversarial examples via the convex outer adversarial polytope](https://mlsanity.com/paper/1711.00851/) (2017)
- [Are adversarial examples inevitable?](https://mlsanity.com/paper/1809.02104/) (2018)
- [Adversarial examples from computational constraints](https://mlsanity.com/paper/1805.10204/) (2018)
- [Adversarial vulnerability for any classifier](https://mlsanity.com/paper/1802.08686/) (2018)
- [Lower Bounds on Adversarial Robustness from Optimal Transport](https://mlsanity.com/paper/1909.12272/) (2019)
- [The Curse of Concentration in Robust Learning: Evasion and Poisoning Attacks from Concentration of Measure](https://mlsanity.com/paper/1809.03063/) (2018)
- [Adversarial Risk and Robustness: General Definitions and Implications for the Uniform Distribution](https://mlsanity.com/paper/1810.12272/) (2018)
- [Empirically Measuring Concentration: Fundamental Limits on Intrinsic Robustness](https://mlsanity.com/paper/1905.12202/) (2019)
- [Understanding the Intrinsic Robustness of Image Distributions using Conditional Generative Models](https://mlsanity.com/paper/2003.00378/) (2020)

## Built on by (most cited first, 4 of 4)

- [It Is All About Data: A Survey on the Effects of Data on Adversarial Robustness](https://mlsanity.com/paper/2303.09767/) (2023)
- [Understanding Intrinsic Robustness Using Label Uncertainty](https://mlsanity.com/paper/2107.03250/) (2021)
- [On some theoretical limitations of Generative Adversarial Networks](https://mlsanity.com/paper/2110.10915/) (2021)
- [The Role of Input Dimensionality in the Emergence and Targeted Control of Adversarial Examples](https://mlsanity.com/paper/2606.26207/) (2026)

## Abstract (arXiv)

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 ℓp-norms (p ≥ 2). We leverage these theoretical insights to design a method that uses half-spaces to estimate the concentration of any empirical dataset under ℓ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.