Local Urysohn Width: A Topological Complexity Measure for Classification

Abstract

We introduce 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 classes, Urysohn width characterizes the topological-geometric complexity of the classification 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 strict hierarchy theorem: for every integer w 1, there exists a classification problem on a 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 topology geometry scaling law: width scales as Ω(w L/D_0), where w counts independent loops and L/D_0 is the ratio of loop circumference to locality scale. Third, a 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 sample complexity lower bound: any learner that must correctly classify all points in the safe region of a width-w problem needs Ω(w w) samples, independent of VC dimension.

Reproductions