Robust Regression via Hard Thresholding

Abstract

We study the problem of Robust Least Squares Regression (RLSR) where several response variables can be adversarially corrupted. More specifically, for a data matrix X \in R^{p x n} and an underlying model w*, the response vector is generated as y = X'w* + b where b \in R^n is the corruption vector supported over at most C.n coordinates. Existing exact recovery results for RLSR focus solely on L1-penalty based convex formulations and impose relatively strict model assumptions such as requiring the corruptions b to be selected independently of X. In this work, we study a simple hard-thresholding algorithm called TORRENT which, under mild conditions on X, can recover w* exactly even if b corrupts the response variables in an adversarial manner, i.e. both the support and entries of b are selected adversarially after observing X and w*. Our results hold under deterministic assumptions which are satisfied if X is sampled from any sub-Gaussian distribution. Finally unlike existing results that apply only to a fixed w*, generated independently of X, our results are universal and hold for any w* \in R^p. Next, we propose gradient descent-based extensions of TORRENT that can scale efficiently to large scale problems, such as high dimensional sparse recovery and prove similar recovery guarantees for these extensions. Empirically we find TORRENT, and more so its extensions, offering significantly faster recovery than the state-of-the-art L1 solvers. For instance, even on moderate-sized datasets (with p = 50K) with around 40% corrupted responses, a variant of our proposed method called TORRENT-HYB is more than 20x faster than the best L1 solver.

24 pages, 3 figures

References in corpus (2)

• On Iterative Hard Thresholding Methods for High-dimensional M-Estimation
• Fast and Robust Least Squares Estimation in Corrupted Linear Models

Cited by in corpus (35)

• Byzantine-Robust Distributed Learning: Towards Optimal Statistical Rates
• Non-convex Optimization for Machine Learning
• Gradient Descent with Early Stopping is Provably Robust to Label Noise for Overparameterized Neural Networks
• High Dimensional Robust Sparse Regression
• Certified Robustness to Label-Flipping Attacks via Randomized Smoothing
• Byzantine Fault Tolerant Distributed Linear Regression
• Optimal Robust Linear Regression in Nearly Linear Time
• Robust and Differentially Private Mean Estimation
• Online Robust Regression via SGD on the l1 loss
• Robust subset selection
• Choosing the Sample with Lowest Loss makes SGD Robust
• On Tilted Losses in Machine Learning: Theory and Applications
• Identifying noisy labels with a transductive semi-supervised leave-one-out filter
• Between hard and soft thresholding: optimal iterative thresholding algorithms
• Defending Against Saddle Point Attack in Byzantine-Robust Distributed Learning
• Resilience in Collaborative Optimization: Redundant and Independent Cost Functions
• Approximate Byzantine Fault-Tolerance in Distributed Optimization
• Robust Meta-learning for Mixed Linear Regression with Small Batches
• Multivariate Regression with Grossly Corrupted Observations: A Robust Approach and its Applications
• Iterative Least Trimmed Squares for Mixed Linear Regression
• Robustly Clustering a Mixture of Gaussians
• Outlier-robust estimation of a sparse linear model using ${\ell }_1$-penalized Huber's $M$-estimator
• On the exact minimization of saturated loss functions for robust regression and subspace estimation
• Tilted Empirical Risk Minimization
• Robust Gaussian Process Regression for Real-Time High Precision GPS Signal Enhancement
• Making Paper Reviewing Robust to Bid Manipulation Attacks
• Robust Risk Minimization for Statistical Learning
• Learning Deep Neural Networks under Agnostic Corrupted Supervision
• Regret Bounds for Non-decomposable Metrics with Missing Labels
• Robust Mean Estimation on Highly Incomplete Data with Arbitrary Outliers
• On the adversarial robustness of robust estimators
• Demarcating Endogenous and Exogenous Opinion Dynamics: An Experimental Design Approach
• Layered Sampling for Robust Optimization Problems
• ReLU Regression with Massart Noise
• Learning Mixtures of Low-Rank Models