1
$\begingroup$

Let $X$ be a measurable space and let $P$ be a probability distribution on $X \times \{\pm 1\}$. Let $F$ be a function class on $X$, i.e., a collection of (measurable) functions from $X$ to $\mathbb R$. Fix $\alpha \in \mathbb R$ and $\beta > 0$, and cobsider a derived function class on $H := \{\ell_f \mid f \in F\}$ on $X \times \{\pm 1\}$, where for each $f \in F$, the new function $\ell_f:X \times \{\pm 1\} \to \{0,1\}$ is defined by $$ \ell_f(x,y) = \begin{cases} 1,&\mbox{ if }|yf(x)-\alpha| \ge \beta,\\ 0,&\mbox{ otherwise.} \end{cases} $$

Question. What is the a good upper-bound on VC-dimension of $H$ in terms of some complexity measure associated with $F$ (e.g., Rademacher complexity of $F$, VC-dimension of $\mathrm{subgraph}(F) := \{A_f \mid f \in F\}$, where $A_f := \{x \in X \mid f(x) \le 0\}$, etc.) ?

I'm particularly interested in the case where $X=$ euclidean $\mathbb R^d$ (or unit-sphere in $\mathbb R^d$) and $F$ is the collection of functions $f:\mathbb R^d \to \mathbb R$ of the form $f(x) \equiv x^\top w + c$, for some $b \in \mathbb R$ and unit vector $w \in \mathbb R^d$.

Related: Rademacher complexity of function class $\{(x,y) \mapsto 1[|yf(x)-\alpha| \ge \beta]$ in terms of $\alpha$, $\beta$, and Rademacher complexity of $F$

$\endgroup$

1 Answer 1

0
$\begingroup$

Consider the "loss function" $\ell_t:\mathbb R^2 \to \{0,1\}$ defined by $\phi_t(y,y') := 1_{yy' \le t}$, and let consider the function class on $X \times \{\pm 1\}$ given by $$ S_t(F):= \ell_t \circ (Id,F) = \{(x,y) \mapsto \ell_t(y,f(x)) \mid f \in F\}. $$

Since $|yf(x)-\alpha| \ge \beta$ iff $yf(x)\le \alpha-\beta$ or $-yf(x) \le -\alpha-\beta$, it is clear that

$$ H = S_{\alpha-\beta}(F) \lor S_{-\alpha-\beta}(-F), $$

where where $-F := \{-f \mid f \in F\}$. and $A \widetilde{\cup} B := \{a \lor b \mid a \in A,\, b \in B\}$.

Thus, thanks to van der Vaart and Wellner, Lemma 2.6.17, we deduce that

\begin{equation} \begin{split} \mathrm{VCdim}(H) &\le \mathrm{VCdim}(S_{\alpha-\beta}(F)) + \mathrm{VCdim}(S_{-\alpha-\beta}(-F))\\ &= \mathrm{VCdim}(S_{\alpha-\beta}(F)) + \mathrm{VCdim}(S_{\alpha+\beta}(F))\\ &\le 2\cdot \mathrm{VCdim}(S_{\alpha-\beta}(F)). \end{split} \tag{1} \end{equation}

Finally, because for $t \in \mathbb R$, the loss function $\ell_t$ is monotone in the second (in fact, in both!) arguments, we know that $\mathrm{VCdim}(S_t(F)) \le \mathrm{SG}(F)$, where $$ \mathrm{SG}(F) := \{\{x \in X \mid f(x) \le 0\} \mid f \in F\} $$ is the subgraph of $F$. Combining with (1) then gives

$$ \mathrm{VCdim}(H) \le 2\cdot\mathrm{VCdim}(\mathrm{SG}(F)), $$

In particular, we deduce that for the half-space function class $F_{\mathrm{lin}}$ on $\mathbb R^d$, then

$$ \mathrm{VCdim}(H_{\alpha-\beta}(F_{\mathrm{lin}})) \le 2\cdot \mathrm{VCdim}(\mathrm{SG}(F_{\mathrm{lin}})) = 2d. $$

$\endgroup$
2
  • 1
    $\begingroup$ It is not true in general that $VC(A\vee B)\leq VC(A)+VC(B)$. The cited result in van der Vaart and Wellner proves that the VC-density of $A\vee B$ is at most the sum of the VC-densities of $A$ and $B$ (which then implies $VC(A\vee B)$ is finite whenever $VC(A)$ and $VC(B)$ are). From the proof of this one can obtain (e.g.) $VC(A\vee B)< 10\max\{VC(A),VC(B)\}$. $\endgroup$ Commented Jan 8 at 21:25
  • $\begingroup$ Thanks for the input. OK, that's quite subtle. I'll take a look at the precise statement of the cited result asap. In any case, using what you're saying would give $\mathrm{VC}(H) \le Cd = O(d)$, with $C=10$. This is still sufficient for my purposes. Will come back to this asap. $\endgroup$
    – dohmatob
    Commented Jan 8 at 22:31

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.