arXiv:2607.10751cs.LGmath.CO2026-07

研究带边界区域的几何概念类的VC维,给出与维度无关的上界。

The VC dimension of partial concept classes via Radon's theorem

  • 通过Radon定理将距离线性化,结合符号和估计方法分析
  • 在L_p空间中,对扩展球类的VC维给出不依赖维度的上界
  • 适用于关注几何学习理论、泛化能力的研究者

延续Alon等人(FOCS 2021)的工作,定义部分概念类(PCC)为从基集到{0,1,∗}的局部函数族,其概念将集合划分为黑(f⁻¹(1))、灰(f⁻¹(∗))和白(f⁻¹(0))三部分。其VC维基于不取∗值的集合的可分性定义。本文研究实巴拿赫空间中的两类几何PCC:带边距δ>0的扩展半空间(灰区为邻近半空间的宽度至少δ的条带)和扩展球(灰区为单位球周围宽度δ的环形区域)。主要成果是在L_p(μ)空间(1≤p<∞,含非欧几里得情形ℓ₁^d)中,对扩展球类的PCC给出了维度无关的上界,该上界仅依赖于边距δ和半径,不随环境维度或测度空间变化。此结果扩展了Bourneuf、Charbit和Thomassé(FOCS 2025)在欧氏空间ℓ₂^d中的工作。同时证明了与上界匹配的下界,且在L_p空间中建立了一个稠密邻域引理,推广了已知的欧氏结果。方法依赖于将距离映射至具有非平凡Rademacher型的空间,并使用平衡符号和估计或无维Radon定理。论证融合了泛函分析思想,对非专业读者亦清晰可读。

原文摘要 · Abstract (English)

Following Alon, Hanneke, Holzman, and Moran (FOCS 2021), we define a partial concept class (PCC) as a family of partial functions \(f: V\to\{0,1,\ast\}\); equivalently, its concepts partition the ground set into black ($f^{-1}(1)$), grey ($f^{-1}(\ast)$), and white parts ($f^{-1}(0)$). Its VC dimension is defined by shattering sets on which the value $\ast$ is not taken. We study two geometric PCCs in real Banach spaces, both with a margin \(δ>0\): expanded half-spaces, where the grey part is a strip of width at least \(δ\) adjacent to a half-space, and expanded balls, where the grey part is an annulus of width \(δ\) around a unit radius ball. Our main results are dimension-free upper bounds on the VC dimension of the PCC of expanded balls in \(L_p\parenthμ\), \(1\le p<\infty\), including the non-Euclidean and algorithmically particularly relevant case \(\ell^d_1\). These bounds depend on the margin and on the radii, but not on the ambient dimension or the underlying measure space. These are extensions of the work of Bourneuf, Charbit, and Thomassé (FOCS 2025) who studied the PCC of expanded balls in Euclidean space, that is, $\ell_2^d$. We also prove lower bounds on the VC dimension that match the upper bounds in terms of the margin parameter $δ$. Finally, we derive a Dense Neighborhood Lemma in \(L_p\)-spaces, again extending the known Euclidean results. Our method relies on the linearization of the distance through a map into a space of non-trivial Rademacher type, and then the use of a balanced signed-sum estimate, or a no-dimensional Radon theorem. The arguments rely on ideas from functional analysis that are clearly explained for the non-expert in that field.

VC维几何学习泛化能力泛函分析

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