# Minimax Linear Regression under the Quantile Risk

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

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- Builds on 9 of its 33 references that are in the map.
- First posted on arXiv 17 Jun 2024.

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

- [An Introduction to Matrix Concentration Inequalities](https://mlsanity.com/paper/1501.01571/) (2015)
- [Loss minimization and parameter estimation with heavy tails](https://mlsanity.com/paper/1307.1827/) (2013)
- [Sub-Gaussian estimators of the mean of a random vector](https://mlsanity.com/paper/1702.00482/) (2017)
- [Exact minimax risk for linear least squares, and the lower tail of sample covariance matrices](https://mlsanity.com/paper/1912.10754/) (2019)
- [Covariance Estimation: Optimal Dimension-free Guarantees for Adversarial Corruption and Heavy Tails](https://mlsanity.com/paper/2205.08494/) (2022)
- [Fast Algorithms for ℓp-Regression](https://mlsanity.com/paper/2211.03963/) (2022)
- [`local' vs. `global' parameters -- breaking the gaussian complexity barrier](https://mlsanity.com/paper/1504.02191/) (2015)
- [Optimal Excess Risk Bounds for Empirical Risk Minimization on p-Norm Linear Regression](https://mlsanity.com/paper/2310.12437/) (2023)
- [Optimal Sub-Gaussian Mean Estimation in ℝ](https://mlsanity.com/paper/2011.08384/) (2020)

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

- [High-probability minimax lower bounds](https://mlsanity.com/paper/2406.13447/) (2024)
- [A Geometric Analysis of PCA](https://mlsanity.com/paper/2510.20978/) (2025)
- [On the Efficiency of ERM in Feature Learning](https://mlsanity.com/paper/2411.12029/) (2024)

## Abstract (arXiv)

We study the problem of designing minimax procedures in linear regression under the quantile risk. We start by considering the realizable setting with independent Gaussian noise, where for any given noise level and distribution of inputs, we obtain the exact minimax quantile risk for a rich family of error functions and establish the minimaxity of OLS. This improves on the known lower bounds for the special case of square error, and provides us with a lower bound on the minimax quantile risk over larger sets of distributions. Under the square error and a fourth moment assumption on the distribution of inputs, we show that this lower bound is tight over a larger class of problems. Specifically, we prove a matching upper bound on the worst-case quantile risk of a variant of the recently proposed min-max regression procedure, thereby establishing its minimaxity, up to absolute constants. We illustrate the usefulness of our approach by extending this result to all p-th power error functions for p ∈ (2, ∞). Along the way, we develop a generic analogue to the classical Bayesian method for lower bounding the minimax risk when working with the quantile risk, as well as a tight characterization of the quantiles of the smallest eigenvalue of the sample covariance matrix.