Paperlane

no. 16 · Tuesday 17 November 2026

Information-theoretic Limits of Learning and Estimation

Abbas El Gamal and Maxim Raginsky

math.IT · v2

Abstract

Information theory plays a central role in establishing fundamental limits on what any learning or estimation algorithm can -- and cannot -- achieve, regardless of computational power. This draft provides an introduction to these connections. We begin by introducing concentration inequalities along with the notions of covering and packing in metric spaces, and the associated concept of metric entropy. These tools are essential for our analysis. We then introduce the learning-theoretic framework and derive upper bounds on generalization error in terms of metric entropy, Rademacher complexity, and the VC dimension, as well as mutual information and relative entropy. Finally we discuss the minimax estimation framework and establish lower bounds on minimax risk using Fano's inequality, yielding bounds in terms of relative entropy and covering and packing numbers. A significantly revised and augmented version of this manuscript will appear as two chapters in the forthcoming third edition of Cover and Thomas's Elements of Information Theory. For questions, please contact abbas@ee.stanford.edu.

fields
Information Theory, Statistics Theory
pdf ↗ page arXiv:2605.06710 ↗