Abstract In virtually all machine learning applications, hyper-parameter tuning is required to maximize predictive accuracy. Such tuning is computationally expensive, and the cost is further exacerbated by the need for multiple evaluations (via crossvalidation or bootstrap) at each con?guration setting to guarantee statistically signi?cant results. This paper presents a simple, general technique for improving the ef?ciency of hyper-parameter tuning by minimizing the number of resampled evaluations at each con?guration. We exploit the fact that train-test samples can easily be matched across candidate hyper-parameter con?gurations. This permits the use of paired hypothesis tests and power analysis that allow for statistically sound early elimination of suboptimal candidates to minimize the number of evaluations. Results on synthetic and real-world datasets demonstrate that our method improves over competitors for discrete parameter settings, and enhances state-of-the-art techniques for continuous parameter settings.