Information-Theoretic Lower Bounds

Overview

This field studies fundamental limits on how accurately or efficiently algorithms can learn, estimate, predict, or make decisions from limited information. Researchers derive lower bounds using tools such as Fano’s and Le Cam’s inequalities, KL divergence, mutual information, and hard-instance constructions, often comparing them with algorithms’ upper bounds. Common settings include bandit regret and sample complexity, quantum-state tomography, differentially private learning, compressed sensing, and communication-constrained optimization. Matching upper and lower bounds are known in many precisely defined models, while a continuing challenge is understanding how adaptivity, feedback, computational restrictions, and structural assumptions change the limits.

Latest papers

92 papers10 papers in the last four weeks, down 52% on the four weeks before. 0.1% of all new papers.

Feb 16, 2026

On the Rate-Distortion-Complexity Tradeoff for Semantic Communication

Semantic communication is a novel communication paradigm that focuses on conveying the user's intended meaning rather than the bit-wise transmission of source signals. One of the key challenges is to effectively represent and extract the semantic meaning of any given source signals. While deep learning (DL)-based solutions have shown promising results in extracting implicit semantic information from a wide range of sources, existing work often overlooks the high computational complexity inherent in both model training and inference for the DL-based encoder and decoder. To bridge this gap, this paper proposes a rate-distortion-complexity (RDC) framework which extends the classical rate-distortion theory by incorporating the constraints on semantic distance, including both the traditional bit-wise distortion metric and statistical difference-based divergence metric, and complexity measure, adopted from the theory of minimum description length and information bottleneck. We derive the closed-form theoretical results of the minimum achievable rate under given constraints on semantic distance and complexity for both Gaussian and binary semantic sources. Our theoretical results show a fundamental three-way tradeoff among achievable rate, semantic distance, and model complexity. Extensive experiments on real-world image and video datasets validate this tradeoff and further demonstrate that our information-theoretic complexity measure effectively correlates with practical computational costs, guiding efficient system design in resource-constrained scenarios.
Feb 13, 2026

Calculating Mutual Information between a Reward Maximizer and its Environment

An important question in the field of AI is the extent to which successful behaviour requires an internal representation of the world. In this work, we quantify the amount of information an optimal policy provides about the underlying environment. We consider a Controlled Markov Process (CMP) with nn states and mm actions, assuming a uniform prior over the space of possible transition dynamics. We prove that observing a deterministic policy that is optimal for any non-constant reward function then conveys exactly nlog⁡mn \log m bits of information about the environment. Specifically, we show that the mutual information between the environment and the optimal policy is nlog⁡mn \log m bits. This bound holds across a broad class of objectives, including finite-horizon, infinite-horizon discounted, and time-averaged reward maximization. These findings provide a precise information-theoretic lower bound on the ``implicit world model'' necessary for optimality.