Upper bounding VC dimension of an indicator function class

Question

I would like to upper bound the VC dimension of the function class $ F$ defined as follows:

$$ F := \left\{ (x,t) \mapsto \mathbb{1} \left( c_Q\min_{q \in Q} {\|x-q \|}_1 - t > 0 \right) \; | \; Q \subset \mathbb{R}^{d}, |Q| = k \right\}, $$

where $k$ is a fixed positive integer, $x,q \in \mathbb{R}^d, t \in \mathbb{R}, \mathbb{1}(A) $ denotes the indicator function (=1 if A is true and 0 otherwise), $\| \cdot \| _ 1 $ is the L1 norm, and $c_Q$ is a constant that depends on $Q$.

Context: I am studying a grouping procedure that minimizes $L_1$ norm. In particular, I would like understand how the complexity of the class of functions $\left\{ c_Q \min_{q \in Q} {\|x-q \|}_1 \; | \; Q \subset \mathbb{R}^{d}, |Q| = k \right\}$ scales with $k$ and $d$ (i.e., $O(d k \log k)$) . The above is a generalization of VC-dimension called Pseudodimension.

I would appreciate any suggestions you might have. Thanks!

Answer 1

Not an answer to the question

We prove that for $p=2$ $$dim_{VC}\underset{\substack{k\to\infty\\d\to\infty}}=O\Big( dk\ln(dk)\Big).$$ for the family of functions $$A_p=\{(x,t_1,...,t_k)\mapsto1(\min_i||x-q_i||_p-t_i>0)|(x_1,...,x_k)\in(\mathbb R^d)^k\},$$ which is still bigger than the dimension of $$B=\{(x,t)\mapsto1(\min_q||x-q_i||_p-t>0)|Q\subset\mathbb R^d, \#(Q)=k\}.$$ $$=\{(x,c_Qt)\mapsto1(c_Q\min_q||x-q_i||_p-t>0)|Q\subset\mathbb R^d, \#(Q)=k\}.$$ We note $Norm(\cdot)=||\cdot||_p$

Using $k$ clusters of $(d+1)$ points laid out in simplexes, we can find that $dim_{VC}(A_p)\geq(d+1)k$, so $d=_{k,d\to\infty}o(dim_{VC}(A_p))$. This relation will be of use later.

Consider $n$ the VC-dimension of $A_p$ and a set $x_1,...,x_n\in\mathbb R^d$ that we can pulverize. We first try to give an upper bound to the cardinal of $\big\{\{x_i\}_{1\leq i\leq n}\cap f^{-1}(\{0\})\big\}_{f\in A_p}$, then use it to derive a majoration of $n$.

For every $1\leq i\not=j\leq n$, we can choose some hyperplane $H_{i,j}=H_{j,i}$ separating the sets $Norm(q-x_i)<Norm(q-x_j)$ and $Norm(q-x_i)>Norm(q-x_j)$. To each $q\in\mathbb R^d\setminus(\bigcup_{i,j}H_{i,j})$, associate $\sigma_q$ such that $\sigma_q(i)<\sigma_q(j)$ iff $q$ and $x_i$ are on the same side of $H_{i,j}$. If $q\in H_{i,j}$, set $\sigma_q$ to be the permutation of a neighbouring region of $\mathbb R^d\setminus(\bigcup_{i,j}H_{i,j})$.

If we note $N=\frac{n(n-1)}2$ the number of hyperplanes, $\mathbb R^d\setminus(\bigcup_{i,j}H_{i,j})$ has at most $P_d(N)=\dbinom{N+1}{0}+\dbinom{N+1}{1}+...+\dbinom{N+1}{d}$ open regions. Note that $P_n$ is of degree $d$. For $k$ and $d$ going to $\infty$, we have $d=_{d,k\to\infty}o(dk)=_{d,k\to\infty}o(N)$, so we should have $P_d(N)\sim_{k,d\to\infty}\binom{N+1}d\frac{((N+1)/d-0.5)^de^d}{\sqrt{2\pi k}}.$ Without proof of the former, let us use the much coarser $P_d(N)\leq (d+1)\binom{N+1}d$.

For every $q\in\mathbb R^d$, $Norm(q-x_{\sigma_q(i)})$ is non decreasing, so when we picking a radius $t$, the ball of center $q$ and radius $t$ can have at most $n+1$ intersections with $\{x_1,...,x_n\}$ : no points, $\{x_{\sigma_q(1)}\}$, $\{x_{\sigma_q(1)},x_{\sigma_q(2)}\}$,... or all the $x_i$. For a ball of center $q_i$ and radius $t_i$, choosing $q_i$ gives at most $P_d(N)$ possibilities for $\sigma_q$, wich then translates to at most $(n+1)P_d(N)$ possibilities for $B(q_i,t_i)\cap\{x_i\}_{i\leq n}$. With $k$ balls, we get $\big((n+1)P_d(N)\big)^k$ possible sets.

Since we can pulverize $x_1,...,x_n$, we have \begin{align*} 2^n&\leq\big((n+1)P_d(N)\big)^k\\ n\ln(2)&\leq k\ln\big((n+1)P_d(\frac{n(n-1)}2)\big)\\ n&\leq \frac{k}{\ln(2)}\ln\left((n+1)(d+1)\binom{N}{d}\right)\\ &\underset{\substack{k\to\infty\\d\to\infty}}=O\Big( k\ln(nd\frac{(\frac{N}d-\frac12)^d\mathrm e^d}{\sqrt d})\Big)\\ &\underset{\substack{k\to\infty\\d\to\infty}}=O\Big( k\big(\ln(n)+\ln(d)+d\ln(\frac{N}d-\frac12)+d-\frac12\ln(d)\big)\Big)\\ &\underset{\substack{k\to\infty\\d\to\infty}}=O\Big( dk\ln(\frac{N}d)\Big)\\ &\underset{\substack{k\to\infty\\d\to\infty}}=O\Big( dk\ln(n)\Big)\\ &\underset{\substack{k\to\infty\\d\to\infty}}=O\Big( dk\ln(dk\ln(n))\Big)\\ &\underset{\substack{k\to\infty\\d\to\infty}}=O\Big( dk\ln(dk)\Big)+O\Big(dk\ln(\ln(n))\Big)\\ &\underset{\substack{k\to\infty\\d\to\infty}}=O\Big( dk\ln(dk)\Big)+o\Big(dk\ln(n)\Big)\\ &\underset{\substack{k\to\infty\\d\to\infty}}=O\Big( dk\ln(dk)\Big) \end{align*} For $k,d\to\infty$, we used an equivalent for $\binom{N}k$ when $k=o(N)$, and used the fact that $\ln(N)=O( \ln(n))$. Using the better equivalent $P_d(N)\sim\binom{N+1}d$ (if true) should provide $O(dk\ln(k)).$