  In this paper, we investigate the adversarial robustness of feature selection
based on the $\ell_1$ regularized linear regression model, namely LASSO. In the
considered model, there is a malicious adversary who can observe the whole
dataset, and then will carefully modify the response values or the feature
matrix in order to manipulate the selected features. We formulate the
modification strategy of the adversary as a bi-level optimization problem. Due
to the difficulty of the non-differentiability of the $\ell_1$ norm at the zero
point, we reformulate the $\ell_1$ norm regularizer as linear inequality
constraints. We employ the interior-point method to solve this reformulated
LASSO problem and obtain the gradient information. Then we use the projected
gradient descent method to design the modification strategy. In addition, We
demonstrate that this method can be extended to other $\ell_1$ based feature
selection methods, such as group LASSO and sparse group LASSO. Numerical
examples with synthetic and real data illustrate that our method is efficient
and effective.
