The VC-Dimension of Axis-Parallel Boxes on the Torus
arXiv:2004.13861v1
Originality Synthesis-oriented
AI Analysis
This provides a theoretical insight into learning theory and computational geometry, addressing a specific mathematical problem with incremental novelty.
The paper determined that the VC-dimension of axis-parallel boxes and cubes on a torus scales asymptotically as d log2(d), which is surprising because it typically grows linearly with dimension in comparable scenarios.
We show in this paper that the VC-dimension of the family of $d$-dimensional axis-parallel boxes and cubes on the $d$-dimensional torus are both asymptotically $d \log_2(d)$. This is especially surprising as the VC-dimension usually grows linearly with $d$ in similar settings.