ERM and RERM are optimal estimators for regression problems when malicious outliers corrupt the labels
This provides theoretical guarantees for robust regression methods in machine learning, applicable to scenarios with heavy-tailed noise and outliers, though it is incremental as it extends existing minimax optimality results to contaminated settings.
The paper tackles regression problems with malicious outliers corrupting labels, showing that Empirical Risk Minimizers (ERM) and Regularized ERM (RERM) achieve minimax-optimal error rates bounded by r_N + AL|O|/N, where r_N is the non-contaminated rate and |O| is the number of outliers.
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 $L_2$-error rate is bounded by $ r_N + AL |\cO|/N$, where $N$ is the total number of observations, $r_N$ is the $L_2$-error rate in the non-contaminated setting and $A$ is a parameter coming from the local Bernstein condition. When $r_N$ is minimax-rate-optimal in a non-contaminated setting, the rate $r_N + 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 $\ell_1$-norm) and for general regularized learning problems in reproducible kernel Hilbert spaces when the noise can be heavy-tailed.