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.

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
Sample Complexities of Estimating Gumbel--Max Watermark Proportions with and without Reduction to Pivotal Statistics
Jun 30, 2026Shuwen Chai, Qiaosen WangMinimax Estimation LLM Watermarking
Northwestern University · University of Chicago
The Fundamental Limits of Valid Transport Map Estimation
Jun 29, 2026Sivaraman BalakrishnanMinimax Estimation Generative Modeling
Department of Statistics and Data Science† · Machine Learning Department‡
Adversarial Contamination Meets Hard Thresholding: An Iterative Algorithm with Signal Adaptivity and Minimax Optimality
Jun 26, 2026Shixiang Liu, Hanming YangRobust Regression Sparse Recovery
School of Statistics, Renmin University of China · Institute of Statistics and Big Data, Renmin University of China
Fast algorithms for learning a Gaussian under halfspace truncation with optimal sample complexity
Jun 25, 2026Haitong Liu, Deepak Narayanan Sridharan, David Steurer +1Minimax Estimation Statistical Learning Theory
ETH Zurich
Black-Box Assisted Regression: Phase Transitions and Minimax Optimality
Jun 24, 2026Yan ZhouResidual Learning Nonparametric Regression
School of Mathematics and Statistics, Changsha University of Science and Technology.
On the Curse of Dimensionality in Private Sparse Covariance Estimation and PCA
Jun 20, 2026Syamantak Kumar, Shourya Pandey, Purnamrita Sarkar +1Principal Component Analysis Minimax Estimation
University of Texas at Austin
Optimal Deterministic Multicalibration and Omniprediction
Jun 18, 2026Georgy Noarov, Aaron RothMinimax Estimation Model Calibration
University of Pennsylvania
A Complexity Measure for Active Learning in Multi-group Mean Estimation
Jun 12, 2026Abdellah Aznag, Rachel Cummings, Adam N. ElmachtoubMulti-Armed Bandits Active Learning
Department of Industrial Engineering and Operations Research & Data Science Institute, Columbia University
Pointwise Complexity for Gaussian Fields: Upper Envelopes, Algorithmic Lower Bounds, and Separation
Jun 6, 2026Yunbei XuGaussian Processes Minimax Estimation
National University of Singapore
A Temporal Spatial Minimax Rate for Smoothly-Varying Distributions in Wasserstein Space
Jun 5, 2026Munsik KimMinimax Estimation Spatiotemporal Forecasting
Improved Distribution Estimation in $\ell_\infty$
May 28, 2026Doron Cohen, Aryeh Kontorovich, Yonatan LivshitzMinimax Estimation
Department of Computer Science, Ben-Gurion University of the Negev, Beer-Sheva, Israel
Reward Transfer from Inverse Reinforcement Learning: A Coupled Minimax Approach
May 27, 2026Guang-Yuan Hao, Lars van der Laan, Aurélien Bibaut +1Reinforcement Learning Minimax Estimation
Cornell Tech, Cornell University · Netflix Research · Department of Statistics, University of Washington
Minimax Limits of k-Fold Cross-Validation via Majority
May 25, 2026Ido Nachum, Rüdiger Urbanke, Thomas WeinbergerMinimax Estimation Statistical Learning Theory
University of Haifa, Haifa, Israel. · EPFL, Lausanne, Switzerland.
Instance-Optimal Estimation with Multiple LLM Judges on a Budget
May 22, 2026Junghyun Lee, Sanghwa Kim, Yassir Jedra +2Parameter Estimation LLM Evaluation
KAIST AI · ICL EEE · KTH EECS
Extended Wasserstein-GAN Approach to Causal Distribution Learning: Density-Free Estimation and Minimax Optimality
May 11, 2026Shu Tamano, Masaaki ImaizumiCausal Effect Estimation Causal Counterfactual Generation
1The University of Tokyo · 2Japan Institute for Health Security · 3RIKEN Center for Advanced Intelligence Project +1
The Minimax Rate of Perturbed Second-Order Calibration
May 8, 2026Kamil Ciosek, Banafsheh Rafiee, Sina Ghiassian +1Post-Hoc Calibration Minimax Estimation
Spotify
ConquerNet: Convolution-Smoothed Quantile ReLU Neural Networks with Minimax Guarantees
May 7, 2026Tianpai Luo, Fangwei Wu, Weichi WuQuantile Regression Minimax Estimation
Department of Statistics and Data Science Tsinghua University Beijing, 100084, China
Direct Estimation of Schrödinger Bridge Time-Series Drifts: Finite-Sample, Asymptotic, and Adaptive Guarantees
May 6, 2026Othmane Mazhar, Huyên PhamParameter Estimation Schrödinger Bridges
LPSM, Sorbonne Université and Université Paris Cité · École Polytechnique, CMAP
Information-theoretic Limits of Learning and Estimation
May 6, 2026Abbas El Gamal, Maxim RaginskyInformation-Theoretic Generalization Bounds Minimax Estimation
Stanford University* · UIUC**
Minimax Optimality and Spectral Routing for Majority-Vote Ensembles under Markov Dependence
Apr 15, 2026Ibne Farabi Shihab, Sanjeda Akter, Anuj SharmaEnsemble Learning Majority Voting
Department of Computer Science, Iowa State University · Department of Civil, Construction & Environmental Engineering, Iowa State University
Online Covariance Estimation in Averaged SGD: Improved Batch-Mean Rates and Minimax Optimality via Trajectory Regression
Apr 12, 2026Yijin Ni, Xiaoming HuoPolyak-Ruppert Averaging Covariance Estimation
H. Milton Stewart School of Industrial and Systems Engineering, Georgia Institute of Technology
Order-Optimal Sequential 1-Bit Mean Estimation in General Tail Regimes
Apr 9, 2026Ivan Lau, Jonathan ScarlettMinimax Estimation Adaptive Sampling
National University of Singapore
Efficient machine unlearning with minimax optimality
Apr 7, 2026Jingyi Xie, Linjun Zhang, Sai LiMachine Unlearning Statistical Learning Theory
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
Minimaxity and Admissibility of Bayesian Neural Networks
Apr 6, 2026Daniel Andrew Coulson, Martin T. WellsBayesian Neural Networks Minimax Estimation
Department of Statistics and Data Science, Cornell University
Minimax and Adaptive Covariance Matrix Estimation under Differential Privacy
Mar 20, 2026T. Tony Cai, Yicheng LiCovariance Estimation Parameter Estimation
Department of Statistics and Data Science, The Wharton School, University of Pennsylvania · KLATASDS-MOE, School of Statistics, East China Normal University
Deep regression learning from dependent observations with minimum error entropy principle
Mar 11, 2026William Kengne, Modou WadeNonparametric Regression Minimax Estimation
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
The Epistemic Support-Point Filter: Jaynesian Maximum Entropy Meets Popperian Falsification
Mar 10, 2026Moriba Kemessia JahEpistemic Uncertainty Minimax Estimation
Black Swan Research Group, GaiaVerse, Ltd. · Jah Decision Intelligence Group, Aerospace Engineering & Engineering Mechanics, The University of Texas at Austin
On the Statistical Optimality of Optimal Decision Trees
Mar 5, 2026Zineng Xu, Subhro Ghosh, Yan Shuo TanDecision Tree Learning Statistical Learning Theory
Department of Statistics and Data Science, National University of Singapore · Department of Mathematics, National University of Singapore

Jul 2, 2026J/K move · Enter open · S save

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

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

Open paper AskPDF arXiv

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.