Robust regression with covariate filtering: Heavy tails and adversarial contamination

• URL: http://arxiv.org/abs/2009.12976v2
• Date: Mon, 17 May 2021 16:40:45 GMT
• Title: Robust regression with covariate filtering: Heavy tails and adversarial contamination
• Authors: Ankit Pensia, Varun Jog, Po-Ling Loh
• Abstract summary: We show how to modify the Huber regression, least trimmed squares, and least absolute deviation estimators to obtain estimators simultaneously computationally and statistically efficient in the stronger contamination model. We show that the Huber regression estimator achieves near-optimal error rates in this setting, whereas the least trimmed squares and least absolute deviation estimators can be made to achieve near-optimal error after applying a postprocessing step.
• Score: 6.939768185086755
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We study the problem of linear regression where both covariates and responses are potentially (i) heavy-tailed and (ii) adversarially contaminated. Several computationally efficient estimators have been proposed for the simpler setting where the covariates are sub-Gaussian and uncontaminated; however, these estimators may fail when the covariates are either heavy-tailed or contain outliers. In this work, we show how to modify the Huber regression, least trimmed squares, and least absolute deviation estimators to obtain estimators which are simultaneously computationally and statistically efficient in the stronger contamination model. Our approach is quite simple, and consists of applying a filtering algorithm to the covariates, and then applying the classical robust regression estimators to the remaining data. We show that the Huber regression estimator achieves near-optimal error rates in this setting, whereas the least trimmed squares and least absolute deviation estimators can be made to achieve near-optimal error after applying a postprocessing step.

Related papers

• Multivariate root-n-consistent smoothing parameter free matching estimators and estimators of inverse density weighted expectations [51.000851088730684]
  We develop novel modifications of nearest-neighbor and matching estimators which converge at the parametric $sqrt n $-rate. We stress that our estimators do not involve nonparametric function estimators and in particular do not rely on sample-size dependent parameters smoothing.
  arXiv  Detail & Related papers  (2024-07-11T13:28:34Z)
• Relaxed Quantile Regression: Prediction Intervals for Asymmetric Noise [51.87307904567702]
  Quantile regression is a leading approach for obtaining such intervals via the empirical estimation of quantiles in the distribution of outputs. We propose Relaxed Quantile Regression (RQR), a direct alternative to quantile regression based interval construction that removes this arbitrary constraint. We demonstrate that this added flexibility results in intervals with an improvement in desirable qualities.
  arXiv  Detail & Related papers  (2024-06-05T13:36:38Z)
• Error Reduction from Stacked Regressions [12.657895453939298]
  Stacking regressions is an ensemble technique that forms linear combinations of different regression estimators to enhance predictive accuracy. In this paper, we learn these weights analogously by minimizing a regularized version of the empirical risk subject to a nonnegativity constraint. Thanks to an adaptive shrinkage effect, the resulting stacked estimator has strictly smaller population risk than best single estimator among them.
  arXiv  Detail & Related papers  (2023-09-18T15:42:12Z)
• Quantized Low-Rank Multivariate Regression with Random Dithering [23.81618208119832]
  Low-rank multivariate regression (LRMR) is an important statistical learning model. We focus on the estimation of the underlying coefficient matrix. We employ uniform quantization with random dithering, i.e., we add appropriate random noise to the data before quantization. We propose the constrained Lasso and regularized Lasso estimators, and derive the non-asymptotic error bounds.
  arXiv  Detail & Related papers  (2023-02-22T08:14:24Z)
• Scalable Gaussian-process regression and variable selection using Vecchia approximations [3.4163060063961255]
  Vecchia-based mini-batch subsampling provides unbiased gradient estimators. We propose Vecchia-based mini-batch subsampling, which provides unbiased gradient estimators.
  arXiv  Detail & Related papers  (2022-02-25T21:22:38Z)
• Near-optimal inference in adaptive linear regression [60.08422051718195]
  Even simple methods like least squares can exhibit non-normal behavior when data is collected in an adaptive manner. We propose a family of online debiasing estimators to correct these distributional anomalies in at least squares estimation. We demonstrate the usefulness of our theory via applications to multi-armed bandit, autoregressive time series estimation, and active learning with exploration.
  arXiv  Detail & Related papers  (2021-07-05T21:05:11Z)
• Distribution-Free Robust Linear Regression [5.532477732693]
  We study random design linear regression with no assumptions on the distribution of the covariates. We construct a non-linear estimator achieving excess risk of order $d/n$ with the optimal sub-exponential tail. We prove an optimal version of the classical bound for the truncated least squares estimator due to Gy"orfi, Kohler, Krzyzak, and Walk.
  arXiv  Detail & Related papers  (2021-02-25T15:10:41Z)
• Rao-Blackwellizing the Straight-Through Gumbel-Softmax Gradient Estimator [93.05919133288161]
  We show that the variance of the straight-through variant of the popular Gumbel-Softmax estimator can be reduced through Rao-Blackwellization. This provably reduces the mean squared error. We empirically demonstrate that this leads to variance reduction, faster convergence, and generally improved performance in two unsupervised latent variable models.
  arXiv  Detail & Related papers  (2020-10-09T22:54:38Z)
• Fast OSCAR and OWL Regression via Safe Screening Rules [97.28167655721766]
  Ordered $L_1$ (OWL) regularized regression is a new regression analysis for high-dimensional sparse learning. Proximal gradient methods are used as standard approaches to solve OWL regression. We propose the first safe screening rule for OWL regression by exploring the order of the primal solution with the unknown order structure.
  arXiv  Detail & Related papers  (2020-06-29T23:35:53Z)
• Component-wise Adaptive Trimming For Robust Mixture Regression [15.633993488010292]
  Existing robust mixture regression methods suffer from outliers as they either conduct outlier estimation in presence of outliers, or rely on prior knowledge of the level of contamination. Here we propose a fast and efficient robust mixture regression algorithm called adaptive-wise Adaptive Component (CAT) method.
  arXiv  Detail & Related papers  (2020-05-23T20:59:16Z)
• Estimating Gradients for Discrete Random Variables by Sampling without Replacement [93.09326095997336]
  We derive an unbiased estimator for expectations over discrete random variables based on sampling without replacement. We show that our estimator can be derived as the Rao-Blackwellization of three different estimators.
  arXiv  Detail & Related papers  (2020-02-14T14:15:18Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.