arXiv:2603.15412cs.LG2026-03被引 2

用拓扑复杂度衡量分类问题难易,揭示几何结构对学习的决定性影响。

Local Urysohn Width: A Topological Complexity Measure for Classification

  • 基于度量空间的局部连通专家数量定义新复杂度指标
  • 证明了拓扑环数与分类复杂度存在严格正比关系
  • 适合研究学习理论、几何机器学习的学者参考

我们提出局部乌里松宽度(local Urysohn width),作为度量空间上分类问题的拓扑-几何复杂度度量。不同于VC维、肥破碎维和Rademacher复杂度等表征假设类丰富性的指标,乌里松宽度刻画的是分类问题本身的拓扑几何复杂性:在安全区域内正确分类所有点所需的最小连通、直径有界的局部专家数。我们证明四个核心结论:第一,严格层次定理:对任意整数 $w \geq 1$,存在一个连通紧致度量空间(首贝蒂数 $β_1 = w$ 的圆环束)上的分类问题,其乌里松宽度恰好为 $w$,表明输入空间的拓扑复杂性会强制要求分类器复杂性。第二,拓扑×几何标度律:宽度按 $Ω(w \cdot L/D_0)$ 增长,其中 $w$ 表示独立环数,$L/D_0$ 为环周长与局部尺度之比。第三,与VC维的双向分离:存在问题族使宽度无界而VC维恒定,反之亦然。第四,样本复杂度下界:任何必须正确分类宽度为 $w$ 的问题安全区域中所有点的学习器,所需样本数至少为 $Ω(w \log w)$,且与VC维无关。

原文摘要 · Abstract (English)

We introduce \emph{local Urysohn width}, a complexity measure for classification problems on metric spaces. Unlike VC dimension, fat-shattering dimension, and Rademacher complexity, which characterize the richness of hypothesis \emph{classes}, Urysohn width characterizes the topological-geometric complexity of the classification \emph{problem itself}: the minimum number of connected, diameter-bounded local experts needed to correctly classify all points within a margin-safe region. We prove four main results. First, a \textbf{strict hierarchy theorem}: for every integer $w \geq 1$, there exists a classification problem on a \emph{connected} compact metric space (a bouquet of circles with first Betti number $β_1 = w$) whose Urysohn width is exactly~$w$, establishing that topological complexity of the input space forces classifier complexity. Second, a \textbf{topology $\times$ geometry scaling law}: width scales as $Ω(w \cdot L/D_0)$, where $w$ counts independent loops and $L/D_0$ is the ratio of loop circumference to locality scale. Third, a \textbf{two-way separation from VC dimension}: there exist problem families where width grows unboundedly while VC dimension is bounded by a constant, and conversely, families where VC dimension grows unboundedly while width remains~1. Fourth, a \textbf{sample complexity lower bound}: any learner that must correctly classify all points in the safe region of a width-$w$ problem needs $Ω(w \log w)$ samples, independent of VC dimension.

学习理论拓扑机器学习复杂度分析

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