We analyze an optimization-based approach called the NP-Filter for feature selection and show how the scalability of this method can be improved using random sampling of instances from the training data. The NP-Filter has attractive theoretical properties as the final solution quality can be quantified and it is flexible in terms of incorporating various feature evaluation methods. We show how the NP-Filter can automatically adjust to the randomness that occurs when a sample of training instances is used, and present numerical results that illustrate both this key result and the scalability improvement that are obtained.