We provide a novel -- and to the best of our knowledge, the first --
algorithm for high dimensional sparse regression with constant fraction of
corruptions in explanatory and/or response variables. Our algorithm recovers
the true sparse parameters with sub-linear sample complexity, in the presence
of a constant fraction of arbitrary corruptions. Our main contribution is a
robust variant of Iterative Hard Thresholding. Using this, we provide accurate
estimators: when the covariance matrix in sparse regression is identity, our
error guarantee is near information-theoretically optimal. We then deal with
robust sparse regression with unknown structured covariance matrix. We propose
a filtering algorithm which consists of a novel randomized outlier removal
technique for robust sparse mean estimation that may be of interest in its own
right: the filtering algorithm is flexible enough to deal with unknown
covariance. Also, it is orderwise more efficient computationally than the
ellipsoid algorithm. Using sub-linear sample complexity, our algorithm achieves
the best known (and first) error guarantee. We demonstrate the effectiveness on
large-scale sparse regression problems with arbitrary corruptions.

提出了一种用于高维度稀疏回归中具有常量分数的自变量和 / 或响应变量的污染的算法，它是迄今为止的首个这样的算法，利用使用这种算法，我们提供了强健的稀疏回归方法和过滤算法。

高维稳健稀疏回归

High Dimensional Robust Sparse Regression

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.

研究高维稀疏回归的非随机误差问题，并开发算法来支持恢复，实验展示了标准异常值过滤技术、稳健回归算法、处理随机噪声或擦除的算法不能提供支持恢复的保证。