Minimax Estimation

Follow this topic Ask about this topic

Momentum

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

Jul 13Week of Sep 28

Latest papers 50

Jun 30, 2026math.ST

Sample Complexities of Estimating Gumbel--Max Watermark Proportions with and without Reduction to Pivotal Statistics

Watermarking promises statistical traceability of large language model (LLM) uses, but real documents rarely arrive as purely human-written or purely LLM-generated. This motivates a quantitative question beyond detection: what proportion of a document is generated from a pre-specified watermarked LLM? We study this watermark proportion estimation problem under the Gumbel--max watermarking mechanism, treating the next-token prediction distributions as unknown and arbitrary nuisance parameters subject to a non-degeneracy condition. We compare two observation regimes: in the full observation regime, the estimator observes the pseudorandom vector and the selected token at each position; in the more prevalent setting of pivotal reduction, it observes only a scalar pivot, which follows a one-dimensional Uniform--Beta mixture distribution. Under pivotal reduction, we develop a Laguerre-polynomial estimator and establish a matching information-theoretic lower bound for the sample complexity. For full observation, we introduce an event-counting estimator and show a matching lower bound, yielding a substantially smaller sample complexity. As our results imply, although reducing to pivotal statistics is an elegant and prevalent choice, it is not always sample-efficient for estimating the proportion of watermarks.

Shuwen Chai, Qiaosen Wang

Northwestern University · University of Chicago

Minimax Estimation LLM Watermarking

Jun 29, 2026cs.LG

The Fundamental Limits of Valid Transport Map Estimation

Many modern generative modeling methods, including diffusion models, normalizing flows, and flow matching, estimate transport maps or plans between distributions without explicitly targeting an optimal transport (OT) map. In applications like generative modeling, the transport cost itself is irrelevant, and this makes it natural to target maps which are more tractable from either a statistical or computational standpoint. In this short note, we formalize the task of estimating any valid transport map in a rigorous minimax framework. One consequence of this framing is that it yields sample complexity lower bounds for any method whose learned object is evaluated as a transport map or plan, including flow matching and diffusion-based generative models, in settings where direct analysis would be challenging due to the analytic complexity of the methods and their target maps. We observe that, under standard, though strong, stability assumptions from the OT literature, estimating any valid transport map is statistically as hard as estimating the OT map. We complement these results with some examples showing that when these stability assumptions fail, alternative transport maps can be learned substantially more accurately than the OT map. Our minimax framing provides a rigorous foundation for understanding the statistical limits of modern transport-based generative methods and clarifies when targeting sub-optimal maps can provide real statistical advantages.

Sivaraman Balakrishnan

Department of Statistics and Data Science† · Machine Learning Department‡

Minimax Estimation Generative Modeling Optimal Transport

Jun 26, 2026stat.ML

Adversarial Contamination Meets Hard Thresholding: An Iterative Algorithm with Signal Adaptivity and Minimax Optimality

Pervasive data contamination -- stemming from measurement errors, outliers, or adversarial corruption -- has motivated the development of robust statistical methods. In this context, we propose a two-stage Adversarial Contamination-resistant Iterative Hard Thresholding (AC-IHT) algorithm for high-dimensional regression with contamination. Our nonconvex algorithm achieves minimax near-optimal (up to logarithmic terms) estimation by iteratively updating the coefficient vector and the contamination vector with different thresholding scales. We further demonstrate that our AC-IHT estimator is signal-adaptive: under proper signal conditions, it adaptively attains a sharper estimation rate and more accurate support recovery. Moreover, it enjoys the strong oracle property, laying a theoretical foundation for asymptotic inference. Numerical experiments confirm its superior finite-sample performance. Finally, we discuss theoretical extensions of the proposed procedure to generalized linear models and to heavy-tailed noise settings.

Shixiang Liu, Hanming Yang

School of Statistics, Renmin University of China · Institute of Statistics and Big Data, Renmin University of China

Robust Regression Sparse Recovery Adversarial Robustness Minimax Estimation Data Contamination Robust Estimation

Jun 25, 2026cs.DS

Fast algorithms for learning a Gaussian under halfspace truncation with optimal sample complexity

We study the fundamental problem of learning a high-dimensional Gaussian truncated to an unknown halfspace. Lee, Mehrotra and Zampetakis (FOCS'24) recently obtained the first polynomial time algorithm for this problem, but their resulting sample and time complexity bounds are not optimal. Under non-trivial truncation, for any target accuracy

\varepsilon > 0

and dimension

d

we give an efficient algorithm that uses

n = \tilde{O}(d^2/\varepsilon^2)

samples and learns the underlying Gaussian to error

\varepsilon

in total variation distance. Our algorithm is also fast: its runtime is dominated by the cost of computing the empirical covariance matrix. Both our sample and time complexity are optimal in terms of

d

and

\varepsilon

even without truncation: in this regard, we can learn a Gaussian under halfspace truncation for free. The key ingredient behind our result is a novel reinterpretation of the low-degree moments of the truncated Gaussian in terms of a relative truncation parameter. This relative truncation parameter uniquely determines the parameters of the untruncated Gaussian and enables direct parameter recovery. This reinterpretation allows us to circumvent the time intensive projected stochastic gradient descent procedure that is widely used in learning under truncation.

Haitong Liu, Deepak Narayanan Sridharan, David Steurer +1

ETH Zurich

Minimax Estimation Statistical Learning Theory

Jun 24, 2026cs.LG

Black-Box Assisted Regression: Phase Transitions and Minimax Optimality

Foundation models are often used as fixed black-box predictors for downstream tasks with limited labeled data, but their predictions may be biased and unsafe to trust blindly. We study this setting through black-box assisted nonparametric regression: a learner observes labeled samples and can query a fixed predictor

f_0

, while the target

f^*

is close to

f_0

in

L_2(P_X)

up to an unknown radius

δ

. We give a finite-sample minimax characterization showing a phase transition at

δ_c(n) \asymp n^{-β/(2β+d)}

, with leading risk

\min\{δ^2, n^{-2β/(2β+d)}\}

. We then analyze a Safe Residual Estimator: it learns a correction around

f_0

, initializes the residual head at zero so the initial predictor equals

f_0

, and uses holdout selection to revert to

f_0

when the learned correction is not supported by validation data. Here, "safe" means avoiding negative transfer, i.e., performing worse than the black-box predictor alone. The estimator matches the leading minimax term up to an additive validation-selection cost. Synthetic regression experiments verify the predicted phase transition, while CIFAR-100 with CLIP and AG News with Qwen3-8B provide practice-facing evidence that the same residual-correction tradeoff is useful beyond the formal squared-loss regression setting.

Yan Zhou

School of Mathematics and Statistics, Changsha University of Science and Technology.

Residual Learning Nonparametric Regression Minimax Estimation Learning-Augmented Algorithms

Jun 20, 2026cs.LG

On the Curse of Dimensionality in Private Sparse Covariance Estimation and PCA

We study high-dimensional differentially private (DP) covariance estimation in the operator norm, and principal component analysis (PCA), under

k

-row-column sparsity (

k

-RCS) of the covariance matrix. In the non-private setting, it is known that

\mathsf{poly}(k, \log d)

samples suffice to solve both of these problems. However, the only comparable result known under DP (Wang et al. 2021) requires

Ω(d)

samples under standard parameterizations of the problem. We investigate when this curse of dimensionality is inherent for sparse covariance estimation tasks under DP. On the upper bound front, we show that a

\mathsf{poly}(k, \log d)

sample complexity for PCA is possible under DP, if we also posit sparsity of the leading eigenvector. We complement this result with

\mathsf{poly}(d)

lower bounds under DP for both sparse covariance estimation and PCA, establishing an exponential gap between the private and non-private variants of these problems when

k = \mathsf{polylog}(d)

. To our knowledge, no such separation has previously been demonstrated for any sparse estimation problems in private high-dimensional statistics. Our techniques are flexible enough that they imply stronger lower bounds even for the well-studied problem of standard DP PCA, without sparsity assumptions.

Syamantak Kumar, Shourya Pandey, Purnamrita Sarkar +1

University of Texas at Austin

Principal Component Analysis Minimax Estimation Differential Privacy Covariance Estimation

Jun 18, 2026cs.LG

Optimal Deterministic Multicalibration and Omniprediction

A model is multicalibrated on a collection of group weights

G

if it is calibrated -- i.e. unbiased even conditional on its prediction -- not just overall, but also after reweighting contexts by each

g \in G

. It is a useful property for many downstream applications and is a basic desideratum of trustworthy machine learning. Before this work, all predictors known to attain the minimax-optimal

\widetilde O(\varepsilon^{-3})

sample complexity rate for

\varepsilon

-multicalibration were randomized, while deterministic predictors were known only with substantially worse sample complexity. Whether randomization is necessary for optimal sample complexity in multicalibration was explicitly asked by [CLNR26] and implicitly in several prior works. We resolve this open problem by giving a minimax-optimal multicalibration algorithm that outputs a deterministic predictor. We then generalize the algorithm to produce optimal deterministic predictors that satisfy outcome indistinguishability (OI) with respect to finite or finitely covered collections of tests. As an application, this also gives deterministic omnipredictors and panpredictors with optimal sample complexity, resolving open problems posed by [OKK25] and [BHHLZ25].

Georgy Noarov, Aaron Roth

University of Pennsylvania

Minimax Estimation Model Calibration Multicalibration

Jun 12, 2026cs.LG

A Complexity Measure for Active Learning in Multi-group Mean Estimation

We study a \emph{max-risk} objective for active learning in a multi-group mean estimation

d

-armed bandits: a learner adaptively allocates a budget of

T

samples across

d

groups to minimize the worst-case uncertainty index

\max_{k\in[d]}σ_k^2/n_k

, where

σ_k

is the standard deviation of the distribution of arm

d

, and

n_k

is the number of times arm

d

is sampled. We develop a local minimax framework and prove the first general lower bound for this objective, valid for any finite-variance hypothesis class. The bound separates difficulty into three orthogonal factors: a \emph{budget} term, a \emph{heteroscedasticity} index measuring how unevenly the uncertainty is spread across arms, and a model-dependent complexity measure, the \emph{Variance Local Curvature} (

\mathrm{VLC}

), which captures how much information a local change of variance creates inside the hypothesis class. For smooth classes, the

\mathrm{VLC}

is a reparametrization of a variance--Fisher information, with closed-form values for common families. Benchmarking against the strongest available upper bound shows near-optimality up to logarithmic factors in broad regimes, and pinpoints a systematic gap in highly heterogeneous instances. Our proof introduces two key ingredients: a loss-induced

\ell_1

geometry on the decision space, and a representation-based instance generator that reduces hard-instance construction to an explicit random matrix calculation.

Abdellah Aznag, Rachel Cummings, Adam N. Elmachtoub

Department of Industrial Engineering and Operations Research & Data Science Institute, Columbia University

Multi-Armed Bandits Active Learning Minimax Estimation Adaptive Sampling

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

Jun 5, 2026math.ST

A Temporal Spatial Minimax Rate for Smoothly-Varying Distributions in Wasserstein Space

We study the minimax rate of estimating a future value

μ_{t_n+h}

of a curve

t\mapstoμ_t

in the

2

-Wasserstein space

\mathcal{P}_2(\mathbb{R}^d)

from finitely many noisy snapshots of its past, under an adiabatic bound

\|\nabla_t^k v\|\le\varepsilon

on the

k

-th covariant derivative of the velocity field. Our central result is a unified temporal-spatial minimax lower bound: over regular, locally transport-rich subclasses, every estimator incurs

W_2

-risk with

M

-exponent

γ_d(k+1)/(k+1+γ_d)

,

γ_d=\min(1/d,1/2)

(

M

the total sample size). It follows from a temporal-to-spatial reduction: the smoothness budget defines a reachable

W_2

-ball into which a transport packing is embedded along the time axis, and the information of the entire snapshot experiment is controlled by a Fano argument -- the spatial packing is classical, but its smoothness-admissible temporal embedding and the full-window analysis are new. The bound interpolates a dimension-free extrapolation floor of order

\varepsilon h^{k+1}

-- the irreducible cost of an unobserved future, present even with the exact past -- and the spatial estimation curse

M^{-γ_d}

, recovering the static distribution-estimation rate as

k\to\infty

. We state the lower bound in a design-dependent form -- with a design-weighted effective sample size -- valid for arbitrary observation times, and obtain the closed-form exponent in the dense (equispaced) regime. The matching upper bound is established at

k=0

(rate

M^{-1/(d+1)}

,

d\ge3

) and, in a translation submodel, for all

k

; for

k\ge1

a covariant estimator attains the rate conditionally on two estimates (a comparison-geometry bias bound and an optimal-transport map-estimation rate), leaving the unconditional general-

k

upper bound as an open problem. Numerical experiments on synthetic curved and flat families corroborate the predicted exponents.

Munsik Kim

Minimax Estimation Spatiotemporal Forecasting Optimal Transport Wasserstein Distance

May 28, 2026stat.ML

Improved Distribution Estimation in $\ell_\infty$

We present improved bounds for estimating discrete probability distributions under the

\ell_\infty

norm. These include minimax bounds in expectation and high-probability tail bounds. We resolve some of the open questions posed in Kontorovich and Painsky (JMLR, 2025) -- including a fully empirical version of the tightest risk bound they presented and identifying the form of the worst-case extremal distribution. Encouraging empirical results are reported as well.

Doron Cohen, Aryeh Kontorovich, Yonatan Livshitz

Department of Computer Science, Ben-Gurion University of the Negev, Beer-Sheva, Israel

Minimax Estimation

May 27, 2026cs.LG

Reward Transfer from Inverse Reinforcement Learning: A Coupled Minimax Approach

We study the transfer of rewards learned using inverse reinforcement learning from expert demonstrations in one environment to reinforcement learning in a new, different environment. This arises naturally when demonstrations are collected in a controlled environment. We formulate the problem as a joint system of Bellman equations across the source and target environments and develop minimax estimators for the target soft-

q

-function. Whereas a sequential solution approach first estimates the source reward and then plugs it into the target control problem, a coupled approach solves the source and target system of equations jointly. We show that, in contrast to the sequential approach, the coupled approach removes the first-order influence of source Bellman residual error. We characterize the local behavior of each approach, develop finite-sample soft-

q

-function error bounds, and prove regret guarantees for the resulting soft-control policy. An empirical investigation using a sepsis simulator validates the theoretical comparison.

Guang-Yuan Hao, Lars van der Laan, Aurélien Bibaut +1

Cornell Tech, Cornell University · Netflix Research · Department of Statistics, University of Washington

Reinforcement Learning Minimax Estimation

May 25, 2026math.ST

Minimax Limits of k-Fold Cross-Validation via Majority

We study the mean-squared error of

k

-fold cross-validation as a risk estimator, with particular emphasis on how its accuracy depends on the number of folds

k

. Despite the widespread use of cross-validation, principled guidance for choosing

k

is largely absent, mainly due to the complex dependence between fold-wise error estimates. To obtain sharp and interpretable results, we focus on the majority algorithm in binary classification, a minimal yet nontrivial empirical risk minimization procedure. We provide a fine-grained analysis of its cross-validation behavior, showing that even this simple algorithm exhibits subtle and delicate phenomena for which existing theory provides loose and even vacuous bounds. Leveraging this analysis, we introduce a minimax framework for cross-validation risk estimation and prove that no empirical risk minimization algorithm can achieve an

O(1/n)

minimax mean-squared error when the number of folds grows with the number of samples

n

; instead, a lower bound of order

Ω(\sqrt{k}/n)

is unavoidable. Our results reveal fundamental limitations of cross-validation as a data-reuse strategy, clarify gaps and inaccuracies in prior theoretical work, and position the majority algorithm as a natural benchmark that any tight analysis of cross-validation should be able to explain.

Ido Nachum, Rüdiger Urbanke, Thomas Weinberger

University of Haifa, Haifa, Israel. · EPFL, Lausanne, Switzerland.

Minimax Estimation Statistical Learning Theory

May 22, 2026cs.LG

Instance-Optimal Estimation with Multiple LLM Judges on a Budget

Evaluating large language models increasingly relies on LLM-as-a-judge protocols, but such evaluations remain costly: different judges have different prices and reliabilities, and the difficulty of each prompt-response pair can vary substantially. This raises a basic allocation question: under a fixed budget, how should one distribute evaluation queries across heterogeneous judges and instances to obtain the most accurate score estimates? We formalize this question as budgeted heteroskedastic multi-judge estimation. Given

K

prompt-response pairs,

J

judges with known costs, and unknown query-judge variances, the goal is to estimate a bounded score vector while minimizing an

\ell_p

-error. Our first contribution is to analyze the inverse-variance weighted estimator (IVWE) and to derive the oracle allocation that minimizes its error rate. Since this allocation depends on the unknown variances, we then address the practical unknown-variance setting by proposing EST-IVWE, an adaptive algorithm that constructs and leverages optimistically biased variance estimates to stabilize the empirical allocation. We prove that EST-IVWE matches the oracle IVWE rate up to lower-order terms in the budget. Our second and central theoretical contribution is a matching local minimax lower bound, which establishes the instance-optimality of the proposed algorithms. A key technical insight is that Fano-type high-probability arguments are too coarse for this problem: their packing construction loses the local variance structure that governs the optimal allocation. We instead use an Assouad-type in-expectation argument, based on local perturbations, which preserves this structure and yields the sharp allocation-dependent lower bound. Finally, we numerically validate the superiority of our approach over naïve uniform allocation on synthetic and HelpSteer2 datasets.

Junghyun Lee, Sanghwa Kim, Yassir Jedra +2

KAIST AI · ICL EEE · KTH EECS

Parameter Estimation LLM Evaluation LLM-as-a-Judge Minimax Estimation Adaptive Sampling

May 11, 2026math.ST

Extended Wasserstein-GAN Approach to Causal Distribution Learning: Density-Free Estimation and Minimax Optimality

Distributional causal inference requires estimating not only average treatment effects but also interventional outcome distributions, including quantiles, tail risks, and policy-dependent uncertainty. As a method for distributional causal inference, generative adversarial network (GAN)-based counterfactual methods are flexible tools for this task. However, these methods have several limitations. First, the objectives of certain techniques do not coincide with the statistical risk of the identifiable causal target, and therefore provide limited theoretical guarantees regarding estimable counterfactual distributions or optimality. Second, they tend to rely on unstable density-based methods, such as density ratio estimation. In this paper, we propose GANICE (GAN for Interventional Conditional Estimation) with several advantages: it (i) clarifies the conditional interventional distribution for each treatment--covariate state as the causal estimation target; (ii) estimates the conditional distribution such that its averaged Wasserstein risk is minimized; (iii) establishes minimax optimality. GANICE achieves these advantages through the introduction of the extended Wasserstein distance, the incorporation of a cellwise critic in its dual, and an optimality proof based on Besov space theory. Our experiments demonstrate that GANICE consistently outperforms existing methods.

Shu Tamano, Masaaki Imaizumi

1The University of Tokyo · 2Japan Institute for Health Security · 3RIKEN Center for Advanced Intelligence Project +1

Causal Effect Estimation Causal Counterfactual Generation Minimax Estimation Causal Inference Generative Adversarial Networks Wasserstein Distance

May 8, 2026cs.LG

The Minimax Rate of Perturbed Second-Order Calibration

Second-order calibration error quantifies how closely a higher-order predictor's epistemic-uncertainty estimate matches the conditional variance of the label probability on its level sets. We characterize the minimax rate of estimating the second-order calibration error for binary classification in the regime where a small perturbation is applied to the classifier outputs. Our procedure is simple: add independent bandwidth-

h

sech noise to the score coordinates, then regress

Y^{(1)}

and

Y^{(1)}Y^{(2)}

on the perturbed score using low-degree polynomials. Crucially, the sech perturbation makes the calibration functions analytic in a suitable strip. The resulting estimator has error

O_h(\log^{3/2}n/\sqrt n)

, with explicit constants. In the same setting, a matching

Ω(1/\sqrt{n})

lower bound establishes minimax optimality up to logarithmic factors. As a corollary, we give a finite-sample guarantee for perturbed second-order Platt scaling, yielding a post-hoc procedure that recalibrates both the mean prediction and the epistemic-variance estimate of the perturbed higher-order predictor. Along the way, we give an explicit two-moment formulation of second-order calibration error and relate it quantitatively to the bucketed formulation of Ahdritz et al. [2025]. Our experiments confirm the predicted rate and the quality of the recalibrated uncertainties.

Kamil Ciosek, Banafsheh Rafiee, Sina Ghiassian +1

Spotify

Post-Hoc Calibration Minimax Estimation Model Calibration Binary Classification Statistical Learning Theory Uncertainty Calibration+1

May 7, 2026stat.ML

ConquerNet: Convolution-Smoothed Quantile ReLU Neural Networks with Minimax Guarantees

Quantile regression is a fundamental tool for distributional learning but poses significant optimization challenges for deep models due to the non-smoothness of the pinball loss. We propose ConquerNet, a class of \textbf{con}volution-smoothed \textbf{qu}antil\textbf{e} \textbf{R}eLU neural \textbf{net}works, which yield smooth objectives while preserving the underlying quantile structure. We establish general nonasymptotic risk bounds for ConquerNet under mild conditions, providing minimax guarantees over Besov function classes. In numerical studies, we demonstrate that the proposed approach outperforms standard quantile neural networks at multiple quantile levels, showing improved estimation accuracy and training efficiency across the board, with particularly pronounced advantages at high and low quantiles.

Tianpai Luo, Fangwei Wu, Weichi Wu

Department of Statistics and Data Science Tsinghua University Beijing, 100084, China

Quantile Regression Minimax Estimation Neural Network Approximation Theory

May 6, 2026math.ST

Direct Estimation of Schrödinger Bridge Time-Series Drifts: Finite-Sample, Asymptotic, and Adaptive Guarantees

We study nonparametric estimation of Schrödinger bridge (SB) drifts from i.i.d.\ data observed on a single time interval. Starting from the conditional-ratio form of the Schrödinger bridge time-series (SBTS) drift formula, we analyze a direct Nadaraya--Watson plug-in estimator built from kernelized numerator and denominator terms. Unlike recent SB analyses based on entropic-OT potentials, Sinkhorn iterations, or iterative bridge solvers, our approach works directly at the drift level and isolates \emph{statistical error} from optimization, approximation, and discretization error. Under Hölder regularity, a marginal-density floor, and bounded support, we prove a uniform non-asymptotic bound for admissible bandwidth pairs, a pointwise CLT under genuine undersmoothing, and an adaptive bandwidth selector satisfying an oracle inequality. We also prove a pivot-local minimax lower bound which, through an explicit uniform pivot, yields a global minimax lower bound under transparent compatibility conditions; hence the adaptive selector is minimax-rate optimal up to logarithmic factors. Synthetic experiments provide theorem-targeted diagnostics for finite-sample scaling, Gaussian approximation, and adaptive behavior.

Othmane Mazhar, Huyên Pham

LPSM, Sorbonne Université and Université Paris Cité · École Polytechnique, CMAP

Parameter Estimation Schrödinger Bridges Minimax Estimation

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

Jun 27, 2025stat.ML

Optimal Estimation of Watermark Proportions in Hybrid AI-Human Texts

Text watermarks in large language models (LLMs) are an increasingly important tool for detecting synthetic text and distinguishing human-written content from LLM-generated text. While most existing studies focus on determining whether entire texts are watermarked, many real-world scenarios involve mixed-source texts, which blend human-written and watermarked content. In this paper, we address the problem of optimally estimating the watermark proportion in mixed-source texts. We cast this problem as estimating the proportion parameter in a mixture model based on \emph{pivotal statistics}. First, we show that this parameter is not even identifiable in certain watermarking schemes, let alone consistently estimable. In stark contrast, for watermarking methods that employ continuous pivotal statistics for detection, we demonstrate that the proportion parameter is identifiable under mild conditions. We propose efficient estimators for this class of methods, which include several popular unbiased watermarks as examples, and derive minimax lower bounds for any measurable estimator based on pivotal statistics, showing that our estimators achieve these lower bounds. Through evaluations on both synthetic data and mixed-source text generated by open-source models, we demonstrate that our proposed estimators consistently achieve high estimation accuracy.

Xiang Li, Garrett Wen, Weiqing He +3

University of Pennsylvania · Yale University

Text Watermarking Minimax Estimation LLM Watermarking