Distribution-Free Robust Linear Regression
arXiv:2102.12919 · doi:10.4171/MSL/27
Abstract
We study random design linear regression with no assumptions on the distribution of the covariates and with a heavy-tailed response variable. In this distribution-free regression setting, we show that boundedness of the conditional second moment of the response given the covariates is a necessary and sufficient condition for achieving nontrivial guarantees. As a starting point, we prove an optimal version of the classical in-expectation bound for the truncated least squares estimator due to Györfi, Kohler, Krzyżak, and Walk. However, we show that this procedure fails with constant probability for some distributions despite its optimal in-expectation performance. Then, combining the ideas of truncated least squares, median-of-means procedures, and aggregation theory, we construct a non-linear estimator achieving excess risk of order with an optimal sub-exponential tail. While existing approaches to linear regression for heavy-tailed distributions focus on proper estimators that return linear functions, we highlight that the improperness of our procedure is necessary for attaining nontrivial guarantees in the distribution-free setting.
29 pages, to appear in Mathematical Statistics and Learning
References in corpus (8)
- Recent Advances in Algorithmic High-Dimensional Robust Statistics
- Fast learning rates in statistical inference through aggregation
- Dimension-free PAC-Bayesian bounds for matrices, vectors, and linear least squares regression
- Exact minimax risk for linear least squares, and the lower tail of sample covariance matrices
- Robust regression with covariate filtering: Heavy tails and adversarial contamination
- Optimal Robust Linear Regression in Nearly Linear Time
- Excess risk bounds in robust empirical risk minimization
- Learning bounded subsets of