  Hyperparameter tuning is a common technique for improving the performance of
neural networks. Most techniques for hyperparameter search involve an iterated
process where the model is retrained at every iteration. However, the expected
accuracy improvement from every additional search iteration, is still unknown.
Calculating the expected improvement can help create stopping rules for
hyperparameter tuning and allow for a wiser allocation of a project's
computational budget. In this paper, we establish an empirical estimate for the
expected accuracy improvement from an additional iteration of hyperparameter
search. Our results hold for any hyperparameter tuning method which is based on
random search \cite{bergstra2012random} and samples hyperparameters from a
fixed distribution. We bound our estimate with an error of
$O\left(\sqrt{\frac{\log k}{k}}\right)$ w.h.p. where $k$ is the current number
of iterations. To the best of our knowledge this is the first bound on the
expected gain from an additional iteration of hyperparameter search. Finally,
we demonstrate that the optimal estimate for the expected accuracy will still
have an error of $\frac{1}{k}$.
