Being Robust (in High Dimensions) Can Be Practical

By Ilias Diakonikolas, Gautam Kamath, Daniel M. Kane, Jerry Zheng Li, Ankur Moitra, Alistair Stewart. 2017

267 citations recorded by the source corpus.

Robust estimation is much more challenging in high dimensions than it is in one dimension: Most techniques either lead to intractable optimization problems or estimators that can tolerate only a tiny fraction of errors. Recent work in theoretical computer science has shown that, in appropriate distributional models, it is possible to robustly estimate the mean and covariance with polynomial time algorithms that can tolerate a constant fraction of corruptions, independent of the dimension. However, the sample and time complexity of these algorithms is prohibitively large for high-dimensional applications. In this work, we address both of these issues by establishing sample complexity bounds that are optimal, up to logarithmic factors, as well as giving various refinements that allow the algorithms to tolerate a much larger fraction of corruptions. Finally, we show on both synthetic and real data that our algorithms have state-of-the-art performance and suddenly make high-dimensional robust estimation a realistic possibility.

Subfields: Artificial Intelligence, Statistics and Probability, Safety, Robustness & Interpretability, Statistical Learning Theory

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 Statistics and Probability

In Safety, Robustness & Interpretability

In Statistical Learning Theory

Citations in the corpus

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].”
Sever: A Robust Meta-Algorithm for Stochastic Optimization (2018, methodology): “On the other hand, [DKK17] provide a practical implementation of the robust mean and covariance estimation algorithms of [DKK16], but do not consider more general learning tasks.”
Learning Discrete Distributions from Untrusted Batches (2017, background): “These recent works include [LRV16, DKK + 16, DKK + 17] who consider the problem of robustly estimating the mean and covariance of high-dimensional Gaussians (and other distributions such as product distributions), and [SVC16] who consider a sparse ratings aggregation setting.”
An Overview of Federated Deep Learning Privacy Attacks and Defensive Strategies (2020, methodology): “n to all clients. Instead of sending model updates, participating clients send their predicted labels from the publicly available samples. Their subsequent aggregation uses the robust mean estimation [77] algorithm which is speciﬁcally developed or high dimensional robust aggregation. Hereafter the ”
Robust multivariate mean estimation: The optimality of trimmed mean (2019, methodology): “Although this bound is sub-optimal in terms of the conditions and does not recover the sub-Gaussian bounds, the goal in [10], and in other articles in this direction as well, was”
Manipulating the Byzantine: Optimizing Model Poisoning Attacks and Defenses for Federated Learning (2021, methodology): “Our DnC AGR provides strong theoretical robustness guarantees of the removal of malicious updates, when benign updates are independently and identically distributed (iid) [16], [15], [28], [26], [36].”
Efficient Algorithms and Lower Bounds for Robust Linear Regression (2018, methodology): “We pre-process by running ﬁlter algorithms similar to one used in [DKK + 16, DKK + 17a] on the Gaussians y − β ′ T X and X .”
Dataset Security for Machine Learning: Data Poisoning, Backdoor Attacks, and Defenses (2020, methodology): “These algorithms rely on relatively simple primitives and can thus be efficiently implemented even for high-dimensional distributions [165].”
Mean Estimation and Regression Under Heavy-Tailed Distributions: A Survey (2019, unknown): “Various different models have been introduced, see Charikar, Steinhardt, and Valiant [17], Diakonikolas, Kamath, Kane, Li, Moitra, and Stewart [23, 24, 25], Diakonikolas, Kane, and Stewart [26], Diakonikolas, Kong, and Stewart [27], Hopkins and Li [34], Klivans, Kothari, and Meka [42], Kothari, Stei”
Defending Against Saddle Point Attack in Byzantine-Robust Distributed Learning (2018, methodology): “Our results based on the iterative ﬁltering subroutine, on the other hand, are new: • The problem that we tackle is harder than what is considered in the original iterative ﬁltering papers [22, 23].”