On the Vapnik-Chervonenkis dimension of products of intervals in $\mathbb{R}^d$
This provides a theoretical foundation for understanding the combinatorial complexity of geometric sets in machine learning, but it is incremental as it builds on existing VC theory.
The paper tackles the problem of determining the Vapnik-Chervonenkis (VC) dimension for products of intervals in ℝᵈ, resulting in a concrete formula showing that the VC dimension of balls in ℓ∞ᵈ equals ⌊(3d+1)/2⌋.
We study combinatorial complexity of certain classes of products of intervals in $\mathbb{R}^d$, from the point of view of Vapnik-Chervonenkis geometry. As a consequence of the obtained results, we conclude that the Vapnik-Chervonenkis dimension of the set of balls in $\ell_\infty^d$ -- which denotes $\R^d$ equipped with the sup norm -- equals $\lfloor (3d+1)/2\rfloor$.