0
$\begingroup$

I'm searching for an upper-bound for the VC-dimension of the infinite intersection of two spheres. Thanks

$\endgroup$
2
  • $\begingroup$ How many spheres are interesting—two or infinity? And in what space? Finite-dimensional Euclidean or more exotic? $\endgroup$
    – Aryeh
    Apr 20 at 14:21
  • $\begingroup$ To be more precise, VC-dimension of the infinite phases of the moon. Each phase is the intersection of two spheres. In 2D $\endgroup$
    – shai
    Apr 20 at 20:57

1 Answer 1

1
$\begingroup$

Once the OP has clarified that the question is about the VC-dimension of the 2-fold intersection of spheres in $\mathbb{R}^d$ (in fact, $d=2$ was specified), a simple upper bound can be stated. The VC-dim of spheres in $\mathbb{R}^d$ is the same as that of half-spaces (via an easy scaling argument) --- namely, $d+1$. Lemma 3.2.3 of Blumer et al. (1989) bounds the VC-dim of the $k$-fold union/intersection of a class of VC-dim $d$ by $$ 2kd\log(3k). $$ Thus, $2\cdot2\cdot2\log(6)\approx 14$ is an upper-bound on the VC-dimension in the OP.

A. Blumer, A. Ehrenfeucht, D. Haussler, and M. K. Warmuth. Learnability and the Vapnik-Chervonenkis dimension. J. Assoc. Comput. Mach., 36(4):929–965, 1989. ISSN 0004-5411.

$\endgroup$
1
  • 1
    $\begingroup$ Thank you very much! $\endgroup$
    – shai
    Apr 21 at 9:29

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.