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"{o}rfi, Kohler, Krzy.{z}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.
Recommendations
- Robust linear least squares regression
- Loss minimization and parameter estimation with heavy tails
- Mean estimation and regression under heavy-tailed distributions: A survey
- Efficient algorithms and lower bounds for robust linear regression
- Iteratively reweighted \(\ell_1\)-penalized robust regression
Cites work
- scientific article; zbMATH DE number 3954047 (Why is no real title available?)
- scientific article; zbMATH DE number 3790208 (Why is no real title available?)
- scientific article; zbMATH DE number 1522808 (Why is no real title available?)
- scientific article; zbMATH DE number 194744 (Why is no real title available?)
- scientific article; zbMATH DE number 3446442 (Why is no real title available?)
- scientific article; zbMATH DE number 1420699 (Why is no real title available?)
- scientific article; zbMATH DE number 3320125 (Why is no real title available?)
- A theory of the learnable
- Adaptive importance sampling in least-squares Monte Carlo algorithms for backward stochastic differential equations
- Aggregation via empirical risk minimization
- An unrestricted learning procedure
- Challenging the empirical mean and empirical variance: a deviation study
- Combining different procedures for adaptive regression
- Competitive On-line Statistics
- Conditions d'intégrabilité pour les multiplicateurs dans le TLC banachique. (Integrability conditions for multiplicators in the central limit theorem in Banach spaces)
- Convergence of the Robbins-Monro method for linear problems in a Banach space
- Convergence rates of least squares regression estimators with heavy-tailed errors
- Empirical entropy, minimax regret and minimax risk
- Empirical risk minimization for heavy-tailed losses
- Extending the scope of the small-ball method
- Fast learning rates in statistical inference through aggregation
- Geometric median and robust estimation in Banach spaces
- How Many Variables Should be Entered in a Regression Equation?
- Improving the sample complexity using global data
- Learning Bounded Subsets of Lₚ
- Learning Theory and Kernel Machines
- Learning by mirror averaging
- Learning without concentration
- Local Rademacher complexities
- Loss minimization and parameter estimation with heavy tails
- Mean estimation and regression under heavy-tailed distributions: A survey
- Mixing strategies for density estimation.
- Near-optimal mean estimators with respect to general norms
- Nonparametric stochastic approximation with large step-sizes
- On aggregation for heavy-tailed classes
- On optimality of empirical risk minimization in linear aggregation
- On the stability and accuracy of least squares approximations
- On the strong universal consistency of a series type regression estimate
- Optimal rates for the regularized least-squares algorithm
- Performance of empirical risk minimization in linear aggregation
- Predicting \(\{ 0,1\}\)-functions on randomly drawn points
- Quantitative error estimates for a least-squares Monte Carlo algorithm for American option pricing
- Random generation of combinatorial structures from a uniform distribution
- Regression function estimation on non compact support in an heteroscesdastic model
- Relative expected instantaneous loss bounds
- Relative loss bounds for on-line density estimation with the exponential family of distributions
- Risk minimization by median-of-means tournaments
- Robust Statistics
- Robust \(k\)-means clustering for distributions with two moments
- Robust covariance estimation under \(L_4\)-\(L_2\) norm equivalence
- Robust linear least squares regression
- Robust machine learning by median-of-means: theory and practice
- Robust multivariate mean estimation: the optimality of trimmed mean
- Robust statistical learning with Lipschitz and convex loss functions
- Sub-Gaussian estimators of the mean of a random vector
- Sub-Gaussian mean estimators
- The lower tail of random quadratic forms with applications to ordinary least squares
- The sample complexity of learning linear predictors with the squared loss
- The space complexity of approximating the frequency moments
- Weak convergence and empirical processes. With applications to statistics
Cited in
(6)- Robust linear regression with broad distributions of errors
- Suboptimality of constrained least squares and improvements via non-linear predictors
- Nonexact oracle inequalities, \(r\)-learnability, and fast rates
- An elementary analysis of ridge regression with random design
- Least squares regression under weak moment conditions
- Robust linear least squares regression
This page was built for publication: Distribution-free robust linear regression
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2113267)
