# Average-Case Information Complexity of Learning

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

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 25 Nov 2018.

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

- [Towards a Unified Information-Theoretic Framework for Generalization](https://mlsanity.com/paper/2111.05275/) (2021)
- [Information Complexity and Generalization Bounds](https://mlsanity.com/paper/2105.01747/) (2021)
- [Information bottleneck theory of high-dimensional regression: relevancy, efficiency and optimality](https://mlsanity.com/paper/2208.03848/) (2022)
- [Information-Theoretic Analysis of Minimax Excess Risk](https://mlsanity.com/paper/2202.07537/) (2022)

## Abstract (arXiv)

How many bits of information are revealed by a learning algorithm for a concept class of VC-dimension d? Previous works have shown that even for d=1 the amount of information may be unbounded (tend to ∞ with the universe size). Can it be that all concepts in the class require leaking a large amount of information? We show that typically concepts do not require leakage. There exists a proper learning algorithm that reveals O(d) bits of information for most concepts in the class. This result is a special case of a more general phenomenon we explore. If there is a low information learner when the algorithm em knows the underlying distribution on inputs, then there is a learner that reveals little information on an average concept em without knowing the distribution on inputs.