Reverse Euclidean and Gaussian isoperimetric inequalities for parallel sets with applications
This work addresses foundational geometric inequalities with applications to theoretical machine learning, particularly in adversarial settings, but it appears incremental as it extends known isoperimetric inequalities to parallel sets.
The paper tackles the problem of bounding the surface area of parallel sets in Euclidean and Gaussian spaces, showing upper bounds of e^{Θ(d)}V/r for Euclidean surface area and max(e^{Θ(d)}, e^{Θ(d)}/r) for Gaussian surface area, and applies these results to bound computational and sample complexity in machine learning tasks such as learning parallel sets and estimating robust risk.
The $r$-parallel set of a measurable set $A \subseteq \mathbb R^d$ is the set of all points whose distance from $A$ is at most $r$. In this paper, we show that the surface area of an $r$-parallel set in $\mathbb R^d$ with volume at most $V$ is upper-bounded by $e^{Θ(d)}V/r$, whereas its Gaussian surface area is upper-bounded by $\max(e^{Θ(d)}, e^{Θ(d)}/r)$. We also derive a reverse form of the Brunn-Minkowski inequality for $r$-parallel sets, and as an aside a reverse entropy power inequality for Gaussian-smoothed random variables. We apply our results to two problems in theoretical machine learning: (1) bounding the computational complexity of learning $r$-parallel sets under a Gaussian distribution; and (2) bounding the sample complexity of estimating robust risk, which is a notion of risk in the adversarial machine learning literature that is analogous to the Bayes risk in hypothesis testing.