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

Subspace Uncertainty and Sharp Sampling Thresholds on the Boolean Cube
Oct 8, 2026Thomas WeinbergerSample Complexity Statistical Learning Theory
School of Computer and Communication Sciences, EPFL, Switzerland
Holdout Best-of-N: Unbiased Evaluation and Its Cost
Oct 6, 2026Shrey Shah, Yinheng LiBest-of-N Sampling Policy Evaluation
Detecting a Shift Is Not Enough: Exact Minimax Limits of Linear Representation Repair
Oct 6, 2026Anuar Aimoldin, Yankai Chen, Ayana Mussabayeva +1Distribution Shift Robustness Minimax Estimation
Mohamed bin Zayed University of Artificial Intelligence (MBZUAI)
Uniform Discrete Diffusion Models are Minimax Optimal for Estimating Distributions with Small Effective Support Size
Oct 6, 2026Dongsun Yoon, Saptarshi ChakrabortyMinimax Estimation Statistical Learning Theory
Department of Statistics, University of Michigan
Assumption-lean logistic regression with missing covariates
Oct 5, 2026Jyotishka Ray Choudhury, Kabir Aladin Verchand, Richard J. Samworth +1Logistic Regression Learning with Missing Data
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
Minimax Additive Regression under Unknown Dependent Designs
Sep 30, 2026Baptiste Ferrere, Fabrice Gamboa, Jean-Michel LoubesNonparametric Regression Minimax Estimation
Université de Toulouse EDF R&D · Université de Toulouse ANITI
Minimax rates for learning spectral Barron functions by deep ReLU neural networks
Sep 30, 2026Songqiu Ma, Yunfei YangReLU Neural Networks Minimax Estimation
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.
Sharp Limits for Honest Uncertainty in Hard-Budget Repeated Evaluation
Sep 24, 2026Yezhou Cheng, Runjia Du, Zeming Liu +5Confidence Region Estimation Uncertainty Quantification
Independent · Northwestern University · Pinterest, Inc.
Error Bounds for Statistical Estimators in BTL Model with Parametric Multivariate Utility Functions
Sep 22, 2026Yicheng Li, Huifu XuParameter Estimation Minimax Estimation
Department of Systems Engineering and Engineering Management, The Chinese University of Hong Kong.
Statistical Gains from Looped Estimation under Parameter Budgets
Sep 22, 2026Xinyu Tian, Xiaotong ShenParameter Estimation Minimax Estimation
School of Statistics, University of Minnesota
Optimal Tradeoffs Between Network Size and Parameter Magnitude in Neural Approximation and Minimax Regression
Sep 22, 2026Baicheng Li, Zuowei Shen, Haizhao Yang +1Neural Network Optimization Nonparametric Regression
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.
Conformalized Quantile Regression and Minimax Limits of Fixed-Score Calibration under Known Covariate Shift
Sep 21, 2026Rustam Isaev, Anton Conrad, Denis Belomestny +2Conformal Prediction Covariate Shift
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
Optimal estimation for Functional Linear Regression with Noisy Discretized Data
Sep 8, 2026Sixtine SphabmixayNonparametric Regression Minimax Estimation
Université Paris Cité, CNRS, MAP5, F-75006 Paris, France
Non-Adaptive 1-Bit Mean Estimation: Minimax Rates and the Sample-Interval Tradeoff
Sep 8, 2026Ivan Lau, Jonathan ScarlettMinimax Estimation
National University of Singapore
Sharp Structure-Agnostic Minimax Risk for Partial Linear Models
Sep 7, 2026Haichen Hu, David Simchi-LeviDouble ML Semiparametric Inference
Center for Computational Science and Engineering, MIT · Department of Civil and Environmental Engineering, MIT · Institute for Data, Systems, and Society, MIT
Minimax bounds for watermarked and masked recursive discrete distribution estimation
Aug 31, 2026Millen Kanabar, Michael GastparDataset Watermarking Minimax Estimation
School of Computer and Communication Sciences, EPFL, Switzerland
Algorithms for adaptive and heteroskedastic linear regression at the computational threshold
Aug 19, 2026Spencer Compton, Tselil SchrammMinimax Estimation Heteroscedastic Regression
Stanford University
Hierarchical Empirical-Bayes Naive Bayes: Minimax Smoothing and Calibration with AODE Extension
Aug 11, 2026Nguyen Thai Anh, Truong Viet Vu, Tran Thien Thanh +2Probability Calibration Empirical Bayes
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
The Cost of Adaptivity: Matching Lower Bounds Across Learning Problems
Aug 9, 2026Ibne Farabi Shihab, Adria Binte HabibMinimax Estimation
Department of Computer Science, Iowa State University, USA · Department of Computer Science & Engineering, Independent University of Bangladesh, Bangladesh
Robust Average-Reward Markov Decision Processes: Minimax-Optimal Learning via Plug-in Reductions
Aug 6, 2026Yuepeng Yang, Yuxin Chen, Yuejie ChiRobust Markov Decision Processes Average-Reward RL
*Department of Statistics and Data Science, Yale University. · †Department of Statistics and Data Science, the Wharton School, University of Pennsylvania.
Optimal Rates for Learning with Monotone Adversaries
Aug 6, 2026Anay MehrotraMinimax Estimation Statistical Learning Theory
Stanford University
Minimax Optimal Early-Stopped Gradient Descent for Gaussian Mixture Classification
Aug 6, 2026Alex Buna, Shirley Xiaoqi Liu, Patrick RebeschiniEarly Stopping Gradient Descent
Department of Statistics, University of Oxford
Interaction Is Not Necessary for Order-Optimal 1-Bit Mean Estimation
Aug 3, 2026Jiachen Hu, Han ZhongSample Complexity Minimax Estimation
Shanghai University of Finance and Economics · Shanghai Jiao Tong University
The Noise Premium in Adversarial Training for Kernel Regression
Jul 30, 2026Yiling Xie, Xiaoming HuoAdversarial Training Kernel Regression
Department of Decision Analytics and Operations, City University of Hong Kong · H. Milton Stewart School of Industrial and Systems Engineering Georgia Institute of Technology
Tight Sample Complexity for Low-Rank Adaptation: Matching Bounds and Rank Selection
Jul 30, 2026Arunan JSample Complexity Low-Rank Adaptation
Independent Researcher, Chennai, India.
Minimax Lower Bounds of Kernel Discrepancy Estimation: MMD, HSIC, KSD
Jul 27, 2026Jose Cribeiro-Ramallo, Florian Kalinke, Zoltán SzabóMaximum Mean Discrepancy Minimax Estimation
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
Efficient Learning of Truncated Boolean Product Distributions: Influence to the Rescue
Jul 24, 2026Rohan Chauhan, Ioannis PanageasEfficient Inference Minimax Estimation
University of California, Irvine
Open Problem: Is Interaction Necessary for Order-Optimal 1-bit Mean Estimation?
Jul 3, 2026Ivan Lau, Jonathan ScarlettMinimax Estimation
National University of Singapore
Contaminated Multi-task Learning with Heterogeneity: Fundamental Limits and Optimal Algorithms
Jul 2, 2026Ye Tian, Mengchu Li, Marco Avella MedinaMulti-Task Learning Minimax Estimation
Department of Statistics, Pennsylvania State University · School of Mathematics, University of Birmingham · Department of Statistics, Columbia University
Aggregation with Exponential Weights is Optimal in Expectation
Jul 2, 2026Mikael Møller Høgsgaard, Patrick Rebeschini, Tobias WegelEnsemble Learning Minimax Estimation
Department of Statistics, University of Oxford · Department of Computer Science, ETH Zurich

Oct 8, 2026, math.PRJ/K move · Enter open · S save

Subspace Uncertainty and Sharp Sampling Thresholds on the Boolean Cube

Thomas Weinberger

School of Computer and Communication Sciences, EPFL, Switzerland

Sample Complexity Statistical Learning Theory Minimax Estimation

Open paper AskPDF arXiv

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)\}

Momentum

Related topics

Latest papers 50