Back to Search
Start Over
Reverse Euclidean and Gaussian Isoperimetric Inequalities for Parallel Sets With Applications.
- Source :
-
IEEE Transactions on Information Theory . Oct2021, Vol. 67 Issue 10, p6368-6383. 16p. - Publication Year :
- 2021
-
Abstract
- The $r$ -parallel set of a set $A \subseteq {\mathbb {R}} ^{d}$ is the set of all points whose distance from $A$ is less than $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. [ABSTRACT FROM AUTHOR]
Details
- Language :
- English
- ISSN :
- 00189448
- Volume :
- 67
- Issue :
- 10
- Database :
- Academic Search Index
- Journal :
- IEEE Transactions on Information Theory
- Publication Type :
- Academic Journal
- Accession number :
- 153710487
- Full Text :
- https://doi.org/10.1109/TIT.2021.3102828