  Over the last decade, research on automated parameter tuning, often referred
to as automatic algorithm configuration (AAC), has made significant progress.
Although the usefulness of such tools has been widely recognized in real world
applications, the theoretical foundations of AAC are still very weak. This
paper addresses this gap by studying the performance estimation problem in AAC.
More specifically, this paper first proves the universal best performance
estimator in a practical setting, and then establishes theoretical bounds on
the estimation error, i.e., the difference between the training performance and
the true performance for a parameter configuration, considering finite and
infinite configuration spaces respectively. These findings were verified in
extensive experiments conducted on four algorithm configuration scenarios
involving different problem domains. Moreover, insights for enhancing existing
AAC methods are also identified.
