论文标题
与应用相反的欧几里得和高斯等等不平等现象
Reverse Euclidean and Gaussian isoperimetric inequalities for parallel sets with applications
论文作者
论文摘要
$ r $ - 平行的可测量集合$ a \ subseteq \ mathbb r^d $的集合是所有点的集合，其距离$ a $的距离最多为$ r $。在本文中，我们表明，$ \ mathbb r^d $设置为$ r $ - 平行的表面积，最多$ v $由$ e^{θ（d）} v/r $上限，而其高斯表面积是$ \ max（e^> e^（e^θ（d）}，e^}，e^}（d）}（d）。我们还以$ r $ - 平行的集合得出了Brunn-Minkowski不等式的反向形式，作为高斯平滑的随机变量的反向熵功率不等式。我们将结果应用于理论机器学习中的两个问题：（1）在高斯分布下学习$ r $ - 平行集的计算复杂性； （2）界定估计稳健风险的样本复杂性，这是对抗性机器学习文献的风险概念，在假设检验中类似于贝叶斯风险。
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.
