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


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


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

  • $\begingroup$ BTW, no measurability assumptions are needed -- shattering is a purely combinatorial condition. $\endgroup$
    – Aryeh
    Apr 27, 2022 at 18:55
  • 1
    $\begingroup$ 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! $\endgroup$
    – dohmatob
    Apr 28, 2022 at 8:09

Your Answer

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

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