Information-Theoretic Lower Bounds

Momentum

12 papers in the last four weeks, up 140% on the four weeks before. 0.1% of all new papers.

Jul 13Week of Sep 28

Latest papers 53

Jun 23, 2026cs.CC

Token Complexity of Certifying Stochastic-Oracle Reliability

Wang~\cite{Wang2026} introduced the Stochastic-Oracle Turing Machine (SOTM) framework and defined token complexity as the minimum expected cost of interacting with a stochastic oracle needed to attain a specified solution quality for a task. This paper develops an analogous notion for certifying the reliability of a stochastic oracle on a given domain. Certification token complexity is the minimum expected token cost required, with controlled error probability, to distinguish oracles that meet a target reliability level from those that fall below a lower reliability threshold. We construct an SPRT-based certification SOTM that queries the oracle, computes binary correctness scores, and stops when the accumulated log-likelihood evidence crosses a decision threshold. The SOTM halts almost surely, satisfies the desired two-sided error guarantee over the reliability regions to be certified, and yields an explicit upper bound on certification token complexity in terms of the reliability thresholds, the error bound, and the expected per-turn token cost. We then establish a matching information-theoretic lower bound: even with adaptive queries, every error-bounded certification SOTM must incur the same leading-order expected token cost as the SPRT-based construction as the prescribed error bound tends to zero. Together, these bounds characterize the leading-order certification token complexity in the small-error regime.

Jie Wang

Richard Miner School of Computing and Information Sciences, University of Massachusetts, Lowell, MA 01854, USA.

Sample Complexity Information-Theoretic Lower Bounds

Ask PDF

Jun 22, 2026cs.LG

Minimax Quantile Lower Bounds for Interactive Statistical Decision Making with Privacy

Minimax risk and regret are expectation-based criteria and do not capture rare but consequential failures. To address this concern, we develop a

δ

-explicit minimax-quantile theory for interactive statistical decision making (ISDM). We first provide structural relations between minimax quantiles, lower minimax quantiles, and minimax risk. This includes a quantile-to-expectation conversion and an equivalence between strict and lower minimax quantiles outside a countable set of confidence levels. We then derive two converse tools for ISDM: a high-probability interactive Fano's method and a high-probability interactive Le Cam's method. Then, we show that mutual-information (MI) privacy can be handled in the same framework by restricting the admissible decision class. For coordinatewise Gaussian privatization, we derive a two-point template that isolates the privacy-induced variance inflation. We instantiate this template for Gaussian mean estimation, and use the same two-point strategy directly for two-armed Gaussian bandits. We then derive a minimax quantile lower bound for the

K

-armed Gaussian bandit problem, showing that the interactive Fano method captures the exploration cost over multiple possible best arms. The resulting lower bounds are explicit in the confidence level

δ

and in the privacy budget for the private problems. They yield

\log(1/δ)/n

scaling for squared-error Gaussian mean estimation,

\sqrt{T\log(1/δ)}

scaling for two-armed bounded-mean Gaussian bandits, and

\sqrt{KT\log(1/δ)}

-type scaling for the

K

-armed bandits, with privacy appearing through a Gaussian variance-inflation factor for the private problems.

Raghav Bongole, Amirreza Zamani, Tobias J. Oechtering +1

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

Multi-Armed Bandits Decision-Making under Uncertainty Information-Theoretic Lower Bounds

Ask PDF

Jun 14, 2026cs.LG

The Information-Theoretic Benefit of Shared Representations under Orthogonality Constraints

Modern deep learning architectures are increasingly multi-task and multi-modal, using a pretrained foundation model combined with task-specific, fine-tuned models. Empirically, exploiting similarity across different problems, instead of solving them individually, can significantly improve overall performance. While the generalization and sample complexity properties of multitask learning have been widely studied, the parametric complexity of joint approximation in comparison to separate approximation remains less well understood. The question is particularly relevant in modern deep learning, where models are increasingly required to satisfy structural constraints such as equivariance, conservation laws, or orthogonality. We prove lower and upper bounds on the description-length for separate and joint approximation classes, respectively, in uniform norm. We build a class of orthogonal functions by composing a shared hard feature, realized by a Rademacher-Haar wavelet series, with Sawtooth-Walsh readouts to enforce orthogonality of output coordinates. The dyadic tree structure of the Rademacher-Haar wavelet concentrates the approximation hardness in the common feature component, while the readouts act as task-specific heads. Using an information-theoretic framework, we obtain a sharp gap between the optimal approximation rates achievable by joint and separate coding. Finally, we realize this separation in a neural network model using Heaviside activations via reduction to triangle-wave approximation. Our results show that even under an orthogonality constraint joint approximation requires strictly fewer bits in compositional architectures, provided the tasks share a latent hard feature. This provides theoretical insight into the description-length-efficiency of compositional multi-output architectures and clarifies how neural networks can retain expressivity under geometric constraints.

Thomas Dittrich, Oliver Potocki, Philipp Grohs

Johann Radon Institute of Computational and Applied Mathematics, Austrian Academy of Sciences · Faculty of Mathematics, University of Vienna

Representation Learning Minimum Description Length Multi-Task Learning Neural Network Approximation Theory Information-Theoretic Lower Bounds

Ask PDF

Jun 12, 2026math.ST

Recovery thresholds for hidden weighted sparse graphs

Recovering structural information from noisy high-dimensional data is a fundamental task in statistical inference. We investigate the recovery thresholds for a graph hidden in a randomly weighted complete graph. Specifically, an unknown graph

H^* \in H_n

is chosen uniformly at random, and hidden in a complete graph of

n

vertices as follows: the weight of an edge

e \in H

is distributed independently according to

P_n

; otherwise the weight is distributed independently according to

Q_n

. The goal is to recover almost all of

H

from these edge weights. Assuming a local Lipschitzness of the Rényi divergence between distributions

P_n

and

Q_n

, and a mild density condition for the graphs

H_n

, we give a unified characterization of the information-theoretic limit for recovering almost all of

H

(also known as almost exact recovery). Our characterization connects the KL divergence between

P_n

and

Q_n

to the logarithm of the first moment threshold of

H

in the Erdős-Rényi random graph model

G(n,p)

. Our lower bound also extends to the task of partial recovery, in which only a constant

λ

-fraction of

H

needs to be recovered. Last but not least, for certain Bernoulli and Exponential regimes, and for Gaussian distributions, we are able to show an All-or-Nothing (AoN) threshold phenomenon at the exponential scale.

Zhe Hou, Jingcheng Liu

State Key Laboratory for Novel Software Technology, Nanjing University

Graph Structure Learning Information-Theoretic Lower Bounds

Ask PDF

Jun 10, 2026quant-ph

Quantum Occam Learning: Sample-Supported Expressibility for Circuit-Based Quantum Learning

A central principle in quantum machine learning is that an ansatz should be expressive enough to represent the quantum data of interest. Yet, the expressibility is statistically meaningful only insofar as it can be learned from finitely many copies of an unknown quantum state. In this work, we develop an information-theoretic Occam theory for quantum data generated by finite-size quantum circuits. For the class

S_{n,G}

n

-qubit pure states preparable with at most

G

two-qubit gates, a metric-entropy argument gives the realizable sample law

\widetildeΘ(G/ε^2)

in the circuit-limited regime. For an arbitrary source

\hatρ

, we introduce the best

G

-gate approximation error

d_G(\hatρ)

and the approximate circuit complexity

C_η(\hatρ)

. We prove an agnostic quantum Occam theorem: with

M

copies, one can learn up to the best

G

-gate approximation error plus a statistical penalty

\widetilde{O}(\sqrt{G/M})

. We then remove the need to know

G

in advance through an adaptive model-selection theorem whose oracle inequality selects the circuit complexity justified by the data. Matching lower bounds yield a sample-supported expressibility law: at trace-distance accuracy

ε

M

samples can support only

G_{\rm supported} \simeq Mε^2

gates, up to logarithmic factors and tomography saturation at

2^n

. Thus, the circuit complexity becomes an adaptive statistical resource rather than a static promise. Our framework turns bounded circuit complexity into a model-selection principle for quantum machine learning.

Jeongho Bang, Kyoungho Cho, Jeongwoo Jae

Institute for Convergence Research and Education in Advanced Technology, Yonsei University, Seoul 03722, Republic of Korea · Department of Quantum Information, Yonsei University, Incheon 21983, Republic of Korea · Department of Statistics and Data Science, Yonsei University, Seoul 03722, Republic of Korea +1

Model Selection Sample Complexity Quantum Machine Learning Statistical Learning Theory Information-Theoretic Lower Bounds

Ask PDF

Jun 9, 2026cs.LG

Bellman-sufficient Information Complexity

We introduce Bellman-sufficient information complexity for minimax analysis of sequential decision problems. A Bellman-sufficient state retains enough of the history to close the controlled recursion, while an index

Y=χ(Ω)

specifies the decision-relevant information being charged. The upper bound is a log-penalized Bellman program; the lower bound is a Bellman--Fano comparison along an algorithm-dependent reference trajectory. If the two values match at a common localization scale and the stated admissibility, calibration, and growth conditions hold, they form an information-risk sandwich. UCB, E2D, and AMS/EBO control or relax the upper Bellman bracket in different ways. For the main application, we give a negative answer to a widely studied form of the GP--UCB minimax-optimality question. For every

0<α<1/4

, we construct one bounded continuous kernel whose minimax regret is

Θ(T^{1-α})

along an infinite sequence of horizons, while two globally calibrated GP--UCB rules incur linear regret under one fixed truth. An epochwise finite-marginal action-index AIR Bellman policy, implemented through robust AIR/AMS/EBO control, attains the minimax order. The construction separates realized information from the cost of uniform optimism: many low-value directions inflate the exploration multiplier and change the trajectory. Through the canonical RKHS feature map, it also yields a finite-horizon polynomial minimax separation for the specified maximal-information-calibrated LinUCB rule. A reproducible experiment illustrates the mechanism.

Yunbei Xu

National University of Singapore

Multi-Armed Bandits Minimax Regret Regret Minimization UCB Algorithms Information-Theoretic Lower Bounds

Ask PDF

Jun 6, 2026math.PR

Pointwise Complexity for Gaussian Fields: Upper Envelopes, Algorithmic Lower Bounds, and Separation

We prove a variance-aware pointwise majorizing-measure theorem for centered Gaussian processes. Classical generic chaining characterizes the scalar quantity

\mathbb E\sup_{x\in T}X_x

; the theorem here gives a simultaneous high-probability envelope for the entire field. For an ambient prior

μ

, the envelope at

x

is governed by a pointwise Fernique-Talagrand functional

Φ_μ(x):=\int_0^{4σ(x)}\sqrt{\log\frac{1}{μ(B_d(x,\varepsilon))}}\,d\varepsilon,

together with the corresponding Gaussian tail term. The theorem provides a reusable field-level refinement of classical generic chaining and a Gaussian-process counterpart of pointwise empirical-process bounds for deep neural networks. We also record a Bayesian algorithmic lower envelope from the interactive Fano/data-processing principle. For a known prior

π

, an observation channel, and a concrete estimator

\widehat t(Y)

, the lower bound is expressed through the exact ghost small-ball mass

\mathbb E_{Y\sim Q}π(B_d(\widehat t(Y),Δ))

, rather than a worst-case covering number. In Gaussian location experiments, comparison decoders convert Bayes location error into lower bounds on decision-aligned Gaussian ranges. We then construct an elementary example separating the usual Fano relaxation, the Bayesian algorithmic lower envelope, the pointwise Gaussian envelope, and the full-class minimax risk. Together, these results show that algorithmic lower bounds provide local-geometric validations of pointwise complexity for fixed estimators in overparameterized ambient classes, precisely in regimes where classical minimax theory becomes either too coarse or oracle-dependent. This separation can also be recast in minimax language as penalty-range information relaxation, highlighting an important question of algorithmic robustness for classical high-dimensional models and regularized algorithms.

Yunbei Xu

National University of Singapore

Gaussian Processes Minimax Estimation Information-Theoretic Lower Bounds

Ask PDF

Jun 5, 2026cs.DS

Towards Tight Bounds for Streaming Attention

The attention mechanism is a cornerstone of modern transformer architectures. However, its expressive power comes at the cost of quadratic runtime and linear space usage. In particular, the classical transformer architecture explicitly stores all previously seen input elements (tokens) in order to generate the next one. The problem of implementing a transformer in limited space, known as KV cache compression, has received much interest over the past few years, spurring the development of powerful heuristics. Recent works of Haris et al, COLT'25 and Kochetkova et al, NeurIPS'25, formalized KV cache compression as the streaming attention approximation problem, providing both upper bounds (based on discrepancy theory) and information theoretic lower bounds. However, those papers left open a significant gap between the upper and lower bounds. For example, the space usage of their algorithms increases with the precision parameter, but the lower bound does not get stronger. In this work, we revisit the streaming attention approximation problem and provide nearly tight bounds on its space complexity. On the algorithmic side, we achieve the result through a surprisingly tight interplay between three distinct methods for kernel density estimation: discrepancy-based coreset constructions (e.g., Charikar-Kapralov-Waingarten'24), the polynomial method (e.g., Greengard-Rokhlin'87, Alman-Song'23), and space partitioning (e.g., Andoni-Laarhoven-Razenshteyn-Waingarten'17, Charikar-Kapralov-Nouri-Siminelakis'20). On the lower bound side, our main technical contribution is a new technique for using the INDEX problem with a large amount of side information that we hope will prove useful in other high dimensional geometric estimation problems.

Justin Y. Chen, Ying Feng, Piotr Indyk +3

MIT · EPFL

Efficient Attention KV-Cache Compression Information-Theoretic Lower Bounds Streaming Algorithms

Ask PDF

May 30, 2026cs.IT

Information-Theoretic Lower Bounds for Bit-Constrained Stochastic Optimization via a Reduction to Compressed Gaussian Mean Estimation

Low-precision pretraining (FP8, MXFP4, NVFP4) is now standard for frontier language models, yet the literature is almost entirely achievability -- algorithms and empirical scaling laws -- with no matching characterization of what is information-theoretically possible. We study a B-bit quantized stochastic first-order oracle: an optimizer interacts for T rounds and receives, each round, a B-bit adaptive public-coin description of its stochastic gradient. Our main contribution is an exact reduction from optimizing a strongly convex quadratic family to interactively compressed Gaussian mean estimation -- under the B-bit oracle the query carries no information, so optimization collapses exactly onto a sequential distributed-estimation problem. This yields two unconditional lower bounds, a communication bound TB = Omega(d) and a statistical bound T = Omega(sigma^2 d / eps^2), and the sharp product-form bound T = Omega((sigma^2 d / eps^2) max{1, d/B}). The product form is also unconditional: a B-bit transcript carries at most O(TB / sigma^2) of Fisher trace about the mean, so bits rather than dimension limit the recoverable information, and combined with the multivariate van Trees inequality this gives the bound directly, without bounded-likelihood-ratio truncation. We give a near-matching achievability result with exact per-round bit accounting under a bounded-dynamic-range oracle, tight up to a logarithmic factor; the lower bound is for truly Gaussian (unbounded) gradients, and closing this oracle gap is left open. A sequential rate-distortion perspective extends the reduction to correlated and drifting oracles and corrects an earlier conjecture: positive noise correlation raises the bound by (1+rho)/(1-rho) rather than relaxing it. The bounds give an information-theoretic baseline for any low-bit gradient path, not an optimality claim about deployed FP4 systems.

Munsik Kim

Stochastic Optimization Stochastic Optimization Convergence Communication Complexity Information-Theoretic Lower Bounds

Ask PDF

May 29, 2026cs.LG

Auditing Near-Optimal Policies Can Be Exponentially Hard: Conditional Query Lower Bounds via Occupancy Rashomon Capacity

When many reinforcement-learning policies achieve near-optimal return, a post-hoc auditor may have to distinguish among many behaviorally distinct but return-equivalent policies. We formalize this phenomenon through an occupancy-measure analogue of Rashomon capacity: the metric entropy of the near-optimal occupancy region, computed relative to an audited deployment class. Because occupancy measures identify behavior only up to occupancy equivalence, we formulate auditing at the occupancy-class level and distinguish exact local-query oracles from noisy sample-query oracles. Our main exact-query result is conditional: if the audited class contains a

2/H

-separated near-optimal packing whose local signatures are

b

-sparse, then exact local-query auditing requires

Ω(M/b)

queries; when the packing realizes deployment-class capacity and

b=O(1)

, this becomes

Ω(2^{\Hopt^\cF(\eps)})

. We give a finite discounted hidden-branch MDP attaining this bound and show the exact Bayes success law. For noisy hidden-trigger testing, we prove a mixture lower bound of order

M/β

, where

β

is the per-sample KL signal, yielding

Ω(2^{\Hopt^\cF(\eps)}/(ρ^2Δ^2))

for capacity-order packings with

β=O(ρ^2Δ^2)

. We also provide a static target-recognition information lower bound, a transcript-compatible oracle-cover verification upper bound, and a canonical occupancy regularizer whose regularized audited capacity collapses when a trusted reference occupancy is available. Controlled benchmarks distinguish positive sparse-signature instances from high-capacity negative controls where exact auditing is easy, and map the noisy-trigger law to post-processed continuous-control and visual-RL auditing regimes.

Ibne Farabi Shihab, Sanjeda Akter, Anuj Sharma

Department of Computer Science, Iowa State University · Department of Civil, Construction & Environmental Engineering, Iowa State University

Information-Theoretic Lower Bounds Black-Box Model Auditing

Ask PDF

May 19, 2026cs.LG

A Van Trees Lower Bound for Fully Interactive Differentially Private Federated Learning

Federated differentially private protocols can communicate over many adaptive rounds and reuse each client's local samples. Existing lower bound arguments for federated DP are often restricted to noninteractive protocols or fresh batch decompositions, so the fundamental information-theoretic limit of estimation under fully interactive protocols remains unknown. We establish a federated van Trees inequality for parameter estimation under squared \ell_2 loss from any complete public transcript satisfying a clientwise zCDP constraint at the sample level. A scalar trace form covers homogeneous experiments, while a matrix form preserves directional Fisher geometry in heterogeneous experiments where different clients are informative in different subspaces. Together with existing upper bounds for the corresponding problems, these results identify the minimax rates for various statistical problems including mean estimation, linear regression, nonparametric regression, and functional mean estimation over the full class of interactive public-transcript protocols. For these problems, arbitrary public interaction and repeated sample reuse do not improve the rate over simpler restricted protocols. The key technical ingredient in our paper is a contraction inequality for the Fisher information in the transcript: each client's contribution is bounded both by the Fisher information in its local experiment and by its total privacy budget.

T. Tony Cai, Yicheng Li

Department of Statistics and Data Science, The Wharton School, University of Pennsylvania, Philadelphia, PA, USA. · KLATASDS-MOE, School of Statistics, East China Normal University, Shanghai, China.

Differentially Private Federated Learning Differential Privacy Information-Theoretic Lower Bounds Federated Learning

Ask PDF

May 15, 2026cs.IT

PrismQuant: Rate-Distortion-Optimal Vector Quantization for Gaussian-Mixture Sources

For a Gaussian source under mean-squared error (MSE), classical transform coding is rate--distortion (RD) optimal: the Karhunen--Loeve transform (KLT) diagonalizes the covariance, reverse waterfilling allocates the bits, and scalar quantization closes the loop. This elegant story breaks down for multimodal sources, where no single covariance can capture heterogeneous local geometries, and the RD function loses its closed form. We revisit this problem through Gaussian-mixture sources and develop a constructive RD theory for them. Our key finding is that the mixture structure incurs only a component label cost. Conditioned on the active mixture component, each branch is Gaussian; the challenge is allocating bits across heterogeneous branches. We prove that the genie-aided conditional RD function is governed by a single global reverse-waterfilling level shared across all components and eigenmodes. Building on this result, we introduce PrismQuant, which transmits the component label losslessly and encodes the residual using the component-matched KLT, followed by scalar quantization, achieving a rate of H(C)/n bits per source dimension of the converse, with a vanishing asymptotic gap. We further develop a practical implementation based on EM-driven Gaussian-mixture learning, component-adaptive KLTs, and entropy-constrained scalar quantization (ECSQ). Experiments on synthetic Gaussian mixtures show that PrismQuant closely approaches the theoretical RD bound, while experiments on real-world channel-state-information (CSI) data demonstrate competitive or superior performance compared with transformer-based learned codecs at more than one order of magnitude smaller model size.

Bumsu Park, Chanho Park, Youngmok Park +1

Department of Electrical Engineering POSTECH Pohang, South Korea

Rate-Distortion Theory Gaussian Mixture Models Vector Quantization Rate-Distortion Optimization Information-Theoretic Lower Bounds

Ask PDF

May 12, 2026cs.LG

Autoregressive Learning in Joint KL: Sharp Oracle Bounds and Lower Bounds

We study the fundamental and timely problem of learning long sequences in autoregressive modeling and next-token prediction under model misspecification, measured by the joint Kullback--Leibler (KL) divergence. Our goal is to characterize how the sequence horizon

H

affects both approximation and estimation errors in this joint-distribution, sequence-level regime. By establishing matching upper and lower bounds, we provide, to our knowledge, the first complete characterization of long-horizon error behavior under the natural joint KL objective, with improved rates and optimality justification relative to existing work. On the approximation side, we show that joint KL admits a horizon-free approximation factor, in sharp contrast to Hellinger-based analyses that exhibit an

Ω(H)

dependence for computationally efficient methods; this isolates the choice of divergence as the source of approximation amplification. On the estimation side, we prove a fundamental information-theoretic lower bound of order

Ω(H)

that holds for both decomposable policy classes and fully shared policies, matching the

\widetilde O(H)

upper bounds achieved by computationally efficient algorithms. Our analysis clarifies the landscape of recent autoregressive learning results by aligning the log-loss training objective, the sequence-level evaluation metric, and the approximation metric {\color{black}through a sharp joint-KL oracle theory}. We further show that these joint-KL guarantees imply policy learning regret bounds at rates matching prior imitation learning literature.

Yunbei Xu, Yuzhe Yuan, Ruohan Zhan

National University of Singapore · University College London

Statistical Learning Theory Information-Theoretic Lower Bounds Autoregressive Modeling

Ask PDF

May 6, 2026cs.IT

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 Bounds Minimax Estimation Statistical Learning Theory Information-Theoretic Lower Bounds Generalization Bounds

Ask PDF

May 6, 2026cs.CL

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 Modeling Associative Memory Sequence Modeling Information-Theoretic Lower Bounds

Ask PDF

May 5, 2026cs.DS

Provable Accuracy Collapse in Embedding-Based Representations under Dimensionality Mismatch

Embedding-based representations in Euclidean space

\mathbb{R}^d

are a cornerstone of modern machine learning, where a major goal is to use the \emph{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

d

is chosen close to the ground-truth dimension

D

, 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

m

anchor--positive--negative triplets

(i,j,k)

encoding distance comparisons

\mathrm{dist}(i,j) < \mathrm{dist}(i,k)

. Specifically, given triplets realizable by an unknown ground-truth embedding in

D

dimensions, we prove that there exists constant

c < 1

, such that \emph{every embedding of dimension at most

cD

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=1

dimension, no polynomial-time algorithm -- \textit{regardless of its dimension} -- can achieve accuracy above the trivial

50\%

baseline.

Dionysis Arvanitakis, Vaggos Chatziafratis, Yiyuan Luo

Northwestern University, IL, USA · University of California

Intrinsic Dimensionality Contrastive Learning Dimensionality Reduction Information-Theoretic Lower Bounds

Ask PDF

May 4, 2026stat.ML

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 answer oracle induced by an SCM for a class of queries. Our main construction gives binary acyclic SCMs whose observational distribution has constant description length, while the single-variable interventional answer oracle has description length

Θ(n^2)

. A degree-sensitive upper bound shows that finite-gate-schema SCMs of indegree

d

have observational-interventional gap at most

O(nd \log(en/d) + n \log n)

, making 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

\varepsilon < 1/4

. At the next rung, the full hard-do interventional oracle can still leave a

Θ(n)

counterfactual description gap. A general ambiguity-to-bits theorem and Shannon analogue show that these gaps 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 Models Causal Inference Counterfactual Reasoning Information-Theoretic Lower Bounds

Ask PDF

May 2, 2026stat.ML

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(\cdot \mid S)

for an unknown truncation set

S

that may hide up to an

\varepsilon

-fraction of the probability mass. For distributions with

p

-th directional moments of magnitude at most

ν_{P,p}

, truncation induces a bias of order

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\!\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(\varepsilon)

. This reveals an intermediate regime in which estimation requires

Θ(d)

samples for uniform recovery, while testing recovers the classical

Θ(\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 Complexity Information-Theoretic Lower Bounds Statistical Hypothesis Testing

Ask PDF

Apr 24, 2026quant-ph

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

\operatorname{tr}(ρ^t)

, but whether replica number marks a sharp information-theoretic resource boundary has remained unclear. For every fixed order

t\ge 3

, existing protocols show that

\lceil t/2\rceil

replicas already suffice for polynomial-sample estimation of

\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

\lceil t/2\rceil-1

replicas requires dimension-growing sample complexity, while

\lceil t/2\rceil

replicas suffice by prior work. Thus the exact replica threshold for fixed-order pure moments is

\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

\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 Complexity Information-Theoretic Lower Bounds

Ask PDF

Apr 21, 2026cs.IT

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 ML Information-Theoretic Lower Bounds

Ask PDF

Apr 17, 2026cs.AI

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 Attribution Explainable Artificial Intelligence Neural Network Interpretability Explainability Evaluation Information-Theoretic Lower Bounds

Ask PDF

Apr 12, 2026cs.LG

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

d

-dimensional distributions, given access to score estimates with polynomial accuracy

\varepsilon=d^{-O(1)}

(in any

L^p

sense), any sampling algorithm requires

\widetildeΩ(\sqrt{d})

adaptive score queries. In particular, our proof shows that, within any polynomial total-query budget, successful sampling requires searching over

\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 Complexity Diffusion Sampling Information-Theoretic Lower Bounds Diffusion Models

Ask PDF

Feb 13, 2026cs.AI

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

n

states and

m

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

n \log m

bits of information about the environment. Specifically, we show that the mutual information between the environment and the optimal policy is

n \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 Processes Reinforcement Learning World Models Information-Theoretic Lower Bounds Mutual Information

Ask PDF

Momentum

Related topics

Latest papers 53