<p>Let us suppose that <span class="math-container">$H$</span> shatters some <span class="math-container">$k$</span> points <span class="math-container">$(x_i,y_i)$</span>, <span class="math-container">$i\in[k]$</span>.
That means that for all <span class="math-container">$b\in\{0,1\}^k$</span>, there is an <span class="math-container">$f=f_b\in F$</span> such that <span class="math-container">$y_if(x_i)\le\gamma$</span> if <span class="math-container">$b_i=1$</span> and
<span class="math-container">$y_if(x_i)&gt;\gamma$</span> if <span class="math-container">$b_i=0$</span>, for all <span class="math-container">$i\in[k]$</span>.
Let <span class="math-container">$J\subset[k]$</span> correspond to the indices for which <span class="math-container">$y_i=1$</span>.
Then certainly <span class="math-container">$\mathrm{sg}(F)$</span> shatters the set <span class="math-container">$\{(x_i,\gamma):i\in J\}$</span>.
Now let <span class="math-container">$J’=[k]\setminus J$</span> correspond to the indices for which <span class="math-container">$y_i=-1$</span>.
For these, we have
<span class="math-container">$f(x_i)\ge\gamma$</span> if <span class="math-container">$b_i=1$</span> and
<span class="math-container">$f(x_i)&lt;\gamma$</span> if <span class="math-container">$b_i=0$</span>, for all <span class="math-container">$i\in J’$</span>.
Define <span class="math-container">$$\eta:=\max_{b\in\{0,1\}^k}\max_{i\in J’,b_i=0}y_i f_b(x_i).$$</span> We know that <span class="math-container">$\eta&lt;\gamma$</span>, so <span class="math-container">$\gamma’:=(\gamma+\eta)/2\in(\eta,\gamma)$</span>. It is easy to see that
<span class="math-container">$\mathrm{sg}(F)$</span> shatters the set <span class="math-container">$\{(x_i,\gamma’):i\in J’\}$</span>.
Since <span class="math-container">$|J|\le d$</span> and <span class="math-container">$|J’|\le d$</span> and <span class="math-container">$k=|J|+|J’|$</span>, it follows that VC-dim<span class="math-container">$(H)\le2d$</span> without any additional closure assumptions on <span class="math-container">$F$</span>.</p>

CC BY-SA 4.0
2022-04-27T18:55:58.823Z
BTW, no measurability assumptions are needed -- shattering is a purely combinatorial condition.
Aryeh
CC BY-SA 4.0
2022-04-28T08:09:43.757Z
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!
dohmatob
CC BY-SA 4.0
2022-04-27T16:46:58.343Z
2022-04-28T09:36:52.663Z
2022-04-28T09:36:52.663Z
Aryeh
<p><span class="math-container">$\DeclareMathOperator\sg{sg}\DeclareMathOperator\VCdim{VCdim}$</span>
Let <span class="math-container">$X$</span> be a measurable space and given a measurable function <span class="math-container">$f:X \to \mathbb R$</span>, recall that the <em>subgraph</em> of <span class="math-container">$f$</span>, denoted <span class="math-container">$\sg(f)$</span> is defined by
<span class="math-container">$$
\sg(f) := \{(x,t) \in X \times \mathbb R \mid f(x) \le t\}.
$$</span></p>
<p>Let <span class="math-container">$F$</span> be a collection of measurable functions <span class="math-container">$f: X \to \mathbb R$</span>, such that the set <span class="math-container">$\sg(F) := \{\sg(f) \mid f \in F\}$</span> has <em>VC dimension</em> at most <span class="math-container">$d$</span>. Fix <span class="math-container">$\gamma \in \mathbb R$</span> and define a collection of measurable subsets of <span class="math-container">$X \times \{\pm 1\}$</span> by
<span class="math-container">$$
H := \Lambda(F) := \{\Lambda(f) \mid f \in F\},
$$</span>
where <span class="math-container">$\Lambda(f):= \{(x,y) \in X \times \{\pm 1\} \mid yf(x) \le \gamma\}$</span>.</p>
<blockquote>
<p><strong>Question.</strong> <em>Is there an upper-bound for the VC dimension of <span class="math-container">$H$</span> in terms of <span class="math-container">$d$</span> ?</em></p>
</blockquote>
<h2>Observation</h2>
<p>For any <span class="math-container">$f \in F$</span>, define <span class="math-container">$f_y:X \to \mathbb R$</span> by <span class="math-container">$f_y(x) := yf(x)-\gamma + y$</span>, and let <span class="math-container">$F_y := \{f_y \mid f \in F\}$</span>. Thus, <span class="math-container">$F_y$</span> is an affine translation of <span class="math-container">$F$</span>. Then, one computes</p>
<p><span class="math-container">$$
\begin{split}
\Lambda(f) &amp;= \cup_{y \in \{\pm 1\}} \{(x,y) \mid x \in X,\, yf(x) \le \gamma\}\\
&amp;= \cup_{y \in \{\pm 1\}} \{(x,y) \mid x \in X,\, f_y(x) \le y\}\\
&amp;= \cup_{y \in \{\pm 1\}} \{(x,t) \in X \times \mathbb R \mid f_y(x) \le t\} \cap X \times \{y\}\\
&amp;= \cup_{y \in \{\pm 1\}} \sg(f_y) \cap X \times \{y\}\\
&amp;= \cup_{y \in \{\pm 1\}} \Lambda_y(f),
\end{split}
$$</span>
where <span class="math-container">$\Lambda_y(f) := \sg(f_y) \cap X \times \{y\}$</span>. For every <span class="math-container">$y$</span>, let <span class="math-container">$\Lambda_y(F) := \{\Lambda_y(f) \mid f \in F\}$</span>. We deduce that
<span class="math-container">$$
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)\},
$$</span>
and so, thanks to Lemma 2.6.17 (part <em>(iii)</em>) of van der Vaart and Wellner's <em>Weak convergence and empirical processes</em> book, we obtain
<span class="math-container">$$
\VCdim(H) \le \sum_{y \in \{\pm 1\}}\VCdim(\Lambda_y(F)).
\tag{1}
$$</span></p>
<p>Now, observe that <span class="math-container">$\Lambda_y(F) = \{A \cap X \times \{y\} \mid A \in \sg(F_y)\}$</span>, and so by part <em>(ii)</em> of the same lemma as before, we get
<span class="math-container">$$
\VCdim(\Lambda_y(F)) \le \VCdim(\sg(F_y)).
\tag{2}
$$</span>.</p>
<blockquote>
<p><strong>Assumption 1.</strong> <em><span class="math-container">$F$</span> is closed under transformations of the form <span class="math-container">$f \mapsto yf+c$</span>, with <span class="math-container">$y \in \{\pm 1\}$</span> and <span class="math-container">$c  \in \mathbb R$</span>.</em></p>
</blockquote>
<p>Under this assumption, it holds that <span class="math-container">$F_y \subseteq F$</span> for all <span class="math-container">$y$</span> and we deduce from (2) that <span class="math-container">$\VCdim(\Lambda_y(F)) \le \VCdim(\sg(F)) \le d$</span>. Combining with (1) gives
<span class="math-container">$$
\VCdim(H) \le 2d.
\tag{3}
$$</span></p>
<blockquote>
<p><strong>Question.</strong> <em>Are my computations correct, and can a bound in the form of (3), i.e. <span class="math-container">$\VCdim(H) \le Cd$</span> (for an absolute constant <span class="math-container">$C$</span>), be obtained without <strong>Assumption 1</strong>?</em></p>
</blockquote>
<hr />
<p><strong>Related:</strong> <a href="https://mathoverflow.net/q/420830/78539">https://mathoverflow.net/q/420830/78539</a></p>

<machine-learning><pr.probability><st.statistics><vc-dimension>
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\}$
dohmatob
# 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\}$

(Asked by: username_0 on 2022-04-23)

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

**Tags:** machine-learning, pr.probability, st.statistics, vc-dimension

---

## 1 answers

### Answer by username_1 on 2022-04-27. Score: 2 | Accepted answer

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

> **Comments:**
> **username_1**: BTW, no measurability assumptions are needed -- shattering is a purely combinatorial condition.  
> **username_0**: 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!  

---

