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

ERM and RERM are optimal estimators for regression problems when malicious outliers corrupt the labels CHINOT Geoffrey ENSAE, 5 avenue Henri Chatelier, 91120, Palaiseau, France email: geoffrey.chinot@ensae.fr Abstract: 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 O malicious outliers may contaminate the labels. In that case, we show that the L 2-error rate is bounded by r N L O /N, where N is the total number of observations and r N is the L 2-error rate in the non-contaminated setting. When r N is minimax-rate-optimal in a non-contaminated setting, the rate r N L O /N is also minimax-rate-optimal when O 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.