# A spectral least-squares-type method for heavy-tailed corrupted regression with unknown covariance & heterogeneous noise

arXiv: https://arxiv.org/abs/2209.02856 · HTML: https://mlsanity.com/paper/2209.02856/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 25 of its 40 references that are in the map.
- First posted on arXiv 6 Sep 2022.

## Builds on (most cited first, 25 of 25)

- [Robust Estimators in High Dimensions without the Computational Intractability](https://mlsanity.com/paper/1604.06443/) (2016)
- [Mean estimation and regression under heavy-tailed distributions--a survey](https://mlsanity.com/paper/1906.04280/) (2019)
- [Agnostic Estimation of Mean and Covariance](https://mlsanity.com/paper/1604.06968/) (2016)
- [Sever: A Robust Meta-Algorithm for Stochastic Optimization](https://mlsanity.com/paper/1803.02815/) (2018)
- [Recent Advances in Algorithmic High-Dimensional Robust Statistics](https://mlsanity.com/paper/1911.05911/) (2019)
- [Robust Estimation via Robust Gradient Estimation](https://mlsanity.com/paper/1802.06485/) (2018)
- [Efficient Algorithms and Lower Bounds for Robust Linear Regression](https://mlsanity.com/paper/1806.00040/) (2018)
- [Loss minimization and parameter estimation with heavy tails](https://mlsanity.com/paper/1307.1827/) (2013)
- [Robust regression with covariate filtering: Heavy tails and adversarial contamination](https://mlsanity.com/paper/2009.12976/) (2020)
- [Robust Covariance and Scatter Matrix Estimation under Huber's Contamination Model](https://mlsanity.com/paper/1506.00691/) (2015)
- [Robust and Heavy-Tailed Mean Estimation Made Simple, via Regret Minimization](https://mlsanity.com/paper/2007.15839/) (2020)
- [Robust Linear Regression: Optimal Rates in Polynomial Time](https://mlsanity.com/paper/2007.01394/) (2020)
- [Quantum Entropy Scoring for Fast Robust Mean Estimation and Improved Outlier Detection](https://mlsanity.com/paper/1906.11366/) (2019)
- [High-Dimensional Robust Mean Estimation in Nearly-Linear Time](https://mlsanity.com/paper/1811.09380/) (2018)
- [Robust subgaussian estimation of a mean vector in nearly linear time](https://mlsanity.com/paper/1906.03058/) (2019)
- [Mean Estimation with Sub-Gaussian Rates in Polynomial Time](https://mlsanity.com/paper/1809.07425/) (2018)
- [Optimal Robust Linear Regression in Nearly Linear Time](https://mlsanity.com/paper/2007.08137/) (2020)
- [Outlier-robust estimation of a sparse linear model using ℓ1-penalized Huber's M-estimator](https://mlsanity.com/paper/1904.06288/) (2019)
- [Robust Regression via Mutivariate Regression Depth](https://mlsanity.com/paper/1702.04656/) (2017)
- [Robust estimation via generalized quasi-gradients](https://mlsanity.com/paper/2005.14073/) (2020)
- [Fast Mean Estimation with Sub-Gaussian Rates](https://mlsanity.com/paper/1902.01998/) (2019)
- [Robust Regression Revisited: Acceleration and Improved Estimation Rates](https://mlsanity.com/paper/2106.11938/) (2021)
- [A Fast Spectral Algorithm for Mean Estimation with Sub-Gaussian Rates](https://mlsanity.com/paper/1908.04468/) (2019)
- [A spectral algorithm for robust regression with subgaussian rates](https://mlsanity.com/paper/2007.06072/) (2020)
- [Outlier-robust sparse/low-rank least-squares regression and robust matrix completion](https://mlsanity.com/paper/2012.06750/) (2020)

## Built on by (most cited first, 1 of 1)

- [On efficient robust regression with subquadratic samples](https://mlsanity.com/paper/2605.18042/) (2026)

## Abstract (arXiv)

We revisit heavy-tailed corrupted least-squares linear regression assuming to have a corrupted n-sized label-feature sample of at most ε n arbitrary outliers. We wish to estimate a p-dimensional parameter b^* given such sample of a label-feature pair (y,x) satisfying y=langle x,b^*rangle+xi with heavy-tailed (x,xi). We only assume x is L4-L2 hypercontractive with constant L>0 and has covariance matrix Sigma with minimum eigenvalue 1/μ2>0 and bounded condition number kappa>0. The noise xi can be arbitrarily dependent on x and nonsymmetric as long as xi x has finite covariance matrix Xi. We propose a near-optimal computationally tractable estimator, based on the power method, assuming no knowledge on (Sigma,Xi) nor the operator norm of Xi. With probability at least 1-δ, our proposed estimator attains the statistical rate μ2VertXiVert1/2(fracpn+fraclog(1/δ)n+ε)1/2 and breakdown-point εlesssimfrac1L4kappa2, both optimal in the ℓ2-norm, assuming the near-optimal minimum sample size L4kappa2(plog p + log(1/δ))lesssim n, up to a log factor. To the best of our knowledge, this is the first computationally tractable algorithm satisfying simultaneously all the mentioned properties. Our estimator is based on a two-stage Multiplicative Weight Update algorithm. The first stage estimates a descent direction hat v with respect to the (unknown) pre-conditioned inner product langleSigma(·),·rangle. The second stage estimate the descent direction Sigmahat v with respect to the (known) inner product langle·,·rangle, without knowing nor estimating Sigma.