Robust regression with covariate filtering: Heavy tails and adversarial contamination

Ankit Pensia, Varun Jog, Po-Ling LoharXiv 2020 · OpenReview

Abstract

Linear regression is often compromised by heavy-tailed distributions and adversarial outliers. While classical robust estimators like Huber regression address outliers in response variables, they remain vulnerable to high-leverage points in the covariates. This paper presents a "filter-then-regress" framework that preprocesses covariates to ensure stability before applying robust M-estimators. We demonstrate that this simple modification allows Huber, Least Trimmed Squares (LTS), and Least Absolute Deviation (LAD) estimators to achieve near-optimal error rates under strong contamination models, effectively bridging the gap between computational efficiency and statistical robustness.

Introduction

Linear regression serves as a foundational tool in statistical modeling, yet its standard implementation—Ordinary Least Squares (OLS)—is notoriously sensitive to data corruption. In real-world scenarios, data often deviates from the ideal Gaussian assumption, exhibiting heavy tails or containing malicious outliers. While robust M-estimators like Huber regression were designed to mitigate the impact of outliers in the response variable ($y$), they are frequently derailed by outliers in the covariates ($X$), known as high-leverage points.

This vulnerability is particularly acute in the "strong contamination model," where an adversary can corrupt both inputs and outputs. Recent theoretical solutions have often relied on complex, computationally expensive methods like Sum-of-Squares programming. This work asks whether we can achieve high-end robustness using simple, classical estimators by introducing a targeted preprocessing step.

The Filter-then-Regress Framework

The core contribution of this work is a two-stage algorithmic framework that restores the robustness of classical estimators through covariate filtering.

1. Covariate Filtering

Before running any regression, the algorithm applies an iterative filtering process to the covariates. The goal is to identify a subset of the data that is "stable," meaning its empirical covariance matrix is approximately isotropic (well-behaved in all directions). If a specific data point contributes too much to the spectral norm of the covariance, it is flagged as a potential outlier and removed. This ensures that no single point or small group of points can exert undue influence on the regression outcome.

2. Robust Regression

Following the filtering step, standard robust estimators are applied to the remaining "cleaned" data. The authors specifically analyze three estimators:

  • Huber Regression: A convex loss function that behaves like squared error for small residuals and absolute error for large ones.
  • Least Trimmed Squares (LTS): An estimator that minimizes the sum of the smallest squared residuals.
  • Least Absolute Deviation (LAD): An estimator that minimizes the sum of absolute residuals.

For scenarios involving asymmetric noise, the authors introduce a symmetrization trick—subtracting pairs of observations—to satisfy theoretical assumptions without losing the underlying signal.

Theoretical Insights and Stability

The primary insight of this research is that the "approximate isotropy" (stability) of the covariates is a sufficient condition for classical M-estimators to succeed. By ensuring the $X$ matrix is not skewed by high-leverage points, the Huber loss function can effectively ignore outliers in the response variable.

Furthermore, the framework treats heavy-tailed distributions and adversarial contamination through a unified lens. From the perspective of the filtering algorithm, a naturally occurring extreme value in a heavy-tailed distribution (like a Pareto distribution) looks identical to a point injected by an adversary. Consequently, the same filtering logic mitigates both issues simultaneously.

Empirical Results

The proposed method achieves near-optimal error rates that match known theoretical lower bounds. For a contamination fraction $\epsilon$ and $k$ bounded moments, the filtered Huber estimator reaches an $\ell_2$ error rate of $O(\sigma(\sqrt{p/n} + \epsilon^{1-1/k}))$. In the specific case of Gaussian covariates, this improves to $O(\sigma(\sqrt{p/n} + \epsilon \sqrt{\log(1/\epsilon)}))$.

In simulations with $n=200$ and $p=40$, the authors demonstrated that while "vanilla" Huber regression fails in high-confidence regimes (as the failure probability $\tau$ decreases), the filtered version maintains low error. By removing even a tiny fraction of unstable points (e.g., 5%), the reliability of the model increases significantly.

Conclusion

The "filter-then-regress" approach offers a computationally practical alternative to previous robust methods. By utilizing iterative filtering and standard convex optimization, the method is feasible for real-world engineering applications. While the current theory assumes independence between noise and covariates, future work may extend this logic to high-dimensional sparse regression (such as the Lasso) and explore settings with dependent noise or unknown covariance structures.

Summary updated

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.
BibTeX
@misc{pensia2020robust,
  author = {Ankit Pensia and Varun Jog and Po-Ling Loh},
  title = {{Robust regression with covariate filtering: Heavy tails and adversarial contamination}},
  year = {2020},
  eprint = {2009.12976},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2009.12976},
}
Figure