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\}$

Question

$\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?

---

Related: https://mathoverflow.net/q/420830/78539

Answer 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$.