Information-Theoretic Lower Bounds

Follow this topic Ask about this topic

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

All topics

Oct 8, 2026cs.LG

Verification with Transfer: Exact Information Frontiers and Their Price in Calls

A verifier that accepts or rejects whole answers reveals little: under a flat prior over

k

-bit answers, zero error needs

2^k-1

verifications. The usual remedy is to solve related source tasks, either all first, as a curriculum does, or interleaved with verification. We price this remedy in information and in calls. With an exact verifier, the least causal information that any interleaving of source calls and

n

verifications needs to succeed with probability

s

is a list rate-distortion function, attained by one observation before any verification. It lower-bounds the expected number of binary source calls, which designed sources meet within

1+\log_25

calls for unique answers and within a logarithmic term in general, where no additive constant suffices. With an exact verifier and fixed sources, moving every call before the first verification preserves all hard caps on calls, although interleaving can save unboundedly many expected calls; under a noisy verifier, source-first protocols can lose unbounded factors in information and in error. For linear banks over

\mathbb{F}_2

, optimal accuracy has a closed form, and after a polynomial-time reduction the budget profile is computable in time

2^{O(h^2)}\operatorname{poly}(J,k+h)

for

J

sources and nuisance dimension

h

. In these banks, for zero error under a hard cap, the calls beyond the rounded-up information price are exactly those spent on nuisance. Every numbered result apart from two clauses about the planner is machine-checked in Lean 4, assuming two published results. Used as a ruler, the frontier shows a small transformer using all delivered bits at latent dimension

5

and none at

11

within fixed training budgets; in a test with predictions recorded before training, low XOR degree of the target bits did not suffice for their use.

Hazar Yueksel

Information-Theoretic Lower Bounds Query Complexity

Ask PDF

Oct 8, 2026cs.LG

Recovery Guarantees for Posterior Sampling of One-Bit Compressed Sensing

We study the sample complexity of noisy one-bit compressed sensing for signals drawn from a prior distribution. By characterizing the effective distributional complexity of the prior via its approximate covering number, we prove that posterior sampling achieves accurate recovery with high probability when the number of measurements scales with the logarithm of the approximate covering number, up to a one-bit separation gap factor. This upper bound is robust to learned prior mismatch. Specifically, we show that posterior sampling with an approximate prior remains reliable, provided that the learned prior distribution is sufficiently close to the true signal distribution in Wasserstein distance. In addition, we establish a sample complexity lower bound for any reliable method of noisy one-bit compressed sensing, showing that our upper bound is nearly matched in its main prior dependent term. To approximate the ideal posterior sampling process for real world scenarios, we instantiate posterior sampling through a plug-and-play algorithm with diffusion priors. Experiments on the FFHQ and ImageNet datasets demonstrate the effectiveness of our proposed approach.

Jing Ma, Yujia Wu, Zhaoqiang Liu

University of Electronic Science and Technology of China

Compressed Sensing Sample Complexity Posterior Sampling Information-Theoretic Lower Bounds

Ask PDF

Oct 8, 2026cs.LG

New Lower Bound and Upper Bounds on the Regret for Online Sparse Linear Regression

We study online sparse linear regression (OSLR) where any algorithm is restricted to accessing only

b

out of

d

attributes per instance for prediction and

b_0\geq 0

additional attributes after prediction, which was proved to be NP-hard. Previous work focused on designing computationally efficient algorithms under regularity assumptions, but did not characterize its information theoretic complexity. In this work, we give the first lower bound on the minimax regret of OSLR and design algorithms with better upper bounds without regularity assumptions. We characterize how minimax regret scales with problem-dependent parameters, capturing the information theoretic complexity of OSLR.

Xiaofeng Cao, Junfan Li, Langzhang Liang +2

School of Computer Science and Technology, Tongji University, Shanghai, China · School of Computing and Artificial Intelligence, Shanghai University of Finance and Economics, Shanghai, China · AI3 Institute, Fudan University and Shanghai Innovation Institute +2

Linear Regression Minimax Regret Information-Theoretic Lower Bounds

Ask PDF

Oct 8, 2026stat.ML

A General $\widetildeΩ(\sqrt{T γ_T})$ Lower Bound for Kernel Bandits

The kernel bandit problem consists of sequentially optimizing an unknown function with noisy feedback, where the function has bounded norm in a given Reproducing Kernel Hilbert Space (RKHS). A central quantity in the regret analysis of kernel bandits is the maximum information gain

γ_T

. In particular, the best existing upper bounds scale as

\sqrt{Tγ_T}

up to log factors, and nearly-matching lower bounds have been derived for specific kernels such as squared exponential and Matérn. However, lower bounds for general kernels are lacking, thus making it unclear in what generality the upper bounds are near-optimal. In this paper, we establish a general

Ω(\sqrt{Tγ_T/\log T})

minimax regret lower bound for non-constant continuous kernels on compact domains, establishing near-optimality (within log factors) in a very general sense. We show that the log factor appearing in this bound is unavoidable in general, but that it can be removed under certain conditions. Among other things, our findings imply that the minimax-optimal scaling is exactly

Θ(\sqrt{Tγ_T})

(i.e., within constant factors) for the Matérn-

ν

kernel with

ν\in (0,2)

γ

-exponential kernel with

γ\in (0,2)

, and certain piecewise-polynomial kernels.

Chenkai Ma, Jonathan Scarlett

National University of Singapore

Minimax Regret Multi-Armed Bandits Information-Theoretic Lower Bounds

Ask PDF

Oct 6, 2026cs.LG

An Accuracy-Information Tradeoff for Loss-Difference Conditional Mutual Information

Loss-difference conditional mutual information (ld-CMI) uses the smallest of the standard observations in the supersample hierarchy of generalization bounds: it measures what a learner's loss differences reveal about which candidate of each pair it was trained on. Accuracy is known to force information into the model; data processing does not carry such lower bounds to losses. We show, by bounding three moments of the loss differences, that accuracy also forces ld-CMI. For linear predictors with a smooth convex loss of nonzero slope at zero, such as the logistic loss, plus a regularizer whose curvature and growth are both of power

r\ge2

, on product distributions over a scaled sign cube in dimension at least linear in

n

, every proper learner with expected excess risk at most

\varepsilon

on these distributions at the optimal sample size

n\asymp\varepsilon^{-2+2/r}

has worst-case ld-CMI of order

n

bits, and

Θ(n/(1+(τ/\varepsilon)^2))

bits under Gaussian noise of standard deviation

τ

on the loss differences. The same holds without a regularizer, at

n\asymp\varepsilon^{-2}

. Consequently, range-scaled ld-CMI bounds cannot vanish on these distributions, although every proper learner's generalization gap is

O(n^{-1/2})

. We also show that model-level information does not determine noisy loss-difference information, and that the growth, slope and dimension conditions are needed, the last up to a logarithm.

Hazar Yueksel

Statistical Learning Theory Information-Theoretic Generalization Bounds Information-Theoretic Lower Bounds Mutual Information

Ask PDF

Sep 30, 2026cs.CV

Structural Limits of the Information-Theoretic Uncertainty Decomposition

Uncertainty estimation in machine learning typically decomposes uncertainty into aleatoric uncertainty (AU) and epistemic uncertainty (EU) using the standard information-theoretic framework. However, in practice, two critical issues arise: entanglement (AU and EU are highly correlated) and epistemic collapse (EU magnitude shrinks with increasing model capacity). We analyze this framework on a functional level and discover that significant portions of the assumed AU, EU range are infeasible in finite settings, and cannot be attained with any class probabilities. We characterize how this infeasible region scales with the number of classes and Monte Carlo samples

N

(e.g., from ensembles with

N

members), revealing it is bounded by

\text{AU} \leq \log(2)/N

. Crucially, the infeasible region's boundary helps explain epistemic collapse: when model confidence is high,

\text{AU} > \text{EU}

is guaranteed by this fundamental structural limitation. Our findings show that increasing ensemble size mitigates epistemic collapse by reducing the infeasible area. Lastly, we caution against interpreting AU and EU as independent quantities in low AU regimes, since we show they are coupled when

\text{AU} \leq \log(2)/N

Jakob Lønborg Christensen, Christian F. Baumgartner, Morten Rieger Hannemose +2

DTU Compute Technical University of Denmark · Faculty of Health Sciences and Medicine University of Lucerne

Aleatoric Uncertainty Information-Theoretic Lower Bounds Uncertainty Decomposition Epistemic Uncertainty

Ask PDF

Sep 29, 2026stat.ML

Lower Bounds for Linear-Oracle Online Learning

Can a constant number of linear minimizations per round improve on the

T^{3/4}

regret rate of online Frank-Wolfe on general convex sets? Weibel et al. conjectured that fixed-coefficient methods cannot. We prove their conjecture and extend the lower bound to every deterministic learner in an oracle-only model. The learner receives an initial feasible point and a diameter bound, and must remain feasible on every domain consistent with its oracle replies. For

T

rounds, at most

b

calls between decisions, diameter bound

D

, and gradient norm bound

L

, we construct an instance in dimension

d=2b(T-1)+1

with regret at least

2^{-1/4}LDb^{-1/4}T^{3/4}

. The adversary fixes the domain, initial point, deterministic tie rule and linear losses before play. The vertices form a path on which every point available before a decision has zero current loss, while the final vertex has negative loss on every round. For constant

b

, the result matches the known upper rate for dimension-independent guarantees. For one-call fixed schedules with a nonzero coefficient on the newest gradient, a second construction gives regret at least

3LDT^{3/4}/4

with unique minimizers at every issued query. Exact-arithmetic certificates for the tuned schedule of Weibel et al. closely match their finite-horizon numerical worst cases, with unique oracle replies.

Mohit Sinha

Online Convex Optimization Information-Theoretic Lower Bounds

Ask PDF

Sep 29, 2026cs.LG

A Sharp Transition in Data Reconstruction under Differential Privacy

Data reconstruction attacks have empirically been successful in recovering training samples from learned models, raising privacy concerns and motivating defenses with guarantees that remain valid against future threats. While differential privacy (DP) provides formal protection, choosing the privacy budget remains a challenge: small budgets severely reduce utility, but it is hard to quantify how large the budget can be without allowing accurate reconstruction. In this work, we study informed attackers who aim to reconstruct a single

d

-dimensional training sample from a

ρ

-zero-concentrated DP model, knowing all other training data. Our main contribution is to establish a sharp transition at

ρ\asymp d

for data reconstruction: on the one hand, we derive entropy-based lower bounds for any private mechanism and any attack, characterizing a set of target priors for which reconstruction is information-theoretically impossible for

ρ\ll d

; on the other hand, we analyze a simple attack on private linear regression with output perturbation, showing that reconstruction is practically feasible for

ρ\gg d

. Remarkably, the transition moves to

ρ\asymp s

for data lying in an

s

-dimensional subspace, demonstrating that the privacy budget guaranteeing adequate protection must be assessed in terms of the effective dimension of the data. We validate our findings via experiments on synthetic data and natural images (CIFAR-10, ImageNet).

Max Cairney-Leeming, Simone Bombari, Marco Mondelli

Institute of Science and Technology Austria

Adversarial Attacks Differential Privacy Information-Theoretic Lower Bounds

Ask PDF

Sep 28, 2026cs.LG

QAM: Quadratic-Accurate Checkpoint Merging via Sequential Consistency

Saved checkpoints record states along a training trajectory, but generally do not determine the updates at states that would be visited under a different schedule. We study how accurately these checkpoints can reconstruct the endpoint of a sequential reference with prescribed update strengths. Under a common local transition model, two checkpoint-index moment conditions characterize all convex merges that agree with this reference through second order. We then prove an information limit that for nondegenerate profiles, no algorithm using only a fixed-length gradient-descent (GD) history with step size

h

can achieve

o(h^3)

endpoint error uniformly over a fixed class of smooth, strongly convex losses. The lower bound follows from two losses with identical GD checkpoint histories but sequential reference endpoints separated by

Ω(h^3)

. \textbf{Quadratic-Accurate Merging} (QAM) achieves a matching uniform

O(h^3)

endpoint error bound. Its explicit coefficients also define the unique profile-dependent merge that exactly matches the sequential GD reference across all fixed quadratic objectives. Across two public Adam checkpoint trajectories (SmolLM3-3B and OpenEuroLLM-Prelude-9B), three windows and three profiles per model, and 15 tasks, QAM shows mixed results for short windows and broader advantages over \textbf{Warmup-Stable and Merge} (WSM) for longer windows. Matched-moment GSM8K diagnostics further show that local consistency alone does not fully determine downstream scores. These results characterize the reconstruction limits of saved histories, provide a coefficient rule that attains the optimal rate, and assess its practical utility.

Shihao Wang, Rui Kong, Xinran Chen +7

University of Wisconsin – Madison · Baidu Inc. · University of Arizona +3

Language Model Merging Model Merging Information-Theoretic Lower Bounds

Ask PDF

Sep 22, 2026quant-ph

When are bosonic Gaussian states classical to learn?

A fundamental question in physics is: When does classical behavior emerge from quantum systems? Bosonic Gaussian states provide a natural setting to explore this quantum-classical boundary, as they capture both the classical field behavior and the intrinsic quantum nature of light. Here, we address this problem from a learning-theoretic perspective by asking: When are bosonic Gaussian states classical to learn? That is, under what conditions (if any) can an n-mode bosonic Gaussian state be learned with as few samples, and with operations as simple, as are needed to learn a classical 2n-variate Gaussian distribution? We establish a smooth crossover in learnability governed by the state's thermal fluctuations: - Cold Gaussian states are non-classical to learn: When the covariance matrix satisfies

Σ\le(\frac12+O(\frac1n))I

, i.e. close to the vacuum covariance, tomography under single-copy (i.e., non-entangled) measurements fundamentally requires

Ω(n^3)

copies, strictly exceeding the sample complexity

Θ(n^2)

of learning classical Gaussian distributions. We show that this hardness persists even when few-copy entangled measurements are allowed. - Warm Gaussian states are classical to learn: When thermal fluctuations exceed the vacuum noise, parameterized by

Σ\ge(\frac12+ν)I

for any parameter

ν>0

, we prove that single-copy tomography requires

N=Θ\left(n^2\min(n,1+ν^{-1})\right)

copies. This bound is tight and is achieved by simple, non-adaptive, unentangled heterodyne measurements. Crucially, for

ν=Ω(1)

, the sample complexity drops to

Θ(n^2)

, matching the classical case. Our results tightly characterize a quantum-to-classical crossover in the learnability of bosonic Gaussian states, reveal a novel connection between fundamental physics and statistical learning theory, and have implications for real-world sensing experiments.

Senrui Chen, Antonio Anna Mele, Francesco Anna Mele +1

Institute for Quantum Information and Matter, Caltech, Pasadena, CA 91125, USA · Dahlem Center for Complex Quantum Systems, Freie Universität Berlin, 14195 Berlin, Germany

Quantum State Tomography Statistical Learning Theory Information-Theoretic Lower Bounds

Ask PDF

Sep 21, 2026cs.IT

On the Information-Theoretic Limits of Latent-Space Watermarking Through Pretrained Generators

We study latent-space watermarking through a pretrained generator using a prescribed latent-to-output stochastic mapping, called the renderer. A watermark encoder selects the latent input using a message and secret key. For every message and semantic context, the released output must have exactly the desired conditional output distribution. For finite alphabets, we derive rate--key inner and outer bounds and characterize the coding and coordination requirements for realizing watermark communication through the prescribed latent interface. When the target output distribution of the generator uniquely determines the corresponding latent input distribution through the renderer, a strengthened converse yields the capacity region; the same region governs explicit preservation of the pretrained latent distribution. We extend the analysis to general jointly Gaussian models and identify a sufficient statistic of the latent that captures both the watermark-bearing information available at the generated output and the latent coordination required to preserve its target distribution. For the vector Gaussian model, we further characterize the optimal allocation of the secret-key resource across the resulting modes. Finally, we turn to an emerging robustness threat that is particularly natural in generative watermarking: an adversary can regenerate the released sample to obtain a fresh realization of the same underlying content while attenuating or destroying the embedded watermark. We incorporate this robustness axis into our framework and characterize the one-pass compound capacity of the scalar Gaussian model when the semantic context is known to the encoder but hidden from the detector, while the regeneration attack may depend on that context. Extending the analysis to multiple rounds of repeated canonical regeneration, we characterize the resulting watermark-capacity decay.

Jinwan Jeon, Minju Lee, Sung Hoon Lim

Hallym University, CHUNCHEON-SI, GANGWON-DO, South Korea

Robust Watermarking Information-Theoretic Lower Bounds

Ask PDF

Sep 14, 2026cs.LG

Learning CNF Formulas from Uniform Random Solutions: Near-Tight Sample Complexity for Valiant's Algorithm

We revisit Valiant's algorithm (Commun. ACM'84) for learning

n

-variable CNF formulas with clause size

k

and variable degree

d

from i.i.d. uniform random solutions in the local lemma regime. For fixed

t\geq1

, under

k\gtrsim(1+1/t)\log d

, Valiant's algorithm achieves total variation error

\varepsilon

with

\widetilde{O}(n^{\lceil t \rceil}/\varepsilon)

sample complexity. For

t>1

, we prove a matching lower bound for Valiant's algorithm. At

t=1

(covering

0<t<1

), we show Valiant's algorithm has optimal sample complexity up to logarithmic factors by an information-theoretic lower bound

\widetildeΩ(n/\varepsilon)

Weiming Feng, Yixiao Yu, Yiyao Zhang

School of Computing and Data Science, The University of Hong Kong. · State Key Laboratory for Novel Software Technology, New Cornerstone Science Laboratory, Nanjing University.

Boolean Function Learning Sample Complexity PAC Learning Information-Theoretic Lower Bounds

Ask PDF

Sep 9, 2026cs.LG

A positive resolution of the gap-entropy conjecture

We prove the gap-entropy conjecture for fixed-confidence best-arm identification with independent unit-variance Gaussian arms, means in

[0,1]

, and a unique optimal arm. For each suboptimal arm

i

, let

Δ_i=μ_*-μ_i

be its gap from the optimal mean, and write

H=\sum_{i\ne *}Δ_i^{-2}

. Let

p_r

be the fraction of

H

contributed by arms with

2^{-(r+1)}<Δ_i\le2^{-r}

, and let

\mathrm{Ent}(I)=\sum_{r:p_r>0} p_r\log(1/p_r)

. Among all algorithms that identify the optimal arm with probability at least

1-δ

on every Gaussian instance, the optimal expected number of samples on a given instance, averaged over all permutations of the arm labels, is within absolute constant factors of

H(\log(1/δ)+\mathrm{Ent}(I))

. Moreover, there is an algorithm, independent of the instance, whose expected number of samples is bounded by a constant multiple of this quantity plus

g^{-2}\log\log(e^e/g)

, where

g=\min_{i\ne *}Δ_i

is the gap to the closest competitor.

P. M. Aronow, Nathan Kallus, Patrick Lopatto

Best-Arm Identification Information-Theoretic Lower Bounds

Ask PDF

Sep 9, 2026quant-ph

Optimal Low-Rank Quantum State Tomography with Bounded-Sample Joint Measurements

We determine the optimal sample complexity of low-rank quantum state tomography when each measurement may act jointly on at most

t

samples. For sufficiently small

\varepsilon

, estimating an unknown state on

\mathbb{C}^d

of rank at most

r

to trace norm error

\varepsilon

with constant success probability requires, and is achievable with,

Θ\left(\frac{dr}{\varepsilon^2}\mathop{\mathrm{max}}\left\{1,\frac{r}{\sqrt{t}}\right\}\right)

samples. The lower bound allows the protocol to choose each joint measurement adaptively using all previous classical outcomes; the matching upper bound is nonadaptive. Thus joint measurements on at most

t

samples improve the complexity of algorithms making single-sample measurements by at most a factor

\sqrt{t}

. Further, measuring order

r^2

samples jointly is necessary and sufficient to attain the unrestricted collective rate. For the lower bound, we vary the support of a state with fixed uniform spectrum and bound the Fisher information trace of every joint measurement on

t

samples. The adaptive Fisher chain rule and the van Trees inequality then give the trace norm lower bound. For the upper bound, we construct and analyze a nonadaptive tomography protocol based on a Gaussian joint measurement. An explicit second moment identity and a conditional Gaussian law outside the state's support give a rank-dependent error analysis, yielding the matching rate.

Ashwin Nayak, Xingyu Zhou

Department of Combinatorics and Optimization, and Institute for Quantum Computing, University of Waterloo. · Department of Computer Science, University of British Columbia.

Quantum State Tomography Information-Theoretic Lower Bounds

Ask PDF

Sep 8, 2026math.OC

Oracle Complexity of Stochastic Fixed-Point Equations with Nonexpansive Maps

We study the oracle complexity of computing a point with small fixed-point residual

\|T(x)-x\| \leq ε

, for a general norm

\|\cdot\|

and a self-map

T

of a compact convex set. We study this problem in the setting where

T

is nonexpansive with respect to the same norm

\|\cdot\|

and accessed via an unbiased stochastic oracle with bounded variance

σ^2

. We provide an algorithm that solves such instances for any norm with a weak Rademacher type

q > 1

, with high probability. The algorithm is based on a recursive anchoring technique. For type-

2

spaces, such as

\ell_p

-spaces for

p \in [2, \infty]

, our algorithm attains stochastic oracle complexity

\tilde O(σ^2 ε^{-3} + ε^{-1})

. We further prove a near-matching lower bound (i.e., matching up to poly-log factors) for such

\ell_{\infty}

-norm instances in high dimensions. Our lower bound holds against any randomized algorithm that succeeds with constant probability. It further extends to settings with ``sparse'' noise, where variance measured with respect to any

\ell_p

norm is of the same order, ruling out the possibility of improving oracle complexity as a function of

\varepsilon

by measuring variance in a non-matching

\ell_p

norm.

Jelena Diakonikolas, Cristóbal Guzmán, David Martínez-Rubio

Department of Computer Sciences, University of Wisconsin-Madison · Institute for Mathematical and Computational Engineering, Faculty of Mathematics and School of Engineering, Pontificia Universidad Católica de Chile, Santiago, Chile · IMDEA Software Institute, Madrid, Spain

Oracle Complexity Stochastic Approximation Information-Theoretic Lower Bounds

Ask PDF

Sep 8, 2026cond-mat.stat-mech

Speed Limit for Information Acquisition in Stochastic Learning Dynamics

Neural networks acquire internal representations through learning. In this work, we formulate stochastic gradient descent (SGD) as a Markovian stochastic process and derive a Fisher-information flow speed limit that bounds the rate at which trainable parameters can acquire information about latent variables in the data-generating process. The resulting inequality decomposes the information flow into drift and noise contributions, thereby quantifying the roles of deterministic learning forces and SGD-induced fluctuations from an information-theoretic perspective. We verify the bound in analytically tractable basis-function linear regression, where the information budget predicted by the bound reproduces the ordering and characteristic time scales with which different latent variables are encoded in the learned parameters. These results establish Fisher-information speed limits as a quantitative framework for diagnosing when and how different aspects of the data-generating mechanism are acquired during stochastic learning.

Shuta Kobayashi, Andreas Dechant

Department of Physics, Kyoto University, Kyoto 606-8502, Japan

Neural Network Training Dynamics Information-Theoretic Lower Bounds Stochastic Gradient Descent

Ask PDF

Sep 7, 2026cs.IT

A Fundamental Limit in Decentralized Decision-Making

In decentralized decision-making, several agents connected according to a network graph aim at solving a classification problem by collecting streaming observations. Due to decentralization, they run an iterative algorithm where, at each iteration, they can only exchange information locally with their neighbors. While decentralized estimation solutions have been shown to match the performance of optimal centralized systems, we show here that surprisingly this conclusion does not hold for decentralized decision-making. Specifically, we prove that the error probability for the best decentralized decision strategy exhibits an irreducible loss with respect to the optimal centralized classifier. This result establishes a fundamental limit for the performance of any decentralized decision strategy. We obtain an analytical relation showing that this limit is related to the interplay between decentralization and classification. The first aspect appears through the distances between the nodes in the graph, while the second aspect plays through the moment generating functions of the likelihood ratios that describe the decision problem. By applying the derived closed-form relation to different network topologies and inference problems, we observe some interesting and perhaps unexpected behavior emerging. In particular, we characterize the scaling law (with the network size) for the loss over popular network topologies, showing that the error probabilities might differ by orders of magnitude; and we examine how performance is affected by the relative distance between informative and uninformative agents over the graph.

Marco Carpentiero, Felice Scala, Vincenzo Matta +1

Department of Information and Electrical Engineering and Applied Mathematics (DIEM), University of Salerno, I-84084 Fisciano (SA), Italy · Institute of Electrical and Micro Engineering, EPFL, CH-1015 Lausanne, Switzerland

Classification Distributed Inference Information-Theoretic Lower Bounds

Ask PDF

Aug 31, 2026cs.IT

Minimax bounds for watermarked and masked recursive discrete distribution estimation

Watermarking has been proposed as a way to identify synthetic samples in estimation settings where no metadata is available to distinguish them from real samples, but its precise effects remain unexplored. In the absence of a distinguishing mechanism, it has been shown that adding synthetic samples significantly reduces the marginal efficacy of new real samples. In this work, we study the minimax loss of such recursive discrete distribution estimation in the presence of watermarks in contrast to the unassisted and oracle-assisted losses. When the fraction of real samples vanishes asymptotically, we provide a lower bound that shows that it is impossible to improve performance by adding watermarks unless the false negative rate of detection also vanishes. Additionally, we show that in most regimes, the worst-case losses of a sequence of simple deterministic estimators match the corresponding lower bounds up to constants. Finally, we propose masking, a randomization procedure that narrows the gap in the remaining regimes to a Jensen gap. We conjecture that a tighter lower bound argument can close this gap.

Millen Kanabar, Michael Gastpar

School of Computer and Communication Sciences, EPFL, Switzerland

Dataset Watermarking Minimax Estimation Density Estimation Information-Theoretic Lower Bounds

Ask PDF

Aug 31, 2026cs.IT

Strengthening Recursive Constructions for Zero-Error Shannon Capacity

The exact Shannon capacity is unknown for every odd cycle beyond the five-cycle

C_5

, making odd cycles a central open problem in zero-error information theory. Improving the known lower bounds requires constructing large independent sets in strong powers of these graphs. Recent AI-assisted work has produced a rapid sequence of improvements: building on the construction of Itty et al., Gao developed a recursive product construction for combining structured independent sets, and Buys, Polak, and Zuiddam (BPZ) subsequently strengthened this through a richer recursion framework. We continue this line of AI-assisted exploration and introduce a heterogeneous refinement of these constructions. The central observation is that the usefulness of an intermediate construction depends not only on the size of its current main independent set, but also on the auxiliary structure it carries into subsequent recursion. Consequently, different parts of that auxiliary structure need not use the same independent set, and different occurrences in a recursion need not use the same intermediate representation. We formalize this for Gao's binary product and derive explicit propagation rules showing how heterogeneous choices strengthen the resulting gadget while leaving its current code size unchanged, then extend the principle to the more general BPZ framework, tailoring constructions to the distinct roles they play within the recursion. Applying these refinements to the seven-cycle

C_7

, we obtain an independent set in

C_7^{\boxtimes 500}

yielding

Θ(C_7)\ge 3.25883262\ldots

, improving the best known lower bound. Beyond the numerical gain, the results illustrate a general principle for recursive zero-error constructions: intermediate structures with the same dimension and current code size can have different downstream value depending on where and how they are used in the recursion.

Ravi Tandon

School of Electrical, Computing and Software Engineering, University of Arizona, Tucson, AZ 85721, USA.

Combinatorial Optimization Information-Theoretic Lower Bounds

Ask PDF

Aug 27, 2026cs.IT

Sharp Minimax Regret for Infinite-Memory Logistic Prediction

We determine the minimax cumulative log-loss regret of a finite-alphabet, exogenously driven source with genuinely infinite input memory: independent Rademacher inputs

(U_t)

are observed sequentially and the next binary mark has logit

\sum_{j\ge1}θ_jU_{t+1-j}

, the unknown coefficients obeying a summable envelope

|θ_j|\le r_j

\sum_jr_j\le B

. At horizon

T

, lag

j

can move the logit by at most

r_j

and is exercised in only

n_{T,j}=(T-j+1)_+

rounds, and the two limitations combine into the sum

Γ_T(r)=\sum_{j\le T}\log(1+n_{T,j}r_j^{2})

. One coordinate-localised Bayesian mixture achieves

R_T(r)\le CΓ_T(r)

for \emph{every} summable envelope with

C

universal. Our main result is a matching nonasymptotic converse for the canonical exponential and polynomial envelopes; its new ingredients are a modular finite-sample information bound for logistic experiments with an exogenous random design, and a conditioning estimate for the overlapping Toeplitz lag matrix obtained by exhibiting each off-diagonal Gram sum as a sum of independent Rademacher variables indexed by the edges of a forest, needing neither local asymptotic normality nor any spectral theorem for random Toeplitz matrices. So

Γ_T(r)

is the minimax regret scale here, giving

Θ(α^{-1}\log^{2}T)

for

r_j=Ae^{-αj}

and

Θ(T^{1/(2s)})

for

r_j=Aj^{-s}

s>1

--- the latter without the extra

(\log T)^{1-1/(2s)}

factor any window-truncation analysis pays. We also show memory decay cannot determine regret, and that a profile-scaled online Newton predictor attains

O_B(Γ_T(r))

in polynomial time per round.

Vaneet Aggarwal

Purdue University

Logistic Regression Bayesian Mixture Models Minimax Regret Regret Minimization Information-Theoretic Lower Bounds

Ask PDF

Aug 14, 2026cs.LG

Quantum Multi-Armed Bandits and Linear Bandits: Lower Bounds and Algorithms

We study quantum multi-armed bandits (QMAB) and quantum linear bandits (QLB), where the learner queries each arm or action through a quantum reward oracle or its inverse. Prior work gives algorithms over horizon

T

with regret

O(K\log T)

for QMAB with

K

arms and

O(d^2\operatorname{polylog} T)

for

d

-dimensional QLB. This leaves open the optimal dependence on

K

and

T

and whether the dependence on

d

can be further improved. In this work, we prove the first tight minimax regret bound of

Θ(K\log(1+T/K))

for QMAB and the first lower bound of

Ω(d\log(1+T/d))

for finite-action QLB, ruling out regret independent of

T

. Our lower bounds rely on a high-confidence single-arm quantum testing lower bound for distinguishing a fixed reward mean from an interval of alternatives. A bandit-to-testing reduction then lifts it to the QMAB lower bound, while a linear embedding gives the finite-action QLB lower bound. The matching QMAB upper bound is obtained using a tail bound for the Quantum Monte Carlo (QMC) estimator. For finite-action QLB, we propose a phased elimination algorithm that combines a low-bias low-variance quantum mean estimator with a small-support

G

-optimal design through a query allocation matched to the design weights. When the action set has size

\operatorname{poly}(d)

, its regret is nearly linear in

d

and matches our lower bound up to polylogarithmic factors.

Maoli Liu, Zhuohua Li, John C. S. Lui

The Chinese University of Hong Kong · Xidian University

Multi-Armed Bandits Information-Theoretic Lower Bounds

Ask PDF

Aug 13, 2026math.ST

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

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 underlying data-generating process, which are formalized in terms of informational bounds. In this work we examine intrinsic limits of data-driven decision systems from an information-theoretic and interaction-based perspective. We analyze minimal achievable error in classification through Fano-type bounds and precision limits in parametric estimation via the Cramér-Rao inequality, emphasizing that such limits depend on the underlying model rather than on algorithmic sophistication alone. We further discuss how implicit assumptions, such as independence, ergodicity, and distributional stability, affect the validity of inferential procedures. Building on interaction-based modeling principles, we review typical frameworks such as Markov Random Fields and potential based representations for encoding dependence mechanisms. We also describe decision systems, including LLM-integrated agent architectures, as feedback-driven stochastic processes where state-dependent dynamics may induce emergent macroscopic behavior. This perspective highlights the importance of having adequate models for the data as a prerequi- site for expanding predictive capability, and situates algorithmic learning within the informational limits imposed by the models.

Nestor R. Barraza, Gabriel Pena

Universidad Nacional de Tres de Febrero. Departamento de Ciencia y Tecnología. · Universidad de Buenos Aires. Facultad de Ingeniería.

Stochastic Linear Dynamical Systems Statistical Learning Theory Decision-Making under Uncertainty Information-Theoretic Lower Bounds

Ask PDF

Aug 2, 2026cs.CR

Why Formal Monitors Fail: Attack Distribution Entropy as a Coverage Bound for LTL-Based LLM Agent Safety

Runtime safety monitors based on Linear Temporal Logic (LTL) and finite automata (FSA) are increasingly deployed to intercept unsafe tool-call sequences in LLM agents. Yet the same monitor achieves 68-75% attack coverage on some model architectures and near-zero on others, with no explanation from capability scores, training data, or prompt design. We provide the missing theory. We prove that the recall of any fixed-invariant FSA monitor is bounded above by the concentration of the attack distribution: the fraction of attacks covered by the k most frequent trigger-completion patterns. When attacks concentrate (low Shannon entropy), a small fixed invariant set achieves high recall; when they disperse across many structurally distinct patterns (high entropy), no fixed invariant set of tractable size can, regardless of how the invariants were derived. We validate this entropy-coverage bound across eight frontier LLM architectures. GPT-class and DeepSeek backends yield highly concentrated attacks (H ~ 0.24 bits; one pattern covers 96%), explaining 68-75% recall; Gemini variants yield high-entropy distributions (H ~ 2.81 bits; 7 clusters each <= 7%), explaining near-zero recall (6-13%), invariant to architecture-matched retraining. Entropy accounts for 76% of variance in coverage (Pearson r = -0.87, p = 0.005, 95% CI [-0.98, -0.78]), holding under leave-one-out (r in [-0.91, -0.82]). We introduce a pre-deployment entropy test that predicts monitor coverage from a small attack sample, enabling architecture-aware monitor selection before deployment. The bound and test are architecture-agnostic and apply to any FSA-based runtime monitor over discrete action sequences.

Ruiyang Zhang

Ryonix Labs Inc. Flock.io

Formal Verification AI Agent Monitoring LLM Agent Safety Information-Theoretic Lower Bounds Runtime Verification

Ask PDF

Jul 21, 2026stat.ML

The Price of Hidden Curvature: An $\widetildeΩ (d^{5/4} \sqrt{T})$ Lower Bound for Bandit Convex Optimization

We establish a

\widetildeΩ(d^{5/4}\sqrt T)

lower bound on the minimax expected regret of stochastic bandit convex optimization of

1

-Lipschitz functions on the Euclidean ball. This presents the first nontrivial regret lower bound that grows faster than

d\sqrt{T}

for this problem, establishing that stochastic bandit convex optimization is fundamentally harder than linear bandits. The hard class of convex functions we construct takes the following form in dimension

2d

: for an action

a = (a^1,a^2) \in \mathbb{B}^{2d}_2

, each function is the scaled soft maximum of a "tube",

r^{-1} \| W^\star a^1 - \frac{r}{8\varepsilon} a^2 \|_2

(hyperparameterized by

\varepsilon,r

), and a squared distance function,

\frac12 \| a^1 - u^\star \|_2^2 - \frac12 \| u^\star \|_2^2

. Here,

W^\star \in \mathbb{R}^{d \times d}

is an unknown linear transformation, and

u^\star \in \mathbb{R}^{d}

is an unknown vector which must be learned to minimize the function. Observations are informative about

u^\star

only when the learner's action lies near the tube determined by

W^\star

, satisfying

a^2 \approx \frac{8\varepsilon}{r} W^\star a^1

: thus the learner must either find this tube without knowing

W^\star

, or spend observations learning useful directions of

W^\star

. Formally, our regret analysis exploits this tradeoff by bounding the posterior spread of Fisher information matrices obtained under an adaptive sequence of actions. Together, these ingredients give a sample complexity lower bound of

\widetildeΩ(d^{5/2}/\varepsilon^2)

to find an

\varepsilon

-optimal action, which translates to an

\widetildeΩ (d^{5/4} \sqrt{T})

regret lower bound. We also extend this lower bound to the unconstrained setting where the action space is

\mathbb{R}^d

Nived Rajaraman

Microsoft Research

Online Convex Optimization Minimax Regret Bandit Convex Optimization Information-Theoretic Lower Bounds

Ask PDF

Jul 19, 2026cs.IT

Rate-Distortion-Perception Theory: Redefining the Fundamental Limits of Information Representation

Classical rate-distortion (RD) theory has long established the fundamental limits of lossy compression by quantifying the minimum number of bits required to represent a source under a prescribed distortion constraint. However, widely used distortion measures such as mean-squared error often fail to capture perceptual quality or semantic validity, which are increasingly central in modern learning-driven applications. Rate-distortion-perception (RDP) theory extends the RD framework by introducing perception as a third fundamental axis, quantified via distributional similarity between the source and reconstructed signals, leading to the rate-distortion-perception function (RDPF). This tutorial provides a structured overview of the coding principles underlying perception-aware lossy compression and surveys recent achievability results under different randomness assumptions. It then presents a unifying optimization viewpoint for computing the RDPF as defined by Blau and Michaeli, for both discrete and continuous sources under broad families of perceptual constraints, including f-divergences, alpha-divergences, and Wasserstein-based metrics. Special attention is given to computational tools such as alternating minimization schemes, Newton-based methods, and convex optimization formulations, as well as to analytically tractable cases such as Gaussian sources and the perfect-realism regime. Unlike recent broad surveys that emphasize generative architectures and AI-empowered communication systems, this tutorial focuses on the coding-theoretic and computational machinery needed to characterize, compute, and interpret the RDP limits. Finally, the tutorial outlines promising research directions at the intersection of information theory, neural compression, robust source coding, and perception-aware networked control systems.

Photios A. Stavrou, Giuseppe Serra, Marios Kountouris

Learned Image Compression Rate-Distortion Theory Rate-Distortion Optimization Distortion-Perception Tradeoff Information-Theoretic Lower Bounds

Ask PDF

Jul 18, 2026cs.IT

Tight Sample Bounds for Renyi and Min-Entropy Estimation

Estimating entropy from samples is fundamental in information theory and property testing. Shannon entropy measures average uncertainty and can be estimated to constant additive accuracy over a

k

-symbol alphabet using

Θ(k/\log k)

samples. Min-entropy depends only on the most likely symbol. Both are special cases of order-

α

R'{e}nyi entropy,

H_α

. We characterize the sample complexity of estimating min-entropy and R'{e}nyi entropy for

k

and integer

α>1

; our lower bounds also hold for noninteger

α\ge1.001

. We prove that min-entropy estimation to constant additive accuracy has sample complexity

Θ(k\log k)

. The upper bound uses the largest empirical frequency and concentration via dyadic grouping. The matching lower bound hides a slightly heavier symbol at a uniformly random location. Thus, min-entropy requires

Θ(\log^2 k)

more samples than Shannon entropy and corrects a previously stated

Θ(k/\log k)

characterization. For every integer

2\leα\le c_0\log k

, we prove the matching fixed-accuracy bound

Θ_{c_0}(αk^{1-1/α})

. Previous results gave

Ω_α(k^{1-1/α})

for fixed integer

α>1

and

O_{c_0}(α^2k^{1-1/α})

for all integer

α>1

. Our upper bound analyzes an unbiased falling-factorial estimator based on

α

-way collisions, while a hidden-heavy-coordinate construction gives the matching lower bound and shows that the factor

α

is unavoidable. For every real

1.001\leα\le c_0\log k

, we prove the uniform lower bound

Ω_{c_0}(αk^{1-1/α})

. Finally, since

0\le H_α(p)-H_\infty(p)\le\log k/(α-1)

, min-entropy uniformly approximates

H_α

when

α

is a sufficiently large multiple of

\log k

. Combining this reduction with our min-entropy bounds gives

Θ_\varepsilon(k\log k)

sample complexity in the high-order regime.

Arman Adibi, Piotr Krysta

Department of Computer Science

Sample Complexity Information-Theoretic Lower Bounds

Ask PDF

Jul 18, 2026cs.LG

When Can Safe Controllers Adapt? Information before Commitment

Safe adaptive control is online adaptation under a safety guarantee on the learning trajectory itself. The controller may use any causal, history-dependent rule and act differently across environments as data arrive. Only its safety guarantee is uniform: the same rule must satisfy it under every initially plausible model. Performance is measured against a safe oracle that knows the realized model. Many finite-time analyses assume persistent excitation of the uniformly safe closed loop, so the data distinguish every pair of models requiring different control decisions. Under that assumption, feasibility is already settled; only the rate remains. We ask instead: Do the safety constraints permit such an informative experiment at all? While an alternative remains plausible, the controller must preserve a safe continuation under it. We call the first action that forecloses such a continuation commitment. Chance safety allows commitment only on an event rare under the alternative, and the evidence must arrive beforehand: the observation generated by the committing action is too late. We define precommitment information as the KL divergence between learner-visible laws stopped before commitment. Our main result is a causal reduction. The commitment rule determines (1) the probability that safety permits commitment under the alternative, (2) the target-side cost of remaining noncommittal, (3) and the information available when the decision is made. Bounded precommitment information therefore leaves a fixed fraction of the oracle gap unavoidable. If the gap is Ω(T), every uniformly safe policy has linear regret. We establish the obstruction in a constrained linear system with quadratic regulation cost. We also prove recovery in special cases and derive semidefinite upper certificates for deterministic linear-Gaussian systems.

Venkatesh Saligrama

Department of Electrical and Computer Engineering, Boston University, MA 02215

RL Exploration Optimal Control Adaptive Control Information-Theoretic Lower Bounds

Ask PDF

Jul 15, 2026stat.ML

Price of Fairness in Bandits: A Tight Minimax Characterization

In bandit problems, standard regret-minimizing algorithms treat exploration as an amortized cost, which can expose early participants to unfair ex-ante losses in settings such as clinical trials. Recent work addresses this by evaluating the sequence of per-round expected rewards through the generalized

p

-mean, interpolating between utilitarian welfare (

p=1

), Nash welfare (

p\to0

), and Rawlsian fairness (

p\to-\infty

). Although tight guarantees are known for

p\ge0

, the strictly fair regime

q=-p>0

remains unresolved because negative-power means are dominated by the smallest per-round rewards. For

σ

-sub-Gaussian rewards with nonnegative means, the best prior algorithm relied on uniform early exploration and achieved regret

O(k^{(q+1)/2}/\sqrt{T})

, while the only general lower bound was the classical

Ω(σ\sqrt{k/T})

. Thus it was unclear whether the extra dependence on

k

was intrinsic to strict fairness or an artifact of uniform exploration. We close this gap by identifying the exact polynomial price of strict fairness. Using a needle-in-haystack construction, we prove an algorithm-independent lower bound

Ω(σ\sqrt{k^{\max(1,q)}/T})

; for

q>1

, this shows that the penalty

k^{q/2}

is information-theoretically unavoidable. We then introduce \textsf{UCB-HARE} (Harmonic Anchored Rank Exploration), which replaces uniform exploration with an inverse-weighted harmonic rank schedule protected by a certified positive-mean anchor. Its regret is

\widetilde{O}(σ\sqrt{k^{\max(1,q)}/T})

, matching the lower bound up to logarithmic factors. Experiments on synthetic instances confirm that \textsf{UCB-HARE} improves over uniform-exploration baselines, with gains increasing as

q

grows.

Dhruv Sarkar, Soumyadeep Dutta, Sayak Ray Chowdhury

1Indian Institute of Technology Kharagpur · 2Mohamed bin Zayed University of Artificial Intelligence · 3Indian Institute of Technology Kanpur

Multi-Armed Bandits Minimax Regret Fair Resource Allocation Algorithmic Fairness UCB Algorithms Information-Theoretic Lower Bounds

Ask PDF

Jul 14, 2026cs.CR

Watermark Forensics for Generative Models: An Information-Theoretic Perspective

A watermark in a generative model's output is usually asked only whether a text is machine-made. The same mark can do more: attribute it to the user who produced it, extract a hidden payload, or localize the part that survives editing. These form a forensic ladder, and we ask what each rung costs in the sample length

n

. One object organizes the answers. Let

S

be the secret the mark carries (a user's identity or payload), and let the information profile

ν(t)=I(S;X_t\mid X_{<t})

record how much the

t

-th token reveals about

S

given the earlier ones. Its total mass pays for attribution and extraction; how that mass is spread pays for localization; and detection alone is paid for not by information but by presence, the distance from the marked to the unmarked distribution. The literature's two quality models, a mark subtle on every token and one that stamps a few tokens loudly, are two incomparable ways of capping this profile. Our main theorem settles the ladder's entropy column. For statistically distortion-free schemes, attributing a text to one of

N

users costs

Θ(\log N/h)

tokens over every stationary-ergodic source of entropy rate

h

, sharp to a

(1+o(1))

factor: to our knowledge the first tight entropy-rate law for multi-user attribution (via exact alignment). The natural collision-counting analysis overcharges without bound; only a decoder thresholding each candidate by its own realized surprisal attains the rate while almost never implicating an innocent user. A matching converse makes the law two-sided, and extraction of an

\ell

-bit payload costs

Θ(\ell/h)

. Two gaps are real, not modeling artifacts: a

Θ(\log N)

-token window in which a text is provably machine-made yet unattributable, and a footprint-resolution uncertainty principle. Experiments on GPT-2, Pythia-410M, and Qwen2.5 recover the predicted constants.

Xiaoyu Li, Zheng Gao, Xiaoyan Feng +3

University of New South Wales · 2Griffith University

Text Watermarking LLM Watermarking Robust Watermarking Information-Theoretic Lower Bounds

Ask PDF

Jul 13, 2026cs.LG

Fundamental Limitations of Fixed-Budget Best-Arm Identification

In fixed-budget best-arm identification, also known as ranking and selection, an algorithm has a sampling budget to distribute across

K

arms. Each sample provides noisy feedback about that arm's mean, and the goal is to identify the arm with the largest mean. A common performance benchmark is the static oracle: a non-adaptive strategy that knows the means in advance and chooses fixed sampling proportions to maximize the exponential decay rate of the probability of incorrect identification. Several adaptive algorithms have been constructed such that their sampling proportions converge to the static oracle proportions. However, it has remained open whether any algorithm could match the static oracle's error decay rate uniformly across all problem instances. We answer this in the negative. For any

K\ge 3

and for rewards drawn from any one-parameter natural exponential family, we show that for any algorithm, there is at least one instance where the error decay rate is at most

\left(1 + \frac{\log(K)}{8}\right)^{-1}

times that of the static oracle. This also answers the open question posed by Qin (2022), showing that fixed-budget best-arm identification does not admit a complexity.

Motti Goldberger

Yale University

Multi-Armed Bandits Best-Arm Identification Information-Theoretic Lower Bounds

Ask PDF

Momentum

Related topics

Latest papers 53