  We study the problem of black-box optimization of a noisy function in the
presence of low-cost approximations or fidelities, which is motivated by
problems like hyper-parameter tuning. In hyper-parameter tuning evaluating the
black-box function at a point involves training a learning algorithm on a large
data-set at a particular hyper-parameter and evaluating the validation error.
Even a single such evaluation can be prohibitively expensive. Therefore, it is
beneficial to use low-cost approximations, like training the learning algorithm
on a sub-sampled version of the whole data-set. These low-cost
approximations/fidelities can however provide a biased and noisy estimate of
the function value. In this work, we incorporate the multi-fidelity setup in
the powerful framework of noisy black-box optimization through tree-like
hierarchical partitions. We propose a multi-fidelity bandit based tree-search
algorithm for the problem and provide simple regret bounds for our algorithm.
Finally, we validate the performance of our algorithm on real and synthetic
datasets, where it outperforms several benchmarks.
