The VC-Dimension of Axis-Parallel Boxes on the Torus

2020/04/28 by Gillibert, Pierre, Lachmann, Thomas, Müllner, Clemens · 1 citation
#Combinatorics (math.CO) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #Machine Learning (cs.LG)

paper · doi:10.48550/arxiv.2004.13861

Abstract

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₂(d). This is especially surprising as the VC-dimension usually grows linearly with d in similar settings.

Cited by

• VC-dimension of generalized progressions in some nonabelian groups

Related

• Empty axis-parallel boxes
• The Vapnik-Chervonenkis dimension of cubes in ℝ^d
• Vapnik-Chervonenkis Dimension of Axis-Parallel Cuts
• Box-Counting Dimension Using Triangles
• The VC-dimension of k-vertex d-polytopes