arXiv:2411.14664stat.MLcs.CC2024-11被引 3

用少量点近似高维高斯过程的上确界,且数量与维度无关。

Sparsifying Suprema of Gaussian Processes

  • 从任意有界向量集提取少量点,通过加权后逼近原过程上确界。
  • 所提稀疏集大小仅依赖于精度ε,与数据维度和集合大小无关。
  • 适用于高维统计学习、凸集近似及鲁棒算法设计。

我们给出了中心高斯过程上确界的维数无关稀疏化结果:设T为ℝⁿ中任意(可能无限)有界向量集,{Xₜ := t·g}ₜ∈T为定义在T上的标准高斯过程,其中g∼N(0, Iₙ)。我们证明存在一个O_ε(1)大小的子集S⊆T及一组实数{cₛ}ₛ∈S,使得随机变量supₛ∈S{Xₛ + cₛ}在L¹意义下是supₜ∈T Xₜ的ε-近似。值得注意的是,稀疏集大小完全独立于|T|和环境维度n。本文给出两个应用:一是范数的“朱尼亚定理”——任一ℝⁿ上的范数ν(x),存在仅依赖于O_ε(1)个方向投影的范数ψ(x),使得ψ(g)以1−ε概率在乘法意义下(1±ε)近似ν(g);二是凸集稀疏化——任意距离原点至少为r的半空间交集,可被仅含O_{r,ε}(1)个半空间的交集以ε精度近似(在N(0,Iₙ)分布下),从而导出多项式时间的对抗性学习与容错性质测试算法。

原文摘要 · Abstract (English)

We give a dimension-independent sparsification result for suprema of centered Gaussian processes: Let $T$ be any (possibly infinite) bounded set of vectors in $\mathbb{R}^n$, and let $\{\boldsymbol{X}_t := t \cdot \boldsymbol{g} \}_{t\in T}$ be the canonical Gaussian process on $T$, where $\boldsymbol{g}\sim N(0, I_n)$. We show that there is an $O_\varepsilon(1)$-size subset $S \subseteq T$ and a set of real values $\{c_s\}_{s \in S}$ such that the random variable $\sup_{s \in S} \{\boldsymbol{X}_s + c_s\}$ is an $\varepsilon$-approximator\,(in $L^1$) of the random variable $\sup_{t \in T} {\boldsymbol{X}}_t$. Notably, the size of the sparsifier $S$ is completely independent of both $|T|$ and the ambient dimension $n$. We give two applications of this sparsification theorem: - A "Junta Theorem" for Norms: We show that given any norm $ν(x)$ on $\mathbb{R}^n$, there is another norm $ψ(x)$ depending only on the projection of $x$ onto $O_\varepsilon(1)$ directions, for which $ψ({\boldsymbol{g}})$ is a multiplicative $(1 \pm \varepsilon)$-approximation of $ν({\boldsymbol{g}})$ with probability $1-\varepsilon$ for ${\boldsymbol{g}} \sim N(0,I_n)$. - Sparsification of Convex Sets: We show that any intersection of (possibly infinitely many) halfspaces in $\mathbb{R}^n$ that are at distance $r$ from the origin is $\varepsilon$-close (under $N(0,I_n)$) to an intersection of only $O_{r,\varepsilon}(1)$ halfspaces. This yields new polynomial-time \emph{agnostic learning} and \emph{tolerant property testing} algorithms for intersections of halfspaces.

高斯过程稀疏化凸集统计学习

Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。