# Finite Littlestone Dimension Implies Finite Information Complexity

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

## Key facts

- Cited by 7 papers in the map (data through 14 Oct 2026).
- Builds on 10 of its 20 references that are in the map.
- First posted on arXiv 27 Jun 2022.

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

- [Information-theoretic analysis of generalization capability of learning algorithms](https://mlsanity.com/paper/1705.07809/) (2017)
- [Reasoning About Generalization via Conditional Mutual Information](https://mlsanity.com/paper/2001.09122/) (2020)
- [Tightening Mutual Information Based Bounds on Generalization Error](https://mlsanity.com/paper/1901.04609/) (2019)
- [How much does your data exploration overfit? Controlling bias via information usage](https://mlsanity.com/paper/1511.05219/) (2015)
- [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)
- [Generalization Error Bounds Via R'enyi-, f-Divergences and Maximal Leakage](https://mlsanity.com/paper/1912.01439/) (2019)
- [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)
- [Information Complexity and Generalization Bounds](https://mlsanity.com/paper/2105.01747/) (2021)

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

- [Limitations of Information-Theoretic Generalization Bounds for Gradient Descent Methods in Stochastic Convex Optimization](https://mlsanity.com/paper/2212.13556/) (2022)
- [Information Theoretic Lower Bounds for Information Theoretic Upper Bounds](https://mlsanity.com/paper/2302.04925/) (2023)
- [The Bayesian Stability Zoo](https://mlsanity.com/paper/2310.18428/) (2023)
- [A Unified Characterization of Private Learnability via Graph Theory](https://mlsanity.com/paper/2304.03996/) (2023)
- [Simple online learning with consistent oracle](https://mlsanity.com/paper/2308.08055/) (2023)
- [The unstable formula theorem revisited via algorithms](https://mlsanity.com/paper/2212.05050/) (2022)
- [Private List Learnability vs. Online List Learnability](https://mlsanity.com/paper/2506.12856/) (2025)

## Abstract (arXiv)

We prove that every online learnable class of functions of Littlestone dimension d admits a learning algorithm with finite information complexity. Towards this end, we use the notion of a globally stable algorithm. Generally, the information complexity of such a globally stable algorithm is large yet finite, roughly exponential in d. We also show there is room for improvement; for a canonical online learnable class, indicator functions of affine subspaces of dimension d, the information complexity can be upper bounded logarithmically in d.