  We develop a hyperparameter optimisation algorithm, Automated Budget
Constrained Training (AutoBCT), which balances the quality of a model with the
computational cost required to tune it. The relationship between
hyperparameters, model quality and computational cost must be learnt and this
learning is incorporated directly into the optimisation problem. At each
training epoch, the algorithm decides whether to terminate or continue
training, and, in the latter case, what values of hyperparameters to use. This
decision weighs optimally potential improvements in the quality with the
additional training time and the uncertainty about the learnt quantities. The
performance of our algorithm is verified on a number of machine learning
problems encompassing random forests and neural networks. Our approach is
rooted in the theory of Markov decision processes with partial information and
we develop a numerical method to compute the value function and an optimal
strategy.
