On the Adversarial Robustness of Feature Selection Using LASSO

In this paper, we investigate the adversarial robustness of feature selection based on the $\ell_1$ regularized linear regression method, named LASSO. In the considered problem, there is an adversary who can observe the whole data set. After seeing the data, the adversary will carefully modify the response values and the feature matrix in order to manipulate the selected features. We formulate this problem as a bi-level optimization problem and cast the $\ell_1$ regularized linear regression problem as a linear inequality constrained quadratic programming problem to mitigate the issue caused by non-differentiability of the $\ell_1$ norm. We then use the projected gradient descent to design the modification strategy. Numerical examples based on synthetic data and real data both indicate that the feature selection is very vulnerable to this kind of attacks.