Search papers, labs, and topics across Lattice.
This paper introduces "local Urysohn width," a novel topological complexity measure for classification problems defined on metric spaces, focusing on the problem's intrinsic geometric structure rather than the hypothesis class. The authors establish a strict hierarchy theorem demonstrating that the topological complexity of the input space directly influences classifier complexity, and derive a scaling law relating width to the number of independent loops and the ratio of loop circumference to locality scale. Furthermore, they prove a two-way separation from VC dimension and establish a sample complexity lower bound of $Ω(w \log w)$ for learning problems with width $w$.
Forget VC dimension – the topological complexity of your data might be the real bottleneck in classification, demanding at least $Ω(w \log w)$ samples even when VC dimension is low.
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.
