Robust Regression via Hard Thresholding

By Kush Bhatia, Prateek Jain, Purushottam Kar. 2015

169 citations recorded by the source corpus.

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 ∈ ℝp x n and an underlying model w*, the response vector is generated as y = XT w* + b where b ∈ ℝ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* ∈ ℝ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 20 x faster than the best L1 solver.

Subfields: Statistics and Probability, 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 Statistics and Probability

In Optimization & Training

Citations in the corpus

Byzantine Stochastic Gradient Descent (2018, background): “Optimization and learning in the presence of adversarial noise is a well-studied problem [4, 5, 15, 20, 22, 28].”
Sever: A Robust Meta-Algorithm for Stochastic Optimization (2018, background): “A number of papers [NTN11, NT13, BJK15, BJKK17] have proposed eﬃcient algorithms for a type of robust linear regression.”
Byzantine-Robust Distributed Learning: Towards Optimal Statistical Rates (2018, background): “…estimation in non-distributed settings, much progress has been made recently in terms of improved performance in high-dimensional problems (Bhatia et al., 2015, Diakonikolas et al., 2016, Lai et al., 2016) as well as developing list-decodable and semi-veriﬁed learning schemes when a…”
Certified Defenses for Data Poisoning Attacks (2017, background): “…(Diakonikolas et al., 2016; Lai et al., 2016; Charikar et al., 2017), classiﬁcation (Klivans et al., 2009; Awasthi et al., 2014), regression (Nasrabadi et al., 2011; Nguyen and Tran, 2013; Chen et al., 2013; Bhatia et al., 2015) and crowdsourced data aggregation (Steinhardt et al., 2016).”
Learning Discrete Distributions from Untrusted Batches (2017, background): “Other learning problems, such as robustly learning halfspaces [KLS09], robust linear regression [BJK15] and more general convex optimization [CSV17] have also been considered in similar settings where some fraction of the data is drawn from a distribution of interest, and no assumptions are made…”
Learning from untrusted data (2016, background): “Bhatia et al. (2015) study linear regression in the presence of adversaries, and obtain bounds for sufficiently large α (say α ≥ 64 65 ) when the design matrix is subset strong convex. Klivans et al. (2009) and Awasthi et al. (2014) provide strong bounds for robust classification in high dimensions ”
Fast low-rank estimation by projected gradient descent: General statistical and algorithmic guarantees (2015, background): “It is also worth noting that other types of algorithms for nonconvex problems have also been analyzed, including alternating minimization [37, 32, 34], EM algorithms [4, 63] and power methods [33], various hard-thresholding and singular value projection [36, 53, 38, 9], gradient descent for nonconve”
Efficient Statistics, in High Dimensions, from Truncated Samples (2018, background): “Other robust estimation works include robust linear regression [19] and robust estimation algorithms under sparsity assumptions [20], [21].”
Choosing the Sample with Lowest Loss makes SGD Robust (2020, background): “Recently, [5, 6, 32, 20, 18] have proposed robust learning algorithms for linear regression which require the computation of gradient over the entire dataset which may be computationally intractable for large datasets.”
Consistent Robust Regression (2017, methodology): “A solution to this is to exclude corrupted Oblivious No Weighted subsampling Bhatia et al., 2015 [3] α ≥ Ω (1) Adaptive No Hard thresholding This paper α ≥ Ω (1) Oblivious Yes Hard thresholding points from consideration.”
Gradient Descent with Early Stopping is Provably Robust to Label Noise for Overparameterized Neural Networks (2019, methodology): “In the context of robust regression and high-dimensional statistics, much of the focus is on regularization techniques to automatically detect and discard outliers by using tools such as (cid:96) 1 penalization [6,10,15,17,22,32,35].”
Learning with Bad Training Data via Iterative Trimmed Loss Minimization (2018, methodology): “(2) In [BJK15], convergence of the parameter is characterized by the linear convergence of i ∈ S t r 2 i with constant rate.”
Efficient and accurate extraction of in vivo calcium signals from microendoscopic video data (2018, unknown): “To overcome this problem, we use robust least squares regression (RLSR) via hard thresholding to avoid contaminations from the outliers (Bhatia et al., 2015).”
Tilted Empirical Risk Minimization (2020, background): “For example, in robust regression, it is common to consider losses such as the L1 loss, Huber loss, or general M -estimators (Holland & Ikeda, 2019) as a way to mitigate the effect of outliers (Bhatia et al., 2015).”
Non-convex Optimization for Machine Learning (2017, methodology): “These properties are related to the traditional RSC/RSS properties and it can be shown (see for example, [Bhatia et al., 2015]) that RIP-inducing distributions over matrices (see § 7.6) also produce matrices that satisfy the SSC/SSS properties, with high probability.”
Computationally Efficient Robust Sparse Estimation in High Dimensions (2017, background): “Hard Thresholding: The idea of using hard thresholding in sparse estimation problems in order to ensure that the overall estimation error is well controlled, has been explored recently in iterative hard thresholding algorithms (see for instance Bhatia et al. (2015); Jain et al. (2014)).”
Efficient Algorithms and Lower Bounds for Robust Linear Regression (2018, methodology): “The reader is referred to [RL87, BJK15] and references therein.”
Defending Against Saddle Point Attack in Byzantine-Robust Distributed Learning (2018, background): “A recent line of work develops efficient robust estimation algorithms in high-dimensional settings [8, 22, 39, 13, 60, 45, 9, 36, 46].”
Resilience: A Criterion for Learning in the Presence of Arbitrary Outliers (2017, background): “…recently that provable algorithms for learning in the presence of a large fraction of arbitrary (and potentially adversarial) data have been formulated in high-dimensional settings (Diakonikolas et al., 2016; Lai et al., 2016; Charikar et al., 2017; Steinhardt et al., 2016; Bhatia et al., 2015).”
Robust estimation via robust gradient estimation (2018, methodology): “As our baselines, we use OLS, TORRENT [16], the Huber-loss M-estimator, RANSAC and a plugin estimator (detailed further in Section sec:linregtheory, and which in a nutshell robustly estimates the sufficient statistics required for the OLS estimator).”