What is the VC Dimension of the class of $k$-dimensional cross-polytope (1-norm ($l_1$) balls)?

A $k$-dimensional $l_1$ ball with radius $r\in \mathcal R$ and center $\mathbb v\in \mathcal R^k$ is

$\{\mathbb x\in\mathcal R^k: ||\mathbb x-\mathbb v||_1\le r\}$.

Namely, denote $\mathbb x = [x_1,x_2,...,x_k]$ and $\mathbb v = [v_1,v_2,...,v_k]$, A $k$-dimensional $l_1$ ball with radius $r$ and center $\mathbb v$ is

$\{\mathbb x\in\mathcal R^k, |x_1-v_1|+|x_2-v_2|+...+|x_k-v_k|\le r\}$.

  • $\begingroup$ Can you answer this for $k = 1$? $\endgroup$ Aug 6, 2021 at 22:14
  • $\begingroup$ When $k=1$, the class of 1-norm balls becomes the class of intervals whose VC Dimension is 2. $\endgroup$ Aug 7, 2021 at 6:20
  • $\begingroup$ Does the answer change for larger $k$? $\endgroup$ Aug 7, 2021 at 13:12
  • $\begingroup$ Yes. When $k=2$, the class of $l_1$ balls is the class of squares whose edges parallel the $[1,1]$ or $[1,-1]$. The VC Dimension of such class of squares is 3. $\endgroup$ Aug 7, 2021 at 13:28
  • $\begingroup$ What happens for $k=3$? $\endgroup$ Aug 7, 2021 at 13:30


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Browse other questions tagged or ask your own question.