# Upper bound for VCdim of $H$ in terms of subgraph$(F)$, where $H := \{S(f) | f \in F\}$, with $S(f) := \{(x,y) \in X \times \{\pm 1\} | yf(x) \le 1\}$

$$\DeclareMathOperator\sg{sg}\DeclareMathOperator\VCdim{VCdim}$$ Let $$X$$ be a measurable space and given a measurable function $$f:X \to \mathbb R$$, recall that the subgraph of $$f$$, denoted $$\sg(f)$$ is defined by $$\sg(f) := \{(x,t) \in X \times \mathbb R \mid f(x) \le t\}.$$

Let $$F$$ be a collection of measurable functions $$f: X \to \mathbb R$$, such that the set $$\sg(F) := \{\sg(f) \mid f \in F\}$$ has VC dimension at most $$d$$. Fix $$\gamma \in \mathbb R$$ and define a collection of measurable subsets of $$X \times \{\pm 1\}$$ by $$H := \Lambda(F) := \{\Lambda(f) \mid f \in F\},$$ where $$\Lambda(f):= \{(x,y) \in X \times \{\pm 1\} \mid yf(x) \le \gamma\}$$.

Question. Is there an upper-bound for the VC dimension of $$H$$ in terms of $$d$$ ?

## Observation

For any $$f \in F$$, define $$f_y:X \to \mathbb R$$ by $$f_y(x) := yf(x)-\gamma + y$$, and let $$F_y := \{f_y \mid f \in F\}$$. Thus, $$F_y$$ is an affine translation of $$F$$. Then, one computes

$$\begin{split} \Lambda(f) &= \cup_{y \in \{\pm 1\}} \{(x,y) \mid x \in X,\, yf(x) \le \gamma\}\\ &= \cup_{y \in \{\pm 1\}} \{(x,y) \mid x \in X,\, f_y(x) \le y\}\\ &= \cup_{y \in \{\pm 1\}} \{(x,t) \in X \times \mathbb R \mid f_y(x) \le t\} \cap X \times \{y\}\\ &= \cup_{y \in \{\pm 1\}} \sg(f_y) \cap X \times \{y\}\\ &= \cup_{y \in \{\pm 1\}} \Lambda_y(f), \end{split}$$ where $$\Lambda_y(f) := \sg(f_y) \cap X \times \{y\}$$. For every $$y$$, let $$\Lambda_y(F) := \{\Lambda_y(f) \mid f \in F\}$$. We deduce that $$H = \{\cup_{y \in \{\pm 1\}} \Lambda_y(f) \mid f \in F\} \subseteq \{A \cup B \mid A \in \Lambda_+(F),\, B \in \Lambda_-(F)\},$$ and so, thanks to Lemma 2.6.17 (part (iii)) of van der Vaart and Wellner's Weak convergence and empirical processes book, we obtain $$\VCdim(H) \le \sum_{y \in \{\pm 1\}}\VCdim(\Lambda_y(F)). \tag{1}$$

Now, observe that $$\Lambda_y(F) = \{A \cap X \times \{y\} \mid A \in \sg(F_y)\}$$, and so by part (ii) of the same lemma as before, we get $$\VCdim(\Lambda_y(F)) \le \VCdim(\sg(F_y)). \tag{2}$$.

Assumption 1. $$F$$ is closed under transformations of the form $$f \mapsto yf+c$$, with $$y \in \{\pm 1\}$$ and $$c \in \mathbb R$$.

Under this assumption, it holds that $$F_y \subseteq F$$ for all $$y$$ and we deduce from (2) that $$\VCdim(\Lambda_y(F)) \le \VCdim(\sg(F)) \le d$$. Combining with (1) gives $$\VCdim(H) \le 2d. \tag{3}$$

Question. Are my computations correct, and can a bound in the form of (3), i.e. $$\VCdim(H) \le Cd$$ (for an absolute constant $$C$$), be obtained without Assumption 1?

Let us suppose that $$H$$ shatters some $$k$$ points $$(x_i,y_i)$$, $$i\in[k]$$. That means that for all $$b\in\{0,1\}^k$$, there is an $$f=f_b\in F$$ such that $$y_if(x_i)\le\gamma$$ if $$b_i=1$$ and $$y_if(x_i)>\gamma$$ if $$b_i=0$$, for all $$i\in[k]$$. Let $$J\subset[k]$$ correspond to the indices for which $$y_i=1$$. Then certainly $$\mathrm{sg}(F)$$ shatters the set $$\{(x_i,\gamma):i\in J\}$$. Now let $$J’=[k]\setminus J$$ correspond to the indices for which $$y_i=-1$$. For these, we have $$f(x_i)\ge\gamma$$ if $$b_i=1$$ and $$f(x_i)<\gamma$$ if $$b_i=0$$, for all $$i\in J’$$. Define $$\eta:=\max_{b\in\{0,1\}^k}\max_{i\in J’,b_i=0}y_i f_b(x_i).$$ We know that $$\eta<\gamma$$, so $$\gamma’:=(\gamma+\eta)/2\in(\eta,\gamma)$$. It is easy to see that $$\mathrm{sg}(F)$$ shatters the set $$\{(x_i,\gamma’):i\in J’\}$$. Since $$|J|\le d$$ and $$|J’|\le d$$ and $$k=|J|+|J’|$$, it follows that VC-dim$$(H)\le2d$$ without any additional closure assumptions on $$F$$.
• Thanks for the nice and clear answer. Also thanks for the comment about measurability, which i don't even use. Finally, concerning closure under the mapping $\phi_{y,c}: f \mapsto yf + c$ , indeed it seems I can do away without that assumption by noting $\phi_{y,c}$ is a bijection between $F$ and $G:=\phi_{y,c}(F)$, and so $F$ and $G$ have the same VC pseudo-dimension. Consequently, $F$ and $F_y$ (notation in the question) have same VC pseudo-dimension. Thanks again! Commented Apr 28, 2022 at 8:09