<p>Consider two real-valued function classes,
<span class="math-container">$\mathcal{F}_1$</span> acting on some set <span class="math-container">$\mathcal{X}_1$</span>
and
<span class="math-container">$\mathcal{F}_2$</span> acting on some set <span class="math-container">$\mathcal{X}_2$</span>.
I am going to bound the Pdim of
<span class="math-container">$\mathcal{F}_3$</span>
acting on
<span class="math-container">$\mathcal{X}_1\times \mathcal{X}_2$</span>
given by
<span class="math-container">$$
\mathcal{F}_3=\{
(x_1,x_2)\mapsto f_1(x_1)-f_2(x_2); 
f_1\in \mathcal{F}_1,
f_2\in \mathcal{F}_2
\}.
$$</span>
Since obviously <span class="math-container">$\mathcal{F}_3\supseteq \mathcal{F}'$</span>,
this also upper-bounds the Pdim of <span class="math-container">$\mathcal{F}'$</span>.</p>
<p>By definition,
<span class="math-container">$$
\mathrm{Pdim}(\mathcal{F}_3)
=
\mathrm{VCdim}(\{
(x_1,x_2,t)\mapsto 1_{f_1(x_1)-f_2(x_2)&gt;t}
;
f_1\in \mathcal{F}_1,
f_2\in \mathcal{F}_2
\}).
$$</span>
Now we use the basic fact that
<span class="math-container">$$a+b&gt;t \implies
\exists t_1,t_2: a&gt;t_1, b&gt;t_2
$$</span>
to conclude
<span class="math-container">$$
\mathrm{Pdim}(\mathcal{F}_3)
\le
\mathrm{VCdim}(\{
(x_1,x_2,t_1,t_2)\mapsto 
1_{f_1(x_1)&gt;t_1}\cdot 
1_{-f_2(x_2)&gt;t_2}
;
f_1\in \mathcal{F}_1,
f_2\in \mathcal{F}_2
\}).
$$</span></p>
<p>The question has now been reduced to a more basic one:
If <span class="math-container">$\mathcal{H}_1, \mathcal{H}_2$</span>
are Boolean function classes acting on
<span class="math-container">$\mathcal{X}_1, \mathcal{X}_2$</span>, resp.,
how can we control the VCdim of
<span class="math-container">$\mathcal{H}_3$</span> acting on
<span class="math-container">$\mathcal{X}_1\times \mathcal{X}_2$</span>
given by
<span class="math-container">$$
\mathcal{H}_3
=
\{
(x_1,x_2)\mapsto h_1(x_1)h_2(x_2);
h_1\in \mathcal{H}_1,
h_2\in \mathcal{H}_2
\}
$$</span>
in terms of the VCdim of
<span class="math-container">$\mathcal{H}_1, \mathcal{H}_2$</span>?</p>
<p>Clearly, on any sequence
<span class="math-container">$(x_1,y_1),\ldots,(x_n,y_n)$</span>,
the number of behaviors achieved by
<span class="math-container">$\mathcal{H}_3$</span>—formally, the cardinality of the
projection/restriction of
<span class="math-container">$\mathcal{H}_3$</span>
this set, denoted by
<span class="math-container">$\mathcal{H}_3[(x_1,y_1),\ldots,(x_n,y_n)]$</span>—is upper-bounded by
<span class="math-container">$\mathcal{H}_1[x_1,\ldots,x_n]
\cdot
\mathcal{H}_2[y_1,\ldots,y_n]
$</span>.
If <span class="math-container">$d_1,d_2$</span> are the VCdims of
<span class="math-container">$\mathcal{H}_1, \mathcal{H}_2$</span>, resp,
then Sauer's lemma implies
<span class="math-container">$$
\mathcal{H}_3[(x_1,y_1),\ldots,(x_n,y_n)]
\le
\mathcal{H}_1[x_1,\ldots,x_n]
\cdot
\mathcal{H}_2[y_1,\ldots,y_n]
\le
\left(
\frac{e n}{d_1}
\right)^{d_1}
\cdot
\left(
\frac{e n}{d_2}
\right)^{d_2}
\le
\left(
\frac{2 e n}{d_1+d_2}
\right)^{d_1+d_2}
,
$$</span>
where the last inequality is contained in the proof of
Lemma 16 in
<a href="https://www.jmlr.org/papers/v23/20-1353.html" rel="nofollow noreferrer">https://www.jmlr.org/papers/v23/20-1353.html</a>
It further follows from that lemma (taking <span class="math-container">$k=2$</span>)
that
<span class="math-container">$$
\mathrm{VCdim}(\mathcal{H}_3)
\le
2\log(6)(d_1+d_2).
$$</span>
The only remaining piece is the trivial observation that
<span class="math-container">$
\mathrm{Pdim}(\mathcal{F})=
\mathrm{Pdim}(-\mathcal{F})
$</span>.</p>
<p>It follows that
<span class="math-container">$$
\mathrm{Pdim}(\mathcal{F}_3)
\le
2\log(6)(
\mathrm{Pdim}(\mathcal{F}_1)
+
\mathrm{Pdim}(\mathcal{F}_2)
).
$$</span></p>

CC BY-SA 4.0
2023-12-20T10:25:12.823Z
Sorry about the boldface in the middle. No idea how it got there or how to get rid of it.
Aryeh
CC BY-SA 4.0
2023-12-20T11:27:45.350Z
Thanks for your great answer! This is a very clear and concise result!
Recursion
CC BY-SA 4.0
2023-12-20T10:23:14.713Z
2024-01-03T07:23:16.817Z
2024-01-03T07:23:16.817Z
Aryeh
<p>Not at all. Just imagine that <span class="math-container">$f(x)&gt;0$</span> for all <span class="math-container">$f$</span> and <span class="math-container">$x$</span>. The differences <span class="math-container">$f(x_1)-f(x_2)$</span> can look arbitrarily horrendous.</p>

CC BY-SA 4.0
2023-12-20T06:18:04.183Z
Thanks for your answer. This is what I was thinking about, but I can't construct a counterexample.
Recursion
CC BY-SA 4.0
2023-12-20T09:05:28.850Z
I don't think this is quite a counterexample. You are allowed a different threshold $t_i$ at each shattered point $x_i$. Thus, for example, the class of all increasing functions on $[0,1]$ s.t. $f(0)=0$ have infinite Pdim.
Aryeh
CC BY-SA 4.0
2023-12-20T09:41:37.157Z
@Aryeh After your edit, the question starts to make sense. I still don't see why increasing functions would have infinite Pdim. From a set $\{a,b\}$ with $a<b$, how can you cut out only $a$?
domotorp
CC BY-SA 4.0
2023-12-20T09:50:55.503Z
It's essentially the VCdim of the collection of the induced epigraph sets. So step functions with many steps will have an epigraph with large VC-dim.
Aryeh
CC BY-SA 4.0
2023-12-19T21:59:21.413Z
2023-12-19T21:59:21.413Z
domotorp
<p>Let <span class="math-container">$\mathcal{F}\subseteq \left\{f:\mathbb{R}^d\to\mathbb{R}\right\}$</span> be a family of functions with bounded pseudo-dimension <span class="math-container">$\text{Pdim}(\mathcal{F})\le N$</span>, i.e., the VC-dimension <span class="math-container">$\text{VCdim}(\left\{\text{sgn}(f(x)-r)|f\in\mathcal{F}\right\})\le N$</span>. We can assume that functions in <span class="math-container">$\mathcal{F}$</span> satisfy some good properties, such as Lipschitzness and smoothness.</p>
<p>Let <span class="math-container">$\mathcal{F}^\prime$</span> be a linear combination of <span class="math-container">$f\in\mathcal{F}$</span> with different inputs, e.g., <span class="math-container">$\mathcal{F}^\prime=\left\{f^\prime|f^\prime(x_1,x_2)=f(x_1)-f(x_2),f\in\mathcal{F}\right\})$</span>. Is it possible to obtain an upper bound of the pseudo-dimension <span class="math-container">$\text{Pdim}(\mathcal{F}^\prime)$</span> of such <span class="math-container">$\mathcal{F}^\prime$</span>?</p>
<p>Edit (Aryeh): To clarify, the Pdim of a set of real-valued functions <span class="math-container">$\mathcal{F}$</span> acting on <span class="math-container">$\mathcal{X}$</span> is defined as the VCdim of the following set of <span class="math-container">$\{0,1\}$</span>-valued functions acting on <span class="math-container">$\mathcal{X}\times\mathbb{R}$</span>:
<span class="math-container">$$
\{
(x,t)\mapsto 1_{f(x)&gt;t}; f\in\mathcal{F}
\}.
$$</span></p>

CC BY-SA 4.0
2023-12-19T20:14:44.227Z
The definition of Pdim needed some refinement; edited.
Aryeh
CC BY-SA 4.0
2023-12-19T20:16:32.677Z
Also, are you sure you want $f(x_1)-f(x_2)$ and not $f_1(x_1)-f_2(x_2)$ ranging over $f_1,f_2\in\mathcal{F}$ ?
Aryeh
CC BY-SA 4.0
2023-12-20T05:54:00.327Z
Yes. I am considering $f(x_1)-f(x_2)$, not $f_1(x_1)-f_2(x_2)$.
Recursion
<lg.learning><vc-dimension>
An upper bound of pseudo-/VC-dimension
Recursion
# An upper bound of pseudo-/VC-dimension

(Asked by: username_0 on 2023-12-19)

Let $\mathcal{F}\subseteq \left\{f:\mathbb{R}^d\to\mathbb{R}\right\}$ be a family of functions with bounded pseudo-dimension $\text{Pdim}(\mathcal{F})\le N$, i.e., the VC-dimension $\text{VCdim}(\left\{\text{sgn}(f(x)-r)|f\in\mathcal{F}\right\})\le N$. We can assume that functions in $\mathcal{F}$ satisfy some good properties, such as Lipschitzness and smoothness.

Let $\mathcal{F}^\prime$ be a linear combination of $f\in\mathcal{F}$ with different inputs, e.g., $\mathcal{F}^\prime=\left\{f^\prime|f^\prime(x\_1,x\_2)=f(x\_1)-f(x\_2),f\in\mathcal{F}\right\})$. Is it possible to obtain an upper bound of the pseudo-dimension $\text{Pdim}(\mathcal{F}^\prime)$ of such $\mathcal{F}^\prime$?

Edit (username_1): To clarify, the Pdim of a set of real-valued functions $\mathcal{F}$ acting on $\mathcal{X}$ is defined as the VCdim of the following set of $\{0,1\}$-valued functions acting on $\mathcal{X}\times\mathbb{R}$:
$$
\{
(x,t)\mapsto 1\_{f(x)>t}; f\in\mathcal{F}
\}.
$$

**Tags:** lg.learning, vc-dimension

> **Comments:**
> **username_1**: The definition of Pdim needed some refinement; edited.  
> **username_1**: Also, are you sure you want $f(x_1)-f(x_2)$ and not $f_1(x_1)-f_2(x_2)$ ranging over $f_1,f_2\in\mathcal{F}$ ?  
> **username_0**: Yes. I am considering $f(x_1)-f(x_2)$, not $f_1(x_1)-f_2(x_2)$.  

---

## 2 answers

### Answer by username_1 on 2023-12-20. Score: 1 | Accepted answer

Consider two real-valued function classes,
$\mathcal{F}\_1$ acting on some set $\mathcal{X}\_1$
and
$\mathcal{F}\_2$ acting on some set $\mathcal{X}\_2$.
I am going to bound the Pdim of
$\mathcal{F}\_3$
acting on
$\mathcal{X}\_1\times \mathcal{X}\_2$
given by
$$
\mathcal{F}\_3=\{
(x\_1,x\_2)\mapsto f\_1(x\_1)-f\_2(x\_2);
f\_1\in \mathcal{F}\_1,
f\_2\in \mathcal{F}\_2
\}.
$$
Since obviously $\mathcal{F}\_3\supseteq \mathcal{F}'$,
this also upper-bounds the Pdim of $\mathcal{F}'$.

By definition,
$$
\mathrm{Pdim}(\mathcal{F}\_3)
=
\mathrm{VCdim}(\{
(x\_1,x\_2,t)\mapsto 1\_{f\_1(x\_1)-f\_2(x\_2)>t}
;
f\_1\in \mathcal{F}\_1,
f\_2\in \mathcal{F}\_2
\}).
$$
Now we use the basic fact that
$$a+b>t \implies
\exists t\_1,t\_2: a>t\_1, b>t\_2
$$
to conclude
$$
\mathrm{Pdim}(\mathcal{F}\_3)
\le
\mathrm{VCdim}(\{
(x\_1,x\_2,t\_1,t\_2)\mapsto
1\_{f\_1(x\_1)>t\_1}\cdot
1\_{-f\_2(x\_2)>t\_2}
;
f\_1\in \mathcal{F}\_1,
f\_2\in \mathcal{F}\_2
\}).
$$

The question has now been reduced to a more basic one:
If $\mathcal{H}\_1, \mathcal{H}\_2$
are Boolean function classes acting on
$\mathcal{X}\_1, \mathcal{X}\_2$, resp.,
how can we control the VCdim of
$\mathcal{H}\_3$ acting on
$\mathcal{X}\_1\times \mathcal{X}\_2$
given by
$$
\mathcal{H}\_3
=
\{
(x\_1,x\_2)\mapsto h\_1(x\_1)h\_2(x\_2);
h\_1\in \mathcal{H}\_1,
h\_2\in \mathcal{H}\_2
\}
$$
in terms of the VCdim of
$\mathcal{H}\_1, \mathcal{H}\_2$?

Clearly, on any sequence
$(x\_1,y\_1),\ldots,(x\_n,y\_n)$,
the number of behaviors achieved by
$\mathcal{H}\_3$—formally, the cardinality of the
projection/restriction of
$\mathcal{H}\_3$
this set, denoted by
$\mathcal{H}\_3[(x\_1,y\_1),\ldots,(x\_n,y\_n)]$—is upper-bounded by
$\mathcal{H}\_1[x\_1,\ldots,x\_n]
\cdot
\mathcal{H}\_2[y\_1,\ldots,y\_n]
$.
If $d\_1,d\_2$ are the VCdims of
$\mathcal{H}\_1, \mathcal{H}\_2$, resp,
then Sauer's lemma implies
$$
\mathcal{H}\_3[(x\_1,y\_1),\ldots,(x\_n,y\_n)]
\le
\mathcal{H}\_1[x\_1,\ldots,x\_n]
\cdot
\mathcal{H}\_2[y\_1,\ldots,y\_n]
\le
\left(
\frac{e n}{d\_1}
\right)^{d\_1}
\cdot
\left(
\frac{e n}{d\_2}
\right)^{d\_2}
\le
\left(
\frac{2 e n}{d\_1+d\_2}
\right)^{d\_1+d\_2}
,
$$
where the last inequality is contained in the proof of
Lemma 16 in
<https://www.jmlr.org/papers/v23/20-1353.html>
It further follows from that lemma (taking $k=2$)
that
$$
\mathrm{VCdim}(\mathcal{H}\_3)
\le
2\log(6)(d\_1+d\_2).
$$
The only remaining piece is the trivial observation that
$
\mathrm{Pdim}(\mathcal{F})=
\mathrm{Pdim}(-\mathcal{F})
$.

It follows that
$$
\mathrm{Pdim}(\mathcal{F}\_3)
\le
2\log(6)(
\mathrm{Pdim}(\mathcal{F}\_1)
+
\mathrm{Pdim}(\mathcal{F}\_2)
).
$$

> **Comments:**
> **username_1**: Sorry about the boldface in the middle. No idea how it got there or how to get rid of it.  
> **username_0**: Thanks for your great answer! This is a very clear and concise result!  

---

### Answer by username_2 on 2023-12-19. Score: 0

Not at all. Just imagine that $f(x)>0$ for all $f$ and $x$. The differences $f(x\_1)-f(x\_2)$ can look arbitrarily horrendous.

> **Comments:**
> **username_0**: Thanks for your answer. This is what I was thinking about, but I can't construct a counterexample.  
> **username_1**: I don't think this is quite a counterexample. You are allowed a different threshold $t_i$ at each shattered point $x_i$. Thus, for example, the class of all increasing functions on $[0,1]$ s.t. $f(0)=0$ have infinite Pdim.  
> **username_2**: @username_1 After your edit, the question starts to make sense. I still don't see why increasing functions would have infinite Pdim. From a set $\{a,b\}$ with $a<b$, how can you cut out only $a$?  
> **username_1**: It's essentially the VCdim of the collection of the induced epigraph sets. So step functions with many steps will have an epigraph with large VC-dim.  

---

