# High-probability minimax lower bounds

arXiv: https://arxiv.org/abs/2406.13447 · HTML: https://mlsanity.com/paper/2406.13447/

## Key facts

- Cited by 13 papers in the map (data through 14 Oct 2026).
- Builds on 10 of its 57 references that are in the map.
- First posted on arXiv 19 Jun 2024.

## Builds on (most cited first, 10 of 10)

- [Mean estimation and regression under heavy-tailed distributions--a survey](https://mlsanity.com/paper/1906.04280/) (2019)
- [Robust Covariance and Scatter Matrix Estimation under Huber's Contamination Model](https://mlsanity.com/paper/1506.00691/) (2015)
- [Sub-Gaussian estimators of the mean of a random vector](https://mlsanity.com/paper/1702.00482/) (2017)
- [Robust subgaussian estimation of a mean vector in nearly linear time](https://mlsanity.com/paper/1906.03058/) (2019)
- [SLOPE - Adaptive variable selection via convex optimization](https://mlsanity.com/paper/1407.3824/) (2014)
- [Mean Estimation with Sub-Gaussian Rates in Polynomial Time](https://mlsanity.com/paper/1809.07425/) (2018)
- [High-dimensional principal component analysis with heterogeneous missingness](https://mlsanity.com/paper/1906.12125/) (2019)
- [The Price of Adaptivity in Stochastic Convex Optimization](https://mlsanity.com/paper/2402.10898/) (2024)
- [Minimax Linear Regression under the Quantile Risk](https://mlsanity.com/paper/2406.12145/) (2024)
- [Anytime-valid t-tests and confidence sequences for Gaussian means with unknown variance](https://mlsanity.com/paper/2310.03722/) (2023)

## Built on by (most cited first, 13 of 13)

- [The Pitfalls of Imitation Learning when Actions are Continuous](https://mlsanity.com/paper/2503.09722/) (2025)
- [Segmenting Human-LLM Co-authored Text via Change Point Detection](https://mlsanity.com/paper/2605.03723/) (2026)
- [Optimal Recovery Meets Minimax Estimation](https://mlsanity.com/paper/2502.17671/) (2025)
- [Risk level dependent Minimax Quantile lower bounds for Interactive Statistical Decision Making](https://mlsanity.com/paper/2510.05808/) (2025)
- [Efficient machine unlearning with minimax optimality](https://mlsanity.com/paper/2604.05669/) (2026)
- [Robust Estimation Under Heterogeneous Corruption Rates](https://mlsanity.com/paper/2508.15051/) (2025)
- [High-Probability Bounds For Heterogeneous Local Differential Privacy](https://mlsanity.com/paper/2510.11895/) (2025)
- [Sharp Concentration Inequalities: Phase Transition and Mixing of Orlicz Tails with Variance](https://mlsanity.com/paper/2603.25934/) (2026)
- [Near-optimal Rank Adaptive Inference of High Dimensional Matrices](https://mlsanity.com/paper/2510.08117/) (2025)
- [On-Average Stability of Multipass Preconditioned SGD and Effective Dimension](https://mlsanity.com/paper/2603.11989/) (2026)
- [Optimal Rates for Pure varepsilon-Differentially Private Stochastic Convex Optimization with Heavy Tails](https://mlsanity.com/paper/2604.06492/) (2026)
- [Instantiating Bayesian CVaR lower bounds in Interactive Decision Making Problems](https://mlsanity.com/paper/2604.12519/) (2026)
- [Minimax Quantile Lower Bounds for Interactive Statistical Decision Making with Privacy](https://mlsanity.com/paper/2606.23096/) (2026)

## Abstract (arXiv)

The minimax risk is often considered as a gold standard against which we can compare specific statistical procedures. Nevertheless, as has been observed recently in robust and heavy-tailed estimation problems, the inherent reduction of the (random) loss to its expectation may entail a significant loss of information regarding its tail behaviour. In an attempt to avoid such a loss, we introduce the notion of a minimax quantile, and seek to articulate its dependence on the quantile level. To this end, we develop high-probability variants of the classical Le Cam and Fano methods, as well as a technique to convert local minimax risk lower bounds to lower bounds on minimax quantiles. To illustrate the power of our framework, we deploy our techniques on several examples, recovering recent results in robust mean estimation and stochastic convex optimisation, as well as obtaining several new results in covariance matrix estimation, sparse linear regression, nonparametric density estimation and isotonic regression. Our overall goal is to argue that minimax quantiles can provide a finer-grained understanding of the difficulty of statistical problems, and that, in wide generality, lower bounds on these quantities can be obtained via user-friendly tools.