Adaptive multi-fidelity optimization with fast learning rates
| Authors | Come Fiegel et al. |
| Year | 2026 |
| Field | Statistics / ML |
| arXiv | 2604.16239 |
| Download | |
| Categories | stat.ML, cs.LG |
Abstract
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.
Engineering Breakdown
Plain English
This paper tackles multi-fidelity optimization—a practical problem where you have access to multiple approximate versions of an expensive function, each with different costs and accuracy levels, and need to find a good solution with a limited budget. The authors prove theoretical lower bounds on how well any algorithm can perform under different assumptions about function smoothness and the cost-accuracy tradeoffs of available approximations. They then introduce Kometo, an adaptive algorithm that achieves near-optimal performance without requiring prior knowledge of function smoothness or fidelity characteristics, matching the lower bounds up to logarithmic factors. In experiments, Kometo outperforms existing multi-fidelity methods while remaining completely tuning-free.
Core Technical Contribution
The core novelty is a theoretically-grounded adaptive algorithm that automatically balances exploration between low-cost biased approximations and high-cost accurate evaluations without requiring problem-specific tuning. The paper establishes matching upper and lower bounds on regret for multi-fidelity optimization under different smoothness and bias assumptions, proving that any algorithm must pay at least a certain cost-dependent penalty. Kometo achieves these rates adaptively by learning the optimal fidelity allocation schedule online, without knowing the cost-to-bias function in advance. This is a significant advance over prior work which either required explicit knowledge of problem parameters or suffered from suboptimal logarithmic gaps in their guarantees.
How It Works
Kometo operates in rounds where at each step it must decide which fidelity level to query: a cheap but biased approximation, or expensive but accurate evaluations of the target function. The algorithm maintains confidence bounds around its estimate of the true function's optimum using evaluations from all fidelity levels, adaptively learning which fidelities provide the best information-per-cost ratio. When the algorithm discovers that a low-cost approximation has favorable bias properties, it queries that fidelity more often; conversely, if a fidelity proves too noisy or expensive relative to its accuracy, the algorithm downweights it. The key mechanism is a principled weighting scheme that treats the multi-fidelity problem as a cost-weighted bandit problem, where each fidelity is an arm with unknown cost-accuracy tradeoff. The algorithm terminates with a recommendation of the best point found, and the simple regret (distance from true optimum) decreases as budget increases, with rate determined by the cost-to-bias structure of available fidelities.
Production Impact
In real-world optimization scenarios like hyperparameter tuning for ML models or Bayesian optimization in drug discovery, this approach eliminates the need to manually specify problem-dependent parameters—you point Kometo at your fidelity sources and it automatically learns how to use them efficiently. This is immediately valuable in hyperparameter optimization where you could use cheap validation-set evaluations alongside expensive full cross-validation, or in simulation-based optimization where low-fidelity simulators are orders of magnitude faster than high-fidelity ones. The practical benefit is reduced total wall-clock time and compute cost for optimization tasks: if you have access to fast approximations, Kometo will discover and exploit them automatically rather than wasting budget on expensive ground truth when unnecessary. Integration complexity is moderate—you need to implement the adaptive fidelity selection logic and maintain confidence estimates, but the algorithm is stateless across iterations so it parallelizes naturally. The main trade-off is that Kometo requires some burn-in queries to learn fidelity characteristics, so on very small budgets (< 100 queries) hand-tuned multi-fidelity methods might still win if you have expert knowledge of your specific problem.
Limitations and When Not to Use This
The paper assumes function smoothness properties and well-behaved cost-to-bias functions, which may not hold when dealing with highly multimodal objectives or when cheaper approximations are misleadingly biased in certain regions. Kometo is designed for simple regret (finding a good solution) rather than cumulative regret (performance over all iterations), so the theory doesn't directly apply to continual optimization settings where online performance matters. The algorithm also assumes access to multiple fidelities is genuinely available—in problems with only a single expensive function, standard Bayesian optimization is more appropriate. The paper doesn't fully explore how the method scales with the number of fidelities (dimension of the fidelity selection decision), though the analysis suggests it should handle moderate numbers gracefully. Finally, the logarithmic factors hidden in the "with additional logarithmic factors" statement in the abstract could be substantial in practice, and the paper would benefit from tighter constants and computational complexity analysis for large-budget scenarios.
Research Context
This work extends the multi-fidelity optimization literature which includes foundational work on multi-fidelity Bayesian optimization and multi-level Monte Carlo methods, but with a focus on adaptation and worst-case theoretical guarantees rather than Bayesian modeling. The paper builds on regret analysis frameworks from the online learning and bandit communities, translating the fidelity selection problem into a cost-weighted exploration-exploitation problem. It improves upon prior results like the work of Kannan et al. and multi-fidelity UCB variants by removing the requirement for explicit problem knowledge and tightening regret bounds. The research direction opened is toward developing practical adaptive algorithms that handle composite optimization problems with heterogeneous information sources, with applications extending beyond traditional optimization to active learning and experiment design where similar cost-accuracy tradeoffs appear.
:::tip Subscribe Get weekly breakdowns of papers like this in AI Letters - the newsletter for engineers building production AI systems. :::