Minimax Estimation

Follow this topic Ask about this topic

Minimax estimation asks how accurately an unknown quantity can be recovered in the hardest case within a specified model, and how many observations are needed. Researchers establish upper bounds for concrete estimators and lower bounds that apply to every method, often using regularization, aggregation, thresholding, and information-theoretic tools such as Fano's and Le Cam's methods. The framework covers settings including nonparametric regression, sparse covariance and distribution estimation, one-bit data, dependent observations, and differential privacy. A central challenge is understanding when adaptation to unknown structure is possible without extra cost, especially when privacy, contamination, or computational limits change the achievable rates.

Latest papers

96 papers23 papers in the last four weeks, up 92% on the four weeks before. 0.1% of all new papers.

Jul 2, 2026

Contaminated Multi-task Learning with Heterogeneity: Fundamental Limits and Optimal Algorithms

Integrating information across related tasks can improve estimation and prediction in transfer, multi-task, and federated learning, but contamination and heterogeneity make robust borrowing challenging. We study a contaminated multi-task empirical risk minimization (ERM) framework in which an

ε

fraction of

K

tasks, each with sample size

n

, may be arbitrarily contaminated while the remaining tasks are heterogeneous. Our goal is to estimate both the global minimizer of the average risk and the clean task-specific minimizers, thereby combining robustness and personalization. In the Gaussian mean model, we show that several common paradigms, including adaptive and robust regularization around a shared center, global matrix regularization, decomposition-based regularization, and score-based outlier-task detection, all suffer from a worst-case contamination error of order

ε\sqrt{d/n}

, which is suboptimal compared to the lower bound

ε/\sqrt{n}

. This identifies a dimension-dependent barrier for these approaches. We then establish minimax lower bounds for a general heterogeneous ERM setting and propose a computationally efficient filtering-based robust multi-task gradient descent method. Under local strong convexity, smoothness, and sub-Gaussian gradient assumptions, the proposed method attains high-probability upper bounds matching the minimax rates up to logarithmic factors over a broad regime. In particular, it removes the extra

\sqrt{d}

contamination dependence of many regularization-based methods and score-based outlier detection, while achieving personalization to local tasks under strong heterogeneity. Simulations and a real-data analysis demonstrate strong robustness and personalization relative to a broad range of benchmark methods.

Ye Tian, Mengchu Li, Marco Avella Medina

Department of Statistics, Pennsylvania State University · School of Mathematics, University of Birmingham · Department of Statistics, Columbia University

Multi-Task Learning Minimax Estimation Statistical Learning Theory Robust Estimation

Ask PDF

Jul 2, 2026

Aggregation with Exponential Weights is Optimal in Expectation

The aggregation with exponential weights (AEW) estimator is not fully understood in the basic setting of model selection aggregation with squared loss. In particular, whether it is minimax-rate optimal in expectation for large enough fixed temperatures and under random design has been an open problem since its introduction, which was explicitly posed by Lecué and Mendelson (2013). In this paper, we settle this problem by showing that without requiring a Bernstein-type assumption, the AEW indeed achieves the excess risk

T \log (M) / (n+1)

in expectation, whenever the temperature

T

satisfies

(L^2/T)\exp(B/T)\leq μ/2

. Here, the number of dictionary elements is

M

, the estimator has observed

n

i.i.d. samples from any distribution, and the loss is assumed to be bounded by

B

L

-Lipschitz continuous and

μ

-strongly convex. For squared loss, we show that

T\geq 4 b^2

suffices when the predictions and labels are

[0,b]

-valued. Because AEW is known to be suboptimal in expectation for temperatures below some constant, this shows that AEW has a sharp phase transition when the temperature is large enough but constant, as conjectured by Lecué and Mendelson.

Mikael Møller Høgsgaard, Patrick Rebeschini, Tobias Wegel

Department of Statistics, University of Oxford · Department of Computer Science, ETH Zurich

Ensemble Learning Minimax Estimation Statistical Learning Theory

Ask PDF

Jun 30, 2026

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

Ask PDF

Jun 29, 2026

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

Ask PDF

Jun 26, 2026

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

Ask PDF

Jun 25, 2026

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

Ask PDF

Jun 24, 2026

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

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

Ask PDF

Jun 20, 2026

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

Ask PDF

Jun 18, 2026

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

Ask PDF

Jun 12, 2026

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

We study a 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 budget term, a heteroscedasticity index measuring how unevenly the uncertainty is spread across arms, and a model-dependent complexity measure, the 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

Ask PDF

Jun 6, 2026

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

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

Ask PDF

May 28, 2026

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

Ask PDF

May 27, 2026

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 Transfer Learning in RL

Ask PDF

May 25, 2026

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 Cross-Validation

Ask PDF

May 22, 2026

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

Ask PDF

May 11, 2026

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

Ask PDF

May 8, 2026

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

Ask PDF

May 7, 2026

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 convolution-smoothed quantile ReLU neural networks, 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

Ask PDF

May 6, 2026

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

Ask PDF

May 6, 2026

Information-theoretic Limits of Learning and Estimation

Information theory plays a central role in establishing fundamental limits on what any learning or estimation algorithm can -- and cannot -- achieve, regardless of computational power. In this chapter, we provide an introduction to these connections. End-of-chapter exercises makes the material suitable for both classroom use and self-study. We begin by introducing concentration inequalities along with the notions of covering and packing in metric spaces, and the associated concept of metric entropy. These tools are essential for our analysis. We then introduce the learning-theoretic framework and derive upper bounds on generalization error in terms of metric entropy, Rademacher complexity, and the VC dimension, as well as mutual information and relative entropy. Finally we discuss the minimax estimation framework and establish lower bounds on minimax risk using Fano's inequality, yielding bounds in terms of relative entropy and covering and packing numbers. This manuscript contains preprint of a chapter under consideration for inclusion in the forthcoming third edition of Cover and Thomas's Elements of Information Theory, posted with permission from Wiley. It would follow the chapter posted at arXiv:2605.02989 . The table of contents of the new edition can be found at: https://docs.google.com/document/d/1L-m4oQEJw1PJhoxBeMwrrBD8S_HmvzMEkPbYvS24980/edit?usp=sharing . For feedback, please contact [email protected].

Abbas El Gamal, Maxim Raginsky

Stanford University* · UIUC**

Information-Theoretic Generalization Bounds Minimax Estimation Statistical Learning Theory Information-Theoretic Lower Bounds Generalization Bounds

Ask PDF

Apr 15, 2026

Minimax Optimality and Spectral Routing for Majority-Vote Ensembles under Markov Dependence

Majority-vote ensembles achieve variance reduction by averaging over diverse, approximately independent base learners. When training data exhibits Markov dependence, as in time-series forecasting, reinforcement learning (RL) replay buffers, and spatial grids, this classical guarantee degrades in ways that existing theory does not fully quantify. We provide a minimax characterization of this phenomenon for discrete classification in a fixed-dimensional Markov setting, together with an adaptive algorithm that matches the rate on a graph-regular subclass. We first establish an information-theoretic lower bound for stationary, reversible, geometrically ergodic chains in fixed ambient dimension, showing that no measurable estimator can achieve excess classification risk better than

Ω(\sqrt{\Tmix/n})

. We then prove that, on the AR(1) witness subclass underlying the lower-bound construction, dependence-agnostic uniform bagging is provably suboptimal with excess risk bounded below by

Ω(\Tmix/\sqrt{n})

, exhibiting a

\sqrt{\Tmix}

algorithmic gap. Finally, we propose adaptive spectral routing, which partitions the training data via the empirical Fiedler eigenvector of a dependency graph and achieves the minimax rate

\mathcal{O}(\sqrt{\Tmix/n})

up to a lower-order geometric cut term on a graph-regular subclass, without knowledge of

\Tmix

. Experiments on synthetic Markov chains, 2D spatial grids, the 128-dataset UCR archive, and Atari DQN ensembles validate the theoretical predictions. Consequences for deep RL target variance, scalability via Nyström approximation, and bounded non-stationarity are developed as supporting material in the appendix.

Ibne Farabi Shihab, Sanjeda Akter, Anuj Sharma

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

Ensemble Learning Majority Voting Classification Minimax Estimation

Ask PDF

Apr 12, 2026

Online Covariance Estimation in Averaged SGD: Improved Batch-Mean Rates and Minimax Optimality via Trajectory Regression

We study online covariance matrix estimation for Polyak--Ruppert averaged stochastic gradient descent (SGD). The online batch-means estimator of Zhu, Chen and Wu (2023) achieves an operator-norm convergence rate of

O(n^{-(1-α)/4})

, which yields

O(n^{-1/8})

at the optimal learning-rate exponent

α\rightarrow 1/2^+

. A rigorous per-block bias analysis reveals that re-tuning the block-growth parameter improves the batch-means rate to

O(n^{-(1-α)/3})

, achieving

O(n^{-1/6})

. The modified estimator requires no Hessian access and preserves

O(d^2)

memory. We provide a complete error decomposition into variance, stationarity bias, and nonlinearity bias components. A weighted-averaging variant that avoids hard truncation is also discussed. We establish the minimax rate

Θ(n^{-(1-α)/2})

for Hessian-free covariance estimation from the SGD trajectory: a Le Cam lower bound gives

Ω(n^{-(1-α)/2})

, and a trajectory-regression estimator--which estimates the Hessian by regressing SGD increments on iterates--achieves

O(n^{-(1-α)/2})

, matching the lower bound. The construction reveals that the bottleneck is the sublinear accumulation of information about the Hessian from the SGD drift.

Yijin Ni, Xiaoming Huo

H. Milton Stewart School of Industrial and Systems Engineering, Georgia Institute of Technology

Polyak-Ruppert Averaging Covariance Estimation Minimax Estimation Stochastic Gradient Descent

Ask PDF

Apr 9, 2026

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

In this paper, we study the problem of mean estimation under 1-bit communication constraints. We propose a novel adaptive mean estimator based solely on randomized threshold queries, where each 1-bit outcome indicates whether a given sample exceeds a sequentially chosen threshold. Our estimator is

(ε, δ)

-PAC for any distribution with a bounded mean

μ\in [-λ, λ]

and a bounded

k

-th central moment

\mathbb{E}[|X-μ|^k] \le σ^k

for any fixed

k > 1

. Moreover, our sample complexity is order-optimal in all such tail regimes, i.e., for every such

k

value. For

k \neq 2

, our estimator's sample complexity matches the unquantized minimax lower bounds plus an unavoidable

O(\log(λ/σ))

localization cost. For the finite-variance case (

k=2

), our estimator's sample complexity has an extra multiplicative

O(\log(σ/ε))

penalty, and we establish a novel information-theoretic lower bound showing that this penalty is a fundamental limit of 1-bit quantization. We also establish a significant adaptivity gap: for both threshold queries and more general interval queries, the sample complexity of any non-adaptive estimator must scale linearly with the search space parameter

λ/σ

, rendering it vastly less sample efficient than our adaptive approach. Finally, we present algorithmic variants that (i) handle an unknown sampling budget, (ii) adapt to an unknown scale parameter

σ

given (possibly loose) bounds, (iii) require only two stages of adaptivity to achieve order-optimal sample complexity at the expense of more general 1-bit queries, and (iv) leverage multiple local samples per 1-bit query to proportionally reduce communication costs.

Ivan Lau, Jonathan Scarlett

National University of Singapore

Minimax Estimation Adaptive Sampling Information-Theoretic Lower Bounds

Ask PDF

Apr 7, 2026

Efficient machine unlearning with minimax optimality

There is a growing demand for efficient data removal to comply with regulations like the GDPR and to mitigate the influence of biased or corrupted data. This has motivated the field of machine unlearning, which aims to eliminate the influence of specific data subsets without the cost of full retraining. In this work, we propose a statistical framework for machine unlearning with generic loss functions and establish theoretical guarantees. For squared loss, especially, we develop Unlearning Least Squares (ULS) and establish its minimax optimality for estimating the model parameter of remaining data when only the pre-trained estimator, forget samples, and a small subsample of the remaining data are available. Our results reveal that the estimation error decomposes into an oracle term and an unlearning cost determined by the forget proportion and the forget model bias. We further establish asymptotically valid inference procedures without requiring full retraining. Numerical experiments and real-data applications demonstrate that the proposed method achieves performance close to retraining while requiring substantially less data access.

Jingyi Xie, Linjun Zhang, Sai Li

Institute of Statistics and Big Data, Renmin University of China, Beijing 100872, China · Department of Statistics, Rutgers University, Piscataway, NJ 08854, USA · Department of Statistics and Data Science, Tsinghua University, Beijing 100084, China

Machine Unlearning Statistical Learning Theory Minimax Estimation

Ask PDF

Apr 6, 2026

Minimaxity and Admissibility of Bayesian Neural Networks

Bayesian neural networks (BNNs) offer a natural probabilistic formulation for inference in deep learning models. Despite their popularity, their optimality has received limited attention through the lens of statistical decision theory. In this paper, we study decision rules induced by deep, fully connected feedforward ReLU BNNs in the normal location model under quadratic loss. We show that, for fixed prior scales, the induced Bayes decision rule is not minimax. We then propose a hyperprior on the effective output variance of the BNN prior that yields a superharmonic square-root marginal density, establishing that the resulting decision rule is simultaneously admissible and minimax. We further extend these results from the quadratic loss setting to the predictive density estimation problem with Kullback--Leibler loss. Finally, we validate our theoretical findings numerically through simulation.

Daniel Andrew Coulson, Martin T. Wells

Department of Statistics and Data Science, Cornell University

Bayesian Neural Networks Minimax Estimation Bayesian Decision Theory

Ask PDF

Mar 20, 2026

Minimax and Adaptive Covariance Matrix Estimation under Differential Privacy

Estimating covariance matrices is fundamental to a wide range of statistical applications. This paper studies minimax and adaptive estimation of high-dimensional covariance matrices under

ρ

-zero-concentrated differential privacy (

ρ

-zCDP) over three nested classes: the pointwise-decay class

\mathcal{H}_α

, the row-tail class

\mathcal{G}_α

, and the separated-block class

\mathcal{F}_α

. We consider both squared operator norm loss and normalized squared Frobenius norm loss. For

\mathcal{H}_α

and

\mathcal{G}_α

, we develop center--outer dyadic estimators tailored to the refined geometry of the two classes, while for

\mathcal{F}_α

, we develop a blockwise tridiagonal estimator. The resulting minimax-optimal rates reveal a nontrivial interplay among the smoothness

α

, the loss, the geometry of the covariance class, and the privacy constraint. In contrast to the non-private setting, privacy distinguishes covariance classes that share the same leading non-private rate and induces a polynomial dependence on the ambient dimension. We further develop procedures that adapt to the unknown decay parameter over all three covariance classes under both losses, at the cost of at most polylogarithmic factors. To establish minimax lower bounds, we develop a novel differentially private van Trees inequality that connects Fisher information with the

ρ

-zCDP constraint and may be useful for other private estimation problems. We also construct carefully designed prior distributions to obtain matching minimax lower bounds.

T. Tony Cai, Yicheng Li

Department of Statistics and Data Science, The Wharton School, University of Pennsylvania · KLATASDS-MOE, School of Statistics, East China Normal University

Covariance Estimation Parameter Estimation Minimax Estimation Differential Privacy

Ask PDF

Mar 11, 2026

Deep regression learning from dependent observations with minimum error entropy principle

This paper considers nonparametric regression from strongly mixing observations. The proposed approach is based on deep neural networks with minimum error entropy (MEE) principle. We study two estimators: the non-penalized deep neural network (NPDNN) and the sparse-penalized deep neural network (SPDNN) predictors. Upper bounds of the expected excess risk are established for both estimators over the classes of Hölder and composition Hölder functions. For the models with Gaussian error, the rates of the upper bound obtained match (up to a logarithmic factor) with the lower bounds established in \cite{schmidt2020nonparametric}, showing that both the MEE-based NPDNN and SPDNN estimators from strongly mixing data can achieve the minimax optimal convergence rate.

William Kengne, Modou Wade

Institut Camille Jordan, Université Jean Monnet, 23 Rue Dr Paul Michelon 42023 Saint-Etienne Cedex 2, France · THEMA, CY Cergy Paris Université, 33 Boulevard du Port, 95011 Cergy-Pontoise Cedex, France

Nonparametric Regression Minimax Estimation Sparse Neural Networks

Ask PDF

Mar 10, 2026

The Epistemic Support-Point Filter: Jaynesian Maximum Entropy Meets Popperian Falsification

This paper proves that the Epistemic Support-Point Filter (ESPF) is the unique optimal recursive estimator within the class of epistemically admissible evidence-only filters. Where Bayesian filters minimize mean squared error and are driven toward an assumed truth, the ESPF minimizes maximum entropy and surfaces what has not been proven impossible -- a fundamentally different epistemic commitment with fundamentally different failure modes. Two results locate this theorem within the broader landscape of estimation theory. The first is a unification: the ESPF's optimality criterion is the log-geometric mean of the alpha-cut volume family in the Holder mean hierarchy. The Popperian minimax bound and the Kalman MMSE criterion occupy the p=+inf and p=0 positions on the same curve. Possibility and probability are not competing frameworks: they are the same ignorance functional evaluated under different alpha-cut geometries. The Kalman filter is the Gaussian specialization of the ESPF's optimality criterion, not a separate invention. The second result is a diagnostic: numerical validation over a 2-day, 877-step Smolyak Level-3 orbital tracking run shows that possibilistic stress manifests through necessity saturation and surprisal escalation rather than MVEE sign change -- a direct consequence of the Holder ordering, not an empirical observation. Three lemmas establish the result: the Possibilistic Entropy Lemma decomposes the ignorance functional; the Possibilistic Cramer-Rao Bound limits entropy reduction per measurement; the Evidence-Optimality Lemma proves minimum-q selection is the unique minimizer and that any rule incorporating prior possibility risks race-to-bottom bias.

Moriba Kemessia Jah

Black Swan Research Group, GaiaVerse, Ltd. · Jah Decision Intelligence Group, Aerospace Engineering & Engineering Mechanics, The University of Texas at Austin

Epistemic Uncertainty Minimax Estimation

Ask PDF

Mar 5, 2026

On the Statistical Optimality of Optimal Decision Trees

While globally optimal empirical risk minimization (ERM) decision trees have become computationally feasible and empirically successful, rigorous theoretical guarantees for their statistical performance remain limited. In this work, we develop a comprehensive statistical theory for ERM trees under random design in both high-dimensional regression and classification. We first establish sharp oracle inequalities that bound the excess risk of the ERM estimator relative to the best possible approximation achievable by any tree with at most

L

leaves, thereby characterizing the interpretability-accuracy trade-off. We derive these results using a novel uniform concentration framework based on empirically localized Rademacher complexity. Furthermore, we derive minimax optimal rates over a novel function class: the piecewise sparse heterogeneous anisotropic Besov (PSHAB) space. This space explicitly captures three key structural features encountered in practice: sparsity, anisotropic smoothness, and spatial heterogeneity. While our main results are established under sub-Gaussianity, we also provide robust guarantees that hold under heavy-tailed noise settings. Together, these findings provide a principled foundation for the optimality of ERM trees and introduce empirical process tools broadly applicable to other highly adaptive, data-driven procedures.

Zineng Xu, Subhro Ghosh, Yan Shuo Tan

Department of Statistics and Data Science, National University of Singapore · Department of Mathematics, National University of Singapore

Decision Tree Learning Statistical Learning Theory Empirical Risk Minimization Minimax Estimation

Ask PDF