# An upper bound of pseudo-/VC-dimension

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

• The definition of Pdim needed some refinement; edited. Dec 19, 2023 at 20:14
• 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}$ ? Dec 19, 2023 at 20:16
• Yes. I am considering $f(x_1)-f(x_2)$, not $f_1(x_1)-f_2(x_2)$. Dec 20, 2023 at 5:54

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

• Sorry about the boldface in the middle. No idea how it got there or how to get rid of it. Dec 20, 2023 at 10:25
• Thanks for your great answer! This is a very clear and concise result! Dec 20, 2023 at 11:27

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.

• Thanks for your answer. This is what I was thinking about, but I can't construct a counterexample. Dec 20, 2023 at 6:18
• 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. Dec 20, 2023 at 9:05
• @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$? Dec 20, 2023 at 9:41
• 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. Dec 20, 2023 at 9:50