  In this paper, we study problem of estimating a sparse regression vector with
correct support in the presence of outlier samples. The inconsistency of
lasso-type methods is well known in this scenario. We propose a combinatorial
version of outlier-robust lasso which also identifies clean samples.
Subsequently, we use these clean samples to make a good estimation. We also
provide a novel invex relaxation for the combinatorial problem and provide
provable theoretical guarantees for this relaxation. Finally, we conduct
experiments to validate our theory and compare our results against standard
lasso.
