Robust High Dimensional Sparse Regression and Matching Pursuit

By Yudong Chen, Constantine Caramanis, Shie Mannor. 2013

21 citations recorded by the source corpus.

We consider high dimensional sparse regression, and develop strategies able to deal with arbitrary -- possibly, severe or coordinated -- errors in the covariance matrix $X$. These may come from corrupted data, persistent experimental errors, or malicious respondents in surveys/recommender systems, etc. Such non-stochastic error-in-variables problems are notoriously difficult to treat, and as we demonstrate, the problem is particularly pronounced in high-dimensional settings where the primary goal is {\em support recovery} of the sparse regressor. We develop algorithms for support recovery in sparse regression, when some number $n_1$ out of $n+n_1$ total covariate/response pairs are {\it arbitrarily (possibly maliciously) corrupted}. We are interested in understanding how many outliers, $n_1$, we can tolerate, while identifying the correct support. To the best of our knowledge, neither standard outlier rejection techniques, nor recently developed robust regression algorithms (that focus only on corrupted response variables), nor recent algorithms for dealing with stochastic noise or erasures, can provide guarantees on support recovery. Perhaps surprisingly, we also show that the natural brute force algorithm that searches over all subsets of $n$ covariate/response pairs, and all subsets of possible support coordinates in order to minimize regression error, is remarkably poor, unable to correctly identify the support with even $n_1 = O(n/k)$ corrupted points, where $k$ is the sparsity. This is true even in the basic setting we consider, where all authentic measurements and noise are independent and sub-Gaussian. In this setting, we provide a simple algorithm -- no more computationally taxing than OMP -- that gives stronger performance guarantees, recovering the support with up to $n_1 = O(n/(\sqrt{k} \log p))$ corrupted points, where $p$ is the dimension of the signal to be recovered.

How researchers see this paper

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

Citations in the corpus

Targeted Backdoor Attacks on Deep Learning Systems Using Data Poisoning (2017, methodology): “Such statistical robust learning algorithms have been proposed for several traditional machine learning models such as linear and logistic regressions [14], [18], [27], [16], [39], [61].”
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).”
Robust High-Dimensional Linear Regression (2016, background): “Recently, Chen et al. [9] and Feng et al. [10] considered recovery strategy when the corruption is adversarially chosen to achieve some malicious goal.”
Robust Linear Regression Against Training Data Poisoning (2017, methodology): “As we can observe, our T-PCR approach’s runtime is almost the same as Chen et al. 2013’s runtime, though our approach’s runtime is not as stable as Chen et al. 2013’s.”