Agnostic Online Learning and Excellent Sets
This work addresses a foundational problem in model theory and combinatorics, specifically for researchers in these fields, by providing a significant improvement in bounds for stable regularity lemmas.
The paper tackles the problem of proving the existence of ε-excellent sets in k-edge stable graphs, improving the bound from ε < 1/2^{2^k} to ε < 1/2, using methods from online learning and model theory.
We use algorithmic methods from online learning to explore some important objects at the intersection of model theory and combinatorics, and find natural ways that algorithmic methods can detect and explain (and improve our understanding of) stable structure in the sense of model theory. The main theorem deals with existence of $ε$-excellent sets (which are key to the Stable Regularity Lemma, a theorem characterizing the appearance of irregular pairs in Szemerédi's celebrated Regularity Lemma). We prove that $ε$-excellent sets exist for any $ε< \frac{1}{2}$ in $k$-edge stable graphs in the sense of model theory (equivalently, Littlestone classes); earlier proofs had given this only for $ε< 1/{2^{2^k}}$ or so. We give two proofs: the first uses regret bounds from online learning, the second uses Boolean closure properties of Littlestone classes and sampling. We also give a version of the dynamic Sauer-Shelah-Perles lemma appropriate to this setting, related to definability of types. We conclude by characterizing stable/Littlestone classes as those supporting a certain abstract notion of majority: the proof shows that the two distinct, natural notions of majority, arising from measure and from dimension, densely often coincide.