Learning from untrusted data

By Moses Charikar, Jacob Steinhardt, Gregory Valiant. 2016

320 citations recorded by the source corpus.

The vast majority of theoretical results in machine learning and statistics assume that the training data is a reliable reflection of the phenomena to be learned. Similarly, most learning techniques used in practice are brittle to the presence of large amounts of biased or malicious data. Motivated by this, we consider two frameworks for studying estimation, learning, and optimization in the presence of significant fractions of arbitrary data. The first framework, list-decodable learning, asks whether it is possible to return a list of answers such that at least one is accurate. For example, given a dataset of n points for which an unknown subset of αn points are drawn from a distribution of interest, and no assumptions are made about the remaining (1 - α)n points, is it possible to return a list of poly(1/α) answers? The second framework, which we term the semi-verified model, asks whether a small dataset of trusted data (drawn from the distribution in question) can be used to extract accurate information from a much larger but untrusted dataset (of which only an α-fraction is drawn from the distribution). We show strong positive results in both settings, and provide an algorithm for robust learning in a very general stochastic optimization setting. This result has immediate implications for robustly estimating the mean of distributions with bounded second moments, robustly learning mixtures of such distributions, and robustly finding planted partitions in random graphs in which significant portions of the graph have been perturbed by an adversary.

Subfields: Artificial Intelligence, Computational Mechanics, Safety, Robustness & Interpretability, Privacy & Security

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 Computational Mechanics

In Safety, Robustness & Interpretability

In Privacy & Security

Citations in the corpus

Stronger data poisoning attacks break data sanitization defenses (2018, background): “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 Diakonikolas et al.”
Spectral Signatures in Backdoor Attacks (2018, background): “Another line of work focuses on applying the robust statistics tools developed in [8, 22, 5, 9] to robust stochastic optimization problems [2, 5, 10, 17, 27].”
Byzantine Stochastic Gradient Descent (2018, background): “Recently, efficient algorithms for high dimensional optimization which are tolerant to a small fraction of adversarial corruptions have been developed [1, 7, 11, 16, 24], building on new algorithms for high dimensional robust statistics [5, 7, 9, 18].”
Sever: A Robust Meta-Algorithm for Stochastic Optimization (2018, methodology): “Motivated by this, recent work in theoretical computer science has developed efficient robust estimators for classical problems such as linear classification [KLS09, ABL14], mean and covariance estimation [DKK16, LRV16], clustering [CSV17], and regression [BJK15, BJKK17, BDLS17].”
Byzantine-Robust Distributed Learning: Towards Optimal Statistical Rates (2018, background): “, 2015) as well as developing list-decodable and semi-verified learning schemes when a majority of the data points are adversarial (Charikar et al., 2017).”
Targeted Backdoor Attacks on Deep Learning Systems Using Data Poisoning (2017, methodology): “Such statistical robust learning algorithms have been proposed for several traditional machine learning models such as linear and logistic regressions [14], [18], [27], [16], [39], [61].”
Certified Defenses for Data Poisoning Attacks (2017, methodology): “Robust algorithms have been exhibited for mean and covariance estimation and clustering (Diakonikolas et al., 2016; Lai et al., 2016; Charikar et al., 2017), classiﬁcation (Klivans et al., 2009; Awasthi et al., 2014), regression (Nasrabadi et al., 2011; Nguyen and Tran, 2013; Chen et al., 2013;…”
Learning Discrete Distributions from Untrusted Batches (2017, methodology): “ivial precision in the setting where ǫ ≥1/2 due to the symmetry between the real distribution and the one chosen by the adversary. Nevertheless, two learning frameworks were proposed for this case in [CSV17]: the list-decodable learning framework (ﬁrst introduced by Balcan et al. [BBV08]), in which ”
Using Pre-Training Can Improve Model Robustness and Uncertainty (2019, methodology): “We also consider the Gold Loss Correction (GLC) method of Hendrycks et al. (2018), which assumes access to a small, trusted dataset of cleanly labeled (gold standard) examples, which is also known as a semi-veriﬁed setting (Charikar et al., 2017).”
Using Self-Supervised Learning Can Improve Model Robustness and Uncertainty (2019, methodology): “This setup is also known as a semi-verified setting Charikar et al. [2017].”
Being Robust (in High Dimensions) Can Be Practical (2017, background): “, 2016c), tolerating much more noise by allowing the algorithm to output a list of candidate hypotheses (Charikar et al., 2017), and developing robust algorithms under sparsity assumptions (Li, 2017; Du et al.”
Using Trusted Data to Train Deep Networks on Labels Corrupted by Severe Noise (2018, background): “umptions, and does not make use of clean labels. Contra [24,17], we make the assumption that during training the model has access to a small set of clean labels. See Charikar, Steinhardt, and Valiant [2] for a general analysis of this assumption. This assumption has been leveraged by others for the ”
The Curse of Concentration in Robust Learning: Evasion and Poisoning Attacks from Concentration of Measure (2018, background): “The works of (Charikar, Steinhardt, and Valiant 2017; Diakonikolas, Kane, and Stewart 2018) performed list-docodeable learning, and (Diakonikolas et al. 2018; Prasad et al. 2018) studied supervised learning.”
Unifying semi-supervised and robust learning by mixup (2019, methodology): “Some work of RLL uses p > 0 setting explicitly (Charikar et al. (2017); Li et al. (2017); Hendrycks et al. (2018)) and implicitly (Jiang et al. (2018); Jenni & Favaro (2018)).”
Robust Federated Learning in a Heterogeneous Environment (2019, background): “[31] Moses Charikar, Jacob Steinhardt, and Gregory Valiant.”
Securing Distributed Gradient Descent in High Dimensional Statistical Learning (2018, background): “Similar uniform concentration of sample covariance matrix has been derived in [4, Lemma 2.1] under the assumption that the gradients are sub-gaussian.”
A Data Prism: Semi-Verified Learning in the Small-Alpha Regime (2017, methodology): “sumed to be “good”—drawn from the distribution or cohort of interest. In the case of [1], the recovery guarantees require that this fraction of good data satisﬁes α ≥ 64 65. The recent works [12] and [3] consider the setting where a minority of the data is “good” (i.e. α < 1/2), with the latter p”
Consistent Robust Regression (2017, background): “We note a recent work [5] in robust stochastic optimization which is able to tolerate a constant fraction of corruptions α → 1 .”