Optimal Multi-Fidelity Best-Arm Identification

Summary

This paper introduces qPOTS (Pareto Optimal Thompson Sampling), a novel approach for efficient batch multiobjective Bayesian optimization in the context of best-arm identification (BAI) with multi-fidelity bandits. The authors present a tight lower bound on the cost complexity of multi-fidelity BAI and propose an algorithm that asymptotically matches this bound. The method combines ideas from Thompson sampling, Gaussian process surrogates, and evolutionary algorithms to address challenges in multiobjective optimization with expensive oracles. The paper provides theoretical analysis, including convergence guarantees, and demonstrates empirical performance on synthetic and real-world problems.

Strengths

Theoretical contributions: The paper presents a tight lower bound on the cost complexity of multi-fidelity BAI, which improves upon previous bounds in the literature. This provides valuable insights into the fundamental limits of such problems. Algorithm development: The proposed qPOTS algorithm is designed to asymptotically match the lower bound, potentially offering optimal performance in the high-confidence regime.

Weaknesses

Limited experimental evaluation: The experiments seem relatively limited in scope, focusing primarily on synthetic problems and a few real-world examples. More extensive testing on diverse real-world applications, such as neural architecture search or classic multi-fidelity Bayesian optimization problems, would strengthen the paper's practical relevance. Connection to real-world problems: While the theoretical results are impressive, it's not immediately clear how they translate to understanding or solving real-world problems. More discussion on practical implications would be beneficial. Assumption realism: The paper relies on some assumptions that may not always hold in practice. For example, Assumption 5 in Theorem 4.1 (asymptotic convergence) may not be realistic in all scenarios. More discussion on the implications of these assumptions would be helpful. Narrow problem focus: The best-arm identification problem, while important, may be seen as somewhat limited compared to more general multi-fidelity Bayesian optimization problems. The authors could elaborate more on how their work relates to or extends to broader MFBO settings. Gradient computation clarity: The explanation of gradient computation with respect to ω and μ could be clearer, especially given that these values are often discrete in bandit problems. More detailed explanations and precise notation would improve understanding.

Questions

How does this work relate to broader multi-fidelity Bayesian optimization problems? Can the authors elaborate on potential extensions or applications beyond best-arm identification? Can the authors provide more intuition or examples of how the theoretical results help in understanding real-world multi-fidelity optimization problems? Theorem 3.1 states that the lower bound holds for any multi-fidelity bandit. Does this truly hold regardless of the specific multi-fidelity model or acquisition function used? If so, could the authors elaborate on why this is the case? How realistic is Assumption (5) in Theorem 4.1? Can the authors provide examples of scenarios where this assumption would or would not hold, and discuss the implications? The gradient computation with respect to ω and μ is not entirely clear, especially given that these are often discrete values in bandit problems. Could the authors provide a more detailed explanation of how these gradients are defined and computed, ensuring clarity and precision in the notation? Have the authors considered applying their method to more complex real-world applications, such as neural architecture search or other MFBO problems that can be framed as BAI? If not, what challenges might arise in such applications?

Rating

4

Confidence

3

Soundness

3

Presentation

1

Contribution

2

Limitations

The paper could benefit from a more thorough discussion of the scenarios where the assumptions might not hold and the potential implications for the algorithm's performance. The authors should provide more context on the limitations of the best-arm identification framework compared to more general multi-fidelity Bayesian optimization problems. A discussion on the potential challenges in applying the method to more complex, real-world problems would be valuable. The paper would benefit from a more comprehensive discussion of the potential negative societal impacts of the work, even if they are indirect.

Summary

This paper considers the fixed confidence BAI problem in a multi-fidelity setting, where each arm can be sampled at lower or higher fidelity levels, with a corresponding lower or higher cost. The objective is to declare the best arm, which is the arm with the highest mean at the highest fidelity level. The authors derive an instance dependent cost lower bound, in terms of optimal sampling frequencies at each fidelity level for each arm. They then propose a sub gradient based algorithm with forced exploration that is asymptotically optimal in terms of cost.

Strengths

This paper makes non-trivial technical contributions to the state of the art in multi fidelity BAI. The measure-zero result in Theorem 3.2 seems novel and interesting. The "achievability" part is also novel, in the sense that it is not an extension of traditional track and stop. It uses a sub gradient ascent algorithm (which has been used in bandits before), but the gradient computation section in 4.2 also appears potentially useful in related problem settings. Appendix B.2 shows that the lower bound in [26] can be significantly worse (by an arbitrarily large multiplicative factor) than the proposed lower bound. In appendix D.6, the authors also identify a problem of "non-stopping" from [33], both numerically and analytically.

Weaknesses

I do not see any issue that can be flagged as a significant weakness.

Questions

I don't see any shaded area denoting confidence intervals in Figure 3. Line 78: notation.

Rating

7

Confidence

3

Soundness

3

Presentation

3

Contribution

3

Limitations

No concerns on social impacts

Summary

The paper studies the problem of multi-fidelity best arm identification in the fixed confidence setting. The main contribution is an instance-dependent lower bound on the cost complexity. The authors demonstrate the bound's tightness by providing an algorithm with a matching upper bound in asymptotics, as well as an instance where the lower bound improves on the previous lower bound by a tighter constant.

Strengths

The paper is well-presented in terms of its theorem statements and comparison with prior works. The theoretical result, specifically the lower bound, shows a clear improvement over previous work.

Weaknesses

I think there is room to improve the presentation of the algorithm. Just by staring at the algorithm box, it took some time to understand the relationships between $\tilde{\omega}$, $\bar{\omega} $, $\tilde{\pi}$, $\pi'$, and have to look for their definitions here and there. It would be great if these could be made clear within the algorithm box itself.

Questions

Do the authors have any conjectures on the fixed-budget setting for multi-fidelity best arm identification? I'm not entirely sure this is a valid problem, but I wonder if it could be approached similarly to the normal track-and-stop method. By solving the optimization problem and sampling according to it without a stopping rule, it naturally turns into a fixed-budget algorithm. Can MF-GRAD be used in a similar manner?

Rating

7

Confidence

4

Soundness

3

Presentation

3

Contribution

3

Limitations

No major limitation to me.