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

All topics

Oct 8, 2026math.PR

Subspace Uncertainty and Sharp Sampling Thresholds on the Boolean Cube

We study Gaussian regression under squared population

L_2

loss in a known

m

-dimensional subspace of degree-at-most-

k

functions on the

d

-dimensional Boolean cube. Random inputs can undersample regions essential for prediction, delaying the parametric rate even when the model is known. For fixed

q_0<1/2

1\le k\le q_0d

, and sufficiently large fixed

A

, the worst-subspace sample threshold for minimax error

Aσ^2(m+t)/n

with confidence

1-e^{-t}

t\ge\log4

, is

N=(m+t)\exp\{E_{d,k}+O(k^{1/3})\}, \quad E_{d,k}=dΨ(k/d),

where

Ψ(q)=\log2-\mathsf H(\tfrac12-\sqrt{q(1-q)})

and

\mathsf H

is binary entropy with natural logarithms. The upper bound holds for every feasible

m

; the matching lower bound holds when

m\le\binom d{\lfloor k^{1/3}\rfloor}

t\ge m

. We sharpen the Polyanskiy--Samorodnitsky uncertainty principle in two respects. First, for fixed leakage

ρ\in(0,1)

, the smallest set carrying a fraction

1-ρ

of a nonzero degree-at-most-

k

polynomial's energy has probability

\exp\{-E_{d,k}+O_{ρ,q_0}(k^{1/3})\}

. An Airy-kernel construction proves that the remainder cannot be

o(k^{1/3})

in general. Second, we construct a subspace of dimension

\binom d{\lfloor k^{1/3}\rfloor}

such that every function in the subspace has at least a fraction

1-ρ

of its energy on the same set, whose probability is at most

\exp\{-E_{d,k}+C_{ρ,q_0}k^{1/3}\}

. For sufficiently large

k

, this set is a Hamming ball. A striking consequence is an exponential cost of noise: the parametric rate can require

(m+t)4^k\exp\{-O(k^{1/3})\}

samples, whereas

O((m+t)2^k)

suffice for noiseless identification. As

k\to\infty

with

k/d\to0

, the noisy threshold is

(m+t)\exp\{2k+o(k)\}

Thomas Weinberger

School of Computer and Communication Sciences, EPFL, Switzerland

Sample Complexity Statistical Learning Theory Minimax Estimation

Ask PDF

Oct 6, 2026cs.CL

Holdout Best-of-N: Unbiased Evaluation and Its Cost

Reusing the scores that select a Best-of-

N

winner can overstate its expected reward. We study evaluation from a fixed matrix of

K

independent scores per candidate for a policy that selects using

J

fresh scores. A single estimator based only on this matrix is exactly unbiased for expected judge reward under every independent, stable collection of candidate-specific score laws if and only if

J<K

, for every pool size

M\ge N\ge2

. At

J=K-1

, the selector deepens as

K

grows. For independent Gaussian scores with common variance and fixed

M\ge N\ge2

, the unbiased minimax risk in this regime is of order

σ^2/\sqrt K

, attained by Holdout; allowing bias improves the rate to

σ^2/K

. For two candidates, we derive the minimum-variance unbiased estimator at known variance and the sharp asymptotic unbiased minimax constant

1/(π\sqrt2)

, which Holdout attains without knowing the variance. The cyclic average over subsets and ties can be computed in

O(MK\log M)

operations. At fixed selector depth, cyclic evaluation of bounded scores has

O(K^{-1})

risk uniformly in pool size. The impossibility result concerns the fixed matrix: one additional fresh winner score permits unbiased evaluation of the all-

K

policy.

Shrey Shah, Yinheng Li

Best-of-N Sampling Policy Evaluation Minimax Estimation Reward Model Evaluation

Ask PDF

Oct 6, 2026cs.LG

Detecting a Shift Is Not Enough: Exact Minimax Limits of Linear Representation Repair

A mean shift between two data sources can be easy to detect but hard to remove without substantially changing their representations. We cast its removal as a statistical decision problem: from noisy differences between paired calibration measurements in

\mathbb{R}^d

, learn one linear map, applied to both sources under a hard distortion budget, that leaves as little of the shift as possible on fresh data. We derive the exact finite-sample minimax risk over all such maps,

(d-k) \mathbb{E}[1/(d+2J)]

with

J\sim\mathrm{Pois}(κ/2)

, where the budget allows deleting

k

directions and

κ

is the calibration signal-to-noise ratio. Projecting out the mean calibration difference attains it without knowing

κ

or the noise scale. This exposes a detection-repair gap: detecting the shift needs only

κ\gg\sqrt d

, whereas removing a fixed fraction of it at constant distortion needs

κ\asymp d

, as for estimating its direction. Standard linear concept erasers (MP, SAL, LEACE) remove the same calibration difference, so the formula gives, before fitting, exactly how much shift they leave on fresh data and how much calibration a target requires. The limit is robust: pairing keeps it exact for non-Gaussian shared content, the projection keeps its guarantee under anisotropic noise, and selective abstention cannot close the gap. On paired clinical and wearable sleep EEG, where differences between participants act as calibration noise, the formula predicts the device shift left in new participants, and more recordings per person soon stop helping. Together, these results tell whether a correction that falls short needs a better method, more recordings, or more participants.

Anuar Aimoldin, Yankai Chen, Ayana Mussabayeva +1

Mohamed bin Zayed University of Artificial Intelligence (MBZUAI)

Distribution Shift Robustness Minimax Estimation Concept Erasure

Ask PDF

Oct 6, 2026stat.ML

Uniform Discrete Diffusion Models are Minimax Optimal for Estimating Distributions with Small Effective Support Size

Discrete diffusion models have emerged as a practically successful framework for generative modeling on discrete product spaces, yet their statistical generalization properties remain poorly understood. Discrete real-world data such as text or biological sequences often concentrate on a small fraction of the astronomically large ambient space because of semantic or physical constraints, but existing bounds fail to capture this distributional structure and instead scale with the size of the ambient space, giving rise to almost vacuous error bounds. We address this gap for uniform discrete diffusion, one of the two dominant discrete diffusion paradigms alongside masking diffusion, by deriving statistical guarantees governed by the effective support size

s_n(P_0)

, a sample-size-dependent measure of distributional complexity. Given

n

independent and identically distributed (i.i.d.) samples from an unknown data distribution

P_0

[K]^d

, we show that, with appropriate choices of network size and hyperparameters, the expected total variation (TV) loss scales as

O(\sqrt{s_n(P_0)/n})

, while the expected Kullback--Leibler (KL) divergence is bounded by

O(\frac{1}{n}s_n(P_0)\log(eK^d/s_n(P_0))\log n)

. Furthermore, we show that the TV rate is minimax optimal and that the KL rate is minimax optimal up to a factor of

\log n

. Together, these upper and lower bounds show that uniform discrete diffusion successfully avoids the curse of dimensionality for distributions with small effective support size: the TV error rate depends on the ambient state-space size only through

s_n(P_0)

, while the corresponding KL rate incurs only an additional logarithmic dependence on the ambient state-space size.

Dongsun Yoon, Saptarshi Chakraborty

Department of Statistics, University of Michigan

Minimax Estimation Statistical Learning Theory Density Estimation Diffusion Models

Ask PDF

Oct 5, 2026stat.ML

Assumption-lean logistic regression with missing covariates

Missing covariates are frequently encountered in supervised learning problems, and classical methods for estimation using such data use carefully chosen imputation schemes for missing data, or likelihood approximations that lead to nonconvex

M

-estimation problems. These methods and their relatives are suitable for scenarios in which the covariate distribution is known, and more broadly, have enjoyed tremendous success in linear models. But even in basic nonlinear problems such as logistic regression in moderate dimensions, such methods can experience drastic failure modes when the covariate distribution is unknown. Motivated by the need for reliable alternatives, we consider the problem of parameter estimation in logistic regression with missing covariates. Crucially, we operate in the assumption-lean setting where the covariate distribution is unknown (but bounded). We design a stochastic approximation method that is based on

Z

-estimation with a novel monotone operator, and establish that our algorithm is computationally efficient and achieves provable signal recovery at parametric rates under the hypothesis that covariates are missing completely at random. Our theory sharply characterizes the

\ell_2^2

risk of the estimator in terms of the missingness profile, accommodating heterogeneous observation probabilities. Importantly, it shows that our method always outperforms the de facto ``complete-case'' estimator that ignores observations with any missing data. Even in the setting with homogeneous missingness (in which each covariate is observed independently with probability

q

), our bounds exhibit intricate and nonstandard dependence on

q

that can yield significant improvements over using only complete cases. We complement our upper bounds with new information-theoretic lower bounds that show that this intricate dependence on

q

is fundamental in a minimax sense.

Jyotishka Ray Choudhury, Kabir Aladin Verchand, Richard J. Samworth +1

School of Industrial and Systems Engineering, Georgia Institute of Technology · Department of Data Sciences and Operations, University of Southern California · Statistical Laboratory, University of Cambridge +1

Logistic Regression Learning with Missing Data Minimax Estimation

Ask PDF

Sep 30, 2026stat.ML

Minimax Additive Regression under Unknown Dependent Designs

We study additive regression under a potentially non-product random design on

[0,1]^d

, allowing the dimension

d

to grow with the sample size

n

. We introduce coupled smoothness classes that separately control the regularity of the marginal densities and the density-weighted additive components. To handle dependence, we adapt a Riesz-basis construction for functional ANOVA models and establish compatibility bounds with constants independent of the dimension under uniform bounds on the joint density. We construct thresholded least-squares estimators and establish matching minimax upper and lower bounds for prediction with known or unknown marginal densities, under suitable dimension-growth conditions. When the marginal densities are at least as smooth as the weighted components, the unknown-density problem attains the known-density minimax rate. When the densities are less smooth, their regularity determines the minimax rate over the coupled class. Finally, we show that the centered additive components can be recovered at the same aggregate upper rate, without an additional order of error.

Baptiste Ferrere, Fabrice Gamboa, Jean-Michel Loubes

Université de Toulouse EDF R&D · Université de Toulouse ANITI

Nonparametric Regression Minimax Estimation

Ask PDF

Sep 30, 2026stat.ML

Minimax rates for learning spectral Barron functions by deep ReLU neural networks

We study how well deep neural networks approximate and learn spectral Barron functions. Recent studies have shown that these function classes can be efficiently approximated by shallow neural networks without suffering from the curse of dimensionality. We complement these results by providing new approximation bounds for deep networks with ReLU activation and establishing the minimax rates for learning these function classes. Specifically, we show that

d

-dimensional spectral Barron functions with smoothness index

s>0

can be approximated by deep ReLU neural networks with approximation rate

\widetilde{\mathcal{O}} (S^{-\frac{1}{2}-\frac{s}{d}})

, where

S

denotes the number of nonzero parameters in the network. Using this approximation result, we further show that deep ReLU neural networks can learn spectral Barron functions in a fast rate

n^{-\frac{d+2s}{2d+2s}}

with

n

training samples. Finally, we prove that this convergence rate is minimax optimal up to logarithmic factors.

Songqiu Ma, Yunfei Yang

School of Mathematics (Zhuhai), Sun Yat-sen University, Zhuhai, China. · School of Mathematics (Zhuhai) and Guangdong Province Key Laboratory of Computational Science, Sun Yat-sen University, Zhuhai, China.

ReLU Neural Networks Minimax Estimation Neural Network Approximation Theory Statistical Learning Theory

Ask PDF

Sep 24, 2026cs.AI

Sharp Limits for Honest Uncertainty in Hard-Budget Repeated Evaluation

Repeated evaluation can estimate a benchmark score accurately while still requiring replication to certify narrow uncertainty. We characterize that requirement on a fixed grid of

M

tasks with

L

binary paths per task under the hard budget

(M+t)K

, where each path costs at most

K

responses or episodes. For fixed

L \ge 3

and

0 < α\le 1/12

, the optimal expected width on the worst pure cohort is

Θ_{α,L}([M(t+1)]^{-1/2})

when every task is observed and

Θ_{α,L}([M(t+\sqrt{M})]^{-1/2})

when omission is allowed. The lower bounds cover adaptive hard-budget policies, and fixed random-subset designs attain both rates through disagreement certificates. A joint mean/disagreement interval turns the task-covering law into practical finite-budget inference. In an equal-budget LiveCodeBench replay with 16 models, 880 tasks, and five outputs per task, the task-covering design reduces median point-estimation MSE by 87.0% relative to pooled uniform sampling, while the Joint certificate produces narrower confidence intervals in 15/16 panels and reduces median interval width by 30.6%. Finite-regime analyses identify task coverage as the effective choice at the evaluated scale and characterize how cohort size and within-task agreement determine the useful operating region. Together, the sharp laws and fixed-budget evidence make replication and task coverage explicit design variables for information-efficient repeated evaluation.

Yezhou Cheng, Runjia Du, Zeming Liu +5

Independent · Northwestern University · Pinterest, Inc.

Confidence Region Estimation Uncertainty Quantification Benchmark Design Minimax Estimation

Ask PDF

Sep 22, 2026stat.ML

Error Bounds for Statistical Estimators in BTL Model with Parametric Multivariate Utility Functions

We study preference elicitation under the Bradley-Terry-Luce (BTL) model where the true partworth vector is unknown and has to be estimated as a parameter with elicited preference information. The set of selected pairwise queries is non-uniform, deterministic, and arbitrary over a collection of alternatives, provided that it satisfies a joint identifiability condition. We focus on understanding when the canonical maximum likelihood estimator (MLE) is finite and admits sharp error bounds without explicit compactness constraints on the feasible set or external regularizers. To this end, we derive minimax lower bounds under the standard bounded dynamic range condition, and find that the same Fisher-information geometry in the classic Cramér-Rao lower bounds underpins the finite-sample difficulty of the estimation problem. By combining a non-asymptotic expansion of the likelihood score equation with a fixed-point localization argument, we identify a design-dependent sample size threshold above which the unconstrained canonical MLE exists and is unique with high probability. The same expansion yields a decomposition of the estimation error into a linear stochastic term, an explicit second-order bias, and a higher-order remainder. A refined analysis gives sufficient sample size conditions under which the canonical MLE attains the minimax rates up to logarithmic and constant factors. These results provide a unified non-asymptotic theory for parametric utility elicitation and reveal when the inference is determined by response data alone rather than by external regularization. Preliminary numerical results are consistent with the theoretical findings.

Yicheng Li, Huifu Xu

Department of Systems Engineering and Engineering Management, The Chinese University of Hong Kong.

Parameter Estimation Minimax Estimation Bradley–Terry Model Preference Elicitation

Ask PDF

Sep 22, 2026stat.ML

Statistical Gains from Looped Estimation under Parameter Budgets

Memory constraints in artificial intelligence motivate accurate function approximation with fewer parameters. We study looping, which repeatedly composes one update function with shared parameters; each output becomes the next input. A looped Transformer, for example, reuses one block, whereas its conventional untied counterpart uses separately parameterized blocks. We compare their parameter requirements for a given worst-case approximation accuracy, or equivalently, their approximation accuracy under a common budget limiting distinct trainable coefficients. We then ask whether this representational parsimony improves statistical accuracy. For general likelihood models, we establish an upper squared Hellinger risk bound for looped sieve maximum likelihood and a minimax lower bound for the jointly tuned untied family. Further loop iterations improve the approximation bound without adding parameters, while increasing computation and the fitted-class complexity bound. For targets of known Hölder smoothness, looped residual feedforward networks and post-layer-normalized Transformers attain the minimax polynomial rate up to logarithmic factors with a fixed number of bounded real parameters. At sufficiently large fixed budgets, looped worst-case risk vanishes while optimal worst-case untied risk remains bounded away from zero. The loop-to-untied risk ratio also tends to zero under specified growing-budget conditions. Regression, binary response, and energy-based generative models illustrate the theory.

Xinyu Tian, Xiaotong Shen

School of Statistics, University of Minnesota

Parameter Estimation Minimax Estimation Neural Network Approximation Theory Statistical Learning Theory

Ask PDF

Sep 22, 2026stat.ML

Optimal Tradeoffs Between Network Size and Parameter Magnitude in Neural Approximation and Minimax Regression

The statistical accuracy of neural networks depends on both their approximation power and the complexity of the class fitted from data. While increasing network size is a natural way to improve approximation, parameter magnitude provides another resource whose role must be quantified in both respects. We establish a sharp width--magnitude tradeoff at fixed depth using one elementary bounded

1

-Lipschitz Dyadic--Triangular Activation. For the unit

β

-Hölder ball on

[0,1]^d

with

0<β\leq1

, the optimal

L^p

approximation error for

0<p<\infty

is of order

[N^2\log(eNT)]^{-β/d}

when the network width satisfies

N\geq2d+3

and the parameter magnitudes are bounded by

T\geq1

. Matching lower bounds hold for every fixed globally Hölder activation; its Hölder exponent affects the constants but not the rate. Under bounded design densities and independent centered sub-Gaussian noise, approximate least squares over the full clipped class at depth

23

attains the classical Hölder minimax risk

\mathcal{O}(M^{-\frac{2β}{2β+d}})

without logarithmic loss whenever

N^2\log(eNT)\asymp M^{\frac{d}{2β+d}}

, where

M

is the sample size. This yields a continuum of statistically optimal choices, ranging from unit parameter radius to fixed network size. At fixed size, four hidden layers with at most

8d+7

nonzero parameters give a near-optimal radius, while six layers with at most

8d+27

attain the optimal order

\log T=\mathcal{O}(η^{-d/β})

at approximation error

η

. The same decoding method also yields fixed-size Transformer approximation.

Baicheng Li, Zuowei Shen, Haizhao Yang +1

Department of Mathematics, University of Maryland, College Park, MD 20742-4015, USA. · Department of Mathematics, National University of Singapore, Singapore 119076. · Department of Applied Mathematics, The Hong Kong Polytechnic University, Hong Kong, China.

Neural Network Optimization Nonparametric Regression Minimax Estimation Neural Network Approximation Theory

Ask PDF

Sep 21, 2026math.ST

Conformalized Quantile Regression and Minimax Limits of Fixed-Score Calibration under Known Covariate Shift

In this paper, we study nonasymptotic

L^p

error bounds for interval length and conditional coverage in split conformalized quantile regression (CQR). Our bounds rely on local regularity conditions and accuracy guarantees for the estimated quantiles. We further instantiate our bounds for quantile regression with sparse ReLU neural networks. We also consider covariate shift, where the calibration and test covariates have different distributions, and derive nonasymptotic bounds for this setting. We obtain matching minimax upper and lower bounds in expectation for two constructed fixed-score calibration benchmarks under known covariate shift. The bounds match for every

p\in[1,\infty]

in the scalar problem and for finite

p

in the

K

-threshold problem; for the latter, a high-probability minimax lower bound holds for every

p\in[1,\infty]

Rustam Isaev, Anton Conrad, Denis Belomestny +2

Faculty of Computer Science, HSE University, Moscow, Russia · Faculty of Computational Mathematics and Cybernetics, Lomonosov Moscow State University, Moscow, Russia · Laboratoire de Recherche d’EPITA, Le Kremlin-Bicêtre, France +2

Conformal Prediction Covariate Shift Minimax Estimation Regression Prediction Intervals

Ask PDF

Sep 8, 2026stat.ML

Optimal estimation for Functional Linear Regression with Noisy Discretized Data

In this paper, we consider the scalar-on-function linear regression model under a realistic sampling scheme in which the functional covariates are observed on a regular grid and contaminated by additive noise. We propose a two-step estimation procedure: first, the underlying curves are reconstructed from the discrete noisy observations using a Fourier-based projection method; second, the slope function is estimated by a penalized least-squares criterion over finite-dimensional trigonometric spaces, with data-driven selection of the model dimension. We establish oracle-type inequalities for the prediction error, both with respect to the reconstructed curves and to the true latent curves. Under regularity assumptions on the slope function and polynomial decay of the eigenvalues of the covariate, we derive convergence rates for the prediction error and show that our estimator attains the minimax rate when the number of grid points is sufficiently large. Finally, the proposed method is illustrated on simulated data and on a real meteorological dataset.

Sixtine Sphabmixay

Université Paris Cité, CNRS, MAP5, F-75006 Paris, France

Nonparametric Regression Minimax Estimation Linear Regression

Ask PDF

Sep 8, 2026stat.ML

Non-Adaptive 1-Bit Mean Estimation: Minimax Rates and the Sample-Interval Tradeoff

We study distributed one-dimensional mean estimation under a 1-bit communication constraint. Each agent observes one sample, drawn independently from an unknown distribution, and returns a single bit in response to a query

Q: \mathbb{R}\to\{0,1\}

chosen by a central learner. The distribution has mean in

[-λ,λ]

and

k

-th central moment at most

σ^k

, for a fixed

k>1

. The order-optimal two-stage protocol of Lau and Scarlett uses responses from the first batch to choose the second-batch queries, motivating the question of whether this single round of interaction is necessary. We answer this negatively: for every

k>1

, a non-adaptive protocol attains the adaptive 1-bit minimax rate (and concurrent works reached the same conclusion via different strategies). We further determine the minimax sample complexity among non-adaptive 1-bit estimators when every one-set

Q^{-1}(1)

is restricted to a union of at most

s

intervals. Relative to unrestricted non-adaptive 1-bit querying, this constraint adds a term of order

(λσ/(s\varepsilon^2))\log(1/δ)

, giving the full tradeoff between sample complexity and interval complexity to within

k

-dependent constant factors. As a corollary, we identify, order-wise, the minimum interval budget needed to retain the unrestricted 1-bit minimax sample rate.

Ivan Lau, Jonathan Scarlett

National University of Singapore

Minimax Estimation

Ask PDF

Sep 7, 2026cs.LG

Sharp Structure-Agnostic Minimax Risk for Partial Linear Models

We characterize the sharp structure-agnostic minimax risk for coefficient estimation in the partial linear model when the outcome and treatment nuisances are learned by two distinct black-box learners, which resolves the open problem in double machine learning posed by Gu (2025). For each nuisance

q\in\{μ,π\}

, we characterize the available learner by an approximation-error budget

a_q

and a stochastic-error budget

s_q

, with the latter controlled through localized Rademacher complexity. Writing

\mathcal E_n

for the minimax mean-squared error, we show that

\mathcal E_n\asymp1\wedge\left\{\frac1n+\left(a_μa_π+\min\left\{a_πs_μ+s_π^2,\,a_μs_π+s_μ^2\right\}\right)^2\right\}.

The main new ingredient is a novel lower bound for the general two-learner problem. Our proof constructs four finite-mixture testing experiments using orthogonal code functions. Across these experiments, the hidden perturbations are placed outside both learner classes, outside only the treatment learner class, outside only the outcome learner class, or inside both learner classes. These four configurations capture, respectively, the interaction between the two approximation errors, the two asymmetric interactions between one learner's approximation error and the other learner's learning error, and the joint estimation difficulty of learning both nuisances. Combining the four resulting lower bounds yields the displayed rate, which matches the latest upper bound in Gu (2026). Our result shows that standard double machine learning can overstate the intrinsic difficulty of target estimation and provides a target-specific principle for learner selection: approximation error and stochastic complexity must be jointly balanced across the two nuisance learners rather than optimized separately.

Haichen Hu, David Simchi-Levi

Center for Computational Science and Engineering, MIT · Department of Civil and Environmental Engineering, MIT · Institute for Data, Systems, and Society, MIT

Double ML Semiparametric Inference Minimax Estimation Statistical Learning Theory

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 19, 2026math.ST

Algorithms for adaptive and heteroskedastic linear regression at the computational threshold

We study finite-sample linear regression in the presence of varied and unknown label noise, focusing on the heteroskedastic and adaptive linear regression models. Heteroskedastic linear regression models settings where the labels are of varying quality. We receive

n

pairs

(X_i,Y_i)

with labels

Y_i=X_i^\topβ+\varepsilon_i

, where

\varepsilon_i\sim N(0,σ_i^2)

and the variances are unknown to the estimator. One natural measurement of the difficulty of this problem is the number of samples

m

for which

σ_i^2\le1

(larger

m

is easier). We obtain a polynomial-time estimator with rate

\tilde{O}((nd^3/m^4)^{1/6})

when

m\gg d^{3/4}n^{1/4}

, as well as nearly-matching lower bounds. For

d=O(1)

, our estimator achieves error

o(1)

when

m\gg n^{1/4}

, whereas

L_1

regression and other traditional approaches require

m\gg n^{1/2}

. In adaptive linear regression, the errors are drawn i.i.d. from an unknown distribution

p

, and our goal is to design a generic estimator that performs nearly as well as the best custom estimator that knows

p

. We introduce a (computationally inefficient) adaptive estimator that, so long as

p

is a mixture of

k

symmetric log-concave densities, achieves error comparable with the optimal estimator that knows

p

and has

\tildeΘ(n/k)

samples. For

k=1

, we show that

L_q

regression (with data-dependent

q

) gives a polynomial-time estimator. Finally, to study the computational limits of both problems, we introduce the planted linear regression problem, where

X_i\sim N(0,I_d)

m

unknown samples are noiseless, and the rest have error

\varepsilon_i\sim N(0,1)

. We conjecture that recovering

β

up to error

\ll\sqrt{d/n}

(or exactly) may have an information-computation gap between

m=d+1

and

m\sim d^{3/4}n^{1/4}

, as is suggested by our near-matching polynomial-time estimator and statistical query (SQ) lower bound.

Spencer Compton, Tselil Schramm

Stanford University

Minimax Estimation Heteroscedastic Regression Linear Regression

Ask PDF

Aug 11, 2026cs.LG

Hierarchical Empirical-Bayes Naive Bayes: Minimax Smoothing and Calibration with AODE Extension

The Naive Bayes (NB) classifier remains a standard choice for categorical data, yet its widely used smoothing rules, such as Laplace, Lidstone, Krichevsky-Trofimov, and the

m

-estimate, all prescribe a fixed smoothing strength that ignores feature cardinality, sample size, and class imbalance, inducing a non-vanishing bias on modern high-cardinality tabular data. We propose hierarchical empirical-Bayes Naive Bayes (HEB-NB), in which each class-feature conditional probability is smoothed by a Dirichlet prior whose concentration is learned data-adaptively via Type-II maximum likelihood, enabling principled information sharing across classes while retaining closed-form inference. We further introduce HEB average one-dependence estimators (HEB-AODE), showing that the adaptive smoothing transfers cleanly to structural relaxations of NB. Theoretically, we establish a non-asymptotic

\ell_1

error bound for HEB-NB matching the empirical-distribution minimax rate plus a vanishing data-adaptive bias, together with a matching Laplace-tight lower bound that yields a finite-sample, risk-level strict separation from Laplace. We further derive a plug-in excess Bayes-risk bound via total-variation tensorization and a population top-1 expected calibration error (ECE) corollary. Empirically, across 31 UCI and OpenML benchmarks, HEB-NB attains the best average Friedman rank on probabilistic metrics, with up to 22.1% log-loss reductions on high-cardinality datasets and consistent improvements of HEB-AODE over vanilla AODE. Combining HEB-NB with mutual-information weighting reduces top-1 ECE by 41%-70%, demonstrating substantial gains in probabilistic accuracy and calibration.

Nguyen Thai Anh, Truong Viet Vu, Tran Thien Thanh +2

Faculty of Information Technology, Van Lang School of Technology, Van Lang University, Ho Chi Minh City, 70000, Vietnam · Institute of Information Technology and Electrical-Electronics Engineering, Ho Chi Minh City University of Transport, Ho Chi Minh City, 700000, Vietnam

Probability Calibration Empirical Bayes Hierarchical Bayesian Modeling Minimax Estimation

Ask PDF

Aug 9, 2026cs.LG

The Cost of Adaptivity: Matching Lower Bounds Across Learning Problems

Adaptive procedures must work without nuisance information an oracle may use, such as a gradient scale or smoothness index, and robust procedures may have to answer queries whose coordinate and inspection time are chosen only after the data are seen. Such comparisons are meaningful only when the oracle advantage and validity contract are stated explicitly. We formalize nuisance adaptation via a slice-normalized minimax ratio retaining the worst-case instance within each nuisance slice, and separately define the robustness cost of expanding from one preannounced Gaussian query to arbitrary post-hoc inspection. Our main result is a finite-horizon composition law for Gaussian certification: from M independent coordinates, a familywise certifier protecting every coordinate and time up to T pays optimal normalized squared half-width of order log(eM) + log log(e^eT), within the sample-mean-centered rectangular class. Epoch stitching gives the upper bound; independent Gaussian block increments across coordinates and geometric time scales give a matching lower bound, already holding on a geometric checkpoint grid, forcing quantiles of the realized maximum width so selection and stopping taxes add. Two benchmark regimes complete the picture: unknown gradient scale in online convex optimization has constant cost, while pointwise adaptation over nested Holder classes costs order (log n / log log n)^(s1/(2s1+1)). Cast as model monitoring, the law lets an analyst inspect any of M slice metrics at any data-dependent time: the naive fixed-query band's selected coverage degrades sharply, to 0.30 at M=1 and to zero for M>=10, while the epoch-stitched certifier holds familywise coverage at an additive iterated-logarithm width cost. Experiments put both sharp predictions at risk of refutation; both survive.

Ibne Farabi Shihab, Adria Binte Habib

Department of Computer Science, Iowa State University, USA · Department of Computer Science & Engineering, Independent University of Bangladesh, Bangladesh

Minimax Estimation

Ask PDF

Aug 6, 2026cs.LG

Robust Average-Reward Markov Decision Processes: Minimax-Optimal Learning via Plug-in Reductions

Distributionally robust Markov decision processes provide a principled framework for sequential decision making under model uncertainty. We study how many samples are necessary and sufficient to learn an

\varepsilon

-optimal robust policy under the average-reward criterion. A generative model provides samples from the nominal transition kernel, whereas policy performance is evaluated over

(s,a)

-rectangular total-variation uncertainty sets of radius at most

σ

. Let

H_0

and

H_σ

denote the nominal and robust optimal bias spans, respectively. We identify

σH_0

as the perturbation scale separating high- and low-tolerance regimes. Our matching upper and lower bounds show that, up to logarithmic factors, the minimax total sample complexity is

NSA \asymp \frac{SA}{\varepsilon^2}\begin{cases} \min\{H_0,H_σ\}, & \varepsilon\gtrsimσH_0,\\ \min\{H_0,H_σ\}+σH_σ^2, & \varepsilon\lesssimσH_0. \end{cases}

Here

S

and

A

are the numbers of states and actions, and

N

is the number of samples per state-action pair. The sample complexity consists of a linear-span term that resembles the nominal AMDP results and a robustness-specific term that appears only in the low-tolerance regime. We attain these rates using reduction-based plug-in procedures that select the reduction---nominal or robust---and its discount factor: a span-informed procedure that makes these choices using known span parameters, and a span-agnostic procedure that calibrates both choices from data.

Yuepeng Yang, Yuxin Chen, Yuejie Chi

*Department of Statistics and Data Science, Yale University. · †Department of Statistics and Data Science, the Wharton School, University of Pennsylvania.

Robust Markov Decision Processes Average-Reward RL Markov Models Minimax Estimation Distributionally Robust RL Sample-Efficient RL

Ask PDF

Aug 6, 2026stat.ML

Optimal Rates for Learning with Monotone Adversaries

A monotone adversary observes an i.i.d. labeled sample and appends a finite number of further examples of its choice, every one of them labeled correctly by the target hypothesis. The learner sees a uniform shuffle of the combined sample and is scored on the original distribution. Every example is correctly labeled, but the insertions depend on the clean sample, so the combined sample is not exchangeable. Larsen, Pabbaraju, and Shetty, who introduced this model, showed that empirical risk minimization attains expected error

O((d/n)\log(n/d))

for classes of VC dimension

d

, and that every known optimal learner can be pushed away from the

Θ(d/n)

rate, optimal for PAC learning. They asked whether the extra logarithm is an artifact of those particular algorithms or an inherent consequence of the lack of exchangeability. We show that this additional cost is inherent beyond VC dimension one. In the worst case over classes of VC dimension

d

and over known finite insertion budgets, the minimax expected error is

Θ(1/n)

d=1

and

Θ((d/n)\log(n/d))

for

d\geq 2

. The same rates hold with Littlestone dimension

d_{\mathrm L}

in place of

d

, so the clean online-to-batch rate

O(d_{\mathrm L}/n)

is unattainable as well. Thus, somewhat counterintuitively, adding correctly labeled examples can make learning harder by a logarithmic factor, even for classes that admit finite mistake bounds in online learning. The dimension-one upper bound is achieved by a simple improper learner whose analysis adapts the leave-one-out argument underlying the one-inclusion graph. All of our lower bounds are elementary and come from a single construction: an explicit class and prior on which two target hypothesis, which differ a point of nonnegligible mass, produce the same sample.

Anay Mehrotra

Stanford University

Minimax Estimation Statistical Learning Theory

Ask PDF

Aug 6, 2026stat.ML

Minimax Optimal Early-Stopped Gradient Descent for Gaussian Mixture Classification

In overparameterised classification, training data can be linearly separable even when the underlying distribution is not. In this setting, gradient descent (GD) on the logistic loss diverges in norm while converging in direction to a max-margin interpolating classifier, whose implicit bias can be statistically suboptimal. In this work, we show that early stopping can overcome this suboptimality: in a Gaussian mixture model with label-flipping noise, GD stopped at an appropriate oracle time achieves minimax-optimal excess zero-one risk for covariance spectra with fast and continuous decay, including polynomial and exponential spectral decays. Our analysis combines a sharp upper bound for the early-stopped iterate with a matching statistical lower bound over arbitrary classifiers, yielding optimal rates that are validated by experiments. A central technical contribution is a new calibration result that converts excess logistic risk into excess zero-one risk; it handles the model misspecification induced by the label-flipping noise, and removes the square-root rate in standard bounds. We also establish a lower bound for linear interpolators, showing that interpolation can require exponentially more samples than early stopping to achieve the same excess risk.

Alex Buna, Shirley Xiaoqi Liu, Patrick Rebeschini

Department of Statistics, University of Oxford

Early Stopping Gradient Descent Gaussian Mixture Models Minimax Estimation Classification

Ask PDF

Aug 3, 2026stat.ML

Interaction Is Not Necessary for Order-Optimal 1-Bit Mean Estimation

This paper is concerned with one-bit mean estimation, where each independent sample is represented by a single binary message. We consider distributions on

\mathbb{R}

with mean in

[-λ,λ]

and absolute

k

-th central moment at most

σ^k

, where

k>1

is fixed. For this class, previous work attained the optimal sample complexity for general queries using a two-stage protocol. The first stage localizes the mean. The second-stage queries are chosen after localization and refine the estimate around the decoded center. We show that this interaction can be avoided by constructing a randomized fully non-adaptive protocol that fixes all queries before observing the data and matches the optimal adaptive sample complexity. For target accuracy

ε

and confidence

1-δ

, its sample complexity scales as

\log\fracλσ + \begin{cases} (σ/ε)^2\log(1/δ), & k>2,\\ (σ/ε)^2\log(σ/ε)\log(1/δ), & k=2,\\ (σ/ε)^{k/(k-1)}\log(1/δ), & 1<k<2, \end{cases}

up to constants depending only on

k

. In the range covered by the known lower bound, this rate is minimax optimal even among fully adaptive protocols. This gives a negative answer to the COLT 2026 open problem asking whether interaction is necessary for order-optimal one-bit mean estimation with general queries \citep[Open Problem~1]{lau2026open}.

Jiachen Hu, Han Zhong

Shanghai University of Finance and Economics · Shanghai Jiao Tong University

Sample Complexity Minimax Estimation

Ask PDF

Jul 30, 2026stat.ML

The Noise Premium in Adversarial Training for Kernel Regression

Adversarial training can improve the robustness of predictive models to bounded perturbations, often at the cost of statistical efficiency. We study this trade-off in kernel regression over a reproducing kernel Hilbert space (RKHS). It is shown that, under squared loss, adversarial training in RKHS introduces a term involving the product of the function norm with the mean absolute value of the response noise, which we call the \textit{noise premium}. Our analysis shows that the noise premium makes the prediction error of adversarial training converge strictly more slowly than the nonparametric minimax benchmark even after balancing approximation and estimation errors. Moreover, for a fixed perturbation budget, once the budget exceeds a certain threshold, the solution to adversarial training collapses to the zero function. To mitigate these effects of the noise premium, we propose noise-debiased adversarial training. The resulting noise-debiased estimator can attain the minimax optimal rate up to a logarithmic factor for the prediction error, raises the collapse threshold, and admits an explicit bound on the increase in adversarial loss. Numerical experiments on synthetic and real data support the theoretical findings and validate the effectiveness of the proposed noise-debiased method.

Yiling Xie, Xiaoming Huo

Department of Decision Analytics and Operations, City University of Hong Kong · H. Milton Stewart School of Industrial and Systems Engineering Georgia Institute of Technology

Adversarial Training Kernel Regression Nonparametric Regression Minimax Estimation Statistical Learning Theory

Ask PDF

Jul 30, 2026cs.LG

Tight Sample Complexity for Low-Rank Adaptation: Matching Bounds and Rank Selection

Low-Rank Adaptation (LoRA) has become the standard mechanism for fine-tuning large pretrained models, yet its statistical properties remain only partially understood. Existing generalization results provide upper bounds of the form O~(sqrt(rd/n)) or O~(rd/n), but a matching lower bound is missing, and the question of how to choose the LoRA rank r has no formal answer. Both gaps are closed here. A local Rademacher argument establishes an upper bound of O~(rd/n) on the excess risk of the empirical risk minimizer over rank-r LoRA, whenever the target adaptation has rank at most r. A matching minimax lower bound of Omega(rd/n) is then proved via a Fano-type packing of the rank-r subspace of R^{d x d}; the bound applies to any estimator whose output lies in the rank-r LoRA class. Combining the two yields a rank-selection dichotomy. For the constrained empirical risk minimizer, the optimal rank equals the intrinsic rank r*, and over-ranking strictly hurts. For adaptive estimators of the nuclear-norm-then-truncate type, over-ranking is harmless and the rate saturates at Theta~(r* d / n) regardless of r. Taken together, the three results characterize the statistical complexity of LoRA fine-tuning within the well-specified locally quadratic regime, and identify the empirically observed over-parameterization penalty as a property of unregularized empirical risk minimization rather than of the LoRA class itself. Predictions of the theory are verified on a synthetic trace-regression benchmark and on real LoRA fine-tuning across three (model, task) configurations covering DistilBERT and RoBERTa on SST-2 and MRPC. All configurations exhibit the predicted U-shape in validation loss, with two showing statistically significant loss inflation at large ranks (paired permutation p = 0.016).

Arunan J

Independent Researcher, Chennai, India.

Sample Complexity Low-Rank Adaptation Minimax Estimation Statistical Learning Theory Empirical Risk Minimization

Ask PDF

Jul 27, 2026stat.ML

Minimax Lower Bounds of Kernel Discrepancy Estimation: MMD, HSIC, KSD

Over the past 20 years, kernel discrepancies have been leveraged as a highly powerful tool for quantifying the disagreement of distributions, with numerous successful applications in two-sample, goodness-of-fit, and independence testing, among others. Their fastest estimators are known to converge at a parametric rate---

n^{-1/2}

---under mild conditions. While this rate is known to be minimax optimal on

\mathbb R^d

under strict assumptions with bounded kernels, little is known about its optimality beyond the finite-dimensional Euclidean setting with unbounded kernels. In this work, we prove that the minimax lower bound of estimation of the most popular kernel discrepancies (maximum mean discrepancy, Hilbert-Schmidt independence criterion and kernel Stein discrepancy; MMD, HSIC, KSD) is

n^{-1/2}

on general topological spaces, and under mild assumptions on the kernel; the same rates are shown (as corollaries) to hold for the estimation of the mean embedding and the centered cross-covariance operator. Our results settle the question of optimal estimation of these kernel discrepancies.

Jose Cribeiro-Ramallo, Florian Kalinke, Zoltán Szabó

Chair of Information Systems, Karlsruhe Institute of Technology, Am Fasanengarten 5, 76131 Karlsruhe, Germany · Department of Statistics, London School of Economics, Houghton Street, London, WC2A 2AE, UK

Maximum Mean Discrepancy Minimax Estimation

Ask PDF

Jul 24, 2026cs.LG

Efficient Learning of Truncated Boolean Product Distributions: Influence to the Rescue

Learning the natural parameters

z \in \mathbb{R}^n

of discrete distributions

μ_z

from independent samples constrained to a subset

S \subseteq \{0,1\}^n

is a foundational challenge in high-dimensional statistics. Existing methods for efficiently estimating truncated Boolean product distributions, notably the work of [Fotakis et al' COLT'20, Algorithmica '22], require either strong local connectivity assumptions on

S

-- a property denoted fatness -- or stringent anti-concentration assumptions and necessitate the total mass of the truncation set to be a constant with respect to

n

. Moreover, the results in [Fotakis et al' COLT'20, Algorithmica '22] suffer from sample complexities that scale as

Ω(2^n)

if the mass of

S

is exponentially small in

n

. In this work, we circumvent these limitations by analyzing the geometry of

S

under the measure

μ_z

. We refine the existing parameter estimation guarantees under the fatness assumption, improving the prior sample complexity to

O( \log n / ε^2)

for

\ell_\infty

-recovery, matching the untruncated minimax rate. We further generalize fatness using the notion of influence utilized in the analysis of Boolean functions and provide sufficient conditions for efficient inference. Notably, unlike previous work, our method does not require sampling at arbitrary parameterizations of the model. Lastly, we establish a theoretical lower bound demonstrating the sample complexity exhibits an intrinsic exponential dependence on the width of the model and the minimum distance between elements in the set.

Rohan Chauhan, Ioannis Panageas

University of California, Irvine

Efficient Inference Minimax Estimation

Ask PDF

Jul 3, 2026cs.IT

Open Problem: Is Interaction Necessary for Order-Optimal 1-bit Mean Estimation?

We ask whether interaction is necessary for order-optimal 1-bit mean estimation over nonparametric finite-moment classes. Adaptive threshold-query protocols achieve the order-optimal 1-bit minimax rate, and the same rate is attainable with general 1-bit queries using only one adaptive transition (i.e., two stages of querying). In the non-adaptive setting, threshold and interval queries are known to be highly suboptimal, but the case of arbitrary non-adaptive quantizers remains unresolved. Can such quantizers match the adaptive rate, yielding an optimal one-shot protocol? Or is the known two-stage estimator stage-optimal, with a single adaptive transition being necessary and sufficient?

Ivan Lau, Jonathan Scarlett

National University of Singapore

Minimax Estimation

Ask PDF

Jul 2, 2026stat.ML

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, 2026math.ST

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 \emph{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

Momentum

Related topics

Latest papers 50