Sever: A Robust Meta-Algorithm for Stochastic Optimization

Abstract

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.

To appear in ICML 2019

Cited by in corpus (59)

• Can You Really Backdoor Federated Learning?
• Gradient Descent with Early Stopping is Provably Robust to Label Noise for Overparameterized Neural Networks
• Cronus: Robust and Heterogeneous Collaborative Learning with Black-Box Knowledge Transfer
• On the Effectiveness of Mitigating Data Poisoning Attacks with Gradient Shaping
• Distribution-Independent PAC Learning of Halfspaces with Massart Noise
• Federated Learning Meets Multi-objective Optimization
• High Dimensional Robust Sparse Regression
• Restricted Minimum Error Entropy Criterion for Robust Classification
• Generalized Resilience and Robust Statistics
• Robust Estimation and Generative Adversarial Nets
• Reducibility and Statistical-Computational Gaps from Secret Leakage
• A Unified Approach to Robust Mean Estimation
• Robustly Learning any Clusterable Mixture of Gaussians
• Byzantine Fault Tolerant Distributed Linear Regression
• Faster Algorithms for High-Dimensional Robust Covariance Estimation
• HaS-Nets: A Heal and Select Mechanism to Defend DNNs Against Backdoor Attacks for Data Collection Scenarios
• Optimal Robust Linear Regression in Nearly Linear Time
• Robust and Differentially Private Mean Estimation
• Choosing the Sample with Lowest Loss makes SGD Robust
• Robust Policy Gradient against Strong Data Corruption
• On Tilted Losses in Machine Learning: Theory and Applications
• Byzantine Fault-Tolerant Distributed Machine Learning Using Stochastic Gradient Descent (SGD) and Norm-Based Comparative Gradient Elimination (CGE)
• A Polynomial Time Algorithm for Learning Halfspaces with Tsybakov Noise
• Defending Against Saddle Point Attack in Byzantine-Robust Distributed Learning
• Improved Natural Language Generation via Loss Truncation
• Regularisation Can Mitigate Poisoning Attacks: A Novel Analysis Based on Multiobjective Bilevel Optimisation
• Corruption-Robust Offline Reinforcement Learning
• Robust Regression Revisited: Acceleration and Improved Estimation Rates
• Robust Training in High Dimensions via Block Coordinate Geometric Median Descent
• Robust Meta-learning for Mixed Linear Regression with Small Batches
• Settling the Robust Learnability of Mixtures of Gaussians
• Robust and Heavy-Tailed Mean Estimation Made Simple, via Regret Minimization
• Iterative Least Trimmed Squares for Mixed Linear Regression
• Randomized Reactive Redundancy for Byzantine Fault-Tolerance in Parallelized Learning
• Tilted Empirical Risk Minimization
• Learning GMMs with Nearly Optimal Robustness Guarantees
• Learning Polynomials of Few Relevant Dimensions
• List-Decodable Mean Estimation in Nearly-PCA Time
• High-Dimensional Robust Mean Estimation via Gradient Descent
• Outlier-Robust Learning of Ising Models Under Dobrushin's Condition
• Learning Structured Distributions From Untrusted Batches: Faster and Simpler
• Nearly Tight Bounds for Robust Proper Learning of Halfspaces with a Margin
• Learning Deep Neural Networks under Agnostic Corrupted Supervision
• Asynchronous Distributed Optimization with Redundancy in Cost Functions
• An Investigation of Data Poisoning Defenses for Online Learning
• Outlier-Robust Sparse Estimation via Non-Convex Optimization
• De-Pois: An Attack-Agnostic Defense against Data Poisoning Attacks
• Robust Estimation for Random Graphs
• Statistical Query Lower Bounds for List-Decodable Linear Regression
• Robust Structured Statistical Estimation via Conditional Gradient Type Methods
• Near-Optimal Statistical Query Hardness of Learning Halfspaces with Massart Noise
• Visions in Theoretical Computer Science: A Report on the TCS Visioning Workshop 2020
• Estimating Principal Components under Adversarial Perturbations
• Certifying Robustness to Programmable Data Bias in Decision Trees
• ReLU Regression with Massart Noise
• Robust Learning of Fixed-Structure Bayesian Networks in Nearly-Linear Time
• Robustness Against Outliers For Deep Neural Networks By Gradient Conjugate Priors
• Tailored Bayes: a risk modelling framework under unequal misclassification costs
• A Separation Result Between Data-oblivious and Data-aware Poisoning Attacks