Agnostic Online Learning and Excellent Sets

Stable graphs, or equivalently Littlestone classes, were characterized by existence of linear-sized "good" sets, a kind of strongly homogeneous set, in work of Malliaris-Shelah and Malliaris-Moran. We prove a parallel result for VC classes, showing these are characterized by existence of linear-sized symmetric or asymmetric good pairs (which we define). We give several proofs, each drawing from methods and results from different areas, and resulting in different kinds of bounds. We finish with a few words on our learning theory motivation for these investigations and state some further research directions.

Paper

Similar papers

© 2026 NYSGPT2525 LLC