The DOI matches its Crossref record; 1 of the 1 references it cites were found in a registry or an index.
Robust Estimators in High Dimensions without the Computational Intractability
Open accessAbstract
We study high-dimensional distribution learning in an agnostic setting where an adversary is allowed to arbitrarily corrupt an $\varepsilon$-fraction of the samples. Such questions have a rich history spanning statistics, machine learning, and theoretical computer science. Even in the most basic settings, the only known approaches are either computationally inefficient or lose dimension-dependent factors in their error guarantees. This raises the following question: Is high-dimensional agnostic distribution learning even possible, algorithmically? In this work, we obtain the first computationally efficient algorithms with dimension-independent error guarantees for agnostically learning several fundamental classes of high-dimensional distributions: (1) a single Gaussian, (2) a product distribution on the hypercube, (3) mixtures of two product distributions (under a natural balancedness condition), and (4) mixtures of spherical Gaussians. Our algorithms achieve error that is independent of the dimension, and in many cases scales nearly linearly with the fraction of adversarially corrupted samples. Moreover, we develop a general recipe for detecting and correcting corruptions in high-dimensions that may be applicable to many other problems.
Overview
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Citations
Cites
The densest hemisphere problem
Johnson, D. S., & Preparata, F. P. (1978) · Theoretical Computer Science · doi:10.1016/0304-3975(78)90006-3 · Cited by 152 · cited 1×
“Keywords-unsupervised learning, statistical learning, density estimation robust algorithm I. INTRODUCTION”
Background
Cited by
Byzantine-Robust Distributed Learning: Towards Optimal Statistical Rates
Yin, D., Chen, Y., Ramchandran, K., & Bartlett, P. (2018) · arXiv · doi:10.48550/arxiv.1803.01498 · Cited by 1,130
TEASER: Fast and Certifiable Point Cloud Registration
Yang, H., Shi, J., & Carlone, L. (2021) · IEEE Transactions on Robotics · doi:10.1109/tro.2020.3033695 · Cited by 895
Robust Aggregation for Federated Learning
Pillutla, K., Kakade, S. M., & Harchaoui, Z. (2022) · IEEE Transactions on Signal Processing · doi:10.1109/tsp.2022.3153135 · Cited by 801
Certified Defenses for Data Poisoning Attacks
Steinhardt, J., Koh, P. W., & Liang, P. (2017) · arXiv · doi:10.48550/arxiv.1706.03691 · Cited by 479
Distributed Statistical Machine Learning in Adversarial Settings: Byzantine Gradient Descent
Chen, Y., Su, L., & Xu, J. (2017) · Proceedings of the ACM on Measurement and Analysis of Computing Systems · doi:10.1145/3154503 · Cited by 390
“A recent line of work [8, 15] presents polynomial algorithms to consistently estimate the mean and covariance of a distribution from N i.”
BackgroundSpectral Signatures in Backdoor Attacks
Tran, B., Li, J., & Mądry, A. (2018) · arXiv (Cornell University) · doi:10.48550/arxiv.1811.00636 · Cited by 343
Self-citationDistributed Statistical Machine Learning in Adversarial Settings: Byzantine Gradient Descent
Chen, Y., Su, L., & Xu, J. (2018) · Abstracts of the 2018 ACM International Conference on Measurement and Modeling of Computer Systems · doi:10.1145/3219617.3219655 · Cited by 228
Stronger Data Poisoning Attacks Break Data Sanitization Defenses
Koh, P. W., Steinhardt, J., & Liang, P. (2018) · arXiv · doi:10.48550/arxiv.1811.00741 · Cited by 189
Remember What You Want to Forget: Algorithms for Machine Unlearning
Sekhari, A., Acharya, J., Kamath, G., & Suresh, A. T. (2021) · arXiv · doi:10.48550/arxiv.2103.03279 · Cited by 99
Self-citation
Metadata
- Authors
- Diakonikolas, I., Kamath, G., Kane, D. M., Li, J., Moitra, A., & Stewart, A.
- Venue
- 2016 IEEE 57th Annual Symposium on Foundations of Computer Science (FOCS)
- Publisher
- IEEE
- Published
- 2016-10
- Volume
- 48
- Issue
- 2
- Pages
- 655-664
- ISSN
- 0272-5428 (ISSN-L)
- OpenAlex
- W2336954923
- Cited by
- 200
- References
- 1
- FWCI
- 14.88
- Type
- conference paper
- Language
- en
- Open access
- green
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
Data sources
Bibliographic data: Semantic Scholar, OpenAlex, Crossref.
Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).
Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.