3
$\begingroup$

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

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

2 Answers 2

1
$\begingroup$

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

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

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.

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

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.