On Interactions of Vapnik-Chervonenkis and Littlestone Dimensions with Logic and Combinatorics

This thesis has five chapters. A longer overview of each will be given in Chapter 1. Chapter 2 consists of joint work with Adela DePavia and Erasmo Tani on Optimal Algorithms for Learning Partitions with Faulty Oracles [57]. Consider a learner seeking to fully recover a partition of a set with $n<\infty$ elements into $k$ groups ($k$ might be known or not to the learner), based on answers to oracle queries of the form "Are $u$ and $v$ in the same group?", for $u$, $v$ in the set. We define exact partition recovery problems with bounded tolerance for faulty oracle answers, false positives, false negatives, or a weighted combination of both. We designed optimal algorithms for this task and proved they achieve optimal query complexity. We discuss the asymmetry between false negative robustness, and false positive robustness. Chapter 3 consists of joint work with Maryanthe Malliaris and Shay Moran, on Epsilon-saturation for stable graphs and Littlestone classes [104]. We introduce the concept of the $\epsilon$-saturation of a (bi)graph, which is obtained by taking the union closure after inductively adding virtual elements, determined by pointwise weighted $\epsilon$-majorities (cf. good and excellent sets from the Stable Regularity Lemma [107]). In the Littlestone class case, we characterize this closure as the smallest $\epsilon$-saturated class containing the initial one. We show the following, for a class $\mathcal{H}$ of Littlestone dimension $\ell$ and Vapnik-Chervonenkis dimension $d$: if $\epsilon<1/(\ell+1)$, then $Ldim_{\infty}(\mathcal{H})=Ldim(\mathcal{H}(\epsilon)) = \ell$; if $\epsilon<1/(d+1)$, then $VC(\mathcal{H}_{\infty}(\epsilon)) = VC(\mathcal{H}(\epsilon)) = d$; but if $\epsilon\geq1/(d+1)$, then $VC(\mathcal{H}_{\infty}(\epsilon))$, and thus $Ldim(\mathcal{H}_{\infty}(\epsilon))$ may go to infinity; if $\epsilon\in[1/(Cd),1/(d+1)]$ for a numerical constant $C\approx 27.7259$, then $Ldim(\mathcal{H}_{\infty}(\epsilon))$, though it may change. We show some analogous results on the case of $\epsilon$-saturation of stable graphs. Chapter 4 consists of Local Combinatorial analogues for bounded VC dimension. From the work of Malliaris and Shelah in [107], and Malliaris and Moran in [105], a class is Littlestone if and only if within any $A\subseteq X$, there exists $A'\subseteq A$ of size at least $c_{1}|A|$ that is $\epsilon$-good. In analogy to this, we characterize the property of bounded $VC$ by the existence of so-called symmetric $\epsilon$-good pairs. We prove this in three ways: first, we use combinatorial techniques including Pigeonhole Principle; second, we apply Haussler's Packing Lemma (see Haussler [86]); last, we apply the VC Regularity Lemma, (see [101, 16, 68]). Chapter 5 states and explores open questions and further research directions.