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