Due to their complexity, modern systems expose many con-figuration parameters which users must tune to maximizeperformance. Auto-tuning has emerged as an alternative inwhich a black-box optimizer iteratively evaluates configura-tions to find efficient ones. Unfortunately, for many systems,such as distributed systems, evaluating performance takestoo long and the space of configurations is too large for theoptimizer to converge within a reasonable time