An upper bound of pseudo-/VC-dimension

Question

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 (Aryeh): 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} \}. $$

Answer 1

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

Answer 2

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.