# ERM and RERM are optimal estimators for regression problems when malicious outliers corrupt the labels

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

## Key facts

- Cited by 5 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 24 Oct 2019.

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

- [Kalman Filtering with Adversarial Corruptions](https://mlsanity.com/paper/2111.06395/) (2021)
- [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)
- [Nearly minimax robust estimator of the mean vector by iterative spectral dimension reduction](https://mlsanity.com/paper/2204.02323/) (2022)
- [Robust Regression with Adaptive Contamination in Response: Optimal Rates and Computational Barriers](https://mlsanity.com/paper/2604.04228/) (2026)

## Abstract (arXiv)

We study Empirical Risk Minimizers (ERM) and Regularized Empirical Risk Minimizers (RERM) for regression problems with convex and L-Lipschitz loss functions. We consider a setting where |cO| malicious outliers contaminate the labels. In that case, under a local Bernstein condition, we show that the L2-error rate is bounded by  rN + AL |cO|/N, where N is the total number of observations, rN is the L2-error rate in the non-contaminated setting and A is a parameter coming from the local Bernstein condition. When rN is minimax-rate-optimal in a non-contaminated setting, the rate rN + AL|cO|/N is also minimax-rate-optimal when |cO| outliers contaminate the label. The main results of the paper can be used for many non-regularized and regularized procedures under weak assumptions on the noise. We present results for Huber's M-estimators (without penalization or regularized by the ℓ1-norm) and for general regularized learning problems in reproducible kernel Hilbert spaces when the noise can be heavy-tailed.