Information-theoretic Limits of Learning and Estimation

2026-05-06 · Abbas El Gamal, Maxim Raginsky arxiv

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.

📄 PDF Abstract BibTeX arXiv:2605.06710

Code (0)

등록된 구현이 없습니다.

Information-theoretic limits of a multiview low-rank symmetric spiked matrix model

2020-05-16 · Jean Barbier, Galen Reeves

We consider a generalization of an important class of high-dimensional inference problems, namely spiked symmetric matrix models, often used as probabilistic models for principal component analysis. Such paradigmatic mod…

A Renderer-Enabled Framework for Computing Parameter Estimation Lower Bounds in Plenoptic Imaging Systems

2026-01-30 · Abhinav V. Sambasivan, Liam J. Coulter, Richard G. Paxman, Jarvis D. Haupt arxiv

This work focuses on assessing the information-theoretic limits of scene parameter estimation in plenoptic imaging systems. A general framework to compute lower bounds on the parameter estimation error from noisy plenopt…

Object Localization

On the Structural Limits of Machine Learning Decision Systems: An Information-Theoretic, Interaction-Based, and Stochastic-Dynamical Perspective

2026-08-13 · Nestor R. Barraza, Gabriel Pena arxiv

Machine learning procedures are commonly evaluated in terms of predictive accuracy and computational efficiency. However, their achievable performance is fundamentally constrained by structural properties of the underlyi…

Computational Efficiency

Tensor SVD: Statistical and Computational Limits

2017-03-08 · Anru Zhang, Dong Xia

In this paper, we propose a general framework for tensor singular value decomposition (tensor SVD), which focuses on the methodology and theory for extracting the hidden low-rank structure from high-dimensional tensor da…

Fundamental MMSE-Rate Performance Limits of Integrated Sensing and Communication Systems

2025-01-02 · Zijie Wang, Xudong Wang

Integrated sensing and communication (ISAC) demonstrates promise for 6G networks; yet its performance limits, which require addressing functional Pareto stochastic optimizations, remain underexplored. Existing works eith…

Integrated sensing and communication ISAC