Reverse Euclidean and Gaussian isoperimetric inequalities for parallel sets with applications

Abstract

The r-parallel set of a measurable set A 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 R^d with volume at most V is upper-bounded by e^(d)V/r, whereas its Gaussian surface area is upper-bounded by (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.

Tasks

Reproductions