acceptodds
Withdrawn from ICLR 2027

KSOS-BO: Improving Sampling in Bayesian Optimization via Kernel Sum of Squares

Withdrawn from ICLR 2027, so left out of the paper lists and the map.

Abstract

Bayesian Optimization (BO) is an effective framework for globally optimizing functions whose evaluations are expensive. It is particularly effective for optimizing functions defined over continuous domains and explicitly handles stochastic noise in evaluations. As a result, it is widely applied in areas such as hyperparameter tuning, robotics policy search, and scientific experiment design, where sample efficiency is essential. Its two-step procedure consists of model fitting followed by optimization of the acquisition function, which is often treated as a generic black-box problem despite its structured nature. In this work, we introduce KSOS-BO, a kernel-based framework for BO acquisition function optimization. KSOS-BO integrates the recently developed KernelSOS framework to formulate the optimization of the acquisition function as a semidefinite program with kernel-induced representations, enabling a structured global search. Across a diverse set of benchmark functions with varying landscape properties, KSOS-BO achieves the best final regret on 13 out of 20 benchmarks compared with Sobol Search, Differential Evolution, CMA-ES, and multi-start L-BFGS-B. On these 13 benchmarks, it improves final regret over the second-best optimizer by 81.08% on average. Wall-clock time experiments further show that, under the optimizer configurations considered in this study, KSOS-BO can reach high-quality solutions faster on many benchmarks despite the additional semidefinite optimization step.

Primary area:
optimization
Keywords:
bayesian optimization, kernel sum of squares, acquisition function

Reviews

Among:
Shape:
1234this paper, Bottom 27%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.00 over 3 reviews, above 27% of the others.
Reviewer_jaygOpenReview ↗
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.

1 comment

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.

Reviewer_AJx2OpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
2
Soundness
3
Read review
Paper summary

The paper proposes KSOS-BO, a framework that uses KernelSOS to optimize BO acquisition functions. KSOS-BO leverages on acquisition functions' structural properties induced by Gaussian processes. The method is validated based on overall BO performances on synthetic functions, where majority (13/20) showed improvement with KSOS-BO.

Critical strengths
  • The problem tackled in the paper is well-motivated. More efficient and better acquisition optimization can improve downstream BO performance.
Critical weaknesses
  • All main experiments use EI as the acquisition function, but EI has largely been superseded by LogEI (Ament et al., 2023), which provides more stable acquisition values over EI. Experiments should use LogEI, and include other common acquisition functions to show more convincingly that the proposed KSOS-BO broadly improves acquisition optimization and BO performance across acquistion functions, especially since acquisition function landscapes change with acquisition function. PI and LCB results are in the appendix but are not referenced in the main paper, and PI is rarely used in modern BO. Including an information-theoretic one instead like MES will be more representative of acquisition functions used commonly in practice. Currently, it is also hard to tell if the results based on EI will hold for LogEI.

  • Lacking experiments on acquisition function optimization performance. Experiments (Fig. 2-4) mostly show better "outer-loop" BO performance, with only a small study on inner acquisition function optimization between different acquisition optimization methods in Appendix C.7 (and not referenced in the main paper). Table 9 in the appendix also seems to suggest that KSOS does not outperform the commonly used L-BFGS-B based on normalized difference to the optimal value. I think further analysis is needed on why the BO performance improves despite unconvincing improvements in acquisition function optimization.

Ament, S., Daulton, S., Eriksson, D., Balandat, M., & Bakshy, E. Unexpected improvements to expected improvement for Bayesian optimization. NeurIPS 2023.

Questions for authors

See weaknesses.

There is at least one existing acquisition optimization method that exploits the structural properties of acquisition functions (Xie et al., 2025), but it is not mentioned in the related works.

Xie, Y., Zhang, S., Paulson, J. A., & Tsay, C. Global optimization of Gaussian process acquisition functions using a piecewise-linear kernel approximation. AISTATS 2025.

Minor:

  • Typo in Fig. 5 top right title "Differnet"
1 comment

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.

Reviewer_z1KBOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
3
Soundness
3
Read review
Paper summary

The paper treats Bayesian optimization (BO) acquisition optimization as a structured global problem rather than a generic black-box one. At each BO iteration, it evaluates the acquisition function on N = 128 Sobol samples, fits a KernelSOS surrogate of the acquisition landscape as a semidefinite program with an anisotropic Gaussian kernel whose bandwidths come from the GP’s ARD length-scales, and returns a candidate recovered as a weighted combination of the samples (Eq. 6). The method is compared against Sobol search, CMA-ES, Differential Evolution, and multi-start L-BFGS-B on 15 synthetic and 5 engineering benchmarks, using EI over 400 iterations with 10 seeds. The authors report the best final regret on 13 of 20 benchmarks and an average 81.08% improvement over the second-best optimizer on those 13. They add wall-clock analyses, a 1D visualization of the surrogate (Figure 5), and ablations over acquisition function, initial design size, dimension, sampling method, kernel, and ξ.

Critical strengths
  • the problem the paper aims to address is import for all BO algorithms. The experimental scope is broader than most acquisition-optimizer papers, with 20 benchmarks across multimodal, bowl-shaped, steep-drop, and engineering functions. The performance on KSOS on many of them also show promising results.

  • The ablations are useful. Table 6 separates the contribution of KSOS from that of Sobol sampling by showing that KSOS with uniform samples still beats standalone Sobol and uniform search on all five benchmarks. The 50D results in Table 5 are a welcome stress test.

Critical weaknesses
  1. Although the paper provides failure modes in acquisition gaps, e.g., Ackley (0.021 vs. 0.010 and 0.017), Rastrigin (0.018 vs. 0.0092), and Michalewicz (0.068 vs. 0.012 and 0.013), it provides little information about the machenism behind them. Providing richer analysis for those results would help readers understand when KSOS works well, as well as its limitations. I believe these aspects are important for study in acquisition optimization. For example, the acquisition surrogate plots in Fig. 5 would be a helpful reference.

  2. From Fig. 5, acquisition surrogate are accurate with sufficient data points, which are random samples such as sobol. My concern is curse of dimensionality of the search space. What would be the performance like when sample points are insufficient to specify a correct optima position?

  3. Some critical data reporting errors: The Table 3 LCB row for Sobol Search on Rosenbrock (168.88 ± 38.77) is identical to the Table 6 entry for Uniform Search on Rosenbrock. The Table 3 PI row for Sobol Search on Rosenbrock (109.04 ± 6.28) is identical to the Table 8 ξ = 1 entry for Sobol Search on Rosenbrock. Those flags raises reproducibility concerns for the results.

Questions for authors

Same as weakness

1 comment

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.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Discussion (0)

Sign in to comment.