VC dimension of Euclidean balls

ID: vc-dimension-of-euclidean-balls

The positive-radius closed Euclidean balls in have VC dimension for . Vertices of a regular simplex are shattered: interpolate any desired signs by an affine function , then perturb a sphere through the vertices to the score . For the upper bound, take an affine dependence among points and orient it so that . Labelling the positive coefficients inside and the negative coefficients outside would force , while the affine dependence makes this sum equal . The weaker upper bound from unrestricted lifted affine linear classifiers loses their fixed quadratic coefficient.

New to topics? Read the docs here!