# A Direct Sum Result for the Information Complexity of Learning

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

## Key facts

- Cited by 6 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 16 Apr 2018.

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

- [User-friendly introduction to PAC-Bayes bounds](https://mlsanity.com/paper/2110.11216/) (2021)
- [PAC-Bayes, MAC-Bayes and Conditional Mutual Information: Fast rate bounds that handle general VC classes](https://mlsanity.com/paper/2106.09683/) (2021)
- [Towards a Unified Information-Theoretic Framework for Generalization](https://mlsanity.com/paper/2111.05275/) (2021)
- [Understanding Generalization via Leave-One-Out Conditional Mutual Information](https://mlsanity.com/paper/2206.14800/) (2022)
- [Information Complexity of Stochastic Convex Optimization: Applications to Generalization and Memorization](https://mlsanity.com/paper/2402.09327/) (2024)
- [Trade-offs in Data Memorization via Strong Data Processing Inequalities](https://mlsanity.com/paper/2506.01855/) (2025)

## Abstract (arXiv)

How many bits of information are required to PAC learn a class of hypotheses of VC dimension d? The mathematical setting we follow is that of Bassily et al. (2018), where the value of interest is the mutual information I(S;A(S)) between the input sample S and the hypothesis outputted by the learning algorithm A. We introduce a class of functions of VC dimension d over the domain X with information complexity at least Omegaleft(dlog log frac|X|dright) bits for any consistent and proper algorithm (deterministic or random). Bassily et al. proved a similar (but quantitatively weaker) result for the case d=1. The above result is in fact a special case of a more general phenomenon we explore. We define the notion of information complexity of a given class of functions H. Intuitively, it is the minimum amount of information that an algorithm for H must retain about its input to ensure consistency and properness. We prove a direct sum result for information complexity in this context; roughly speaking, the information complexity sums when combining several classes.