# Learning from Untrusted Data

arXiv: https://arxiv.org/abs/1611.02315 · HTML: https://mlsanity.com/paper/1611.02315/

## Key facts

- Cited by 90 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 7 Nov 2016.

## Built on by (most cited first, 30 of 90)

- [Truth Serum: Poisoning Machine Learning Models to Reveal Their Secrets](https://mlsanity.com/paper/2204.00032/) (2022)
- [Robust and Differentially Private Mean Estimation](https://mlsanity.com/paper/2102.09159/) (2021)
- [Fixing by Mixing: A Recipe for Optimal Byzantine ML under Heterogeneity](https://mlsanity.com/paper/2302.01772/) (2023)
- [Byzantine Machine Learning Made Easy by Resilient Averaging of Momentums](https://mlsanity.com/paper/2205.12173/) (2022)
- [Corruption-Robust Offline Reinforcement Learning](https://mlsanity.com/paper/2106.06630/) (2021)
- [Teach LLMs to Phish: Stealing Private Information from Language Models](https://mlsanity.com/paper/2403.00871/) (2024)
- [Robust Policy Gradient against Strong Data Corruption](https://mlsanity.com/paper/2102.05800/) (2021)
- [Statistical Query Lower Bounds for List-Decodable Linear Regression](https://mlsanity.com/paper/2106.09689/) (2021)
- [Sum of Ranked Range Loss for Supervised Learning](https://mlsanity.com/paper/2106.03300/) (2021)
- [A Characterization of List Learnability](https://mlsanity.com/paper/2211.04956/) (2022)
- [Defense Against Reward Poisoning Attacks in Reinforcement Learning](https://mlsanity.com/paper/2102.05776/) (2021)
- [Clustering Mixture Models in Almost-Linear Time via List-Decodable Mean Estimation](https://mlsanity.com/paper/2106.08537/) (2021)
- [Efficient Algorithms for Learning from Coarse Labels](https://mlsanity.com/paper/2108.09805/) (2021)
- [Private estimation algorithms for stochastic block models and mixture models](https://mlsanity.com/paper/2301.04822/) (2023)
- [Learning with Noisy Labels by Efficient Transition Matrix Estimation to Combat Label Miscorrection](https://mlsanity.com/paper/2111.14932/) (2021)
- [Fairness-Aware PAC Learning from Corrupted Data](https://mlsanity.com/paper/2102.06004/) (2021)
- [Robust Regression Revisited: Acceleration and Improved Estimation Rates](https://mlsanity.com/paper/2106.11938/) (2021)
- [Learning from a Biased Sample](https://mlsanity.com/paper/2209.01754/) (2022)
- [Private Distribution Learning with Public Data: The View from Sample Compression](https://mlsanity.com/paper/2308.06239/) (2023)
- [Trustworthy Distributed AI Systems: Robustness, Privacy, and Governance](https://mlsanity.com/paper/2402.01096/) (2024)
- [Privately Learning Mixtures of Axis-Aligned Gaussians](https://mlsanity.com/paper/2106.02162/) (2021)
- [List-Decodable Sparse Mean Estimation via Difference-of-Pairs Filtering](https://mlsanity.com/paper/2206.05245/) (2022)
- [Learning GMMs with Nearly Optimal Robustness Guarantees](https://mlsanity.com/paper/2104.09665/) (2021)
- [On the power of adaptivity in statistical adversaries](https://mlsanity.com/paper/2111.10352/) (2021)
- [Learning a Latent Simplex in Input-Sparsity Time](https://mlsanity.com/paper/2105.08005/) (2021)
- [List-Decodable Sparse Mean Estimation](https://mlsanity.com/paper/2205.14337/) (2022)
- [Estimation Contracts for Outlier-Robust Geometric Perception](https://mlsanity.com/paper/2208.10521/) (2022)
- [SoS Certifiability of Subgaussian Distributions and its Algorithmic Applications](https://mlsanity.com/paper/2410.21194/) (2024)
- [Saving Stochastic Bandits from Poisoning Attacks via Limited Data Verification](https://mlsanity.com/paper/2102.07711/) (2021)
- [Security Considerations in AI-Robotics: A Survey of Current Methods, Challenges, and Opportunities](https://mlsanity.com/paper/2310.08565/) (2023)

## Abstract (arXiv)

The vast majority of theoretical results in machine learning and statistics assume that the available training data is a reasonably reliable reflection of the phenomena to be learned or estimated. Similarly, the majority of machine learning and statistical techniques used in practice are brittle to the presence of large amounts of biased or malicious data. In this work we consider two frameworks in which to study 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, with the guarantee that at least one of them 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 operatornamepoly(1/α) answers, one of which is correct? The second framework, which we term the semi-verified learning model, considers the extent to which a small dataset of trusted data (drawn from the distribution in question) can be leveraged to enable the accurate extraction of 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 general result has immediate implications for robust estimation in a number of settings, including 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.