A Matrix Optimization Perspective on Batch Bayesian Optimization

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.