Sparsifying Suprema of Gaussian Processes
Anindya De and Shivam Nadimpalli and Ryan O'Donnell and Rocco A. Servedio
我们为中心高斯进程的至上给出一个维度无关的散景结果:让T成为R^n中的任何(可能是无限)边界的向量集,让 {X_t := t ·g}_t∈ T 成为T上的规范高斯过程,其中g∼N(0,I_n)。 我们显示有一个 O_ε(1) 大小的子集 S ⊆ T 和一组真实值 {c_s}_s ∈ S,因此随机变量 sup_s ∈ S{X_s + c_s} 是随机变量 sup_t 的 ε-approximator (在 L^1) 的随机变量 sup_t ∈ TX_t。 值得注意的是,sparasifier S的大小完全独立于 |T| 环境维度n。 我们给出了这个s 套索定理的两个应用: - 规范的“Junta定理”:我们表明,给定R^n上的任何规范ν(x),有另一个规范ψ(x)仅取决于x对O_ε(1)方向的投影,其中ψ(g)是ν(g)的乘法(1±ε)近似,概率为g-ν(0,I)。 - 凸集合的稀疏:我们表明,R^n中与原点距离r的任何半空(可能无限多)的交集都是ε-close(在N(0,I_n)下)到只有O_r,ε(1)半空的交叉点。 这为半空间的交集带来了新的多项式不可知论学习和宽容属性测试算法。
We give a dimension-independent sparsification result for suprema of centered Gaussian processes: Let T be any (possibly infinite) bounded set of vectors in ℝ^n, and let {X_t := t ·g}_t∈ T be the canonical Gaussian process on T, where g∼ N(0, I_n). We show that there is an O_ε(1)-size subset S ⊆ T and a set of real values {c_s}_s ∈ S such that the random variable sup_s ∈ S{X_s + c_s} is an ε-approximator (in L^1) of the random variable sup_t ∈ TX_t. Notably, the size of the sparsifier S is compl...
