Sever: A Robust Meta-Algorithm for Stochastic Optimization

By Ilias Diakonikolas, Gautam Kamath, Daniel M. Kane, Jerry Zheng Li, Jacob Steinhardt, Alistair Stewart. 2018

319 citations recorded by the source corpus.

In high dimensions, most machine learning methods are brittle to even a small fraction of structured outliers. To address this, we introduce a new meta-algorithm that can take in a base learner such as least squares or stochastic gradient descent, and harden the learner to be resistant to outliers. Our method, Sever, possesses strong theoretical guarantees yet is also highly scalable -- beyond running the base learner itself, it only requires computing the top singular vector of a certain $n \times d$ matrix. We apply Sever on a drug design dataset and a spam classification dataset, and find that in both cases it has substantially greater robustness than several baselines. On the spam dataset, with $1\%$ corruptions, we achieved $7.4\%$ test error, compared to $13.4\%-20.5\%$ for the baselines, and $3\%$ error on the uncorrupted dataset. Similarly, on the drug design dataset, with $10\%$ corruptions, we achieved $1.42$ mean-squared error test error, compared to $1.51$-$2.33$ for the baselines, and $1.23$ error on the uncorrupted dataset.

Subfields: Artificial Intelligence, Optimization & Training

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 Optimization & Training

Citations in the corpus

Advances and Open Problems in Federated Learning (2019, methodology): “ently rely on “data sanitization” methods [123], which aim to remove poisoned or otherwise anomalous 65 data. More recent work has developed improved data sanitization methods using robust statistics [368, 355, 387, 133], which often have the beneﬁt of being provably robust to small numbers of outli”
Can You Really Backdoor Federated Learning? (2019, background): “Existing approaches against backdoor attacks (28; 20; 31; 13; 32; 26) either require a careful examination of the training data or full control of the training process at the server, which may not apply in the federated learning case.”
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].”
Cronus: Robust and Heterogeneous Collaborative Learning with Black-Box Knowledge Transfer (2019, methodology): “The theoretical error bound and sample complexity 1 of the existing robust aggregation algorithms [13], [37], [16], [17], [15], [33] depend on the dimensionality of model parameters.”
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.”
Improved Natural Language Generation via Loss Truncation (2020, methodology): “Our work is related to the (cid:15) -contamination model, in which an (cid:15) fraction of the data has been modiﬁed, potentially by an adversary (Diakonikolas et al., 2018).”
Adversarial Neuron Pruning Purifies Backdoored Deep Models (2021, methodology): “Regarding poisoned data as outliers, we can detect and filter them out using robust statistics in the input space [38, 18, 8, 9] or the feature space [17, 41, 28, 10].”
Learning from History for Byzantine Robust Optimization (2020, background): “There have also been attempts to use recent breakthroughs in robust high-dimensional aggregators (Diakonikolas et al., 2018; Su & Xu, 2018; El-Mhamdi & Guerraoui, 2019; Data et al., 2019; Data & Diggavi, 2020).”
Learning under p-Tampering Attacks (2018, background): “Then, it holds that, b b Using Lemma 18, for every preﬁx d ≤ i ∈ Supp( D ) i we have, Proof. b b We can now describe the actual efﬁcient variant of our Ideal p - Tam attack.”
Efficient Algorithms for Outlier-Robust Regression (2018, methodology): “Using a set of diﬀerent techniques, Diakonikolas, Kamath, Kane, Li, Stein-hardt and Stewart [DKK + 18] and Prasad, Suggala, Balakrishnan and Ravikumar [PSBR18] also obtained robust algorithms for regression in the setting where data ( x , y is generated via the process: y w , x + e for an ﬁxed…”
A Comprehensive Survey on Poisoning Attacks and Countermeasures in Machine Learning (2022, methodology): “Literature Model-protected Strategy Adversarial Setting Year Techniques Goals [4] cross-models data-driven cross-attacks UnT 2010 [33] logistic regression data-driven DM UnT 2014 [72] cross-models data-driven LM UnT 2015 [99] cross-models data-driven LM UnT 2018 [98] cross-models data-driven cross-a”
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].”
Tilted Empirical Risk Minimization (2020, methodology): “1, for regression tasks, we use the drug discovery data extracted from (Diakonikolas et al., 2019) which is originally curated from (Olier et al.”
On the Effectiveness of Mitigating Data Poisoning Attacks with Gradient Shaping (2020, methodology): “Prior work [8,15, 22,41,42] focused primarily on outlier removal (also known as data sanitization).”
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 [DKK + 18, PSBR18, KKM18] and high dimensional [CCM13, BDLS17, LSLC18] settings.”