Information-theoretic Limits of Learning and Estimation

• URL: http://arxiv.org/abs/2605.06710v1
• Date: Wed, 06 May 2026 20:30:09 GMT
• Title: Information-theoretic Limits of Learning and Estimation
• Abstract summary: Information theory plays a central role in establishing fundamental limits on what any learning or estimation algorithm can -- and cannot -- achieve.<n>This manuscript contains preprint of a chapter under consideration for inclusion in the forthcoming third edition of Cover and Thomas's Elements of Information Theory.
• Score: 5.586191108738563
• License: http://creativecommons.org/licenses/by-nc-nd/4.0/
• 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. In this chapter, we provide an introduction to these connections. End-of-chapter exercises makes the material suitable for both classroom use and self-study. 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. This manuscript contains preprint of a chapter under consideration for inclusion in the forthcoming third edition of Cover and Thomas's Elements of Information Theory, posted with permission from Wiley. It would follow the chapter posted at arXiv:2605.02989 . The table of contents of the new edition can be found at: https://docs.google.com/document/d/1L-m4oQEJw1PJhoxBeMwrrBD8S_HmvzMEkPbYvS24980/edit?usp=sharing . For feedback, please contact abbas@ee.stanford.edu.

Related papers

• Information Theory and Statistical Learning [2.0305676256390934]
  Learning and information theory intersect in both model training and the characterization of fundamental performance limits.<n>The chapter focuses on the role of divergence measures in model training, with examples ranging from linear and logistic regression to autoregressive models.<n>The treatment of the generative diffusion model provides a more systematic and explicit derivation than is typical in the literature.
  arXiv  Detail & Related papers  (2026-05-04T16:52:14Z)
• Statistical Learning Theory in Lean 4: Empirical Processes from Scratch [57.00315741159824]
  We present the first comprehensive Lean 4 formalization of statistical learning theory (SLT) grounded in empirical process theory.<n>Our end-to-end formal infrastructure implement the missing contents in latest Lean 4 Mathlib library.<n>This work establishes a reusable formal foundation and opens the door for future developments in machine learning theory.
  arXiv  Detail & Related papers  (2026-02-02T16:24:53Z)
• On the Minimax Regret of Sequential Probability Assignment via Square-Root Entropy [70.10668953625247]
  We show that the minimax regret for the case of no side information can be upper bounded in terms of sequential square-root entropy.<n>For the problem of sequential probability assignment with side information, we develop both upper and lower bounds based on the aforementioned entropy.
  arXiv  Detail & Related papers  (2025-03-22T17:26:34Z)
• Minimum Description Length and Generalization Guarantees for Representation Learning [16.2444595840653]
  This paper presents a framework that allows us to derive upper bounds on the generalization error of a representation learning algorithm. Rather than the mutual information between the encoder's input and the representation, our new bounds involve the "multi-letter" relative entropy. To the best knowledge of the authors, the established generalization bounds are the first of their kind for Information Bottleneck (IB) type encoders and representation learning.
  arXiv  Detail & Related papers  (2024-02-05T18:12:28Z)
• Fat Shattering, Joint Measurability, and PAC Learnability of POVM Hypothesis Classes [8.594140167290098]
  We characterize learnability for quantum measurement classes by establishing matching necessary and sufficient conditions for their PAC learnability. We show that VC dimension generalization upper bounds in previous work are frequently infinite, even for finite-dimensional POVM classes. We show that every measurement class defined on a finite-dimensional Hilbert space is PAC learnable.
  arXiv  Detail & Related papers  (2023-08-21T18:38:24Z)
• Fast Rate Information-theoretic Bounds on Generalization Errors [8.102199960821165]
  The generalization error of a learning algorithm refers to the discrepancy between the loss of a learning algorithm on training data and that on unseen testing data.<n>Various information-theoretic bounds on the generalization error have been derived in the literature.<n>This paper investigates the tightness of these bounds, in terms of the dependence of their convergence rates on the sample size.
  arXiv  Detail & Related papers  (2023-03-26T08:59:05Z)
• Shannon theory beyond quantum: information content of a source [68.8204255655161]
  We extend the definition of information content to operational probabilistic theories. We prove relevant properties as the subadditivity, and the relation between purity and information content of a state.
  arXiv  Detail & Related papers  (2021-12-23T16:36:06Z)
• Geometry of Banach spaces: a new route towards Position Based Cryptography [65.51757376525798]
  We study Position Based Quantum Cryptography (PBQC) from the perspective of geometric functional analysis and its connections with quantum games. The main question we are interested in asks for the optimal amount of entanglement that a coalition of attackers have to share in order to compromise the security of any PBQC protocol. We show that the understanding of the type properties of some more involved Banach spaces would allow to drop out the assumptions and lead to unconditional lower bounds on the resources used to attack our protocol.
  arXiv  Detail & Related papers  (2021-03-30T13:55:11Z)
• Fundamental Limits and Tradeoffs in Invariant Representation Learning [99.2368462915979]
  Many machine learning applications involve learning representations that achieve two competing goals. Minimax game-theoretic formulation represents a fundamental tradeoff between accuracy and invariance. We provide an information-theoretic analysis of this general and important problem under both classification and regression settings.
  arXiv  Detail & Related papers  (2020-12-19T15:24:04Z)
• A Theory of Usable Information Under Computational Constraints [103.5901638681034]
  We propose a new framework for reasoning about information in complex systems. Our foundation is based on a variational extension of Shannon's information theory. We show that by incorporating computational constraints, $mathcalV$-information can be reliably estimated from data.
  arXiv  Detail & Related papers  (2020-02-25T06:09:30Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.