Local Urysohn Width: A Topological Complexity Measure for Classification

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 $\mathbf{\text{strict}}\mathbf{\text{hierarchy}}\mathbf{\text{theorem}}$: for every integer $w\ge 1$, there exists a classification problem on a \emph{connected} compact metric space (a bouquet of circles with first Betti number ${\beta }_1=w$) whose Urysohn width is exactly~$w$, establishing that topological complexity of the input space forces classifier complexity. Second, a $\mathbf{\text{topology}}\times \mathbf{\text{geometry}}\mathbf{\text{scaling}}\mathbf{\text{law}}$: width scales as $\mathrm{\Omega }(w\cdot L\mathrm{/}{D}_0)$, where $w$ counts independent loops and $L\mathrm{/}{D}_0$ is the ratio of loop circumference to locality scale. Third, a $\mathbf{\text{two-way}}\mathbf{\text{separation}}\mathbf{\text{from}}\mathbf{\text{VC}}\mathbf{\text{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 $\mathbf{\text{sample}}\mathbf{\text{complexity}}\mathbf{\text{lower}}\mathbf{\text{bound}}$: any learner that must correctly classify all points in the safe region of a width-$w$ problem needs $\mathrm{\Omega }(w\log w)$ samples, independent of VC dimension.