# The unstable formula theorem revisited via algorithms

arXiv: https://arxiv.org/abs/2212.05050 · HTML: https://mlsanity.com/paper/2212.05050/

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- Builds on 7 of its 25 references that are in the map.
- First posted on arXiv 9 Dec 2022.

## Builds on (most cited first, 7 of 7)

- [Private PAC learning implies finite Littlestone dimension](https://mlsanity.com/paper/1806.00949/) (2018)
- [An Equivalence Between Private Classification and Online Prediction](https://mlsanity.com/paper/2003.00563/) (2020)
- [A Theory of Universal Learning](https://mlsanity.com/paper/2011.04483/) (2020)
- [Adversarial Laws of Large Numbers and Optimal Regret in Online Classification](https://mlsanity.com/paper/2101.09054/) (2021)
- [Sample-efficient proper PAC learning with approximate differential privacy](https://mlsanity.com/paper/2012.03893/) (2020)
- [A Limitation of the PAC-Bayes Framework](https://mlsanity.com/paper/2006.13508/) (2020)
- [Finite Littlestone Dimension Implies Finite Information Complexity](https://mlsanity.com/paper/2206.13257/) (2022)

## Built on by (most cited first, 4 of 4)

- [Borsuk-Ulam and Replicable Learning of Large-Margin Halfspaces](https://mlsanity.com/paper/2503.15294/) (2025)
- [Simplicial covering dimension of extremal concept classes](https://mlsanity.com/paper/2511.11819/) (2025)
- [Tight list replicability bounds via a novel sphere covering theorem](https://mlsanity.com/paper/2606.06148/) (2026)
- [Sign-Rank, Index, and List Replicability: Connections and Separations](https://mlsanity.com/paper/2606.18236/) (2026)

## Abstract (arXiv)

This paper is about the surprising interaction of a foundational result from model theory, about stability of theories, with algorithmic stability in learning. First, in response to gaps in existing learning models, we introduce a new statistical learning model, called ``Probably Eventually Correct'' or PEC. We characterize Littlestone (stable) classes in terms of this model. As a corollary, Littlestone classes have frequent short definitions in a natural statistical sense. In order to obtain a characterization of Littlestone classes in terms of frequent definitions, we build an equivalence theorem highlighting what is common to many existing approximation algorithms, and to the new PEC. This is guided by an analogy to definability of types in model theory, but has its own character. Drawing on these theorems and on other recent work, we present a complete algorithmic analogue of Shelah's celebrated Unstable Formula Theorem, with algorithmic properties taking the place of the infinite.