- Rating
- 2
- Confidence
- 4
- Informativeness
- 1
- Presentation
- 3
- Soundness
- 3
Read review
Paper summary
Bayesian optimization iterates:
- Evaluating a black-box function at some chosen x_t -> y_t
- Updating a GP-based surrogate model fitted to data {(x_s, y_s) | s <= t}
- Choose next x_{t+1} as minimizer of an acquisition function (AF) alpha_{t+1} based on the surrogate model
The AF optimization is a non-convex optmization problem. alpha_t is differentiable w.r.t. inputs, but even if the input space X is closed and convex, this may be hard. The default is to use gradient-based local optimization (like L-BFGS). This paper proposes to use a Kernel-SOS relaxation instead.
As such, this is a nice and potentially useful proposal. The method is plug-in, so can easily be used in existing BO software. However, given that Kernel-SOS has been proposed before, there is almost no novelty here.
On top, the paper glosses over the most important question, namely how large N has to be. They represent alpha_t(.) by a kernel expansion on N points, which are somehow sampled in each round. SDPs scale horribly in N, at the very least O(N^3). None of the baselines compared to need to sample alpha_t at N points or encur O(N^3) or higher.
Given that, the paper does not even say what value of N was used in the experiments. Somewhere in Table 2 (Appendix), I found N = 128, but capital N is also used elsewhere in the Appendix. On top, this table lists 6 variants of Kernel-SOS, none of them mentioned in the main text.
For a paper of this simplicity, as well as such an obvious bottleneck (size of N), I'd expect a lot more empirical work. As such, I cannot judge the usefulness, also because all experiments are done on toy problems only. Running BO on some test functions is not up to standards of an ICLR paper. BO is sometimes useful in ML/AI, but this really has to be demonstrated. Also, most useful BO problems (not test functions!) have categorical, discrete variables. This needs then a further relaxation of X to closed convex, plus some back-projection. None of this is evaluated.
Critical strengths
Given that Kernel-SOS for optimizing AFs has not been proposed, and is not in the main BO libraries (BOTorch, Optuna, ...), the proposal here makes sense. I do not need heavy optimizers like L-BFGS, which can fail in many ways. Instead, of course, I need some SDP solver, which is also heavy.
Having said that, the usefulness of the method here hinges crucially on how large N has to be, whether lambda can be chosen automatically, whether the right N can be chosen automatically, and also on a better understanding how the N points x_i are to be sampled in each round. None of this is really addressed.
Critical weaknesses
Given the simplicity and lack of novelty, the empirical evaluation / ablations is simply nowhere near good enough.
What is crucially missing, is being clear and upfront about N. How large does this have to be? What is the scaling of your solver with N? In fact, if I do not have money to license some SDP solver, what do you propose?
Next, the scope of experiments is much too small and toy-ish. I personally do not care much about age-old test functions which the global optim community overfits on since decades. ICLR readers care about real-world applications, such as tuning hyperparameters of training a DNN or (more timely) tuning parameters for LLM inference, AI in science, or whatever (just check recent literature). Such problems always have categorical parameters, so please deal with them (needs additional relaxations, and it is unclear whether assumption (6) still makes sense then).
If the authors do not want to do any of this, then at least they should use some of the tabulated real-world benchmarks available for HPO today.
Also, there are obvious baselines missing. If you allow me N evals at points x_i, I'd try:
- Pick minimizer of alpha_t(x_i)
- Start L-BFGS for a few iterations from that minimizer, or even from the top-K minimizers,
In fact, there would be many directions along which the authors could try to make this work useful. I list some in the next box.
Questions for authors
Honestly, I do not really believe that SOS relaxation is useful for optimizing the AF:
- Given alpha_t, I can easily compute gradients. You are not using them. Not using gradients for a smooth problem seems wasteful
- Solving the relaxation scales terribly with N, so you'll have to use a fairly small N. Small N and no gradients
You need to do work in order to convince readers like myself that your proposal is useful. A lot of things come to mind:
- Be upfront about N. Run ablations w.r.t. N
- Choice of lambda. Ablations
- Use realistic HPO problems, not toy-ish test functions. Work with categorical and mixed spaces
- Say you figure that N has to remain fairly small. Can you choose/sample the x_i in a particular way, that would make this idea work even if it does not work with randomly sampled x_i?
Finally, if you think this is useful, contribute it to BOTorch or Optuna or elsewhere. In that case, you cannot ask them to license some expensive SDP solver, or depend on some monster code, so you need to work on a special solution for your case. Namely, using an SDP solver to pick the next point in BO is a very big hammer for a small nail.
We sincerely thank the reviewers for their time, thoughtful questions, and constructive feedback. Your comments have been very helpful in identifying important aspects of our work that warrant further investigation and improvement.
After careful consideration, we have decided to withdraw our submission, as we would like to spend more time addressing the reviewers’ concerns, conducting additional experiments, and further strengthening our work.
We truly appreciate your time and effort in reviewing our work, and we look forward to present a refined version in the future.