arXiv:2503.10240cs.DMcs.LG2025-03被引 5

提出球面维数,统一学习理论中拓扑工具的应用。

Spherical dimension

  • 用连续分布空间扩展可实现数据集,构造高维球面对象
  • 球面维数至少等于VC维,且与拓扑定理紧密关联
  • 解决半平面带边距的消歧问题等关键开放难题

我们引入并研究了球面维数,这是VC维的一种自然拓扑松弛,能统一学习理论中多个依赖拓扑证明的结果。球面维数通过将可实现数据集扩展到连续的可实现分布空间来定义:在该空间中,一个大小为d的被分隔集合(以VC意义)被补全为一个d维实现实分布的球面。球面维数即为此空间中最大球面的维度。因此,球面维数至少等于VC维。该概念为利用Borsuk-Ulam定理及相关拓扑工具提供了共同基础。我们展示了其在多种应用中的效用,包括部分概念类的消歧、从分类到随机凸优化的归约、稳定性和可复现性,以及样本压缩方案。出人意料的是,我们证明了Alon、Hanneke、Holzman和Moran(FOCS 2021)提出的关于带边距半平面是否存在非平凡消歧的开放问题,等价于VC维与球面维数是否同时有限这一基本开放问题。

原文摘要 · Abstract (English)

We introduce and study the spherical dimension, a natural topological relaxation of the VC dimension that unifies several results in learning theory where topology plays a key role in the proofs. The spherical dimension is defined by extending the set of realizable datasets (used to define the VC dimension) to the continuous space of realizable distributions. In this space, a shattered set of size d (in the VC sense) is completed into a continuous object, specifically a d-dimensional sphere of realizable distributions. The spherical dimension is then defined as the dimension of the largest sphere in this space. Thus, the spherical dimension is at least the VC dimension. The spherical dimension serves as a common foundation for leveraging the Borsuk-Ulam theorem and related topological tools. We demonstrate the utility of the spherical dimension in diverse applications, including disambiguations of partial concept classes, reductions from classification to stochastic convex optimization, stability and replicability, and sample compression schemes. Perhaps surprisingly, we show that the open question posed by Alon, Hanneke, Holzman, and Moran (FOCS 2021) of whether there exist non-trivial disambiguations for halfspaces with margin is equivalent to the basic open question of whether the VC and spherical dimensions are finite together.

学习理论拓扑VC维球面维数

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