  Recent work on hyperparameters optimization (HPO) has shown the possibility
of training certain hyperparameters together with regular parameters. However,
these online HPO algorithms still require running evaluation on a set of
validation examples at each training step, steeply increasing the training
cost. To decide when to query the validation loss, we model online HPO as a
time-varying Bayesian optimization problem, on top of which we propose a novel
\textit{costly feedback} setting to capture the concept of the query cost.
Under this setting, standard algorithms are cost-inefficient as they evaluate
on the validation set at every round. In contrast, the cost-efficient GP-UCB
algorithm proposed in this paper queries the unknown function only when the
model is less confident about current decisions. We evaluate our proposed
algorithm by tuning hyperparameters online for VGG and ResNet on CIFAR-10 and
ImageNet100. Our proposed online HPO algorithm reaches human expert-level
performance within a single run of the experiment, while incurring only modest
computational overhead compared to regular training.
