8
$\begingroup$

Consider an "ambiguous" function class $F^\star\subseteq\{0,1,\star\}^X$ (i.e., $F$ consists of Boolean functions acting on a set $X$ with some missing values, indicated by $\star$). We say that $F^\star$ shatters a set $S\subseteq X$ if $F^\star(S)\supseteq\{0,1\}^S$. Define $VC(F^\star)$ as the maximal size of any shattered set (possibly, $\infty$).

We say that $\bar f\in\{0,1\}^X$ is a disambiguation of $f^\star\in F^\star$ if the two functions agree on $x\in X$ whenever $f^\star(x)\neq\star$. We say that $\bar F\subseteq\{0,1\}^X$ is a disambiguation of $F^\star$ if each $\bar f\in \bar F$ is a disambiguation of some $f^\star\in F^\star$ and every $f^\star\in F^\star$ has a disambiguated representative $\bar f\in \bar F$.

Conjecture: There is a universal constant $c$ such that for any ambiguous $F^\star$ there is a disambiguation $\bar F$ such that $$ VC(\bar F) \le c VC(F^\star) .$$

Note: This open problem was posed here: https://arxiv.org/abs/1810.02180 . It is known that $c$ must be $>1$, and Lemma 6.2 therein provides an analog of Sauer's lemma for $F^\star$.

Improve this question
$\endgroup$
4
  • 1
    $\begingroup$ Do you have some weaker bound, like $VC(F^\star) \le 2^{VC(\bar F)}$? $\endgroup$
    – domotorp
    Commented Dec 2, 2020 at 19:45
  • $\begingroup$ No, and that would be interesting also. $\endgroup$
    – Aryeh Kontorovich
    Commented Dec 2, 2020 at 20:07
  • 1
    $\begingroup$ This has been disproved in Theorem 11 of arxiv.org/abs/2107.08444. The proof is short and elegant (building on recent deep results of others'). $\endgroup$
    – domotorp
    Commented Jul 20, 2021 at 8:14
  • $\begingroup$ Indeed. Feel free to turn into an answer, I'll accept. $\endgroup$
    – Aryeh Kontorovich
    Commented Jul 20, 2021 at 9:45

1 Answer 1

Reset to default
5
$\begingroup$

This has been disproved in Theorem 11 of Alon, Hanneke, Holzman, and Moran. The proof is short and elegant (building on recent deep results of others').

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .