We present a novel scalable inference algorithm for sparse feature selection in binary classification where the training data show spurious correlations, e.g., due to confounding. The approach builds on the sparse probit linear mixed model which was limited to datasets of a few hundred points. Our algorithm potentially scales to datasets with millions of points.