Adaptive multi-fidelity optimization with fast learning rates
For practitioners of black-box optimization, this work provides a theoretically grounded algorithm that adapts to unknown problem parameters, improving over existing multi-fidelity methods.
The paper addresses multi-fidelity optimization with limited budget, proving lower bounds for simple regret and introducing the Kometo algorithm that achieves optimal rates without prior knowledge of smoothness or fidelity, outperforming previous methods empirically.
In multi-fidelity optimization, biased approximations of varying costs of the target function are available. This paper studies the problem of optimizing a locally smooth function with a limited budget, where the learner has to make a tradeoff between the cost and the bias of these approximations. We first prove lower bounds for the simple regret under different assumptions on the fidelities, based on a cost-to-bias function. We then present the Kometo algorithm which achieves, with additional logarithmic factors, the same rates without any knowledge of the function smoothness and fidelity assumptions, and improves previously proven guarantees. We finally empirically show that our algorithm outperforms previous multi-fidelity optimization methods without the knowledge of problem-dependent parameters.