2020/06/09 by Pierre Laforgue, Laforgue, Pierre, Guillaume Staerman +4
Computer Science · Engineering · Mathematics · #Advanced Statistical Methods and Models #Control Systems and Identification #FOS: Computer and information sciences #Machine Learning (cs.LG) #Machine Learning (stat.ML) #Machine Learning and Algorithms #Statistical Methods and Inference #cs.LG #stat.ML
paper · pdf · doi:10.48550/arxiv.2006.05240
openalex publication_date 2020/06/09 · arxiv created 2021/02/07 · arxiv updated 2021/02/09 · openalex created_date 2022/07/26 · openalex updated_date 2026/07/28
In contrast to the empirical mean, the Median-of-Means (MoM) is an estimator of the mean θ of a square integrable r.v. Z, around which accurate nonasymptotic confidence bounds can be built, even when Z does not exhibit a sub-Gaussian tail behavior. Thanks to the high confidence it achieves on heavy-tailed data, MoM has found various applications in machine learning, where it is used to design training procedures that are not sensitive to atypical observations. More recently, a new line of work is now trying to characterize and leverage MoM's ability to deal with corrupted data. In this context, the present work proposes a general study of MoM's concentration properties under the contamination regime, that provides a clear understanding of the impact of the outlier proportion and the number of blocks chosen. The analysis is extended to (multisample) U-statistics, i.e. averages over tuples of observations, that raise additional challenges due to the dependence induced. Finally, we show that the latter bounds can be used in a straightforward fashion to derive generalization guarantees for pairwise learning in a contaminated setting, and propose an algorithm to compute provably reliable decision functions.