acceptodds
Under review as a conference paper at ICLR 2027

A Matrix Optimization Perspective on Batch Bayesian Optimization

Abstract

Batch Bayesian optimization (BO) selects candidates with dependent outcomes, motivating coordinated updates in joint acquisition optimization. We study this problem via a matrix representation of the batch, relating posterior dependence to gradient modes that combine candidate movements with input directions. For radial kernels, we characterize single-point EI and chained batch-UCB curvature through a shared metric and rank-bounded corrections. We derive an exact local comparison and a sharp perturbation bound identifying when Muon's normalization of active singular modes improves quadratic gain, motivating Muon-BO. We establish a regret bound for chained batch-UCB with explicit acquisition optimization error, account for clipping in projected Muon updates, and connect inner iterations to regret under additional assumptions. Experiments on GP draws, synthetic benchmarks, and a rover task examine the theory and demonstrate practical benefits.

Primary area:
probabilistic methods (Bayesian methods, variational inference, sampling, UQ, etc.)
Keywords:
Bayesian optimization, batch acquisition optimization, acquisition curvature, Gaussian processes, matrix optimization, Muon

Reviews

Among:
Shape:
1234this paper, Top 15%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 3.00 over 3 reviews, above 85% of the others.
Reviewer_EVJ3OpenReview ↗
Rating
3(+1)
Confidence
3
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper proposes to use apply Muon for acquisition maximization in Batch Bayesian Optimization. The paper derives a regret bound, and demonstrates the efficiency of the proposed method on synthetic and real-world experiments.

Critical strengths

Acquisition function maximization is central in the BO literature, and given the recent impact of Muon on gradient-based optimization, the application of Muon to Batch BO is timely and natural.

The experimental results seem convincing and provide a solid proof that Muon is worth considering for acquisition maximization.

Critical weaknesses

Weaknesses are labelled for future discussion with the authors.

(W1) Implicit Assumptions. The paper sometimes introduces assumptions without explicitly listing them as such. I give two examples below:

  • before (1), the paper enforces an acquisition function to be a differentiable function of the posterior mean vector and the posterior covariance matrix. This is true for many acquisition functions, but not for all of them: as far as I know, qKG or some entropy-based acquisition functions do not have this form,

  • after Theorem 6.1, some PL inequality is assumed without being stated as an assumption.

(W2) Assumption 1. Assumption 1 appears to be central in the proofs and is very similar to a popular, proven property of UCB. I am surprised to see it introduced as an assumption, when the next paragraph seems to state that it is actually implied by former results from the literature.

(W3) Figure 1. I am a bit confused about this figure. I struggle to see how Theorem 4.1 can be illustrated with numerical experiments where βt\beta_t is kept fixed. Also, for a Matérn-5/2 kernel in d≥10d \geq 10 dimensions, the information gain is barely sublinear and would require significantly more observations to make the sublinear regime visible.

(W4) Advantage of Muon. The two propositions in Section 5 introduce a lot of notations and are not easy to parse. Furthermore, as far as I understand them, they are about one-step gains given by the polar update. Then Theorem 6.1 gives a result about the optimality gap, but it lacks a connection with ∑t=1Tεt\sum_{t = 1}^T \varepsilon_t in Theorem 4.1.

(W5) Assumption 2. The restrictiveness of Assumption 2 is unclear to me, and I wonder if classical acquisition functions do verify it.

Questions for authors

Here are some questions to spark the discussion with the authors.

(Q1) Have you tried to prove Assumption 1? Can you clarify if it is actually implied by results from the literature? If that is not the case, what makes it a hard result to prove?

(Q2) What are you illustrating with Figure 1? Is it a valid illustration for Theorem 4.1?

(Q3) What can you say about ∑t=1Tεt\sum_{t = 1}^T \varepsilon_t when using Muon as an optimizer? Is the bound actually sublinear? Otherwise, what are its practical implications?

(Q4) Does Assumption 2 hold for classical EI-based acquisition functions? Regardless of the answer, can you discuss its restrictiveness in the main text?

7 comments
AuthorsOpenReview ↗

Response to Reviewer EVJ3 - part 1

Thank you for recognizing the timeliness of applying Muon to batch BO and the strength of the experiments! Below are our detailed response to each comment.

W1. The paper sometimes introduces assumptions without explicitly listing them as such.

Response. Thank you for pointing this out and for identifying two places where the assumptions were implicit. We have revised our paper to state all assumptions explicitly with a discussion followed, and referred to them where they are used. A quick summary of assumptions we have in the updated paper. Assumption 1 (Section 3) states the condition behind Equation (1): the acquisition is a differentiable function of the proposed batch’s posterior mean vector and covariance matrix and we provide a small discussion on its applicability. Assumptions 2–3 (Sections 4 and 6) state the conditions for the regret and inner-solver results, respectively. Assumptions 4–5 (Appendix A.3) collect the conditions used in the curvature analysis. Assumptions 6–7 (Appendix A.4) clarify the second example you raised. They state the PL and basin assumptions used in Proposition A.10 and Corollary A.11.

Revision location. Revision location. Section 3 before Equation (1), Section 4 before Theorem 4.1, and Section 6 around Theorem 6.1. Appendix A.3 collects the curvature assumptions. Appendices A.4.4 and A.4.6 state the PL and basin assumptions used in Proposition A.10 and Corollary A.11.

W2. Assumption 1 appears to be central in the proofs and is very similar to a popular, proven property of UCB.

Response. Thank you pointing this out. The way to understand this assumption is that the standard GP-UCB confidence band uses the posterior mean and standard deviation based on observations already received. Our bound uses the same posterior mean, but the standard deviation can shrink after we account for pending locations whose outcomes are still unknown. We state this as Assumption 2 (formerly Assumption 1) because our proof of Theorem 4.1 compares possible batches and uses the confidence bound at every candidate location for every collection of up to q−1q-1 pending locations. This condition can follow from the GP-BUCB construction of Desautels et al. (2014) when their confidence and information bounds hold. Their Proposition 1 shows that if CC bounds the conditional information in the pending observations, the standard deviation before accounting for those locations is at most eCe^C times the standard deviation afterward. Their Lemmas 8–9 then show that increasing the confidence parameter preserves coverage. When the sequential band holds for every candidate and the information bound holds uniformly over the possible pending locations, this gives our Assumption 2. We stated this connection after the Assumption and provided detailed discussion in Appendix A.2.2.

Revision location. Section 4, after Assumption 2. Appendix A.2.2 offered the derivation and discussion.

AuthorsOpenReview ↗

Response to Reviewer EVJ3 - part 2

W3. Figure 1 used fixed exploration, and a sublinear trend is difficult to see for a high-dimensional Matérn kernel.

Response. These are good points! Our original purpose in Figure 1 was to examine whether jointly optimizing chained batch-UCB produces cumulative-regret trajectories similar to those of greedy GP-BUCB. We agree that keeping βt\beta_t fixed did not adequately illustrate the Theorem 4.1. In response, we reran the experiment with a logarithmically increasing exploration parameter, following the experimental practice of Desautels et al. (2014). For fixed batch size, this gives βT=O(log⁡N)\beta_T=O(\log N), where NN is the number of evaluations. Our revised figure continues to show similar cumulative-regret trajectories for the joint solvers and matched greedy GP-BUCB. We have also updated the caption and surrounding text to explain the comparison.

We also agree that the sublinear trend is difficult to see over the budgets in Figure 1. For a Matérn-5/2 kernel with dimension dd, the information-gain is γN=O(Nd/(d+5)(log⁡N)5/(d+5))\gamma_N=O\left(N^{d/(d+5)}(\log N)^{5/(d+5)}\right). At d=50d=50, for example, the resulting statistical term in the cumulative-regret bound grows as N21/22N^{21/22} up to logarithmic factors. With an exponent this close to one, and the curve can look nearly linear over the plotted range. To address this concern, we therefore added a new two-dimensional GP-draw experiment with Matérn-5/2 and RBF kernels and plotted both cumulative regret and average regret RN/NR_N/N over 1,000 evaluations (using the same logarithmically schedule from Desautels et al. (2014)). With d=2d =2, the corresponding information-gain bounds are γN=O(N2/7(log⁡N)5/7)\gamma_N=O\left(N^{2/7}(\log N)^{5/7}\right) for Matérn-5/2 and γN=O((log⁡N)3)\gamma_N=O\left((\log N)^3\right) for RBF. In our new Figure 5, average regret decreases for all four joint solvers and greedy GP-BUCB, for both kernels and both batch sizes q=2,4q=2,4, and is consistent with Theorem 4.1 sublinear rate guide.

Revision location. Section 4, Figure 1 and its caption. Appendix B.1 gives the exploration schedule, kernel-specific rates, and Figure 5.

W4. Section 5 introduce a lot of notations and are not easy to parse, and the link from Theorem 6.1 to the acquisition errors is unclear.

Response. Thanks for rasining these points and your understanding for section 5 is correct! Propositions 5.3 and 5.4 both concern the gain from a single step of the acquisition. Proposition 5.3 compares a step along the gradient with a step along its polar direction. The polar direction gives a larger gain when its lower curvature offsets its weaker alignment with the gradient. Proposition 5.4 then tells us how large that advantage must be for the comparison to hold under a given change in the Hessian. To make Section 5 easier to follow, we shortened the theory statements by collecting the kernel and curvature assumptions and moving them to the start of Appendix A.3 (Assumptions 4–5), where we explain how each is used. We also revised the discussion after the propositions to make their implications clearer.

Regarding the connection between Theorems 6.1 and 4.1 for Muon, it was established in Corollary A.11 of the original submission. We now state the resulting bound and explain the connection immediately after Theorem 6.1. Theorem 6.1 bounds the gradient norm attained during the run, then under the local PL inequality and the corollary’s basin and restart conditions, this gradient norm bound is converted into an acquisition value gap. Summing these gaps over rounds and substituting into Theorem 4.1 gives RN≤C1NβTγN+NLUDUμPLTin.R_N \le \sqrt{C_1 N\beta_T\gamma_N}+ \frac{N L_U D_U}{\mu_{\mathrm{PL}}T_{\mathrm{in}}}. The second term connects to ∑t=1Tϵt\sum_{t=1}^T \epsilon_t and makes the role of the inner budget TinT_{\mathrm{in}} explicit.

Revision location. Section 5, after Proposition 5.4, and Section 6, after Theorem 6.1. Appendix A.4.6 gives Corollary A.11 and its proof.

AuthorsOpenReview ↗

Response to Reviewer EVJ3 - part 3

W5. The restrictiveness of Assumption 2 (now Assumption 3) is unclear to me, and I wonder if classical acquisition functions do verify it.

Response. Assumption 3 (formerly Assumption 2) requires the acquisition to have a Lipschitz-continuous gradient on the feasible box. Over a compact feasible box, a continuous Hessian is sufficient for the assumption to hold because its norm is then bounded. For the Matérn-5/2 and RBF kernels used here, classical single-point EI and UCB are twice continuously differentiable whenever the posterior standard deviation is positive (non-zero) throughout the feasible box. For chained batch-UCB, positive observation noise ensures that the conditional standard deviations remain positive even when proposed points coincide. It is therefore also twice continuously differentiable for these smooth kernels. In each case, the Hessian is continuous and hence bounded on the compact box, which gives the required Lipschitz gradient. This assumption is more restrictive for batch EI. Exact qEI can fail to be differentiable when two candidates coincide. BoTorch’s qLogEI smooths the improvement calculation, but its finite-sample gradient also depends on how the posterior samples vary with the candidate locations. We have added a small discussion in the main text after this Assumption.

Revision location. Section 6, after Assumption 3.

Reviewer_G5KSOpenReview ↗
Rating
3(+1)
Confidence
2
Informativeness
2
Presentation
1
Soundness
1
Read review
Paper summary

This paper studies the joint optimization of batch acquisition function in Bayesian optimization. The authors propose Muon, which uses the polar facts update, as the inner solver for the acquisition function optimization. Authors provide theoretical justification for the condition that the polar normalization could improve gradient step locally. Empirical results on synthetic and a real-world problem demonstrate that Muon-BO can lead to lower regret compared with other inner solvers.

Critical strengths

The proposed approach is cheap and simple to implement. Empirical results also show that it can improve the performance of batch BO compared with other inner solvers.

Critical weaknesses

There are two major weaknesses for this work.

The theory does not explain the observed empirical gains

  1. In Proposition 5.3, the authors argue that the polar normalization could improve gradient step locally when S(Q)<rˉS(G)S(Q) < \bar{r} S(G). However, this condition is never checked on the acquisition surfaces for the actual empirical runs.

  2. According to Theorem 4.1, higher acquisition value (for chained batch-UCB) should lead to lower cumulative regret. However, this is not always the case in the paper reported results. All inner optimizers result in similar cumulative regret on the GP draw studies, see Table 1.

  3. The central claim of this paper is that Muon can optimize the joint acquisition function better. However, the acquisition values for Muon and other inner solvers are never reported throughout the empirical studies. Hence, we can't know whether the benefit of Muon on the optimization tasks comes from better acquisiion optimization or other reasons.

  4. The theoretical rank bound proposed in Corollary 5.2 has limiting practicality on real data set, where n$\geq d$ easily holds in experiments.

The affect of gradient scale is not isolated while performing the experiments

Muon's step is independent on the gradient scale. In comparison, the step of the projected gradient highly depends on the gradient scale. Hence, there is a chance that the benefit of Muon comes from the scale invariance alone. The authors should consider projected gradient with normalized step as an additional baseline.

Questions for authors
  1. Can the authors confirm that Muon does lead to higher acquisition values compared with other inner solvers?

  2. Can the authors consider projected gradient descent with normalized step size?

7 comments
AuthorsOpenReview ↗

Response to Reviewer G5KS - part 1

Thank you for highlighting Muon’s simplicity and promising empirical results! Below are our detailed response to each comment.

W1(1). The condition in Proposition 5.3 is never checked on the acquisition surfaces for the actual empirical runs.

Response. Thank you for pointing this out. We agree that, in the original submission, we derived the condition in Proposition 5.3 but did not check how often it holds in the reported runs. In response to this concern, we have added an experiment that checks the condition along Muon trajectories on the noiseless chained batch-UCB benchmarks and Rover. Since the acquisition changes as new observations arrive, we examine an early, middle, and final BO round for each objective. Within an early, middle, and final BO round, we record the fraction of proposed Muon iterates where the gradient is nonzero, both directional curvatures are positive, and S(Q)<rˉS(G)S(Q)<\bar r S(G). At these iterates the local model favors the polar step according to Proposition 5.3. The results also look promising. On Rastrigin at d=100d=100, the shares are 72.0%, 72.2%, and 63.2%, and Muon's simple regret drops sharply early. On Levy at d=20d=20, the share rises from 12.0% to 50.1%. On Rover, it falls from 35.3% to 3.5%, and reward improves fastest early in the run. We also provided a detailed discussion in the Appendix for this condition and results.

Revision location. Section 5, after Proposition 5.4. Appendix B.2, Table 2.

W1(2). Higher acquisition value (for chained batch-UCB) should lead to lower cumulative regret. However, this is not always the case in the paper reported results.

Response. Thank you for raising this point. Here we want to clarify the interpretation of our Theorem 4.1. It gives a high-probability upper bound on how large cumulative regret can be, which bounds the worst-case performance. The bound contains the usual GP-BUCB term plus ∑t=1Tϵt\sum_{t=1}^{T}\epsilon_t. Better acquisition optimization therefore tightens the bound when the other terms are fixed. A tighter upper bound, however, does not imply strictly lower realized cumulative regret or determine how two solvers will rank on a given run. We have added a discussion after Theorem 4.1.

We agree that the cumulative-regret results on the GP draws are similar. However, the purpose of Figure 1 and Table 1 is to examine whether joint batch selection achieves performance comparable to greedy GP-BUCB in a controlled simple setting where the GP hyperparameters are known, instead of demonstrating Muon's superiority. At d=20d=20, for example, Muon and matched greedy GP-BUCB attain mean cumulative regrets of 2,820 and 2,840 and mean final simple regrets of 3.97 and 4.10, respectively. Unlimited greedy achieves the lowest mean cumulative and simple regret at all three dimensions, as expected given its greedy batch selection.

The theorem does give a reason to improve the inner solve in order to lower the cumulative-regret upper bound, and the benchmarks let us examine when higher acquisition values accompany better BO performance. On all three noiseless d=100d=100 benchmarks with chained batch-UCB, Muon attains the highest mean first-round acquisition value among the joint solvers and the lowest mean final simple regret. We discuss these comparisons in our response to W1(3).

Revision location. Section 4, discussion after Theorem 4.1. Appendix B.1, Table 1.

AuthorsOpenReview ↗

Response to Reviewer G5KS - part 2

W1(3). The acquisition values for Muon and other inner solvers are never reported throughout the empirical studies.

Response. Thank you for pointing this out. The original submission did not report the acquisition values attained by the joint solvers. In response to this concern, we added a first-round comparison for noiseless chained batch-UCB and BoTorch qLogEI. For a given seed, all solvers will start from the same observations and optimize the same acquisition in round one. Once they evaluate different batches, their posteriors and acquisition functions can differ. For a fair comparison, we therefore record the first-round acquisition value at Muon’s returned batch minus the value at each competing solver’s batch. We report the mean and standard deviation of these paired differences, where a positive mean favors Muon.

The results also look explanatory. On noiseless Rastrigin at d=100d=100 with chained batch-UCB, Muon’s first-round acquisition value exceeds that of normalized projected GD by 448 on average, and Muon also achieves lower mean final simple regret (900 versus 1,090). As discussed in W1(2), Theorem 4.1 relates acquisition error to an upper bound on cumulative regret, which could potentially explain some aspects of Muon's perfomance here. However, we do point out in our discussion in Appendix that this first-round comparison measures how well the solvers optimize a common acquisition. Since the acqusition itself can differ in the subsequent rounds for different solver, this comparison alone cannot tell us whether better acquisition optimization can fully explain the differences in final simple regret.

Revision location. Appendix B.4.6, discussion accompanying Tables 11–12.

W1(4). Is the rank bound in Corollary 5.2 informative once the number of observations exceeds the dimension?

Response. Thank you for raising this concern. We agree that once n+q−1≥dn+q-1\ge d, the bound min⁡(n+q−1,d)\min(n+q-1,d) allows each residual block to have full rank. We have clarified both this limitation and how the decomposition connects to the one-step gain analysis. Theorem 5.1 identifies the curvature structure for single-point EI, and Corollary 5.2 gives the corresponding structure for chained batch-UCB. Each Hessian block has a term determined by the kernel length scales and a correction whose directions come from differences among the observed and proposed points. These are the same Hessian blocks that enter Proposition 5.3. To compare the two steps, we evaluate their combined curvature along the gradient direction and along the polar direction. What matters for the gain is how strongly the acquisition curves along each of those two directions. They can experience quite different curvature even when the residual blocks have full rank. Thus, the rank bound gives additional information when n+q−1<dn+q-1<d, while the directional comparison remains informative as more observations accumulate.

Revision location. Section 5, discussion after Corollary 5.2.

W2. The affect of gradient scale is not isolated while performing the experiments.

Response. This is a good point. We agree that comparing Muon with ordinary projected GD leaves open how much of the benefit comes from removing the gradient scale. We therefore added normalized projected GD to all synthetic benchmark and Rover comparisons. For a nonzero batch acquisition gradient G\mathbf{G}, the update is X+=ΠΩq(X+ηG∥G∥F),\mathbf{X}^{+} = \Pi_{\Omega^q}\left(\mathbf{X} + \eta\frac{\mathbf{G}}{\lVert\mathbf{G}\rVert_{F}}\right),, where ΠΩq\Pi_{\Omega^q} projects the batch onto the feasible box.

Normalization improves projected GD in some settings but not all. On noiseless Levy at d=10d=10 with chained batch-UCB, it reduces mean final simple regret from 35.1 to 18.1 and also outperforms Muon (20.4). On noiseless Ackley at d=10d=10, ordinary projected GD has lower mean final simple regret than its normalized variant (3.14 versus 3.27). At d=100d=100, Muon achieves lower mean final simple regret than normalized projected GD on all three chained batch-UCB benchmarks, both with and without observation noise.

Proposition 5.3 clarifies what normalization alone can change. Dividing by ∥G∥F\lVert\mathbf{G}\rVert_{F} changes the step length but preserves the gradient direction before projection. Muon also changes the direction by giving relatively more weight to singular directions with smaller nonzero singular values. Even after choosing the best step length along each direction, the polar step can still give a larger gain on the local quadratic model when its lower directional curvature offsets its weaker alignment with the gradient.

Revision location. Sections 7.1–7.2, Figures 3–4, and Appendix B.4.5–B.4.6 (Tables 5–10).

AuthorsOpenReview ↗

Response to Questions

Q1. Does Muon attain higher acquisition values than the other joint solvers?

Response. As discussed in W1(3), we compare the acquisition values attained in the first round, when all solvers optimize the same acquisition for a given seed. With chained batch-UCB, Muon's mean first-round advantage over normalized projected GD is positive on every synthetic benchmark and rounds to zero on Rover. L-BFGS-B often attains higher values at lower dimensions. For qLogEI, Muon's mean differences are 0.04 to 0.36 against normalized projected GD, 0.36 to 2.93 against projected GD, 0.01 to 0.12 against Adam, and remain compariable against L-BFGS-B. We also want to clarify that since L-BFGS-B uses an approximate inverse Hessian to choose its direction, Proposition 5.3 does not directly applicable to it, and its comparison remains empirical here.

Revision location. Appendix B.4.6, Tables 11–12 and the accompanying discussion.

Q2. Can you include projected GD with a normalized step?

Response. Yes, we have included normalized projected GD as an additional comparison method to all synthetic benchmark and Rover experiments.

Revision location. Figures 3–4, Appendix B.4.5–B.4.6 (Tables 5–10).

Reviewer_jt6xOpenReview ↗
Rating
3(+1)
Confidence
3
Informativeness
2
Presentation
2
Soundness
3
Read review
Paper summary

This paper investigates the use of Muon for optimizing acquisition functions in batch Bayesian optimization. It primarily focuses on chained batch upper confidence bound (UCB), while also considering expected improvement (EI). Theoretically, the paper analyzes the curvature structure of these acquisition functions and compares optimally scaled gradient and polar steps on a local quadratic model to characterize when polar updates are beneficial. Furthermore, it establishes a regret bound for chained batch-UCB that explicitly accounts for acquisition optimization error. Experiments on GP draws, synthetic benchmark functions, and a rover trajectory-planning task show promising improvements from Muon-based acquisition optimization, particularly for chained batch-UCB, while the benefits are less consistent for qLogEI.

Critical strengths

S1: The paper adresses an interesting and relevant problem of acquisition function optimization by using Muon optimizer, which has shown success in neural network training. The idea to use it here is an interesting approach.

S2: Theoretical analysis and providing intuition for the mechanism and experimental evaluation with well-structured code and reasonable ablations (e.g. ablation of batch size q in the appendix)

Critical weaknesses

W1: The experimental setup has two main weaknesses: The experiments are mostly noiseless and the algorithm is only investigated in a very isolated setting with a custom numpy implementation, leaving it unclear how the benefit in real-world BO experiments would be. While the GP paths have very small observation noise, all synthetic functions (Ackley, Levy, Rastrigin) and the Rover experiment are evaluated without noise. Especially the improved regret performance results are therefore not fully convincing. Lacking BoTorch baseline: the paper implements and benchmarks in a controlled setting with a custom Numpy/Scipy, however, to see the full potential compared to state of the art libraries baselines from these are missing. A comparison against qLogEI or qLogNoisyEI with the standard settings BoTorch implementation and possible replacing optimize_acqf with the Muon implementation would strengthen the contribution.

W2: The paper uses an existing optimization algorithm applying it to acquisition function optimization in Batch BO. While the theoretical results are interesting and are part of the main contribution, their implications for practical Batch BO are limited. Combined with the not fully convincing experimental evaluation (W1), the contribution might not be sufficient for ICLR.

Questions for authors
  • In the related work, the following paper seems to be missing, how does this relate to the presented approach? Batch Bayesian Optimization via Particle Gradient Flows Enrico Crovini, Simon L. Cotter, Konstantinos Zygalakis, and Andrew B. Duncan SIAM/ASA Journal on Uncertainty Quantification 2026 14:1, 197-220 10.1137/23M1549080

  • For high-dimensional Bayesian optimization the line of Local Bayesian Optimization (i.e., with gradient information) is missing. e.g. Müller, Sarah, Alexander von Rohr, and Sebastian Trimpe. "Local policy search with Bayesian optimization." Advances in Neural Information Processing Systems 34 (2021): 20708-20720.

  • (Minor Comment): Figures: several figures have a gray background, their resolution is low and their font does not match the rest of the paper.

6 comments
AuthorsOpenReview ↗

Response to Reviewer jt6x

Thank you for recognizing the value of the curvature analysis and ablation studies! Below are our detailed response to each comment.

W1. Most experiments are noiseless and use a custom implementation. Does the benefit carry over to noisy observations and BoTorch?

Response. Thank you for suggesting experiments with noisy observations and a BoTorch baseline. We initially used a custom implementation because BoTorch does not provide the specific chained batch-UCB acquisition. In response, we used the qLogEI and qLogNEI acquisition functions from the BoTorch package and applied Muon in place of the usual optimize_acqf optimization step to select the batch. We compared five joint solvers, including BoTorch default multistart L-BFGS-B. Muon attained the lowest mean final simple regret in 7 of 12 synthetic settings with noiseless qLogEI and 8 of 12 with noisy qLogNEI.

We also added noisy chained batch-UCB experiments on all three synthetic benchmarks and Rover. We added Gaussian noise with a standard deviation equal to 5% of the standard deviation of objective values on a fixed reference design and evaluated performance on the underlying objective. Muon attained the lowest mean final simple regret in most synthetic settings at each noise level (0% and 5%). On noisy Rover, projected GD attained the highest mean final reward, while Muon and normalized projected GD had the lowest cumulative regret. Those results demonstrate Muon's performance remains competitive under these additional practical setup.

Revision location. Section 7, opening paragraph. Appendix B.4.1 gives the noise setup, B.4.5 reports Rover (Tables 5–6), and B.4.6 reports the synthetic benchmarks (Tables 7–10).

W2. While the theoretical results are interesting and are part of the main contribution, their implications for practical Batch BO are limited.

Response. Thank you for raising this point. We agree that the original experiments left open how well the findings carry over to noisy observations and widely used BO software.

Our major contribution in this paper is the analysis on when a Muon update can help in batch acquisition optimization. Because the GP posterior couples the proposed points, moving several candidates together can change the acquisition differently from moving each one separately. Writing the batch as a matrix lets us identify these coordinated movements. Muon gives more relative weight to gradient directions with smaller singular values. Proposition 5.3 shows when this helps: after choosing the best step size along each direction, the polar step gives a larger gain on the local quadratic model if its lower curvature offsets its weaker alignment with the gradient. For practical implication, we now check this condition along actual runs. On 100-dimensional Rastrigin, for example, it holds at 63–72% of sampled iterates across the three BO rounds examined.

Our another contributions is Theorem 4.1, which gives the regret bound for approximate joint maximization of chained batch-UCB. It applies to any joint solver and covers noisy observations setup. Its practical implication is that the accuracy of the inner solve matters through the acquisition value of the returned batch, and in each round it adds to the cumulative-regret upper bound.

Finally, we also expanded the experiments to test Muon under noisy observations on the synthetic benchmarks and Rover, and to compare it with other inner solvers using the BoTorch package. These additional results continue supporting Muon's competitive performance across different practical settings.

AuthorsOpenReview ↗

Response to Questions and Minor Comment

Q1. How does the work relate to Crovini et al. (2026), “Batch Bayesian Optimization via Particle Gradient Flows”?

Response. Thank you for pointing us to this work. Crovini et al. reformulate batch selection as optimization over a probability distribution μ\mu on candidate locations. They score μ\mu by the expected qEI of a batch drawn from it and use a particle gradient flow to construct the batch. In our formulation, the optimization variable is the batch matrix X\mathbf{X} itself. We optimize the acquisition directly over the matrix of candidate locations and study how the choice of update interacts with acquisition curvature. We have added this reference to our related work section.

Revision location. Section 2 related work, “Dependent batch utilities and joint optimization.”

Q2. The line of Local Bayesian Optimization using gradient information, e.g. Müller et al. (2021)

Response. Thanks for pointing out the missing line of work on local BO. In local BO, the search focuses on a neighborhood of the current solution. Müller et al. (2021) use this idea for policy optimization. They select nearby policies whose reward evaluations help estimate the gradient of expected reward at the current policy, then use that estimate to update the policy. Our work addresses a complementary question within BO. Given a fitted GP and a batch acquisition function, we study how to move the proposed candidates together to increase the acquisition value. We have added this line of work and the reference to our related work section.

Revision location. Section 2 related work, “High-dimensional BO.”

Minor comment. Several figures have gray backgrounds, low resolution, or inconsistent fonts.

Response. Thanks for pointing that out! We have regenerated all the plots in pdf format with white backgrounds and consistent label fonts throughout.

Revision location. Figures 1–4 in the main text and Figures 5–12 in Appendix B.

Dear Reviewer jt6x,

As we're halfway through the discussion phase, please acknowledge the author's response and consider leaving them a comment on whether it has resolved some or all of your concerns.

Thanks!

Comments on the paper

1 comment
AuthorsOpenReview ↗

Response to all reviewers

We thank all reviewers for their detailed and constructive comments. In response, we have clarified the assumptions and some interpretation of our theoretical results and provided additional experiemnts to demonstrate the theory statement and support the practical performance of Muon Bo. Our main revisions are:

  • Observation noise and BoTorch (Reviewer jt6x). We added experiments with 5% observation noise on Levy, Rastrigin, Ackley, and Rover. We also reran the noiseless qLogEI benchmarks using the BoTorch package and added BoTorch qLogNEI for noisy observations. Muon remains competitive with the other inner solvers across acquisitions, dimensions, and noise levels (Appendix B.4, Tables 5–10).
  • Acquisition values, proposition conditions, and the role of normalization (Reviewer G5KS). We added normalized projected GD, measured how often the curvature condition in Proposition 5.3 holds along Muon trajectories, and compared the acquisition values returned by the solvers on the same first-round acquisition optimization. On all three 100-dimensional noiseless benchmarks with chained batch-UCB, Muon has both the highest mean first-round acquisition value among the joint solvers and the lowest mean final simple regret (Figures 3–4 and Tables 2, 7, and 11–12).
  • Assumptions and regret bound (Reviewer EVJ3). We now state explicitly the assumptions behind the acquisition gradient, curvature, and inner-solver results. Section 4 clarifies how acquisition optimization error enters the regret upper bound, and Section 6 shows how this error depends on Muon’s inner iteration count under the stated basin and restart conditions. Figure 1 now uses a logarithmically increasing exploration parameter, following the experiments of Desautels et al. (2014). A new two-dimensional GP draw experiment with Matérn-5/2 and RBF kernels verifies the sublinear rate of Theorem 4.1 (Appendix B.1, Figure 5).

Major revisions are marked in red in the updated paper. We respond to each concern below.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.