# Outlier-robust sparse/low-rank least-squares regression and robust matrix completion

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

## Key facts

- Cited by 7 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 12 Dec 2020.

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

- [Robust and Sparse Estimation of Linear Regression Coefficients with Heavy-tailed Noises and Covariates](https://mlsanity.com/paper/2206.07594/) (2022)
- [Outlier Robust and Sparse Estimation of Linear Regression Coefficients](https://mlsanity.com/paper/2208.11592/) (2022)
- [Computationally Efficient and Statistically Optimal Robust High-Dimensional Linear Regression](https://mlsanity.com/paper/2305.06199/) (2023)
- [A spectral least-squares-type method for heavy-tailed corrupted regression with unknown covariance & heterogeneous noise](https://mlsanity.com/paper/2209.02856/) (2022)
- [Robust Sparse Regression with Non-Isotropic Designs](https://mlsanity.com/paper/2410.23937/) (2024)
- [Adversarial robust weighted Huber regression](https://mlsanity.com/paper/2102.11120/) (2021)
- [Adversarial Contamination Meets Hard Thresholding: An Iterative Algorithm with Signal Adaptivity and Minimax Optimality](https://mlsanity.com/paper/2606.27685/) (2026)

## Abstract (arXiv)

We study high-dimensional least-squares regression within a subgaussian statistical learning framework with heterogeneous noise. It includes s-sparse and r-low-rank least-squares regression when a fraction ε of the labels are adversarially contaminated. We also present a novel theory of trace-regression with matrix decomposition based on a new application of the product process. For these problems, we show novel near-optimal "subgaussian" estimation rates of the form r(n,de)+√log(1/δ)/n+εlog(1/ε), valid with probability at least 1-δ. Here, r(n,de) is the optimal uncontaminated rate as a function of the effective dimension de but independent of the failure probability δ. These rates are valid uniformly on δ, i.e., the estimators' tuning do not depend on δ. Lastly, we consider noisy robust matrix completion with non-uniform sampling. If only the low-rank matrix is of interest, we present a novel near-optimal rate that is independent of the corruption level a. Our estimators are tractable and based on a new "sorted" Huber-type loss. No information on (s,r,ε,a) are needed to tune these estimators. Our analysis makes use of novel δ-optimal concentration inequalities for the multiplier and product processes which could be useful elsewhere. For instance, they imply novel sharp oracle inequalities for Lasso and Slope with optimal dependence on δ. Numerical simulations confirm our theoretical predictions. In particular, "sorted" Huber regression can outperform classical Huber regression.