Distribution-free robust linear regression
From MaRDI portal
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.
Summary: 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 non-trivial 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-ofmeans procedures, and aggregation theory, we construct a non-linear estimator achieving excess risk of order \(d/n\) with the 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 non-trivial guarantees in the distribution-free setting.
Recommendations
Cites work
- 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?
- 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?)
- Improving the sample complexity using global data
- Learning Bounded Subsets of Lₚ
- Learning by mirror averaging
- Learning Theory and Kernel Machines
- 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 \(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
- Robust Statistics
- 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
(9)- Robust linear regression with broad distributions of errors
- An elementary analysis of ridge regression with random design
- Suboptimality of constrained least squares and improvements via non-linear predictors
- Nonexact oracle inequalities, r-learnability, and fast rates
- Robust linear least squares regression
- Least squares regression under weak moment conditions
- Covariance estimation: optimal dimension-free guarantees for adversarial corruption and heavy tails
- Trimmed sample means for robust uniform mean estimation and regression
- The limits of assumption-free tests for algorithm performance
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)
