Kometo: Mastering Multi-Fidelity Optimization without the "Bias" Knowledge

TL;DR

Optimizing complex functions (like tuning hyper-parameters for massive AI models) is slow because every "high-fidelity" evaluation is expensive. Multi-fidelity optimization solves this by using cheaper, "low-fidelity" approximations. This paper introduces Kometo, the first algorithm that proves and achieves optimal rates without knowing how biased those cheap approximations actually are.

The "Oracle" Problem in Multi-Fidelity

In traditional multi-fidelity setups, we assume a cost-to-bias function $\zeta (z)$. If you pay $X$ dollars, you get an answer within $Y$ accuracy. Prior SOTA workers (like MFPDOO) assumed we knew this $Y$ or its mathematical form. But in reality, how do you know how much "bias" is in a 10-epoch training run compared to a 100-epoch one before you've actually run them?

If your assumption is wrong, your optimization fails. Kometo breaks this cycle by being parameter-free regarding both the objective's smoothness and the fidelity's bias.

Methodology: Rank-Based Zipf Sampling

Kometo's magic lies in two components:

1. Rank-Based Logic: Instead of looking at the value of an evaluation (e.g., "Accuracy is 0.72"), it looks at the comparison ("Point A is better than Point B"). This allows the algorithm to handle approximations that are stretched or shifted, as long as they maintain the correct relative order.
2. Strategic Resource Allocation: It uses a tree-based search. As it goes deeper into the tree (finer resolution), it uses a Zipf-like distribution to decide how many cells to open and at what fidelity.

The algorithm allocates its budget $\Lambda$ into an Exploration phase (finding promising areas using cheap fidelities) and a Cross-validation phase (validating the best candidates with high-cost evaluations).

Theoretical Breakthrough: The First Lower Bounds

The authors didn't just build a better mousetrap; they proved how good a mousetrap can possibly be. They established lower bounds for simple regret $r_{\Lambda }$ across three types of fidelity assumptions:

• Polynomial: $\Phi (c)\le A/c^{\alpha }$
• Exponential: $\Phi (c)\le B{e}^{-\sigma c^{\beta }}$
• Constant: $\Phi (c)=0$ after a certain cost.

Kometo matches these lower bounds (up to log factors), proving it is nearly as efficient as an algorithm that knows the smoothness and bias perfectly.

Experimental Battleground

The researchers tested Kometo against MFPDOO (multi-fidelity), POO, and SequOOL (single-fidelity).

Key Highlights:

• Practical Advantage: In the SVM hyper-parameter tuning experiment (bottom-right), Kometo achieved higher accuracy faster than its competitors.
• Robustness: Even when low-fidelity information was misleading in some synthetic tests, Kometo's cross-validation step shielded it from significant performance drops.

Critical Insight: Why Rank-Based is the Future

The most profound contribution of this paper is the relaxation of the bias assumption. By using $\Vert f-g_z\circ f_z{\Vert }_{\infty }\le \zeta (z)$ where $g_z$ is any strictly increasing function, the authors acknowledge that lower fidelities often preserve the "topography" of the search space even if the absolute values are way off. This matches the intuition of ML engineers: a model that performs better on a small dataset likely performs better on a large one too.

Conclusion & Future Work

Kometo is a significant step toward "plug-and-play" optimization. It removes the need for expert-tuned hyper-parameters for the hyper-parameter optimizer itself. While currently focused on deterministic settings, the authors hint that extending this to stochastic noise (e.g., using concentration inequalities) is the next frontier.

Verdict: If you are dealing with expensive simulators or heavy model training where you don't fully understand the fidelity-cost curve, Kometo is the new gold standard for adaptive optimization.