Agnostic Estimation of Mean and Covariance
Open accessThe DOI matches its Crossref record; 4 of the 4 references it cites were found in a registry or an index.
Abstract
We consider the problem of estimating the mean and covariance of a distribution from i.i.d. samples in the presence of a fraction of malicious noise. This is in contrast to much recent work where the noise itself is assumed to be from a distribution of known type. The agnostic problem includes many interesting special cases, e.g., learning the parameters of a single Gaussian (or finding the best-fit Gaussian) when a fraction of data is adversarially corrupted, agnostically learning mixtures, agnostic ICA, etc. We present polynomial-time algorithms to estimate the mean and covariance with error guarantees in terms of information-theoretic lower bounds. As a corollary, we also obtain an agnostic algorithm for Singular Value Decomposition.
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
Robust estimation of a location parameter
Huber, P. J. (1964) · The Annals of Mathematical Statistics · doi:10.1214/aoms/1177703732 · Cited by 7,228
Breakdown Properties of Location Estimates Based on Halfspace Depth and Projected Outlyingness
Donoho, D. L., & Gasko, M. (1992) · The Annals of Statistics · doi:10.1214/aos/1176348890 · Cited by 583
Breakdown Points of Affine Equivariant Estimators of Multivariate Location and Covariance Matrices
Lopuhaa, H. P., & Rousseeuw, P. J. (1991) · The Annals of Statistics · doi:10.1214/aos/1176347978 · Cited by 446
Robust covariance and scatter matrix estimation under Huber’s contamination model
Chen, M., Gao, C., & Ren, Z. (2018) · The Annals of Statistics · doi:10.1214/17-aos1607 · Cited by 146
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
Manipulating the Byzantine: Optimizing Model Poisoning Attacks and Defenses for Federated Learning
Shejwalkar, V., & Houmansadr, A. (2021) · Proceedings 2021 Network and Distributed System Security Symposium · doi:10.14722/ndss.2021.24498 · Cited by 615
“The theoretical error bounds provided by previous robust AGRs [8], [31], [39], [16], [26], [2] depend on the dimensionality of their inputs.”
BackgroundCertified 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
Metadata
- Authors
- Lai, K. A., Rao, A. B., & Vempala, S.
- Venue
- 2016 IEEE 57th Annual Symposium on Foundations of Computer Science (FOCS)
- Publisher
- IEEE
- Published
- 2016-10
- Pages
- 665-674
- ISSN
- 0272-5428 (ISSN-L)
- OpenAlex
- W2464464020
- Cited by
- 204
- References
- 4
- FWCI
- 21.61
- 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.