Asynchronous Bayesian optimization is widely used for gradient-free optimization in domains with independent parallel experiments and varying evaluation times. Existing methods posit that standard acquisitions lead to redundant and repeated queries, proposing complex solutions to enforce diversity in queries. Challenging this fundamental premise, we show that methods, like the Upper Confidence Bound, can in fact achieve theoretical guarantees essentially equivalent to those of sequential Thompson sampling. A conceptual analysis of asynchronous Bayesian optimization reveals that existing works neglect intermediate posterior updates, which we find to be generally sufficient to avoid redundant queries. Further investigation shows that by penalizing busy locations, diversity-enforcing methods can over-explore in asynchronous settings, reducing their performance. Our extensive experiments demonstrate that simple standard acquisition functions match or outperform purpose-built asynchronous methods across synthetic and real-world tasks.
Figures & tables
Figure 1: We find that (I.) standard acquisition outperforms or matches purpose-built methods for asynchronous Bayesian optimization. (II.) Comparing the distances of queries to the closest busy location, we see that standard acquisition exhibits the desirable transition from exploration to exploitation, but does not repeat queries. (III.) Standard acquisition functions query at similar distances as their optimally informed sequential counterparts, suggesting that nearby sampling is a desirable feature and should not be prohibited. See Section 2 for a description of the methods and Section 5.2 for a formal definition of the distance Δ . Results are shown on Ackley (d=10,q=8) .
Figure 2: Synchronous vs. asynchronous BO with q=3 workers. The asynchronous BO can run more experiments in the same overall time.
Figure 3: One full asynchronous BO step for the UCB (left), LP-UCB (middle), and the KB-UCB (right). Row 1 corresponds to line 6 in Algorithm 1 , with n0=3 initial samples and q=2 initialized workers, w1 and w2 . In row 2, w2 finishes first, the GP-surrogate is updated with the new sample (green), and the acquisition function is optimized (orange). Notably, all methods query almost the same location, even the standard UCB, which does not take into account the busy locations. See Figure E.1 for subsequent iterations showing a similar trend.
Figure 4: Sample trajectories for the sequential UCB, the asynchronous (standard) UCB, and the purpose-built LP-UCB, with the same initial data. Like sequential UCB, the asynchronous UCB discovers the global optimum (red) within the budget of 15 iterations, despite performing the occasional close query. The penalization -based method LP-UCB over-explores the search space and does not find the optimum within the budget. See Figure E.2 for more runs and different methods.
Figure 5: Top: The average ARD-RBF kernel lengthscale decreases by about two orders of magnitude from initialization to a plateau for standard methods. Non-standard methods do not all reach this plateau. Bottom: The mean absolute difference in subsequent lengthscales drops significantly from initialization to convergence for standard acquisition functions. Several non-standard methods query locations leading to non-converging kernel lengthscales. See Section 4.2 for formal definitions of ℓn and Δℓn .
Figure 6: Standard acquisition dominates on synthetic tasks. This observation is robust to the dimensionality and the number of workers, whereas the performance of the purpose-built methods is always worse and more sensitive to task parameters (see also Figures G.1 and G.2 ).
Figure 7: Standard acquisition performs well on real-world and hyperparameter tuning tasks and benefits more from an increase in the number of workers than purpose built methods. Both rows show the same optimization tasks, but with different numbers of workers, q . From the axes it can be seen how an increase in evaluation resources speeds up the optimization. Importantly, standard acquisition often benefits disproportionately from more workers, compared to existing methods.
Figure 8: Standard acquisition does not systematically repeat queries and performs an exploration-exploitation trade-off similar to that of its optimally informed sequential counterpart. It can be seen that standard acquisition methods do not repeat queries, and that standard acquisitions query at similar distances to previous queries in the asynchronous setting as in the sequential setting.
Appendix figures & tables11 assets
Supplementary material from the paper’s appendix.
Appendix
Figure E.1: Continuation of Figure 3 . It can be seen that the standard UCB queries essentially the same points as purpose-built methods, without taking into account the busy location. The update via the new sample provides sufficient information to prevent redundant or even repeated queries.
Figure E.2: Query trajectories, see Appendix E for a detailed description.
Figure G.1: Standard acquisition functions are not significantly outperformed on any of our synthetic test functions. In fact, for our experiments, UCB often outperforms alternatives designed for asynchronous BO.
Figure G.2: Extended run times show qualitatively the same results.
Figure G.3: Standard acquisition functions query closer to busy locations than alternatives designed for asynchronous BO, but do not systemically repeat queries.
Figure G.4: While standard acquisition queries the closest to busy locations, distances on real-world tasks are significantly larger than zero for all methods.
Figure G.5: Standard acquisition functions mimic the distance profile of their respective sequential counterparts.
LogEI
TS
LP-UCB
LLP-UCB
AEGIS
KB-LogEI
KB-UCB
E-LogEI
UCB
0.85
1.0
0.95
1.0
1.0
0.95
0.75
0.9
LogEI
–
0.9
0.7
0.85
0.6
0.55
0.4
0.4
Appendix
Table G.1: Ackley (d=10,q=8) , win-rate @ t=30 s
LogEI
TS
LP-UCB
LLP-UCB
AEGIS
KB-LogEI
KB-UCB
E-LogEI
UCB
0.75
0.85
0.75
1.0
1.0
0.85
0.55
0.8
LogEI
–
0.6
0.45
0.8
0.6
0.5
0.2
0.4
Appendix
Table G.2: Michalewicz (d=5,q=16) , win-rate @ t=30 s
Modern engineering workflows increasingly rely on massive parallel simulation, driving the need for scalable, large-batch Bayesian Optimization (BO). Existing batch BO methods, however, incur large computational cost or rely on approximations that erode batch diversity. We propose B3O (Boltzmann Batch Bayesian Optimization), a framework that reframes batch generation as a pure sampling problem: drawing samples directly from the Boltzmann distribution defined by the acquisition function avoids the bottlenecks of existing large-batch methods. Theoretically, we prove that queries sampled from this distribution incur only negligible additional regret. Empirically, B3O outperforms existing batch BO methods on standard synthetic benchmarks and adapts robustly across complex applied tasks, including multi-objective electrode design and mixed-variable race car configuration.
Maximilian Bloor, Liyuan Xu, Hrvoje Stojic +1
Imperial College London London, UK · Secondmind Cambridge, UK
Modern distributed optimization methods mostly rely on traditional synchronous approaches, despite substantial recent progress in asynchronous optimization. We revisit Synchronous SGD and its robust variant, called m-Synchronous SGD, which can be interpreted as a method with a backup-worker strategy, and theoretically show that they are nearly optimal in many heterogeneous computation and communication scenarios, which is somewhat unexpected. We analyze the synchronous methods under random times and adversarial partial participation of workers, and prove that their time complexities are optimal in many practical regimes, up to logarithmic factors. While synchronous methods are not universal solutions and there exist tasks where asynchronous methods may be necessary, we show theoretically that they are sufficient for many modern heterogeneous computation and communication scenarios.
Grigory Begunov, Alexander Tyurin
AXXX, Moscow, Russia · Lomonosov Moscow State University, Moscow, Russia
Heavy-tailed stochastic gradient noise, commonly observed in transformer models, can destabilize the optimization process. Recent works mainly focus on developing and understanding approaches to address heavy-tailed noise in the centralized or distributed, synchronous setting, leaving the interactions between such noise and asynchronous optimization underexplored. In this work, we investigate two communication schemes that handle stragglers with asynchronous updates in the presence of heavy-tailed gradient noise. We propose and theoretically analyze algorithmic modifications based on delay-aware learning rate scheduling and delay compensation to enhance the performance of asynchronous algorithms. Our convergence guarantees under heavy-tailed noise match the rate of the synchronous counterparts and improve delay tolerance compared with existing asynchronous approaches. Empirically, our approaches outperform prior synchronous and asynchronous methods in terms of accuracy/runtime trade-offs and are more robust to hyperparameters in both image and language tasks.