Information-Theoretic Lower Bounds

Ask about this topic

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

CardsList

83 papers18 papers in the last four weeks, up 20% on the four weeks before. 0.1% of all new papers.

May 6, 2026

Information-theoretic Limits of Learning and Estimation

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 [email protected].

Abbas El Gamal, Maxim Raginsky

Stanford University* · UIUC**

Information-Theoretic Generalization BoundsMinimax EstimationStatistical Learning TheoryInformation-Theoretic Lower BoundsGeneralization Bounds
AskPDF
May 6, 2026

The Impossibility Triangle of Long-Context Modeling

We identify and prove a fundamental trade-off governing long-sequence models: no model can simultaneously achieve (i) per-step computation independent of sequence length (Efficiency), (ii) state size independent of sequence length (Compactness), and (iii) the ability to recall a number of historical facts proportional to sequence length (Recall). We formalize this trade-off within an Online Sequence Processor abstraction that unifies Transformers, state space models, linear recurrent networks, and their hybrids. Using the Data Processing Inequality and Fano's Inequality, we prove that any model satisfying Efficiency and Compactness can recall at most O(poly(d)/log V) key-value pairs from a sequence of arbitrary length, where d is the model dimension and V is the vocabulary size. We classify 52 architectures published before March 2026 into the triangle, showing that each achieves at most two of the three properties and that hybrid architectures trace continuous trajectories in the interior. Experiments on synthetic associative recall tasks with five representative architectures validate the theoretical bound: empirical recall capacity lies strictly below the information-theoretic limit, and no architecture escapes the triangle.

Yan Zhou

School of Mathematics and Statistics Changsha University of Science and Technology Changsha, Hunan 410114, China

Long-Context ModelingAssociative MemorySequence ModelingInformation-Theoretic Lower Bounds
AskPDF
May 5, 2026

Provable Accuracy Collapse in Embedding-Based Representations under Dimensionality Mismatch

Embedding-based representations in Euclidean space Rd\mathbb{R}^d are a cornerstone of modern machine learning, where a major goal is to use the smallest dimension that faithfully captures data relations. In this work, we prove sharp dimension--accuracy tradeoffs and identify a fundamental information-theoretic limitation: unless the embedding dimension dd is chosen close to the ground-truth dimension DD, accuracy undergoes a sudden collapse. Our main result shows that this phenomenon arises even in standard contrastive learning settings, where supervision is limited to a set of mm anchor--positive--negative triplets (i,j,k)(i,j,k) encoding distance comparisons dist(i,j)<dist(i,k)\mathrm{dist}(i,j) < \mathrm{dist}(i,k). Specifically, given triplets realizable by an unknown ground-truth embedding in DD dimensions, we prove that there exists constant c<1c < 1, such that \emph{every embedding of dimension at most cDcD violates half of the triplets}, yielding accuracy as low as a trivial one-dimensional solution that ignores the input. We complement our information-theoretic bounds with strong computational hardness results: under the Unique Games Conjecture, even if the given triplets are nearly realizable in D=1D=1 dimension, no polynomial-time algorithm -- regardless of its dimension -- can achieve accuracy above the trivial 50%50\% baseline.

Dionysis Arvanitakis, Vaggos Chatziafratis, Yiyuan Luo

Northwestern University, IL, USA · University of California

Intrinsic DimensionalityContrastive LearningDimensionality ReductionInformation-Theoretic Lower Bounds
AskPDF
May 4, 2026

The Causal Description Gap: Information-Theoretic Separations Across Pearl's Hierarchy

Pearl's causal hierarchy shows that observational, interventional, and counterfactual queries are qualitatively distinct. We ask a quantitative version of this question: how many additional bits are needed to specify higher-rung causal answers once lower-rung answers are known? We formalize this via query-class description length, the Kolmogorov complexity of the answers a structural causal model (SCM) gives to a class of queries, with system size given. Our main construction gives acyclic SCMs on nn binary variables whose common observational distribution has constant description length, while single-variable intervention answers can require Θ(n2)Θ(n^2) additional bits. For SCMs with independent noises, fixed finite gate-schema and noise libraries, and at most dd parents per variable, a degree-sensitive upper bound gives an observational-interventional gap of at most O(ndlog⁡(en/d)+nlog⁡n)O(nd\log(en/d)+n\log n). This makes the quadratic construction order-optimal in the dense regime and a rooted-tree construction order-optimal for bounded indegree. The quadratic separation persists under ε\varepsilon-accurate total-variation descriptions for every fixed ε<1/4\varepsilon<1/4. At the next rung, even knowing every hard-intervention distribution can leave a Θ(n)Θ(n) counterfactual description gap; a masked-parity construction extends this to Θ(n2)Θ(n^2). These separation rates hold in the worst case and with high probability under uniform hidden parameters. A general ambiguity-to-bits theorem and Shannon analogue, together with explicit encodings, show that the gaps in our constructions equal the logarithm of residual higher-rung ambiguity up to lower-order terms.

Seyed Morteza Emadi

Kenan-Flagler Business School, University of North Carolina at Chapel Hill

Structural Causal ModelsCausal InferenceCounterfactual ReasoningInformation-Theoretic Lower BoundsKolmogorov Complexity
AskPDF
May 2, 2026

Mean Testing under Truncation beyond Gaussian

We characterize the fundamental limits of high-dimensional mean testing under arbitrary truncation, where samples are drawn from the conditional distribution P(⋅∣S)P(\cdot \mid S) for an unknown truncation set SS that may hide up to an ε\varepsilon-fraction of the probability mass. For distributions with pp-th directional moments of magnitude at most νP,pν_{P,p}, truncation induces a bias of order O(νP,pε1−1/p)O(ν_{P,p}\varepsilon^{1-1/p}). This bias creates a sharp information-theoretic detectability floor: when the signal αα falls below this threshold, the null and alternative hypotheses are indistinguishable even with infinite data. Above this floor, we prove that a simple second-order test achieving near-optimal sample complexity n=O ⁣(∥ΣP∥(α−4νP,pε1−1/p)2d)n = O\!\left(\frac{\|Σ_P\|}{(α-4ν_{P,p}\varepsilon^{1-1/p})^2}\sqrt{d}\right). We further identify a structural escape from this finite-moment bias barrier. Under a directional median regularity assumption, truncation bias improves to linear order O(ε)O(\varepsilon). This reveals an intermediate regime in which estimation requires Θ(d)Θ(d) samples for uniform recovery, while testing recovers the classical Θ(d)Θ(\sqrt d) rate once truncation bias is eliminated. Together, our results provide a unified framework for mean testing under truncation, connecting finite-moment, sub-Gaussian, and median-regular structural regimes.

Yuhao Wang, Roberto Imbuzeiro Oliveira, Themis Gouleakis

Amazon · IMPA, Rio de Janeiro, RJ, Brazil · Nanyang Technological University

Sample ComplexityInformation-Theoretic Lower BoundsStatistical Hypothesis Testing
AskPDF
Apr 24, 2026

The Exact Replica Threshold for Nonlinear Moments of Quantum States

Joint measurements on multiple copies of a quantum state provide access to nonlinear observables such as tr⁡(ρt)\operatorname{tr}(ρ^t), but whether replica number marks a sharp information-theoretic resource boundary has remained unclear. For every fixed order t≥3t\ge 3, existing protocols show that ⌈t/2⌉\lceil t/2\rceil replicas already suffice for polynomial-sample estimation of tr⁡(ρt)\operatorname{tr}(ρ^t), yet it has remained open whether one fewer replica must necessarily incur a sample-complexity barrier growing with the dimension. We prove that this is indeed the case in the sample/copy-access model with replica-limited joint measurements: any protocol restricted to ⌈t/2⌉−1\lceil t/2\rceil-1 replicas requires dimension-growing sample complexity, while ⌈t/2⌉\lceil t/2\rceil replicas suffice by prior work. Thus the exact replica threshold for fixed-order pure moments is ⌈t/2⌉\lceil t/2\rceil. Equivalently, for fixed-order pure moments, one additional coherent replica is not merely useful but marks the exact threshold between polynomial-sample estimation and a dimension-growing regime in the replica-limited model. We further show that the same threshold law extends to a broad family of observable-weighted moments tr⁡(Oρt)\operatorname{tr}(Oρ^t), including Pauli observables and other observables with bounded operator norm and macroscopic trace norm. Coherent replica number therefore acts as a genuinely discrete resource for nonlinear quantum-state estimation.

Shuai Zeng

School of Communication and Information Engineering, Chongqing University of Posts and Telecommunications, Chongqing 400065, P.R. China

Sample ComplexityInformation-Theoretic Lower Bounds
AskPDF
Apr 21, 2026

Watts-per-Intelligence Part II: Algorithmic Catalysis

We develop a thermodynamic theory of algorithmic catalysis within the watts per intelligence framework, identifying reusable computational structures that reduce irreversible operations for a task class while satisfying bounded restoration and structural selectivity constraints. We prove that any class specific speed-up is upper-bounded by the algorithmic mutual information between the substrate and the class descriptor, and that encoding this information incurs a minimum thermodynamic cost via Landauer erasure. Combining these results yields a coupling theorem that lower-bounds the deployment horizon required for an algorithmic catalyst to be energetically favourable. The framework is illustrated on an affine SAT class and situates contemporary learned systems within an information thermodynamic constraint on intelligent computation.

Elija Perrier

Centre for Quantum Software and Information, University of Technology Sydney, Australia.

Energy-Efficient MLInformation-Theoretic Lower Bounds
AskPDF
Apr 17, 2026

The Query Channel: Information-Theoretic Limits of Masking-Based Explanations

Masking-based post-hoc explanation methods, such as KernelSHAP and LIME, estimate local feature importance by querying a black-box model under randomized perturbations. This paper formulates this procedure as communication over a query channel, where the latent explanation acts as a message and each masked evaluation is a channel use. Within this framework, the complexity of the explanation is captured by the entropy of the hypothesis class, while the query interface supplies information at a rate determined by an identification capacity per query. We derive a strong converse showing that, if the explanation rate exceeds this capacity, the probability of exact recovery necessarily converges to one in error for any sequence of explainers and decoders. We also prove an achievability result establishing that a sparse maximum-likelihood decoder attains reliable recovery when the rate lies below capacity. A Monte Carlo estimator of mutual information yields a non-asymptotic query benchmark that we use to compare optimal decoding with Lasso- and OLS-based procedures that mirror LIME and KernelSHAP. Experiments reveal a range of query budgets where information theory permits reliable explanations but standard convex surrogates still fail. Finally, we interpret super-pixel resolution and tokenization for neural language models as a source-coding choice that sets the entropy of the explanation and show how Gaussian noise and nonlinear curvature degrade the query channel, induce waterfall and error-floor behavior, and render high-resolution explanations unattainable.

Erciyes Karakaya, Ozgur Ercetin

*Department of Electrical and Computer Engineering, University of Maryland, College Park, USA · †Faculty of Engineering and Natural Sciences, Sabanci University, Turkiye

Feature AttributionExplainable Artificial IntelligenceNeural Network InterpretabilityExplainability EvaluationInformation-Theoretic Lower Bounds
AskPDF
Apr 14, 2026

Instantiating Bayesian CVaR lower bounds in Interactive Decision Making Problems

Recent work established a generalized-Fano framework for lower bounding prior-predictive (Bayesian) CVaR in interactive statistical decision making. In this paper, we show how to instantiate that framework in concrete interactive problems and derive explicit Bayesian CVaR lower bounds from its abstract corollaries. Our approach compares a hard model with a reference model using squared Hellinger distance, and combines a lower bound on a reference hinge term with a bound on the distinguishability of the two models. We apply this approach to canonical examples, including Gaussian bandits, and obtain explicit bounds that make the dependence on key problem parameters transparent. These results show how the generalized-Fano Bayesian CVaR framework can be used as a practical lower-bound tool for interactive learning and risk-sensitive decision making.

Raghav Bongole, Tobias J. Oechtering, Mikael Skoglund

Department of Information Science and Engineering (ISE), KTH Royal Institute of Technology

Gaussian Process BanditsDecision-Making under UncertaintyConditional Value-at-RiskInformation-Theoretic Lower Bounds
AskPDF
Apr 12, 2026

Query Lower Bounds for Diffusion Sampling

Diffusion models generate samples by iteratively querying learned score estimates. A rapidly growing literature focuses on accelerating sampling by minimizing the number of score evaluations, yet the information-theoretic limits of such acceleration remain unclear. In this work, we establish the first score query lower bounds for diffusion sampling. We prove that for dd-dimensional distributions, given access to score estimates with polynomial accuracy ε=d−O(1)\varepsilon=d^{-O(1)} (in any LpL^p sense), any sampling algorithm requires Ω~(d)\widetildeΩ(\sqrt{d}) adaptive score queries. In particular, our proof shows that, within any polynomial total-query budget, successful sampling requires searching over Ω~(d)\widetildeΩ(\sqrt{d}) distinct noise levels, providing a formal explanation for why multiscale noise schedules are necessary in practice.

Zhiyang Xun, Eric Price

UT Austin

Query ComplexityDiffusion SamplingInformation-Theoretic Lower BoundsDiffusion Models
AskPDF
Apr 10, 2026

Semantic Channel Theory: Deductive Compression and Structural Fidelity for Multi-Agent Communication

Shannon's information theory deliberately excludes message semantics. This paper develops a rigorous framework for semantic communication that integrates formal proof systems with Shannon-theoretic tools. We introduce an axiomatic information model comprising Lsem-definable state sets linked by computable enabling maps, and define the semantic channel as a composition of Markov kernels whose supports respect the enabling structure. A fixed proof system induces an irredundant semantic core and a derivation-depth stratification, enabling four distortion measures of increasing semantic depth: Hamming, closure, depth, and a parameterized composite. Six families of computable semantic channel invariants are defined and their inter-relationships established, including a data processing bound, a semantic Fano bound, and an ideal-channel collapse theorem. The central quantitative result is a deductive compression gain: under closure-based fidelity, the minimum block length is determined by the irredundant core size rather than the full knowledge-base size. We instantiate the framework for heterogeneous multi-agent communication, introducing an overlap decomposition that yields necessary and sufficient conditions for closure-reliable communication. A semantic bottleneck phenomenon is identified in broadcast settings: vocabulary mismatch imposes irreducible fidelity limitations even over noiseless carriers. All results are verified on an explicit Datalog instance.

Jianfeng Xu

Koguan School of Law, China Institute for Smart Justice, School of Computer Science, Shanghai Jiao Tong University, Shanghai 200030, China

Semantic CommunicationInformation-Theoretic Lower BoundsMulti-Agent Communication
AskPDF
Apr 9, 2026

Optimal Multi-bit Generative Watermarking Schemes Under Worst-Case False-Alarm Constraints

This paper considers the problem of multi-bit generative watermarking for large language models under a worst-case false-alarm constraint. Prior work established a lower bound on the achievable miss-detection probability in the finite-token regime and proposed a scheme claimed to achieve this bound. We show, however, that the proposed scheme is in fact suboptimal. We then develop two new encoding-decoding constructions that attain the previously established lower bound, thereby completely characterizing the optimal multi-bit watermarking performance. Our approach formulates the watermark design problem as a linear program and derives the structural conditions under which optimality can be achieved. In addition, we identify the failure mechanism of the previous construction and compare the tradeoffs between the two proposed schemes.

Yu-Shin Huang, Chao Tian, Krishna Narayanan

Multi-Bit WatermarkingText WatermarkingLLM WatermarkingInformation-Theoretic Lower Bounds
AskPDF
Apr 9, 2026

Order-Optimal Sequential 1-Bit Mean Estimation in General Tail Regimes

In this paper, we study the problem of mean estimation under 1-bit communication constraints. We propose a novel adaptive mean estimator based solely on randomized threshold queries, where each 1-bit outcome indicates whether a given sample exceeds a sequentially chosen threshold. Our estimator is (ε,δ)(ε, δ)-PAC for any distribution with a bounded mean μ∈[−λ,λ]μ\in [-λ, λ] and a bounded kk-th central moment E[∣X−μ∣k]≤σk\mathbb{E}[|X-μ|^k] \le σ^k for any fixed k>1k > 1. Moreover, our sample complexity is order-optimal in all such tail regimes, i.e., for every such kk value. For k≠2k \neq 2, our estimator's sample complexity matches the unquantized minimax lower bounds plus an unavoidable O(log⁡(λ/σ))O(\log(λ/σ)) localization cost. For the finite-variance case (k=2k=2), our estimator's sample complexity has an extra multiplicative O(log⁡(σ/ε))O(\log(σ/ε)) penalty, and we establish a novel information-theoretic lower bound showing that this penalty is a fundamental limit of 1-bit quantization. We also establish a significant adaptivity gap: for both threshold queries and more general interval queries, the sample complexity of any non-adaptive estimator must scale linearly with the search space parameter λ/σλ/σ, rendering it vastly less sample efficient than our adaptive approach. Finally, we present algorithmic variants that (i) handle an unknown sampling budget, (ii) adapt to an unknown scale parameter σσ given (possibly loose) bounds, (iii) require only two stages of adaptivity to achieve order-optimal sample complexity at the expense of more general 1-bit queries, and (iv) leverage multiple local samples per 1-bit query to proportionally reduce communication costs.

Ivan Lau, Jonathan Scarlett

National University of Singapore

Minimax EstimationAdaptive SamplingInformation-Theoretic Lower Bounds
AskPDF
Mar 28, 2026

Forecastability as an Information-Theoretic Limit on Prediction

Forecasting is usually framed as a problem of model choice. This paper starts earlier, asking how much predictive information is available at each horizon. Under logarithmic loss, the answer is exact: the mutual information between the future observation and the declared information set equals the maximum achievable reduction in expected loss. This paper develops the consequences of that identity. Forecastability, defined as this mutual information evaluated across horizons, forms a profile whose shape reflects the dependence structure of the process and need not be monotone. Three structural properties are derived: compression of the information set can only reduce forecastability; the gap between the profile under a finite lag window and the full history gives an exact truncation error budget; and for processes with periodic dependence, the profile inherits the periodicity. Predictive loss decomposes into an irreducible component fixed by the information structure and an approximation component attributable to the method; their ratio defines the exploitation ratio, a normalised diagnostic for method adequacy. The exact equality is specific to log loss, but when forecastability is near zero, classical inequalities imply that no method under any loss can materially improve on the unconditional baseline. The framework provides a theoretical foundation for assessing, prior to any modelling, whether the declared information set contains sufficient predictive information at the horizon of interest.

Peter Maurice Catt

Independent Researcher, Auckland, New Zealand

Time Series ForecastingInformation-Theoretic Lower BoundsMutual Information
AskPDF
Mar 19, 2026

On the Peril of (Even a Little) Nonstationarity in Satisficing Regret Minimization

Motivated by the principle of satisficing in decision-making, we study satisficing regret guarantees for nonstationary KK-armed bandits. We show that in the general realizable, piecewise-stationary setting with LL stationary segments, the optimal regret is Θ(Llog⁡T)Θ(L\log T) as long as L≥2L\geq 2. This stands in sharp contrast to the case of L=1L=1 (i.e., the stationary setting), where a TT-independent Θ(1)Θ(1) satisficing regret is achievable under realizability. In other words, the optimal regret has to scale with TT even if just a little nonstationarity presents. A key ingredient in our analysis is a novel Fano-based framework tailored to nonstationary bandits via a post-interaction reference construction. This framework strictly extends the classical Fano method for passive estimation as well as recent interactive Fano techniques for stationary bandits. As a complement, we also discuss a special regime in which constant satisficing regret is again possible.

Yixuan Zhang, Ruihao Zhu, Qiaomin Xie

Department of Industrial & Systems Engineering, University of Wisconsin-Madison · SC Johnson College of Business, Cornell University

Regret MinimizationNon-Stationary BanditsInformation-Theoretic Lower Bounds
AskPDF
Mar 18, 2026

What resources are needed for optimal learning of bosonic Gaussian states?

Continuous-variable systems enable key quantum technologies in computation, communication, and sensing. Bosonic Gaussian states emerge naturally in various such applications, including gravitational-wave and dark-matter detection. A fundamental question is how to characterize an unknown bosonic Gaussian state from as few samples as possible. Despite decades-long exploration, the ultimate efficiency limit remains unclear. In this work, we study the necessary and sufficient number of copies to learn an nn-mode Gaussian state, with energy less than EE, to ε\varepsilon trace distance with high probability. We prove a lower bound of Ω(n3/ε2)Ω(n^3/\varepsilon^2) for Gaussian measurements, matching the best known upper bound up to doubly-log energy dependence, and Ω(n2/ε2)Ω(n^2/\varepsilon^2) for arbitrary measurements. We further show an upper bound of O~(n2/ε2)\widetilde{O}(n^2/\varepsilon^2) given that the Gaussian state is promised to be either pure or passive. Interestingly, while Gaussian measurements suffice for nearly optimal learning of pure Gaussian states, non-Gaussian measurements are provably required for optimal learning of passive Gaussian states. Finally, focusing on learning single-mode Gaussian states via non-entangling Gaussian measurements, we provide a nearly tight bound of Θ~(E/ε2)\widetildeΘ(E/\varepsilon^2) for any non-adaptive schemes, showing adaptivity is indispensable for nearly energy-independent scaling. As a byproduct, we establish sharp bounds on the trace distance between Gaussian states in terms of the total variation distance between their Wigner distributions, and obtain a nearly tight sample complexity bound for learning the Wigner distribution of any Gaussian state to ε\varepsilon total variation distance. Our results significantly advance quantum learning theory in the bosonic regimes and have practical impact in quantum sensing and benchmarking applications.

Senrui Chen, Francesco Anna Mele, Marco Fanizza +5

Institute for Quantum Information and Matter, Caltech, Pasadena, CA 91125, USA · Scuola Normale Superiore, Piazza dei Cavalieri 7, 56126 Pisa, Italy · Inria, Télécom Paris – LTCI, Institut Polytechnique de Paris, France

Quantum State TomographyInformation-Theoretic Lower Bounds
AskPDF
Mar 16, 2026

The Sampling Complexity of Condorcet Winner Identification in Dueling Bandits

We study best-arm identification in stochastic dueling bandits under the sole assumption that a Condorcet winner exists, i.e., an arm that wins each noisy pairwise comparison with probability at least 1/21/2. We introduce a new identification procedure that exploits the full gap matrix Δi,j=qi,j−12Δ_{i,j}=q_{i,j}-\tfrac12 (where qi,jq_{i,j} is the probability that arm ii beats arm jj), rather than only the gaps between the Condorcet winner and the other arms. We derive high-probability, instance-dependent sample-complexity guarantees that (up to logarithmic factors) improve the best known ones by leveraging informative comparisons beyond those involving the winner. We complement these results with new lower bounds which, to our knowledge, are the first for Condorcet-winner identification in stochastic dueling bandits. Our lower-bound analysis isolates the intrinsic cost of locating informative entries in the gap matrix and estimating them to the required confidence, establishing the optimality of our non-asymptotic bounds. Overall, our results reveal new regimes and trade-offs in the sample complexity that are not captured by asymptotic analyses based only on the expected budget.

El Mehdi Saad, Victor Thuot, Nicolas Verzelen

CC-UM6P-Rabat · INRAE, MISTEA, Institut Agro, Univ. Montpellier Montpellier, France · MISTEA +1

Dueling BanditsBest-Arm IdentificationMulti-Armed BanditsInformation-Theoretic Lower Bounds
AskPDF
Mar 5, 2026

WaterSIC: Information-Theoretically (Near) Optimal Linear Layer Quantization

This paper considers the problem of converting a given dense linear layer to low precision. The tradeoff between compressed length and output discrepancy is analyzed information theoretically (IT). It is shown that a popular GPTQ algorithm may have an arbitrarily large gap to the IT limit. To alleviate this problem, a novel algorithm, termed ``WaterSIC'', is proposed and is shown to be within a rate gap of 0.255 bits to the IT limit, uniformly over all possible covariance matrices of input activations. The key innovation of WaterSIC's is to allocate different quantization rates to different columns (in-features) of the weight matrix, mimicking the classical IT solution known as "waterfilling". Applying WaterSIC to the Llama and Qwen family of LLMs establishes new state-of-the-art performance for all quantization rates from 1 to 4 bits. Our code is available at https://github.com/egorlifar/watersic.

Egor Lifar, Semyon Savkin, Or Ordentlich +1

MIT · Independent Researcher · Hebrew University of Jerusalem

Neural Network QuantizationLLM QuantizationPost-Training QuantizationWeight-Only QuantizationInformation-Theoretic Lower Bounds
AskPDF
Feb 26, 2026

Low-degree Lower bounds for clustering in moderate dimension

We study the fundamental problem of clustering nn points into KK groups drawn from a mixture of isotropic Gaussians in Rd\mathbb{R}^d. Specifically, we investigate the requisite minimal distance ΔΔ between mean vectors to partially recover the underlying partition. While the minimax-optimal threshold for ΔΔ is well-established, a significant gap exists between this information-theoretic limit and the performance of known polynomial-time procedures. Although this gap was recently characterized in the high-dimensional regime (n≤dKn \leq dK), it remains largely unexplored in the moderate-dimensional regime (n≥dKn \geq dK). In this manuscript, we address this regime by establishing a new low-degree polynomial lower bound for the moderate-dimensional case when d≥Kd \geq K. We show that while the difficulty of clustering for n≤dKn \leq dK is primarily driven by dimension reduction and spectral methods, the moderate-dimensional regime involves more delicate phenomena leading to a "non-parametric rate". We provide a novel non-spectral algorithm matching this rate, shedding new light on the computational limits of the clustering problem in moderate dimension.

Alexandra Carpentier, Nicolas Verzelen

Institut für Mathematik, Universität Potsdam, Germany. · INRAE, MISTEA, Univ. Montpellier, Montpellier, France

Low-Degree Polynomial MethodClusteringGaussian Mixture ModelsStatistical Learning TheoryInformation-Theoretic Lower Bounds
AskPDF
Feb 20, 2026

Tighter Regret Lower Bound for Gaussian Process Bandits with Squared Exponential Kernel in Hypersphere

We study an algorithm-independent, worst-case lower bound for the Gaussian process (GP) bandit problem in the frequentist setting, where the reward function is fixed and has a bounded norm in the known reproducing kernel Hilbert space (RKHS). Specifically, we focus on the squared exponential (SE) kernel, one of the most widely used kernel functions in GP bandits. One of the remaining open questions for this problem is the gap in the dimension-dependent logarithmic factors between upper and lower bounds. This paper partially resolves this open question under a hyperspherical input domain. We show that any algorithm suffers Ω(T(ln⁡T)d(ln⁡ln⁡T)−d)Ω(\sqrt{T (\ln T)^{d} (\ln \ln T)^{-d}}) cumulative regret, where TT and dd represent the total number of steps and the dimension of the hyperspherical domain, respectively. Regarding the simple regret, we show that any algorithm requires Ω(ε−2(ln⁡1ε)d(ln⁡ln⁡1ε)−d)Ω(ε^{-2}(\ln \frac{1}ε)^d (\ln \ln \frac{1}ε)^{-d}) time steps to find an εε-optimal point. We also provide the improved O((ln⁡T)d+1(ln⁡ln⁡T)−d)O((\ln T)^{d+1}(\ln \ln T)^{-d}) upper bound on the maximum information gain for the SE kernel. Our results guarantee the optimality of the existing best algorithm up to dimension-independent logarithmic factors under a hyperspherical input domain.

Shogo Iwazaki

LY Corporation, Tokyo, Japan

Gaussian Process BanditsMinimax RegretMulti-Armed BanditsInformation-Theoretic Lower BoundsKernel Methods
AskPDF
Feb 19, 2026

Fundamental Limits of Black-Box Safety Evaluation: Information-Theoretic and Computational Barriers from Latent Context Conditioning

Black-box safety evaluation of AI systems assumes model behavior on test distributions reliably predicts deployment performance. We formalize and challenge this assumption through latent context-conditioned policies -- models whose outputs depend on unobserved internal variables that are rare under evaluation but prevalent under deployment. We establish fundamental limits showing that no black-box evaluator can reliably estimate deployment risk for such models. (1) Passive evaluation: For evaluators sampling i.i.d. from D_eval, we prove minimax lower bounds via Le Cam's method: any estimator incurs expected absolute error >= (5/24)deltaL approximately 0.208deltaL, where delta is trigger probability under deployment and L is the loss gap. (2) Adaptive evaluation: Using a hash-based trigger construction and Yao's minimax principle, worst-case error remains >= delta*L/16 even for fully adaptive querying when D_dep is supported over a sufficiently large domain; detection requires Theta(1/epsilon) queries. (3) Computational separation: Under trapdoor one-way function assumptions, deployment environments possessing privileged information can activate unsafe behaviors that any polynomial-time evaluator without the trapdoor cannot distinguish. For white-box probing, estimating deployment risk to accuracy epsilon_R requires O(1/(gamma^2 * epsilon_R^2)) samples, where gamma = alpha_0 + alpha_1 - 1 measures probe quality, and we provide explicit bias correction under probe error. Our results quantify when black-box testing is statistically underdetermined and provide explicit criteria for when additional safeguards -- architectural constraints, training-time guarantees, interpretability, and deployment monitoring -- are mathematically necessary for worst-case safety assurance.

Vishal Srivastava

Whiting School of Engineering, John Hopkins University, Baltimore, MD 21218

AI Safety EvaluationBlack-Box Model AuditingInformation-Theoretic Lower Bounds
AskPDF
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.

Jingxuan Chai, Yong Xiao, Guangming Shi

the School of Artificial Intelligence at the Xidian University, Shaanxi 710071, China · the School of Electronic Information and Communications at the Huazhong University of Science and Technology, Wuhan 430074, China · the Pengcheng Laboratory, Shenzhen, Guangdong 518055, China +2

Semantic CommunicationRate-Distortion TheoryInformation-Theoretic Lower Bounds
AskPDF
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.

Alfred Harwood, Jose Faustino, Alex Altair

1Dovetail Research · University of Sao Paulo

Markov Decision ProcessesReinforcement LearningWorld ModelsInformation-Theoretic Lower BoundsMutual Information
AskPDF