Learning from untrusted data
From MaRDI portal
Abstract: 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 points for which an unknown subset of points are drawn from a distribution of interest, and no assumptions are made about the remaining points, is it possible to return a list of 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.
Recommendations
Cited in
(34)- Robust matroid bandit optimization: near-optimal rates under adversarial contamination
- Finding planted cliques using gradient descent
- Low rank approximation in the presence of outliers
- Robust matroid bandit optimization against adversarial contamination
- Brief announcement: A case for Byzantine machine learning
- Early warning prediction with automatic labelling in epilepsy patients
- Robust estimators in high-dimensions without the computational intractability
- Brief announcement: Byzantine-tolerant machine learning
- Stronger data poisoning attacks break data sanitization defenses
- A theory of learning with corrupted labels
- Learning from Multiple Sources of Inaccurate Data
- CRIMED: lower and upper bounds on regret for bandits with unbounded stochastic corruption
- DLP learning from uncertain data
- Efficiently learning structured distributions from untrusted batches
- Robustly learning general mixtures of Gaussians
- Can adversarially robust learning leverage computational hardness?
- Resilience: a criterion for learning in the presence of arbitrary outliers
- Efficient parameter estimation of truncated Boolean product distributions
- Sampling correctors
- Mean estimation and regression under heavy-tailed distributions: A survey
- Nearly optimal robust secret sharing against rushing adversaries
- Best arm identification for contaminated bandits
- Semirandom planted clique via 1-norm isometry property
- Robust and computationally efficient gradient-based estimation
- A characterization of list learnability
- Algorithms approaching the threshold for semi-random planted clique
- Learning discrete distributions from untrusted batches
- A combinatorial approach to robust PCA
- Distributionally robust optimization and robust statistics
- Distributed statistical estimation and rates of convergence in normal approximation
- scientific article; zbMATH DE number 6866335 (Why is no real title available?)
- Corruption-tolerant bandit learning
- Robust supervised learning with coordinate gradient descent
- Learning under \(p\)-tampering poisoning attacks
This page was built for publication: Learning from untrusted data
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4977960)
