Resilience: A Criterion for Learning in the Presence of Arbitrary Outliers
read the original abstract
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.
This paper has not been read by Pith yet.
Forward citations
Cited by 3 Pith papers
-
A Unified Approach to Robust Mean Estimation
A connection between Huber's contamination and heavy-tailed models yields unified robust mean estimators that are both computationally efficient and statistically optimal under certain conditions.
-
On efficient robust regression with subquadratic samples
Near-linear time algorithm for robust regression under Gaussian covariates achieves O(sqrt(ε κ)) error with Õ(d/ε⁴) samples when ε κ ≲ 1, plus SQ and low-degree lower bounds.
-
Generalized Rank Regression
Generalized Rank Regression extends rank methods to non-monotonic scores, derives Bahadur representation and asymptotic normality, proposes a two-stage sub-gradient algorithm, and shows variance equivalence to composi...
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.