Resilience: A Criterion for Learning in the Presence of Arbitrary Outliers

By Jacob Steinhardt, Moses Charikar, Gregory Valiant. 2017

145 citations recorded by the source corpus.

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 kth moments. We also provide new algorithmic results on robust distribution learning, as well as robust mean estimation in p-norms. Among our proof techniques is a method for pruning a high-dimensional distribution with bounded 1st moments to a stable "core" with bounded 2nd moments, which may be of independent interest.

Subfields: Artificial Intelligence, Statistics and Probability

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Statistics and Probability

Citations in the corpus

Stronger data poisoning attacks break data sanitization defenses (2018, background): “) and Diakonikolas et al. (2016) designed robust procedures for mean estimation, which again required strong distributional assumptions. Later work (Charikar et al., 2017; Diakonikolas et al., 2017a; Steinhardt et al., 2018) showed how to perform mean estimation under much more mild assumptions, and”
Sever: A Robust Meta-Algorithm for Stochastic Optimization (2018, methodology): “While it is not needed for the theoretical results established in this subsection, we note that the robust mean estimation algorithm of [DKK17] relies on an iterative outlier removal method only requiring basic eigenvalue computations (SVD), while the [SCV18] algorithm employs semidefinite programmi”
Learning Discrete Distributions from Untrusted Batches (2017, background): “This problem is also a natural problem in the space of “robust statistics”, and the recent line of recent work from the theory community on estimation and learning with untrusted data (e.g. [ LRV16, DKK + 16, SVC16, CSV17, SCV17, DKK + 17]), and we outline these connections in Section 1.2.”
Privacy and Robustness in Federated Learning: Attacks and Defenses (2020, methodology): “However, DRACO assumes that each participant can access other participants’ data, limiting its practicability in FL. Su et al. [72] proposed to robustly aggregate the gradients computed by the Byzantine participants based on the ﬁltering procedure proposed by Steinhardt et al. [149].”
Outlier-robust moment-estimation via sum-of-squares (2017, background): “…the underlying distribution, the best known eﬃcient algorithms for robust mean estimation incur an estimation error that depends on the spectral norm of the covariance matrix Σ of the underlying distribution and is proportional to √ ε (where ε > 0 is the fraction of outliers) [DKK + 17a, SCV17].”
Robust multivariate mean estimation: The optimality of trimmed mean (2019, methodology): “Its origins may be traced back to the malicious noise model of Valiant [29] and Kearns and Li [16].”
Mixture models, robustness, and sum of squares proofs (2017, background): “However, a recent flurry of work ([17, 23, 27, 46, 61]) has given new, computationally efficient, nearly optimal robust estimators for the mean and covariance of a high dimensional Gaussian distribution.”
Defending Against Saddle Point Attack in Byzantine-Robust Distributed Learning (2018, methodology): “We start with a recently developed high-dimension robust estimation technique called the iterative filtering algorithm (Diakonikolas et al., 2016; 2017; Steinhardt et al., 2017) and use it to build the subroutine GradAGG.”
Securing Distributed Gradient Descent in High Dimensional Statistical Learning (2018, methodology): “We use an iterative filtering algorithm proposed in [SCV18], formally presented in Algorithm 2.”
Efficient Statistics, in High Dimensions, from Truncated Samples (2018, background): “Some general criteria for robust estimation are formulated in [23].”
Dataset Security for Machine Learning: Data Poisoning, Backdoor Attacks, and Defenses (2020, background): “A significant amount of work in this space shows that, from an information-theoretic point of view, this problem is indeed tractable for a wide variety of tasks and data distributions [157], [159], [160], [161], [162], [163].”
Privately Learning High-Dimensional Distributions (2018, background): “Recently, there has been significant interest in the computer science community in robustly estimating distributions (Diakonikolas et al., 2016; Lai et al., 2016; Charikar et al., 2017; Diakonikolas et al., 2017, 2018; Steinhardt et al., 2018), where the goal is to estimate some distribution from sa”
High-Dimensional Robust Mean Estimation in Nearly-Linear Time (2018, methodology): “ requires computing the SVD of a second moment matrix Ω(logd) times. Consequently, each iteration incurs runtime Ω(d3). Similarly, the robust mean estimation algorithm under bounded second moments in [SCV18] requires computing the SVD of a matrix multiple times, leading to Ω(d3) runtime. 1.4 Our App”
Robustly Learning a Gaussian: Getting Optimal Error, Efficiently (2017, background): “allowing the algorithm to output a list of candidate hypotheses [CSV17], formulating general conditions under which robust estimation is possible [SCV18], developing robust algorithms under sparsity assumptions [Li17, DBS17, BDLS17] where the number of samples is sublinear in the dimension, and leve”