Various technologies described herein pertain to estimating predictive accuracy gain of a potential feature added to a set of features, wherein an existing predictor is trained on the set of features. Outputs of the existing predictor for instances in a dataset can be retrieved from a data store. Moreover, a predictive accuracy gain estimate of a potential feature added to the set of features can be measured as a function of the outputs of the existing predictor for the instances in the dataset. The predictive accuracy gain estimate can be measured without training an updated predictor on the set of features augmented by the potential feature.