- 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 is kept fixed. Also, for a Matérn-5/2 kernel in 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 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 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
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 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 , where 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 , the information-gain is . At , for example, the resulting statistical term in the cumulative-regret bound grows as 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 over 1,000 evaluations (using the same logarithmically schedule from Desautels et al. (2014)). With , the corresponding information-gain bounds are for Matérn-5/2 and 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 , 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 The second term connects to and makes the role of the inner budget 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.
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.
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.
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.
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−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 C bounds the conditional information in the pending observations, the standard deviation before accounting for those locations is at most eC 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.