Resilience: A Criterion for Learning in the Presence of Arbitrary Outliers
This addresses the problem of robust statistical estimation in the presence of arbitrary outliers for researchers and practitioners in machine learning and statistics, offering a weaker condition than existing methods.
The paper introduces a criterion called resilience for robustly computing dataset properties like the mean or low-rank approximations, even when a large fraction of arbitrary outliers is present, enabling broader robust estimation in settings such as distribution learning and stochastic block models.
We introduce a criterion, resilience, which allows properties of a dataset (such as its mean or best low rank approximation) to be robustly computed, even in the presence of a large fraction of arbitrary additional data. Resilience is a weaker condition than most other properties considered so far in the literature, and yet enables robust estimation in a broader variety of settings. We provide new information-theoretic results on robust distribution learning, robust estimation of stochastic block models, and robust mean estimation under bounded $k$th moments. We also provide new algorithmic results on robust distribution learning, as well as robust mean estimation in $\ell_p$-norms. Among our proof techniques is a method for pruning a high-dimensional distribution with bounded $1$st moments to a stable "core" with bounded $2$nd moments, which may be of independent interest.