mlsanityData to 14 Oct 2026

Finite Littlestone Dimension Implies Finite Information Complexity

arXiv 2206.13257 ↗First posted 27 Jun 2022cs.LG cs.IT math.ITcited by 7

Not on the map. Why?

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.

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

10 of 20 references.

References · 10

  1. 2017Information-theoretic analysis of generalization capability of learning algorithmscited by 303
  2. 2020Reasoning About Generalization via Conditional Mutual Informationcited by 147
  3. 2019Tightening Mutual Information Based Bounds on Generalization Errorcited by 117
  4. 2015How much does your data exploration overfit? Controlling bias via information usagecited by 95
  5. 2018Private PAC learning implies finite Littlestone dimensioncited by 74
  6. 2020An Equivalence Between Private Classification and Online Predictioncited by 64
  7. 2019Generalization Error Bounds Via R'enyi-, f-Divergences and Maximal Leakagecited by 48
  8. 2020Sample-efficient proper PAC learning with approximate differential privacycited by 29
  9. 2020A Limitation of the PAC-Bayes Frameworkcited by 25
  10. 2021Information Complexity and Generalization Boundscited by 14

Built on by

Cited by year

Citing papers per year: 2022: 2; 2023: 4; 2024: 0; 2025: 1.

7 papers.

  1. 2022Limitations of Information-Theoretic Generalization Bounds for Gradient Descent Methods in Stochastic Convex Optimizationcited by 19
  2. 2023Information Theoretic Lower Bounds for Information Theoretic Upper Boundscited by 17
  3. 2023The Bayesian Stability Zoocited by 13
  4. 2023A Unified Characterization of Private Learnability via Graph Theorycited by 5
  5. 2023Simple online learning with consistent oraclecited by 5
  6. 2022The unstable formula theorem revisited via algorithmscited by 4
  7. 2025Private List Learnability vs. Online List Learnabilitycited by 2