Robust estimation via robust gradient estimation

By Adarsh Prasad, Arun Sai Suggala, Sivaraman Balakrishnan, Pradeep Ravikumar. 2018

238 citations recorded by the source corpus.

We provide a new computationally efficient class of estimators for risk minimization. We show that these estimators are robust for general statistical models, under varied robustness settings, including in the classical Huber ε‐contamination model, and in heavy‐tailed settings. Our workhorse is a novel robust variant of gradient descent, and we provide conditions under which our gradient descent variant provides accurate estimators in a general convex risk minimization problem. We provide specific consequences of our theory for linear regression and logistic regression and for canonical parameter estimation in an exponential family. These results provide some of the first computationally tractable and provably robust estimators for these canonical statistical models. Finally, we study the empirical performance of our proposed methods on synthetic and real data sets, and we find that our methods convincingly outperform a variety of baselines.

Subfields: Orthopedics and Sports Medicine, Statistics and Probability

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Orthopedics and Sports Medicine

In Statistics and Probability

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].”
Byzantine Stochastic Gradient Descent (2018, background): “Recently, efficient algorithms for high dimensional optimization which are tolerant to a small fraction of adversarial corruptions have been developed [1, 7, 11, 16, 24], building on new algorithms for high dimensional robust statistics [5, 7, 9, 18].”
Sever: A Robust Meta-Algorithm for Stochastic Optimization (2018, neutral): “[PSBR18] independently obtained a robust algorithm for stochastic convex optimization by combining gradient descent with robust mean estimation.”
The Curse of Concentration in Robust Learning: Evasion and Poisoning Attacks from Concentration of Measure (2018, background): “, see (Charikar, Steinhardt, and Valiant 2017; Diakonikolas, Kane, and Stewart 2017; 2018; Diakonikolas et al. 2018; Prasad et al. 2018; Diakonikolas, Kong, and Stewart 2018) and references therein) exploring the possibility of robust statistics over poisoned data with algorithmic guarantees.”
Securing Distributed Gradient Descent in High Dimensional Statistical Learning (2018, methodology): “The correctness of the robust gradient descent method proposed in [PSBR18] relies on uniform approximation of the aggregated gradient to the true population gradient [PSBR18, Def.”
High-Dimensional Robust Mean Estimation in Nearly-Linear Time (2018, methodology): “We note that an eﬃcient algorithm for robust mean estimation under bounded covariance assumptions has been recently used as a subroutine [PSBR18, DKK + 18b] to obtain robust learners for a wide range of supervised learning problems that can be phrased as stochastic convex programs.”
Robust Learning from Untrusted Sources (2019, background): “…a vast body of literature focusing on robustness of learning algorithms to corruptions within a dataset, e.g. (Tukey, 1960; Huber, 2011; Diakonikolas et al., 2016; Prasad et al., 2018), and on identifying data corrup-tions at prediction time , e.g. (Hendrycks & Gimpel, 2017; Sun & Lampert, 2018).”
Learning with Bad Training Data via Iterative Trimmed Loss Minimization (2018, background): “Another line of recent work on robust regression consider strong robustness where the adversary poisons both the inputs and outputs, in both low-dimensional (Diakonikolas et al., 2018; Prasad et al., 2018; Klivans et al., 2018) and high dimensional (Chen et al.”
Efficient Algorithms and Lower Bounds for Robust Linear Regression (2018, methodology): “Three recent works [PSBR18, DKK + 18b, KKM18] provide robust eﬃcient algorithms for linear regression in various settings.”
Choosing the Sample with Lowest Loss makes SGD Robust (2020, background): “[9, 28] provides robust meta-algorithms for stochastic optimization under adversarial corruptions.”
Byzantine Fault-Tolerant Parallelized Stochastic Gradient Descent for Linear Regression (2019, background): “The problem of Byzantine faulty workers in parallelized SGD for machine learning has received considerable attention in recent years [1], [3], [6]–[10], [14], [16].”
Gradient Descent with Early Stopping is Provably Robust to Label Noise for Overparameterized Neural Networks (2019, background): “We would also like to note that there is an interesting line of work that focuses on developing robust algorithms for corruption not only in the labels but also input data [19,31,41].”
Defending Against Saddle Point Attack in Byzantine-Robust Distributed Learning (2018, background): “, 2014), robust estimation (Prasad et al., 2018), and structured non-convex problems (Balakrishnan et al.”
Learning under p-Tampering Attacks (2018, background): “These works led to an active line of work (e.g., see [CSV17, DKS17, DKS18a, DKK + 18, PSBR18, DKS18b] and references therein) exploring the possibility of robust statistics over poisoned data with algorithmic guarantees.”
DORO: Distributional and Outlier Robust Optimization (2021, unknown): “Recent works in statistics and machine learning (Lai et al., 2016; Diakonikolas et al., 2017; Prasad et al., 2018; Diakonikolas et al., 2019) provided efﬁciently computable outlier-robust estimators for high-dimensional mean estimation with corresponding error guarantees.”