Reverse Euclidean and Gaussian isoperimetric inequalities for parallel sets with applications

Abstract

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^{\Theta (d)}V/r$, whereas its Gaussian surface area is upper-bounded by $\max (e^{\Theta (d)},e^{\Theta (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.

32 pages, 4 figures. Updated version contains new results for parallel sets in the ${\ell }_{\infty }$-norm, and versions of the reverse Brunn-Minkowski and reverse entropy power inequalities