Relaxing the Additivity Constraints in Decentralized No-Regret High-Dimensional Bayesian Optimization
Authors: Anthony Bardou
Patrick Thiran
Thomas Begin
Venue: ICLR 2024 poster (2024)
Keywords: Bayesian Optimization
Online Learning
Black-box Optimization
Primary area: optimization

Abstract: Bayesian Optimization (BO) is typically used to optimize an unknown function $f$ that is noisy and costly to evaluate, by exploiting an acquisition function that must be maximized at each optimization step. Even if provably asymptotically optimal BO algorithms are efficient at optimizing low-dimensional functions, scaling them to high-dimensional spaces remains an open problem, often tackled by assuming an additive structure for $f$. By doing so, BO algorithms typically introduce additional restrictive assumptions on the additive structure that reduce their applicability domain. This paper contains two main contributions: (i) we relax the restrictive assumptions on the additive structure of $f$ without weakening the maximization guarantees of the acquisition function, and (ii) we address the over-exploration problem for decentralized BO algorithms. To these ends, we propose DuMBO, an asymptotically optimal decentralized BO algorithm that achieves very competitive performance against state-of-the-art BO algorithms, especially when the additive structure of $f$ comprises high-dimensional factors.

Published as a conference paper at ICLR 2024
RELAXING THE ADDITIVITY CONSTRAINTS IN DE- CENTRALIZED NO-REGRET
BAYESIAN OPTIMIZATION
Anthony Bardou' Patrick Thiran IC, EPFL Lausanne, Switzerland
Thomas Begin
ENS Lyon, UCBL, CNRS, LIP Lyon, France thomas. bewiassebeinnneneeeeeee fr
(anthony. berr
ABSTRACT
Bayesian Optimization (BO) is typically used to optimize an unknown function f that is noisy and costly evaluate, by exploiting acquisition function that must be maximized at each optimization step. Even if provably asymptotically optimal BO algorithms are efficient optimizing low-dimensional functions, scaling them to high-dimensional spaces remains an open problem, often tackled by assuming an additive structure for f. By doing so, BO algorithms typically introduce addi- tional restrictive assumptions on the additive structure that reduce their applicabil- ity domain. This paper contains two main contributions: (i) we relax the restrictive assumptions on the additive structure of without weakening the maximization guarantees of the acquisition function, and (ii) we address the over-exploration problem for decentralized BO algorithms. To these ends, propose DuMBO, asymptotically optimal decentralized BO algorithm that achieves very competitive performance against state-of-the-at art BO algorithms, especially when the additive structure f comprises high- nigh-dimensional factors.
INTRODUCTION
Many real-world applications involve optimizing an unknown, noisy, costly-to-evaluate objec- tive function f. Examples of such tasks include hyper parameters tuning in deep neural net- works (Bergstra et al., 2013), roboties (Lizotte et al.] (007). networking (Hornby et al.) (2066) and computational biology (González et al. 2014). In such applications, f can be seen as a black box that can only be discovered by successive queries. This prevents the use of traditional first-order approaches to optimize
Bayesian Optimization (BO) has become a highly effective framework for black-box optimization. In general, BO algorithm tackles this problem by modeling f Gaussian process (GP) and by leveraging this model to query f at specific inputs. The challenge of querying f is to trade off exploration (i.e. to adequately query input that improves the quality of the GP regression of f) for exploitation (i.e. to query an input that is thought to be the maximal argument of f). To achieve this trade-off time I, BO algorithm maximizes acquisition function (xx)), built by leveraging the information provided by the GP model, to select a query x'.
Although BO has shown its efficiency optimizing black-box functions, so far has mostly found success with wiw-immeniionll input spaces (Wang et al. (2013). However, real-world applications, such as computer vision, robotics or networking, often involve a nigh--dimensionll objective function f. Scaling BO algorithms to such input spaces remains a great challenge as the cost of finding arg max :Pt grows exponentially with the input space dimension d. A classical way to circumvent that issue is to cap the complexity of the maximization by assuming an additive decomposition of (e.g. see Kandasamy et al. (2015) with a low Maximum Factor Size (MFS), denoted by which is the maximum number of dimensions for a factor of the decomposition. Unfortunately, assuming an additive decomposition with low MFS may lead to the optimization of a coarse approximation of f.
"ome of this work was done while AB ENS Lyon.

---

Published as a conference paper at ICLR 2024
The performance of BO algorithms under the assumption of low MFS has been extensively studied (e.g. see Kandasamy et al. (2013); Hoang et al. (2018); Mutny& & Krause (2018), with Hoang et al. MFS. In this paper,
demonstrate that it is possible to completely relax the low-MFS assumptions that limit the applicability domain of asymp- totically optimal BO algorithms while still providing provable global maximization guarantees on the acquisition function. To illustrate this, we propose DuMBO, decentralized, message-passing, asymptotically optimal BO algorithm able infer complex additive decomposition of f without any assumption regarding its MFS. As far as we know, this is the first BO algorithm to display such desirable property. Additionally, we provide an efficient way to approximate the well-known GP-UCB acquisition function (Srinivas et al., (012)) in a decentralized context. Finally, we evaluate DuMBO and establish its superiority against several state-of-the-an solutions on both synthetic and real-world problems wherein the noisy objective function ʃ may may not be decomposed.
(2018) detailing efforts to relax the assumption
2 BACKGROUND
2.1 STATE OF THE ART
Given a black-box objective function f D C Rdd - R. the goal of a BO algorithm to find x² arg max f(x) using few queries possible. The quality of the optimization is measured with the immediate regret ra f(=") fx("), and the cumulative regret R, Σi= T.s A BO algorithm is said to be asymptotically optimal if lim Re/L O, which implies that the BO algorithm will asymptotically reach x and hence guarantees no-regret performance.
A BO algorithm typically uses a GP to infer a posterior distribution for the value of fxx at any point æ E D and selects, at each time step t, a query x'. The BO algorithm bases its query- ing policy on the maximization of an acquisition function that quantifies the benefits of observing fxx) in terms of exploration and exploitation. Common acquisition functions include probability of improvement (Jones et al. 1998), expected improvement (Mockus) 1994) and upper confidence bound (Auer, (003). Like many other acquisition functions, the latter leads to an asymptotically optimal application to GPs, called GP-UCB (Srinivas et al. (012) and defined as
p (x) = (x(()) + 3 (z).
(1)
It involves an exploitation term (z(x)), which is the posterior mean of the GP input x, and an exploration term of (x)) which is the posterior standard deviation of the GP at input æ. The scalar trade-off in order to guarantee the asymptotic optimality
g1/2 handles the of GP-UCB with high probability.
As stated before, scaling BO algorithms to high-dimensional functions is challenging because of the exponential complexity of the optimization algorithms used to maximize pp.. To tackle this problem, BO algorithms generally fall into one of the two following categories (with the exception of TuRBO proposed by Eriksson et al. (2019), which uses trust regions to maximize f).
Embedding BO algorithms assume that only few dimensions significantly impact f and project the high-dimensional space of f into a low-dimensional one where the optimization is actually performed. REMBO (Wang al. 2016) and ALEBO (Letham al. (2020) use random matrices to embed the high-dimensional space while SAASBO (Eriksson & Jankowiak 2021) uses sparse GPs defined on subspaces and LineBO (Kirschner al. 2019) exploits successive line-searches in random directions. Other approaches such as GomezzBombarrlll et al. (0118); Moriconi et al. (2020) are based, respectively, on Variational Auto-Encoders and on manifold GPs to learn an embedding. Gupta et al. (2020) propose to perform the optimization in two orthogonal subspaces. Finally, some approaches select a subset of dimensions of the input space to project onto. Such recent methods include Dropout (Li et al. 2017) and MCTS-VS (Song et al. 2022).
Decomposing BO algorithms assume an additive structure for f and optimize the factors of the induced decomposition. Classical approaches such as MES (Wang & Jegelka 2017). ADD- GPUCB (Kandasamy et al. 2015) or QFF (Mutny & Krause 2018) assume a decomposition with MFS equal to 1 and orthogonal domains. More recent approaches like DEC-HBO (Hoang et al. 2018) are able to optimize decompositions with larger MFS and shared input components. Still, the MFS of the decomposition must be low to avoid a prohibitive computational complexity. Note that,
2

---

Published as a conference paper at ICLR 2024
Table I:
Comparison of state-of-the-art decomposing BO algorithms with DuMBO relevant cri- teria. Here, π is the number of factors in the decomposition, d the number of dimensions of f, d the MFS of the decomposition, the optimization step. the desired accuracy when maximizing (P and NA constant defined in Appendix E N.. is a constant defined in Hoang et al. (2018).
Solution
Complexity
MFS Assumption
Find arg max Pr
ADD-GPUCB
3 + nt? + n²
d d=1
Yes
QFF
(5 (10g) ()
d=1
Yes
DEC-HBO
Nms nn(t +n)) (dN (dNant3(-1)
Low None
Under assumptions
DuMBO
Yes
under some assumptions on f. these approaches provably asymptotically optimal and subset of them. namely ADD-GPUCB (Kandasamy et al. 2015) and DEC-HBO (Hoang et al. (018)018). can be used in decentralized context. Finally, note that in recent work, (Ziomek & Ammar, 2023) showed that, in an adversarial context, exploiting random decompositions is optimal on average.
2.2 DUMBO (DECENTRALIZE) MESSAGE- MESSAGE-PASSING BAYESIAN OPTIMIZATION AT.GORITHM)
We propose DuMBO, decomposing algorithm that relaxes the low MFS constraint the assumed additive decomposition of f. Table gathers the main differences between DuMBO and state-of- the-art decomposing algorithms. Note that ADD-GPUCB and QFF require the simplest form of additive decompositions (i.e., d = 1). As consequence, when optimizing a complex objective function they often need coarsely approximate it. In return, they are able, each time step f, to query arg max fP,. In contrast, DEC-HBO tolerates more complex decompositions (i.e. with 1), but no longer guaranteed to find the global maximum (ps because it uses max-sum algorithm (Rogers et al. 2011) that requires f to have sparse additive decomposition to converge. Finally, DuMBO the only algorithm that is able to completely relax any assumption on the MFS without weakening the maximization guarantees the acquisition function. This allows DuMBO to be simultaneously asymptotically optimal and able to handle arbitrarily complex decompositions.
The remaining of this article is devoted to formulating the BO problem (Section 3) presenting DuMBO (Section 4. providing theoretical guarantees (Section 5 and comparing its empirical per- formance with state-of-the-art BO algorithms (Section 6).
PROBLEM FORMULATION AND FIRST RESULTS
In this section, introduce the core assumptions about the black-box objective function f to obtain an additive decomposition (Section (.T). J. Next, we exploit these assumptions to derive inference formulas (Section 3.2) and adapt GP-UCB decentralized context (Section 3.3
3.1 CORR ASSUMPTIONS
In order to optimize f in decentralized fashion, make several assumptions. Assumption 3.1. The unknown objective function J can be decomposed into a sum of factor func- tions (f()) veft with compact domains (D(9) sElLop such that D U D)0) and
Any decomposition can be represented by a factor graph where each factor and variable node denote, respectively, one of the n factors of the decomposition and one of the d input components of f. An edge exists between factor node i and a variable node j if and only if f(t) uses 2; as an input component. We use V, [1, n]] and F,.j E [1,d]. to denote respectively the of variable
3

---

Published as a conference paper at ICLR 2024
nodes connected to factor node i and the set of factor nodes connected variable node Please refer to Appendix A for detailed example regarding additive decompositions and factor graphs.
To make predictions about the factor functions without any prior knowledge, need model that maps the previously collected inputs with their noisy outputs. Denoting zy, = (zz))ev, let us introduce the following assumption.
Assumption 3.2. Factor functions f(8 are independent GP (1o 1:00 (mv,, with prior
mean Ho (8) 0 and covariance function k(0)
Since f is a sum of independent GPs, Assumption 3.2 implies that f is also GP (no, k( (()) with prior mean μr0 = 0 and covariance function k(æ, x') E k(()) xv,,)
Finally, ensure the no-regret property of DuMBO (see Section 5). introduce the following assumption each A-6)
Assumption 3.3. For any i E [1,m]. k(0 is an L-Lipschitz twice differentiable function on DD())
Furthermore, it exists H > 0 such that, for any a, x' E D(6) we have
|| (x, x 2')122 S H.
(3)
Note that Assumption 3.3 mild: large class of covariance functions satisfy it, such as the Matérn class (with v 5/2), the squared-exponential function even the rational quadratic function. Please refer to Williams & Rasmussen 2006) for details on these covariance functions.
3.2 INFERENCE FORMULAS
and given the previous input queries (a',.... xx), the vector [(x)) ( ((x)) is Gaussian. Given the t-dimensional vector of noisy outputs y (y).... ......,,)). (14) with yi = f(x') + e and e centered Gaussian variable of variance o², the pos- terior distribution of the factor (x) is also Gaussian. Since f can be decomposed, the posterior (2) mean (i-1(22) (zv,) and variance (oi+1 (æv;) ))² of the factor f(+ at time + 1 can be expressed with the posterior means and covariance functions of the factor functions involved decomposition Z
For any x E
(8)
(2) Proposition 3.4. Let ('411 (av.) and (a (+t (ævv, ))2 be the posterior mean and variance of f(i at input ay respectively. Then, for the decomposition (2
(6)T "4t1(av)) (av.)) = kwv,
(K + 7K+
(4)
(o (zv:)) == (IV,, Rvv.) kev. (K (K+ 021) k
(5)
(1) (1.1 aby [1.e) matrix K (k(2) xx ())M)) and I the
with X vectors kay; t x t identity matrix.
For the sake of generality, Proposition 3.4 only requires an additive decomposition of f. Appendix B describes how such a decomposition can be inferred from data, using the method proposed by Gard ner et al. 2017). Note that Proposition does not assume corresponding additive decomposition of the observed outputs in y. However large class of real-world applications naturally come up with such an additive output decomposition (e.g., network throughput maximization (Bardou & Begin 2022), energy consumption minimization (Bourdeau et al. 2019) or UAVs-related applications (Xic) al. 2018)). As shown by Wang et al. (2020), having access a decomposed output can only improve the predictive performance of the GP surrogate model. Therefore, we derive the inference formulas to handle the case where the output decomposition is known in Appendix C Also, we explore the benefits of having access to the decomposed output of f in Section 6
3.3 PROPOSED ACQUISITION FUNCTION
Having defined a surrogate model for f. we now turn to finding an optimal policy for querying the objective function. In this section, we exploit the decomposition of f and its associated factor graph (see Appendix A to build an acquisition function for our BO algorithm that approximates GP-UCB in decentralized context. Proofs for all the presented results can be found in Appendix D
4

---

Published as a conference paper at ICLR 2024
Recall that GP-UCB is defined by (1) the sum of an exploitation term (c(x) and exploration term (2) weighted by some scalar 31/2 FFinding an additive decomposition for GP-UCB is hard, sum, but not (z)).. To circumvent because Assumption 3.1 allows (x(( be expressed
this caveat, Kandasamy et al. (2015) proposed to apply GP-UCB to each factor of the additive decomposition of f. with PP 14 B. 1/22 /2 (6) Then, they proved that their algorithm ADD- ot
GPUCB offers no-regret performance by taking Σi= Pp: f4: - 3//22 Ei= dy as the acquisition function. Although the exploitation term μr is preserved, the exploration term is now overweighted
since Ei_ ol 2 (o)))
de. To reach better empirical performance, one could look
for tighter additive upper bound of of. This is the purpose of this section.
In a given factor graph, factor node i can access information about another factor node if they share a common variable node j (see Figure 3 in Appendix A We gather all the indices of the factor nodes that share least one variable node with the factor node in M Fj. Then, propose the following approximation for (z)):
(2)
(aV))
Σ AEN,
(6)
On the one hand, this approximation is exact and equal to (x)) for complete factor graph (i.e.,
Vi [1, [W] = n). On the other hand, given a decomposition made only of one-dimensional factors with orthogonal domains (i.e., Vi E [1, [V 1). it boils down to the approximation of
proposed by Kandasamy et al. 2015). that is, Σー ( (avy.). benefit of approximation (6) is to better exploit the structure of the factor graph. Indeed, the following result shows that (6) is Tighter
upper bound of oz(2r) than the one proposed in Kandasamy et (2015).
Theorem 3.5. Let Assumptions 3.7 and 3.2 hold. Then, for any factor graph and any a E D.
(R)
(Ivrr)
2
(x)
(IV)))
22
KEN
From the bounds Theorem 3.5 one can expect the acquisition function
(g(()) (avi)
(x(x) = (x) + +
(8)
REN:
to be less prone over-exploration. Thus, BO algorithm using { behaves more like GP-UCB
than ADD-GPUCB or DEC-HBO. Note that has a natural decomposition Σ ( (xv. with
(of [g
=144 4 (Iv.)) = 54 (Iv.) + 8
+
(9)
(ar)))) Aif W&l1
with c, = EKEN
computed by message- passiggg-paingggggo with the variable nodes in V,.
4 DUMBO
In this section, we describe DuMBO, a BO algorithm that exploits the results from Section 3 to find
arg max E ((()) (avv)). Optimizing (xr( E v (avy) while ensuring the consistency
between shared input components is equivalent to solving the constrained optimization problem
max
(8) Pi
(x())
(1) such that a w avnnv, Vi,j E [1.n]
(1)
(10)
5

---

Published as a conference paper at ICLR 2024
with (()))..)... (x)) being the inputs (whose dimension indices are respectively listed in V/, Vn)) of the factor functions ip:
Pi
To simplify the equality constraints in TTP.
we introduce consensus variable I E D and we
reformulate the optimization problem as
(o)) such that ( = Ty, Vi E [1.
max
(11)
We now turn the problem into an unconstrained optimization problem by considering its aug- mented Lagrangian L
2 A):
C, = Σ Pi (x(0) - (xx)(((())) xv,) 21 (100000 Tv
(12)
with ( column vector of dual variables with [V:] components and hyperparameter 1) > 0,
which can be set dynamically following the procedure detailed in [ooyd et al. (201T).
To maximize (2). we consider the Alternating Direction Method of Multipliers (ADMM), proposed by Gabay & Mercier (1976). ADMM is an iterative method that proposes, at iteration k, to solve sequentially the problems
(1) x
k++ arg max ((x(1)) ... ,0 (x)
Tx Ave)
(11)
1++1 = arg max C(x (1)
(n)
(n-1) (n) Txs Ax) #k+1
k-1
Tg+1 = arg max L(x
(1)
a R+t v. A4)
(13)
k-
AR+1 arg max C(x
(1)
(n) #+11 A).
(14)
Note that c Fh-1 can be found concurrently by each factor node of the factor graph of f.
(1)
(n)
We propose to proceed by gradient ascent (e.g. with ADAM (Kingma & Ba 2015 of
(
-0 (z)
(T) (a. Fv.) " (1(00000 Ty. 112-
(15)
(o(f))) [N
Next, each factor node i sends
(8) #k+1
to its variable nodes in V, Each variable
node j uses the received data to compute 13 and
14h. In fact, if E [L, EjEF, A 0, is
known (see Boyd et al. (201T) that the closed-forms for and (14) are
1g41
( k+ti
(16)
[
jEF,
Ast1
1 + [
(17)
re(t,n]]
(of (of [NT
Finally, each variable node j sends
(0)
( as well as
to its factor
IEF
node e F, This allows each factor node i to update its dual variables (0) as well as the value of term 6; in (

---

Published as a conference paper at ICLR 2024
These results describe fully decentralized message-passingg algorithm, called DuMBO, which can run on the factor graph of f. The detailed algorithm (Algorithm D. as well as a discussion about its time complexity, are provided in Appendix E Since DuMBO relies ADMM to maximize Pt: let us briefty discuss its maximization guarantees. It is well known that ADMM converges to- wards the global maximum of a convex fpt- ADMM has also demonstrated very good performance at optimizing non-convex functions (Liavas & Sidiropoulos 2015 Lai & Osher 2014 Chartrand Wohlberg 2013). This is explained by recent works such as Wang et al. (2019), which extends
the global maximization guarantee of ADMM to the class of restricted prox-regular functions that condition. We demonstrate that the acquisition function fe simul-
satisfy the taneously satisfies these conditions in the next section.
5 ASYMPTOTIC OPTIMALITY
In this section, we demonstrate the asymptotic optimality of DuMBO. First, we prove that, at each iteration, ADMM is always able globally maximize the acquisition function yr with Theorem S.1 Then, we demonstrate that DuMBO has lower immediate regret than another asymptotically op- With these two theorems, we establish the asymptotical
timal BO algorithm with Theorem 5.2
optimality of DuMBO, stated in Corollary 5.3
Let us start with the global maximization guarantee of ADMM, whose proof can be found in Ap- pendix F
Theorem 5.1. Under Assumption 3.3 Vi nI, 4p (see ( is a restricted-prey regular func-
fion. Furthermore, the augmented Lagrangian L.g (see (2)) is Kurdyka-Lojasievwa (KL))
Now that we have the guarantee that Pt is always maximized, we can properly establish the asymptotic optimality DuMBO. We start by providing an upper bound on its immediate regret = =f(x)) - fxx, for a finite, discrete domain D. Its proof can be found in Appendix G
Theorem 5.2. Let rt- = f(x") - fxx) denote the immediate regret of DuMBO. Let 6 E (0,1) and 2())
3e 2 log
Then Vt E N, with probability at least 1 1-6 6,
66
(xrv.) (av,) 0r (k)
Tt S 23
(18)
N2
REN
We demonstrate the asymptotic optimality of DuMBO by piggybacking on the asymptotic optimal- ity of DEC-HBO (Hoang al.) 2018). The latter decomposing BO algorithm with imme-
diate regret bound of 2,3, Σ/
f over a finite, discrete domain (see Theorem in Hoang
al. (018)). Interestingly, Theorem 3.5 directly implies that the immediate regret bound (18)
lower than the immediate regret bound of DEC-HBO. As consequence, the immediate regret of DuMBO bounded from above by the regret bound of DEC-HBO. This allows us rely on proofs in Hoang et al. (2018) to establish some properties of DuMBO. In particular, DEC-HBO is prov- ably asymptotically optimal whether the domain D is discrete or continuous (see Theorems and in Hoang et al. (2018)). These results rely on their immediate regret bound over a finite, discrete domain. Hence, they directly apply to DuMBO as well and yield the following corollary.
Corollary 5.3. Let ō E 10 and R4 = =ie= Tl denote the cumulative regret of DuMBO. Then, with probability least 1 - 6, there exists a monotonically increasing sequence {Br}, such that 3e E (log t) and lim Re/t 0.
6 PERFORMANCE EXPERIMENTS
In this section, we detail the experiments carried out to evaluate the empirical performance of DuMBO. An open-source implementation of DuMBO, based BoTorch (Balandat al. (020), is available on GitHut
https://gi thtp:///gtttuuooooo httom//barroo/dmmaaaa

---

Published as a conference paper at ICLR 2024
Table 2: Comparison of eight state-of-the-art solutions against different versions of DuMBO synthetic and real-world problems. Decomposing BO algorithms can be identified with the prefix "(+)". The reported metries are the minimal regret attained for the synthetic functions, and the average negative reward for the real-world problems. The significantly best performance metrics among all the strategies are written bold text, and the significantly best among the strategies that
do not have access to the additive decomposition are underlined.
Synthetic Functions
Real-World Problems (d-d)
Algorithm
(d-d)
SHC (2-2)
Hartmann (6-6)
Powell (24-4)
Rastrigin (100-5)
Cosmo (9-)
WLAN
Rover (60-)
Unknown Add. Dec.
(12-6)
SAASBO
0.013
0.89
3,901
1,073
16.55
116.40
10.82
TuRBO
0.322
1.89
667
1,109
5.82
-118.39
7.01
LineBO
0.016
0.69
4,830
1,388
5.90
-118.68
8.24
MS-UCB
0.012
0.80
22,271
1,455
5.87
111.995
7.65
(+) ADD-GPUCE
0.102
1.29
11,760
N/A
7.46
-119.05
26.57
(+) DEC-HBO
0.005
1.47
7,937
N/A
14.90
-116.58
10.07
(+) DuMBO
0.006
0.54
496
986
5,86
-120.67
6.38
Known Add. Dec.
(+) ADD-DuMMBO 0.009
0.53
469
678
N/A
-121.11
N/A
Our benchmark comprises four synthetic functions and three real-world experiments. We consider two state-of-the-ar art decomposing BO algorithms: ADD-GGUCB (Kandasamy et al. 2013) that as- sumes d and DEC-HBO (Hoang al. 2018) for which, similarly to its authors in their pirical evaluation, we assume d < 3. We also consider four state-of-the-at BO algorithms that do assume an additive decomposition of the objective functioo: TuRBO (Eriksson al. 2019), SAASBO (Eriksson & Jankowiak] (021), LineBO (Kirschner et al. 2019) and MS-UCB (Gupta al., 2020) with its hyperparamettr
We compare these eight algorithms with two versions of the proposed algorithm: DuMBO that must systematically infer an additive decomposition of (see Appendix B) and ADD-DuMBO that, conversely, can observe the true decomposition of it exists (see Appendix C. Finally, note that we chose Matérn kernel (with its hyperparameter v = 5/2) for each GP involved these experiments.
Since BO is often used in the optimization of expensive black-box functions, the ability of each algorithm at obtaining good performance to strengthen results, each experiment is replicated 5 independent times. Table 2 gathers the averaged results that were obtained. Additionally, we made wall-clock time measurements on some experiments and discuss them in Appendix
interested in small number of iterations. Also,
6.1 OPTIMIZING SYNTHETIC FUNCTIONS
In this section, we compare the six BO algorithms mentioned above using four synthetic functions: the 2d Six-Hump Camel (SHC), the 6d Hartmann, the 24d Powell and the 100d Rastrigin. A de- tailed description of the synthetic functions, as well as the complete set of figures depicting the performance of the BO algorithms can be found in Appendix H
Figure ((a) reports the minimal regrets of the algorithms on the Powell function, where d = 24 and the MFS d 4. Observe that the two decomposing algorithms, ADD-GPUCB and DEC-HBO, obtain the worst minimal regrets. This is because they infer an additive decomposition of based on an assumption on the MFS, that is d not make any restrictive assumption on d, manages to rapidly achieve a low regret by inferring an efficient additive decomposition
when actually d 4. Conversely, DuMBO, which does
f. DuMBO also outperforms SAASBO, TuRBO, LineBO and MS-UCB. Finally, Figure ((a) shows that, when given access to the true additive decomposition of f. ADD-DuMBO achieves its lowest regret in a lower number of iterations. Similar results were obtained with the optimization of other synthetic functions (see Appendix H.. Finally, note that among all the BO algorithms tested the experiments, the two versions of DuMBO are the only ones able properly infer and/or exploit the additive decomposition of given its large MFS.
8

---

Published as a conference paper at ICLR 2024
Powell (d=24.
MFS-6)
(d-60)
S43580
120 GPUCO
110.00
SANSID
KGD GPUCR DEC HEO
Tunoo
DEC-H00
TUABO
targntee (imeent
Meirn
220 7UMAO
VI-117
-11..0
1of-
SAASBO
ADD GRUCS D.MD3
Repret
Linelo
115.0
167
-1175
-125.0
200
60
100
40 80
100
Optimizztion step
Optimization step
Optimization stepl
(a)
(c)
Figure 1: Performance achieved by the BO algorithms listed in Section 6 for (a) the 24d Powell synthetic function, (b) the optimization of the Shannon capacity in a WLAN and (c) the trajectory planning of rover. The shaded areas indicate the standard error intervals.
6.2 SOLVING REAL-WORLD PROBLEMS
We consider three real-world problems: (a) fine-tuning some cosmological constants maximize the likelihood of observed astronomical data (Cosmo), (b) controlling the power of devices a Wireless Local Area Network (WLAN) maximize its Shannon capacity (Kemperman) 1974) and (c) the trajectory planning of a rover (Rover). The problems, along with a complete set of figures depicting the performance the tested BO algorithms, are discussed in details in Appendix
Figures l(b) and [[c] depict the performance of the BO algorithms on problems (b) and (c), where 12 and 60, respectively. Figure [(b) shows that DuMBO is able significantly outperform every other state-of-the-aa BO algorithm. Additionally, and similarly to what was observed with Figure [(a] Figure [(b) suggests that having access, and being able handle additive decomposi- tions with large MFS. is significant advantage. As matter of fact, this allows to outperform BO algorithms that are unable to exploit this additional information. Figure exhibiiss patterns sim- ilar to Figure I(a): ADD-GPUCB and DEC-HBO fail to infer an adequate additive decomposition because of their restrictive MFS assumptions. In contrast, DuMBO, which does not make such an assumption on the size of the MFS, achieves the best performance along with TuRBO. Note that ADD-DuMBO not evaluated on problem (c) since its objective function is not additive.
7 CONCLUSION
In this article, we showed that it is possible to completely relax the restrictive assumptions of low- MFS in the additive decomposition of without weakening the asymptotic optimality guarantees of decomposing BO algorithms. This allows BO algorithms to simultaneously keep their no-regret property and infer complex additive decomposition of the objective function f. or directly ex- ploit it when it is available. To illustrate the effectiveness of such design choices, we proposed DuMBO, an asymptotically optimal decentralized BO algorithm that optimizes f using a tighter decentralized approximation of GP-UCB that requires less exploration than the previously proposed approximations, As demonstrated by Sections 5 and 6, DuMBO a no-regret, competitive alter- native to state-of-the-art BO algorithms, able to optimize complex objective functions in small number of iterations. Compared to other decomposing algorithms, such as ADD-GPUCB and DEC- HBO, DuMBO brings significant improvement, particularly when the decomposition of f has large MFS with numerous factors.
For future work, plan to extend DuMBO to batch mode (Li al. 2016 Daxberger & Low
2017 and to apply it to suitable technological contexts such as computer networks (Bardou & Begin 2022
UAVs (Xie et al. 2018) within a robots team (Chen et al. 2013)
ACKNOWLEDGMENNTS
This work supported in part by the LABEX MILYON (ANR-10-LABX-00)) of Université de Lyon, within the program "Investissements d' Avvnnr"" (ANR-II-IDEX. 0007) operated by the French National Research Agency (ANR).

---

Published as a conference paper at ICLR 2024
REFERENCES
Hédy Attouch, Jérôme Bolte, Patrick Redont, and Antoine Soubeyran. Proximal alternating mini- mization and projection methods for nonconvex problems: An approach based on the kurdyka- lojasiewicz inequality. Mathematics of operations research, 35(2):438 457, 2010.
Peter Auer. Using confidence bounds for exploitation-exxlorraion trade-offs. J. Mach. Learn. Res., 3:397-422, mar 2003. ISSN 1532-4435.
Maximilian Balandat, Brian Karrer, Daniel R. Jiang, Samuel Daulton, Benjamin Letham, An- drew Gordon Wilson, and Eytan Bakshy. BoTorch: A Framework for Efficient Monte-Carlo Bayesian Optimization. In Advances in Neural Information Processing Systems 33, 2020. URL.
http://arxiv/ owg.o//g///o... abs 11111191000060 .6403
Anthony Bardou and Thomas Begin. Inspire: Distributed bayesian optimization for improving spa- tial reuse in dense wlans. In Proceedings of the 25th International ACM Conference on Modeling Analysis and Simulation of Wireless and Mobile Systems, pp. 133-142, 2022.
James Bergstra, Daniel Yamins, and David Cox. Making a science of model search: Hyperparameter optimization in hundreds of dimensions for vision architectures. In International conference on machine learning, pp. 115-123. PMLR, 2013.
Mathieu Bourdeau, Xiao qiang Zhai, Elyes Nefzaoui, Xiaofeng Guo, and Patrice Chatellier. Mod- cling and forecasting building energy consumption: A review of data-driven techniques. Sustain- able Cities and Sociery, 48: 10153,, 2019.
Stephen Boyd, Neal Parikh, Eric Chu, Borja Peleato, and Jonathan Eckstein. Distributed Optimiza- fion and Statistical Learning via the Alternating Direction Method of Multipliers. Now Founda- tions and Trends, 2011.
Rick Chartrand and Brendt Wohlberg. A nonconvex admm algorithm for group sparsity with sparse groups. In 2013 IEEE international conference on acoustics, speech and signal processing, pp- 6009-60133 IEEE, 2013.
Jie Chen, Kian Hsiang Low, and Colin Keng- Tan. Gaussian process-based decentralized data fusion and active sensing for mobility-on-demand system. arXiv preprint arXiv: 1306. 1491, 2013.
C.-H. Chuang. F. Prada, A. J. Cuesta, D. J. Eisenstein, E. Kazin, N. Padmanabhan, A. G. Sanchez, X. Xu, F. Beutler, M. Manera, D. J. Schlegel, D. Schneider, D. H. Weinberg, J. Brinkmann, J. R. Brownstein, and D. Thomas. The clustering of galaxies in the SDSS-III III baryon oscillation spectroscopic survey: single-prohs measurements and the strong power of f(z) 8(z) on constrain- ing dark energy. Monthly Notices of the Royal Astronomical Society, 433(4):555- 3571, jul 2013. doi: 10. 10.1099/mrra//stt988.. URL htRttstps:/ http://///.....11111111001330010 wttpb/............00000aaaaaaaa.
Erik A. Daxberger and Bryan Kian Hsiang Low. Distributed batch Gaussian process optimization. In Proceedings of the 34th International Conference on Machine Learning, volume 70 of Pro- ceedings of Machine Learning Research, pp. 951-960. PMLR, 06-11 Aug 2017.
Nicolas Durrande, David Ginsbourger, and Olivier Roustant. Additive covariance kernels for high- dimensional gaussian process modeling- In Annales de la Faculté des sciences de Toulouse: Mathématiques, volume 21, pp. 481-499, 2012.
David K Duvenaud, Hannes Nickisch, and Carl Rasmussen. Additive gaussian processes. Advances in neural information processing systems, 24, 2011.
David Eriksson and Martin Jankowiak. High-dimensional Bayesian optimization with sparse axis- aligned subspaces. In Proceedings of the Thirty-Seventh Conference on Uncertainty in Artificial Intelligence, volume 161 of Proceedings of Machine Learning Research, pp. 493-503. PMLR, 27-30 Jul 2021.
David Eriksson. Michael Pearce, Jacob Gardner, Ryan D Turner, and Matthias Poloczek. Scalable global optimization via local bayesian optimization. In Advances in Neural Information Process- ing Systems, volume 32, Curran Associates, Inc., 2019.
10

---

Published as a conference paper at ICLR 2024
Daniel Gabay and Bertrand Mercier. A dual algorithm for the solution of nonlinear variational problems via finite element approximation. Computers & Mathematics with Applications, 2(1): 17-40, 1976. ISSN
doi: https:/dtb.orr///00106669999 (2200980822217)00003------
Jacob Gardner, Chuan Guo, Kilian Weinberger, Roman Garnett, and Roger Grosse. Discovering and exploiting additive structure for bayesian optimization. In Artificial Intelligence and Statistics, pp- 1311-1319. PMLR, 2017.
Rafael
Jennifer Wei, David Duvenaud, José Miguel Hernández-Lobate Benjamín Sanchez--Lnnellngg Dennis Sheberla, Jorge Sauulera-Iparraguiin Timothy D Hirzel, Ryan P Adams, and Alán Aspuru-Guzik, Automatic chemical design using data-driven contin- representation of molecules. ACS central science, 4(2):268-276. 2018.
Javier González, Joseph Longworth, David C. James, and Neil Lawrence. Bayesian optimization for synthetic gene design. In NIPS Workshop on Bayesian Optimization in Academia and Industry, 2014.
Sunil Gupta, Santu Rana, Svetha Venkatesh, et al. Trading convergence rate with computational budget in high dimensional bayesian optimization. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 34, pp. 2425-2432, 2020.
Trong Nghia Hoang, Quang Minh Hoang, Ruofei Ouyang, and Kian Hsiang Low. Decentralized high-dimensional bayesian optimization with factor graphs. In Proceedings of the Thirty-Secome AAAI Conference Artificial Intelligence and Thirtieth Innovative Applications of Artificial In- telligence Conference and Eighth AAAI Symposium on Educational Advances in Artificial Intelli- gence, AAAI 18/IAAI 18/EAAI 18. AAAI Press, 2018. ISBN 978-1-57735-800-8
Gregory Hornby, Al Globus, Derek Linden, and Jason Lohn. Automated antenna design with evolutionary algorithms. In American Institute of Aeronautics and Astronautics, 2006. doi: 10.2514/6. 201144/66.00-222 7242.
Donald R. Jones, Matthias Schonlau, and William Welch. Efficient global optimization of expen- sive black-box functions. Journal of Global optimization, 13(4):455 492, 1998.
Kirthevasan Kandasamy, Jeff Schneider, and Barnabas Poczos. High dimensional bayesian optimi- sation and bandits via additive models. In Proceedings of the 32nd International Conference on Machine Learning, volume 37 of Proceedings of Machine Learning Research, pp. 295-304, Lille, France, 07-09 Jul 2015. PMLR.
JHB Kemperman. On the shannon capacity of arbitrary channel. In Indagationes Mathematicae (Proceedings), volume 77, pp. 101-115. North-Holland, 1974.
Diederik P. Kingma and Jimmy Ba. Adam: A method for stochastic optimization. In 3rd Inter- national Conference on Learning Representations, ICLR 2015, San Diego, CA, USA, May 7-9, 2015, Conference Track Proceedings, 2015.
Johannes Kirschner, Mojmir Mutny, Nicole Hiller, Rasmus Ischebeck, and Andreas Krause. Adap- tive and safe bayesian optimization in high dimensions via oin-dimensional subspaces. In Inter- national Conference Machine Learning, pp. 3429-34233 3438. PMLR, 2019.
Krzysztof Kurdyka. On gradients of functions definable o-minimal structures. In Annales de l'institut Fourier, volume 48, pp. 769-783, 1998.
Rongjie Lai and Stanley Osher. A splitting method for orthogonality constrained problems. Journal of Scientific Computing, 58(2):431 -449, 2014.
Ben Letham, Roberto Calandra, Akshara Rai, and Eytan Bakshy. Re-examining linear embeddings for high-dimensional bayesian optimization. Advances in neural information processing systems, 33:1546-1555 2020.
Cheng Li, Paul Resnick, and Qiaozhu Mei. Multiple queries as bandit arms. In Proceedings of the 25th ACM International on Conference on Information and Knowledge Management, pp. 1089- 1098, 2016.
11

---

Published as a conference paper at ICLR 2024
Cheng Li, Sunil Gupta, Santu Rana, Vu Nguyen, Svetha Venkatesh, and Alistair Shilton. High dimensional bayesian optimization using dropout. In Proceedings of the Twenty-Siee Inter- national Joint Conference Artificial Intelligence. IJCAI-17, pp. 2096-2102, 2017. doi:
10.24963/jjcai.200 2017/291.
Athanasios P Liavas and Nicholas D Sidiropoulos. Parallel algorithms for constrained tensor factor- ization via alternating direction method of multipliers. IEEE Transactions on Signal Processing, (3(20)55450-5466 2015.
Daniel Lizotte, Tao Wang. Michael Bowling, and Dale Schuurmans. Automatic gait optimization with gaussian process regression. In Proceedings of the 20th International Joint Conference Artifical Intelligence, IJCAI'07, pp. 944-949, San Francisco, CA, USA, 2007. Morgan Kaufmann Publishers Inc.
Xiaoyu Lu, Alexis Boukouvalas, and James Hensman. Additive gaussian processes revisited. In International Conference Machine Learning, pp.
PMLR, 2022.
Jonas Mockus. Application of bayesian approach to numerical methods of global and stochastic optimization. Journal of Global Optimization, 4:347-365, 1994.
Riccardo Moriconi, Mare Peter Deisenroth, and KS Sesh Kumar. High-dimensional bayesian opti- 2020.
mization using low-dimensional feature spaces. Machine Learning,
Mojmir Mutny and Andreas Krause.
Efficient high dimensional bayesian optimization with addi- tivity and quadrature fourier features. In Advances in Neural Information Processing Systems, volume 31. Curran Associates, Inc., 2018.
Christian Robert, George Casella, Christian P Robert, and George Casella. Metropolis hasttigss algorithms. Introducing Monte Carlo Methods with R. pp. 167-197, 2010.
Alex Rogers, Alessandro Farinelli, Ruben Stranders, and Nicholas R Jennings. Bounded approxi- mate decentralised coordination via the max-sum algorithm. Artificial Intelligence, 175(2):730- 759, 2011.
Lei Song, Ke Xue, Xiaobin Huang, and Chao Qian. Monte carlo tree search based variable selce- tion for high dimensional bayesian optimization. In Advances in Neural Information Processing Systems, 2022.
Niranjan Srinivas, Andreas Krause, Sham M. Kakade, and Matthias W. Seeger. Information- theoretic regret bounds for gaussian process optimization the bandit setting. IEEE Transactions Information Theory, 58(5):3250-322) 2012. doi:
The ns3 Project. The Network Simulator ns-3. 09-30.
www.:/wwww.n...mmomm.m..am. org/
Accessed: 2021-
Kai Wang, Bryan Wilder, Sze-chuan Suen, Bistra Dilkina, and Milind Tambe. Improving gp-ucb algorithm by harnessing decomposed feedback. In Machine Learning and Knowledge Discovery in Databases, pp. 555-569, Cham, 2020. Springer International Publishing. ISBN 978-3-030- 43823-4.
Yu Wang, Wotao Yin, and Jinshan Zeng. Global convergence admm in nonconvex nons- mooth optimization. J. Sei. Comput., 78(1):29 63, jan 2019. ISSN 0885-7474. doi: 10.1007/ s10915-018-0757-2z
Zi Wang and Stefanie Jegelka. Max-value entropy search for efficient Bayesian optimization. In Pro- ceedings of the 34th International Conference on Machine Learning, volume 70 of Proceedings of Machine Learning Research, pp. 3627-3635. PMLR, 06-11 Aug 2017.
Zi Wang, Chengtao Li, Stefanie Jegelka, and Pushmeet Kohli. Batched high sigh-dimensional Bayesian optimization via structural kernel learning. In Proceedings of the 34th International Conference on Machine Learning, volume 70 Proceedings of Machine Learning Research, pp. 3656-3664. PMLR, 06-11 Aug 2017.
12

---

Published as a conference paper at ICLR 2024
Zi Wang, Clement Gehring, Pushmeet Kohli, and Stefanie Jegelka. Batched large-scale bayesian optimization in high-dimensional spaces. In International Conference on Artificial Intelligence and Statistics, pp. 745-754. PMLR, 2018.
Ziyu Wang, Frank Hutter, Masrour Zoghi, David Matheson, and Nando de Freitas. Bayesian opti- mization in high-dimensions via random embeddings. In Proceedings of the Twenty-Thire Inter- national Joint Conference on Artificial Intelligence, 2013.
Ziyu Wang, Frank Hutter, Masrour Zoghi, David Matheson, and Nando De Feitas. Bayesian op- timization in billion dimensions via random embeddings. Journal of Artificial Intelligence Research, 55:361-387, 2016.
Christopher KI Williams and Carl Edward Rasmussen. Gaussian processes for machine learning. volume 2. MIT press Cambridge, MA, 2006.
Lifeng Xie, Jie Xu, and Rui Zhang. Throughput maximization for uav-enabled wireless powered communication networks. IEEE Internet of Things Journal, 612):1690-1703,, 2018.
Yuege Xie, Xiaoxia Wu, and Rachel Ward. Linear convergence of adaptive stochastic gradient de- scent. International conference on artificial intelligence and statistics, pp. 1475-1485, PMLR, 2020.
Juliusz Krzysztof Ziomek and Haitham Bou Ammar. Are random decompositions all need in high dimensional bayesian optimisation? In International Conference on Machine Learning, pp- 43347-43368. PMLR, 2023.
Zuntz, M. Paterno, Jennings, D. Rudd, A. Manzotti, Dodelson, S. Bridle, S. Sehrish, and J. Kowalkowski. CosmoSIS: Modular cosmological parameter estimation. Astronomy and Com- puting, 12:45-59 sep 2015. doi: 10. 1016//0assc.m....2. 5.005.005. URL (tI.tttss// :/tt:///d/// //w..//o...../// .org/ 10. 1 01 6 ascom 2015.0 05.005
13

---

Published as a conference paper at ICLR 2024
A FACTOR GRAPH
In this appendix, we provide an example of an additive decomposition and its associated factor graph. Consider the following additive decomposition
f(x) = (x1, x.) + ( (x2) + f( (xz, va) + f1 (21,
(19)
21
(3)
(3)
233
[9
The factor graph of the decomposition 19 The factor nodes and variable nodes are depicted with squares and circles, respectively. In this decomposition, there are n factors and d = 3 variables.
Figure 2:
The associated factor graph is shown in Figure 2 Observe for instance that, since the first factor fi exploits the first and third components of the input æ, the first factor node is connected to the first and third variable nodes æi and 33.
Using this graph, is very easy build V; (1 S i S n), the of variable indices associated with a factor i. In fact, V; comprises the indices of the variable nodes connected to the factor node i. As an example, Vi = (1,3). Similarly, it is trivial build F, associated with a variable j. In fact, F, comprises the indices of the factor nodes connected to the variable node j. As an example, F3 (1.3, 4} since factors fI, fs and fa exploit 13-
I d), the of factor indices
Receive (ol))
Send (o(1)
F(L)
(00)
F())
2 Receive
(dlu)² (ofo)²
Send back
Send (o())
f(2)
Receive
(0 (O(3)
f(())
Receive
202
Receive (000)² (ors)²
(11)
(o00)
Send back
(o(3)
y(8)
((3)
(o(0)* (or0)2
2a Receive
(ol0))
(am0) (o)0)
Receive
43
Send
back
Send (o(0)
f(()
F())
of0
Figure 3: Message passing the factor graph. (Left) The factor nodes compute their variance terms and send them to their variable nodes. Thus, each variable node receives the variance terms of the factor nodes in Fj. (Right) The variable nodes send all the collected variance terms to each of their factor nodes. Thus, each factor node receives the variance terms of the factor nodes in Ar = F
In Section 3.3 introduce
for factor node i, denoted by Nr, which is the set of indices of the factors that share at least one component æ with the ith factor. AG can be easily built from the quantities (Vi)ee and {Fj}ye(n.a as Mr Fy. Note that, by construction, i Ag. Using the factor graph in Figure 2 as an example, we can see that N₁ = (2,3.4) In practice, the sets (Ne)ee) can be computed with message-pasinng, illustrated Figure
14

---

Published as a conference paper at ICLR 2024
B INFERENCE OF THE ADDITIVE DECOMPOSITION
Our decentralized algorithm requires an additive decomposition of the objective function f. spec- ified in Assumption 3.1 and exploited in Proposition 3.4 the decomposition is known, it can be directly specified to DuMBO. If the decomposition is unknown, it can be inferred from the data (Gardner et al. 2017 Wang et al. 2017, Lu et al. 2022: Durrande et al., 2012). Also note that in recent work, Ziomek Ammar (2023) showed that, an adversarial context, using ran- dom decompositions is optimal on average. Since adversarial contexts are not the primary focus of this paper, we consider the approach introduced by (Gardner et al. 2017), and we briefly discuss in the following.
As in Hoang et al. (2018), , let us associate each candidate additive decomposition A with the kernel of an additive GP (Duvenaud et al. 2011). Given & candidates ...... Ar. we reformulate the acquisition function yfr as weighted average with respect to the posterior of each candidate given the dataset S = {(024 (1)),,))) composed of the selected input queries and their observed noisy outputs, that is
(x) = Σ
((A,(S)
(20)
1=1
14.1 ((A
Σ
1 (av,)
(21)
i=1
j=1
|A.
21 (wry,),
(22)
1=1
with vo,4, our proposed acquisition function given the additive decomposition A; and (p given by (9. Moreover, note that (2T) follows from (20) since the additive decomposition A; also pro- vides additive decomposition of our proposed acquisition function, and (22) follows from (2] as proposed by Gardner et al. (017))
The candidates .,.... AA NettoopolisHHasting algorithm (Robert et al. 2010), starting from the fully dependent decompo- sition Ao = {[1, ,d}} at tt O. When the decomposition is unknown, each time step k promising decompositions are sampled by MCMC starting from the last sampled decomposition at time step 1, and 22) is maximized by decentralized algorithm to find promising input æ to query.
are sampled by Monte-Carlo Markov Chain (MCMC) with the
C INFERENCE FORMULAS WITH DECOMPOSED OUTPUT
The decentralized algorithm DuMBO requires an additive decomposition of the objective function f, but does not assume that the corresponding decomposition of the output observable. Nevertheless, as demonstrated by Wang et al. (2020), having access to such decomposed output improves the regression capabilities of the surrogate GP model, mostly by reducing the variance of its predictions. In this appendix, we derive the counterparts of the posterior mean 4 and the posterior variance (5) when the output decomposition of f is observable.
Observing the output decomposition of f means that f is now function Rd + R". where is the number of factors in its additive decomposition. At time t, a BO algorithm has access to a t x n matrix Y instead of t-dimensional output vector y, such that Y1 y. where 1 is the n-dimensional all-1 vector.
Having access to the matrix Y allows to train different GPs instead of a single one with an additive kernel, so that the ith GP (0, fe(() (æv,, *(y)) serves surrogate model only for the ith factor of
the decomposition of f. To condition the ith GP, we consider the data set S; = = {{( ( V.:) Jee (6) )2 are simple
Given S,, the expressions of the posterior mean M141 and the posterior variance
(o+1))
15

---

Published as a conference paper at ICLR 2024
instances of the conditioned Gaussian distribution formulas, where ( (K() + =o²1) Y.:
Kev,
(23)
(o ( 1:( (æv; vv;) 1()TT (K() + 1) 1
(24)
with Yu the ith column of Y, L. x 1 vectors kany = (2V, x )) x matrices (()) (1:0 b. [EEA) and I the identity matrix.
Equations 23 and (2 differ from 4 and (5) mainly by their ability to exploit the inverse of the Gram matrix built only from the ith covariance function k(0), and course, the outputs of the ith factor of the decomposition Y...
D PROPOSED ACQUISITION FUNCTION
In this appendix, we prove Theorem 3.5 Let us start by the following lemma. Lemma D.1. For all factor graphs and for all a E D
0 (k)
(IVr)) )
n1
o (Iv)).
(25)
12
AEA
Proof.
(1) (av)) ))
(avxa)
of (Iv))
(k)
Σ
(26)
Wal2
Welll
kEN;
kEN;
(av))
(27)
W
1=1
kEN.
= Σ (Iv.).
1=1
Equation 26 comes from simple application of the triangle incquality with the euclidean norm.
(av,)
Equation 27 follows by construction of each Mr. as the term
[Wal appears exactly [& times
within the double sum of the RHS (right hand side) of (26). This concludes the proof.
Now, let prove the second lemma that leads to Theorem 3.5
Lemma D.2. For all factor graphs and for all x E D,
2 of ( (ovr.)
(x S
(28)
KEN;
Proof. First, let us denote the LHS (left hand side) of 28 by L(a ... . and the RHS of 28
by (1) (1) ,.!)) Note that the arguments of the variance terms have been omitted for the sake
of simplicity. Next, let us differentiate both L and R with respect to each variance term We find
o
(k)
aL
(29)
(0!
(K)
2
2v
Ei= (o!
ØR
Σ
(30)
2
EjeN; (0,0)
0
iNN
2 PV
W.
16

---

Published as a conference paper at ICLR 2024
Let us now compare (29) and 30 by studying their ratio, denoted Qk=
-1
V - (o!
Qk =
WWP EjEN; of NN,
iEN&
Σラ= (o(2) 2
(31)
(
2))) 2
プラ=
n1
(o
n プラ=ı
(32)
where 31 comes from the fact that Qs is maximized when [i = n, vi E [1.n].
Since vk E n), Qs < 1, we have 0 <
aL
5
aR
This incquality can be exploited by
0(0
0000
observing that
(0!0)²
L(a (1)
00 (n))
L(O, ,0, .0++ + Σ
(0000 2d (0!0)2
aL
n
aL
)
(33)
(0)2
8
θ d (of))2
aR
(34)
1=1
R(a,
(1)
(m)
(35)
where (33) and (35) follow from L(O, ... 0) R(O. ................................ 0) 0, and 34 comes from the inequal-
ity involving the partial derivatives of L and R established above.
This directly implies that for any x and any factor graph, greater than (or equal to) o.(x).
Combining Lemmas D.I and D.2 together yields Theorem 3.5
E DUMBO: ALGORITHM AND TIME COMPLEXITY
In this section, we describe DuMBO in Algorithm ! alongside its time complexity.
We now provide time complexity analysis for Algorithm T The analysis assumes that gradient ascent performs O (c-1) steps for desired accuracy Ç (Xie et al. 2020) and ADMM converges in most NA steps. We also denote by ( the factor size of the ith factor in the decomposition, used by the local acquisition function (1) Note that, within the factor graph of Pt, n factor nodes and d variable nodes work concurrently to run ADMM in decentralized fashion. We provide the
time complexities for the two types of nodes in this section (the communication costs between factor
nodes and variable nodes neglected for the clarity of the analysis).
17

---

Published as a conference paper at ICLR 2024
Algorithm DuMBO
Input: factor graph of the acquisition function yr, sequence Br. 17 0.
2: t
t=0
3: while true do
4: Ao = 0
5:
Vi E [1] init 20 randomly
6: ==0
7:
while stopping criterion not met do
8:
for all factor node [concurrently] do if k o O then
9:
10:
Update A with 17
and the received data
11:
Compute Is Egea
with the received data
12:
end if Compute (3)
by maximizing
15
with gradient ascent starting from æ
14:
Send x
(0) k+,, and
to the variable node j. Vj V;
W.
end for
16:
for all variable node j [concurrently] do Compute 1R+ with (T6)
(at)
Send Ex+1, and
to the factor nodes in F,
iEF
19:
end for
20:
k +
21:
end while
Observe ((++1) f(xx) +GE N (0,00
23:
t= -=++1
end while
Factor node. For a factor node i, it is known that, at iteration t, the time complexity of the infer- ence with GP is O (t*d()), where denotes the number of previous observations. Thus, the time complexity of evaluating (15 is O (f)))). Since the evaluation required O (s-1) times by the gradient ascent, the time complexity finding 2 is O (5-1(add))
factor node also needs to 1 which O (d))).. Since the factor node is called least once and at most NA times for ADMM to converge, the time complexity factor node is
(1)
compute
Variable node. A variable node j is simply charge of collecting messages from FF factor nodes, and to aggregate them into ēx+1,f by averaging, Its time complexity is therefore O (FF))).
F RESTRICTED PROX-REGULARIT AND KL PROPERTY OF THE ACQUISITION FUNCTION
In this section, we prove Theorem 5.1 which is split in two lemmas (Lemmas F.2 and F.4 on the acquisition function and the augmented Lagrangian, respectively. For the sake of completeness, provide the definition of property to prove each lemma before stating the lemma itself.
Let us recall the definition of restricted prox-regularity.
Definition F.1 (Restricted Prox- Frox-Regularity (Wang et al. 2019)). For a lower coniicontiiuous func-
(6) tion u0 let M R.,, and define the exclusion set
SM = f f (t) 11gl12 M, Vg E axp (x)
(36)
with (.p( (2:) (0)))) the set of all subgradients of ( (z)) (z))
18

---

Published as a conference paper at ICLR 2024
( is called restricted prox-regular if. for any M > and bounded T C D(6), there exists
Pt >
such that
Pi (x') + 2 ||s 2112 2 Pi (a:) + 9 T (x' x)), Va E T SM x' E E 0.p 0 (37)
IfT SM = 0, 37 is automatically satisfied.
Lemma F.2. Under Assumption 3.3 for any E [1, pi (see (9) restricted prox prox regular.
Proof. First, note that si given by (9. is indeed a continuous function, and therefore a lower semi-continuous function required by Wang al. (2019).
Then, let us pick M > 0, any bounded set T S D( and build the corresponding exclusion set Sax
with (36). Under Assumption 3.3 and for any æ E Sas. ② differentiable. Therefore, for any
D( 0.p (x)
V (x) V (0) (ax) directly obtained by differentiation of (9) which
also involves differentiating and (5)
1//2 V xx, x)T
(K + (K+ k000 X) D(x)
Vg, 1 (x) (z)
Vk (x, (x, x)_ KK (K++)1=1 y
W
(38)
with Va(0 X) being the L x d matrix (Vi(0 and
T A10) )*)
(x,
D(x) = 100 - A 10 (x, X)_ (K + + (x. X) + IN.13s..
(39)
Observe that, for any x T SM, we have [D(x) 2 DM, for some DM > 0. This is because, otherwise, |/Vx/") (=) could diverge, which is impossible for æ E TAS Under Assumption 3.3 38 is also diffcrentiable. For any M > O, any bounded set T C D(1,, any a E T> SM and any T, we have
|| - x (x)
2 (x') (x) Vigl (x) (x)T(x' (a' - x))
(40)
2
with 42 (8) 1 (x) the Hessian matrix of wp at point x.
We will bound [| (x))22 (z))l2
from above by decomposing 20 A(x) +
g//2
(B(x) + C(x)) with
AT
A(x) V2h (0) (x, X) [K + +o21)~1 y.
(41)
B(x) = 12x (+ (x. X) (K + 021) (2, X) VA (2, X)T (K + 0²1) -1 (1) (x. X);
(42)
C(x) 3(x)3/2 Vill (x, X)T (K + -02-) ~1,00x000x)) x0xxx)))²
(43)
where (1 (xc, X) is the d x d x tensor resulting from stacking the Hessian matrices 72,.000 x²) (j E [1. t on the third axis of the tensor.
We now bound ||A(z) 1| [B)))l and |[C()) from above for any S' In particular, note that under Assumption 3.3 the Pythagorean theorem yields (() [m)]|2 vtH. Also, note
19

---

Published as a conference paper at ICLR 2024
that || xx, X2 2 VEXO. Therefore, we have
|| |a(x))12 S V(HlI (K + 0²)) 1122110112,
(44)
|B(x) = D1/2
(VHHlI (K -K<001)) -1 - -IaveA00=LI(K +221) =1221)
(I -221) (IHA + +²)
(45)
D 1/2
L (K + I² -1 112t (A01)2
|[(() <
(46)
D M
Note that the occurrences of in 45) and (6)
due to k(()) being L-Lipschitz function (see
Assumption 3.3).
Combining 44 45 and (6), we have an upper bound for 2 (8) (x)ll2 for any E T SM::
8/ Vt
[1 (1+ [K
K + 022I) -1 (2(0))
1IV & (x)l2 VK(( + +021) -1 H|ly/l2+ +
HX +L3
IN
D
(47)
Let us denote by the RHS of 47 Then, for any M > 0, any T C (+t) any T SM and any
x' E T, we have
(x') (x) V (0' (x' x) 2 =012
which is equivalent
0i ( (0')
? I|a' 2
a013 20 (x)) (x)
(x))(('' (x' -x).
(48)
This concludes the proof.
Now let focus on the last part of Theorem 5.1 regarding the augmented Lagrangian L., (see 112 We must prove that L,, is KL function, so let us first provide the definition for the sake of com- pleteness.
Definition F.3 (Kurdyka-t.ojasiwwiik Function (Attouch al. 20100). A function L satisfies the fondyka-ttojsiewiii (KL) inequality in a E dom ØL if there exist 7 E (0, + a neighborhood U of x and a continuous concave function { (0,7) + R4, such that:
{(O) = 0,
E is C 70,7),
Us (0,)), 0,
Va' (a'(aalCCa) [(x') < [(x) + 7) the KL inequality holds
(C(x') - L(x)) dist (0, (0,00(x))) 2
(49)
function satisfying the KL inequality Vx E dom OL is called KL.fucctoo. Lemma F.4. Ly (see (2) is KL function.
Proof. First of all, observe that L., continuous, hence a lower semi-continuous function. Also, note that E, is either not subdifferentiable (because of the square root in (9) or differentiable. Therefore, C,, differentiable on dom aC,, and (49) can be rewritten
g' (L., (x)()) || C., (ar 1l 1, Va E dom 0..
(50)
20

---

Published as a conference paper at ICLR 2024
(i) Let first pick noneritical point of Ly is known (see Lemma 2 in Attouch al. (2010) that for any noncritical point a of En, there c > 0 such that, for any x' E dom Ey,, we have
| 2112 + Lc, (x') - (x)) < c = IVV (x'')l2 2 c.
(51)
The point x being noneritical point of fyp
is verified with U
(a': x' E dom Eyp (x,) - (x)x < 1|= x||2),
c and E(s) va V... Indeed
then (s) yrs and for any x' E E n (a) < (z(()) (x) + 7), we have
1V,,,(x0') (x)) 12
(L'((aa)) - (
V Vc(Lo((2)) (a') (z)
v
(52)
(ii) Regarding the critical points of by we use another well-known result (see Theorem LI in Kur- dyka (1998)) stating that, given an open bounded subset Ω of I=,, for any function g Ω + K
differentiable on \ (0), there exist e> 0, 7 and a < such that
[VVg(>)ll2 2 clg(x))).
(53)
for any Q such that 19(x)] E (0,
Let g(x) = C, (x) (,)))), where x" is a critical point of Lyp Then, is differentiable on all æ E dom d.y Therefore, there exist e 0, y > 0 and I such that, for any E U = {x'l (zll)) (x((=)] <>),
[V),( VV(()]l 2 dg(x)) = clC,(x) - (,)x))
(54)
since xx is a critical point. This yields
V L (x:
2
(55)
c ( (x
Choosing x (U < (x') (x( 7} and {(s) 1 1-a (so that E'(s)
al-aa
allows to rewrite (55)
[V,
- Cc,
VC, c(Ln((a) - L.y (z+)a 2
(56)
Combining 52 and (66) concludes our proof.
G IMMEDIATE REGRET BOUND
In this section, we discuss the asymptotic optimality of DuMBO and we provide the proof for The- orem 5.2 considering finite, discrete domain D. We start by proving the following inequality that links f(x) with the posterior mean and variance of f.
[D] 12)=²(2)
Lemma G.1. Pick 8 E (0. 1) and let 3r = 2 log
Then, with probability at least 1 - 8,
(K) (avw)) 2
1f(x) - pe(x)) < S
Σ
(57)
W2
REN;
for all x E D and E N. (x()) and of(xx) = Σm= (o. (2x.) are given by the decomposition
in Proposition 3.4
21

---

Published as a conference paper at ICLR 2024
Proof. For æ E D and t N, we have f(x) N (f Defining sx(x) f(x)) we know that se(x)) ~ (0, 1). Therefore we have successively that
0.(
Pr (s+ S 0,
2 1 - e %
Pr (1((z) Me(zr) I B3 01(())
2 1 e 4
(av) )
Pr [f(x) - me(x)) ((()))
s B
Σ
1 1-- 1
(58)
NN ?
REN.
where the last inequality (58) follows from (see Theorem 3.5). Inequality 588) holds for one
single pair (t, x). Applying the union bound all pairs in D, we have Vt Vx E D
(o. (h) (avr.) 2
Pr [f(x) me(2)) S
3
1W212
2 1 D
e
(59)
REN,
[2)
Pick 5 (0, 1) and let Br = 2log
Then
66
+
+
[D|=2,2
DD
D
66
+00
8.
Therefore, 59 becomes
(, (ave))
Pr (((x)-M((z)
((ce)-ulee s B
Σ
11-8
(60)
Will
keN:
which is the desired result.
We are now ready to bound the immediate regret r; = f(x*)= - f(x²) and prove Theorem 5.2
Proof. By definition, x
(1) arg max Di=1 spt (xV))
Therefore, Σ v0 (x() >
E Pi (x)) and
a (k) (a()))
n
n
Σ
(x)) = Σ
# 0 (xt)) + 3
( pc (xzz)
Wul2
1=1
REN;
2 f(x")
(61)
22

---

Published as a conference paper at ICLR 2024
with (61 following from Lemma G.1 with probability 1-8. We now upper bound the immediate
regret rt, since with probability 6, we have
f(xx' f(xx)
(o. (at)))) 2
( (2bb)) + B//
f(x²)
REAN
(h) (2 2
0 (att) - -s(x') + B7
1=1
AEN:
2
(arhx
=x(x') - f(x² B3
(62)
NN 12
REN.
Combining 57 with 62 get
( (1) (att)) ))
2
S 23 1 Σ
Pr
2 21-6,
(63)
REN;
which is the desired result.
H SYNTHETIC FUNCTIONS
In this section, we describe the synthetic functions constituting our benchmark in Section 6.1
H.1 CAMEL FUNCTION
The Six-Hump Camel function a 2-dimensional function defined by
(21 - + 2.1=² a1 o x1 + 4x²) x²
(64)
It is composed of 3 factors, with MFS d = 2. In experiment, optimize it the rectangle = [-3, 3] x [_, It has local maxima, two of which are global with f(x*) 1.0316.
H.2 HARTMANN FUNCTION
The Hartmann function a 6-dimensional function defined by
f(x)
an exp Σ
Ais (xy- P.))
(65)
with a = (as))e [1,4) A = (Au))..EE... and P = (Po) (t.)e.L)) x[1,s] given as constants.
composed of n 4 factors, with MFS d 6. our experiment, we optimize it on the hypercube D [0, 1] It has 6 local maxima and a global maximum with f(x") = 10.5364.
H.3 POWELL FUNCTION
The Powell function a function of an arbitrary number d = 4k of dimensions, defined by 2xr)²
4/4
f(x) = (aai + 10 5(0 - x2s) (Mar-- 2 2m14-1)* 4 10(x01-p -24)) (66)
Σ
23

---

Published as a conference paper at ICLR 2024
Hump [d=2, M=5
Rastrigin (d- MFS-SI
109
544550
40D-G/PUCB
1500
TuAO Ms-k
DECHIB
30
Rueso
DEC-4B0
ADD-DUNOO
25
Mrsiten
AnC-0.N00
1400
1.a
2.0
Regres
1200
10'4
1000
10-
000
TURBO
DUMBO
0.5
Line0
ADD Du MBO
20
49
60
00
100
20
40
60
80
100
20
40
60
20
100
Optimizet on step
Optmm Zocion step
Optimization stop
(b)
Figure 4: Performance achieved by the studied BO algorithms for (a) the 2d Six- Six-Hump Camel func- tion, (b) the Hartmann function and (c) the 100d Rastrigin function. The shaded areas indicate the standard error intervals.
We chose to set k = 6, so that the resulting Powell function lives in a d = 24 dimensional space. It is composed of n 6 factors, with a MFS d 4. our experiment, we optimize on the hypercube D |44,5 5)24. It has global maximum at x:" O, with f(x") = O.
H.4 RASTRIGIN FUNCTION
The Rastrigin function is a function of an arbitrary number d of dimensions, defined by
f(x) 100
T 10 (2mx,)).
(67)
We chose to set d 100. We also chose to aggregate factors to make the optimization problem harder. The resulting Rastrigin function composed of = 20 factors, with MFS d = 5. In our experiment, optimize on the hypercube D [-5.12, 5.12 100, It has multiple, regularly distributed local maxima, with a global maximum at x and f(x = 0.
H.5 ADDITIONAL FIGURES
Figure depicts the performance of the studied BO algorithms on the synthetic functions not dis- cussed m Section 6.1
Figure 4(a) reports the minimal regrets achieved by the solutions on the Six-Hump Camel (SHC) function. Observe that in this specific example, DuMBO clearly outperforms every other state-of- the-art algorithm except DEC-HBO. This is due to the simplicity of the SHC function that satisfies all the assumptions made by DEC-HBO: MFS d lower than 3 and sparse factor graph. In this case, the variant of the max-sum algorithm used by DEC-HBO is guaranteed to query arg max Pr. each time step
Figures 4(b) and [C) depict dynamics similar to Figure I(a) In both cases, the ability to infer or exploit complex additive decomposition gives DuMBO decisive advantage against the other BO algorithms. As a consequence. DuMBO and ADD-DuMBO manage to outperform them, even in very high dimensional imput spaces (see Figure4(c)). Note that ADD-GPUCB and DEC-HBO were not evaluated on the Rastrigin function, as their execution time exceeded 24 hours because of the large dimensionality of the function.
Finally, observe that LineBO and MS-UCB tend to become less effective as the dimension of the problem grows. Indeed, they adopt strategies (random line searches and discrete sampling high- dimensional spaces) that are very sensitive to the dimension of the problem.
I REAL-WORLD PROBLEMS
In this appendix, describe the real-world problems constituting our benchmark in Section 6.2
24

---

Published as a conference paper at ICLR 2024
Cosmological Constants (d=9)
50
SAAS8O
ADD-GPUCB
TuRBO
DEC.HEO
Average Negative Reward
40
LineR0
DuMRO
20
10-
20
40
60
80
100
Ootimization step
Figure Performance of the studied BO algorithms on the cosmological constants fine-tuning problem.
1.1 COSMOLOGICAL CONSTANTS
The cosmological constants problem consists in fine-tuning an astrophysics tool to optimize the likelihood of some observed data. We chose to compute the likelihood of the galaxy clustering in Chuang et al. (2013) from the Data Release 9 (DR9) CMASS sample of the SDSS-III Baryon Oscillation Spectroscopic Survey (BOSS). To compute the likelihood, instrumented the cosmo- logical parameter estimation code CosmoSIS (Zuntz et al. 2015
We used nine cosmological constants our optimization task, going from the Hubble's constant to the mass of the neutrinos. If BO algorithm provided a set of inconsistent cosmological constants, a likelihood of y = 60 was returned.
Note that similar experiments were described in other works, such as Kandasamy et al. (2015) Eriksson et al.) (2019). However, they were conducted on another, older dataset, with a deprecated NASA simulator 5 This makes the conducted experiments painful to reproduce on modern com- puter. Luckily, CosmoSIS is well documented and easier install and instrument, so we conducted experiment with CosmoSIS to make it casier to replicate.
Figure depicts the performance the described BO algorithms on this problem. Note that, since the objective function does not have additive decomposition. ADD-DuMBO cannot be evaluated. Although the objective function does not have an additive decomposition, DuMBO demonstrates its competitiveness by achieving the best performance, along with TuRBO, LineBO and MS-UCB.
1.2 SHANNON CAPACITY OF A WLAN
The Shannon capacity (Kemperman) 1974) sets theoretical upper bound on the throughput of wireless communication, depending on the Signal-oo-interferenne plus Noise Ratio (SINR) of the communication. Denoting by St,, the SINR between two wireless devices i and communicating on a radio channel of bandwidth W (in Hz), the Shannon capacity C(St,) (in bits) is defined by
C(Sk)) = W log, (1 -1-66 St,).
(68)
In this problem, study Wireless Local Area Network (WLAN) with end-users associated to nodes streaming a continuous, large amount of data. The WLAN topology is depicted in Figure populated with 36 end-users, each one associated each node is within the radio range of at least two other nodes. This creates interference and, consequently, reduces the SINRs between nodes and end-users.
one of the 12 depicted nodes. Note that
Each node has an adjustable transmission power E [100.1 102.5 in mW (milliwatts). This task consists in jointly optimizing the Shannon capacity 688 of each pair (node, associated end-user) by
hhttps:/ https///wm...ttccccecee//eee/eee
BOSS. html
25

---

Published as a conference paper at ICLR 2024
200
150
100
50
0-
50
100
150
7000
Figure 6: The WLAN topology used in the Shannon capacity optimization experiment. The end- users are depicted as black dots, the nodes numbered blue circles and the associations between end-users and nodes as thin gray lines. Two nodes are connected with black line they are within the radio range of each other.
tuning the transmission power of the nodes. That is, the objective function f is 12-dimensional function defined by
12
f(x) Σ Σ C(S.)),
(69)
with N₁ the set of end-users associated node
A difficult trade-off needs to be found because node cannot simply use the maximum transmission
power this would cause lot of interference for the neighboring nodes. Given a configuration
D = [100.1 102.5 12, the SINRs are provided by the well-recognized network simulator ns-3 (The ns3 Project) that reliably reproduces the WLAN internal dynamics. The additive decomposition comprises = 12 factors, with MFS of d = 5, obtained by making the reasonable assumption that only the neighhoring nodes of node i (i.e. those within the radio range of node i) are creating interference for the communications of node
1.3 ROVER TRAJECTORY PLANNING
This problem was also considered by Eriksson et al. (2019); Wang et al. (201).. The goal to optimize the trajectory of rover from a starting point s [0, target E [0. 1J2, over rough terrain.
The trajectory defined by vector B-spline is fitted to these 30 points, determining the trajectory of the rover. The objective function to optimize is
60 dimensions, reshaped into 30 2-d points [0, 1]. A
((x) c(()) 10( a||1 + || E||1),
(70)
with c(x) the cost of the trajectory. obtained by integrating the terrain roughness function over the B-spline, and the two Loooss serving as incentives start the trajectory near 8, and end near t.
J WALL-CLOCK TIME
In this section, provide wall-clock time measurements (excluding the evaluation time of the objective function) of the described BO algorithms on a synthetic function (24d Powell) and a real- world problem (WLAN) described in Appendices H and [ respectively. The measurements were taken using a server equipped with two Intel(R) Xeon(R) CPU E5-2690 v4 @ 2.60GHz, with 14 cores (28 threads) each.
Figure 7 gathers the wall-clock time measurements. Observe that DuMBO does not only offer very competitive performance, it also exhibits lower overhead when compared to the other decompos-
26

---

Published as a conference paper at ICLR 2024
Powell (d-24, MFS=4)
WLAN 12. MFS-6)
-105.0
SAASBO
ADD GPUCE
TURBO
HBC
Avcrage Negative Reward
-107.5
LinaRO MS-UCR
DUMBO
ADD-DuMRQ
-110.0
Regnet
10a
-112.5
GPUC8
TuRBO
DEC-HBO
-115.0
LineBO
DuMBO
MS-UCB
ADD MBO
-117.5
10a
-120.0
1000
2000
3000
4000
100
200
300
400
500
Wall-clock Time (s)
Wall-clokk Time (s)
(a)
(b)
Figure 7: Performance achieved by all the described BO algorithms (including the two versions of DuMBO) for (a) the 24d Powell synthetic function and (b) the maximization of the Shannon capacity in WLAN. The shaded areas indicate the standard error intervals.
ing algorithms (DEC-HBO and ADD-GPUCB). However, SAASBO, TuRBO and LineBO manage to get lower runtimes than DuMBO. This not surprising since, by design, these methods have minimal overheads, at the expense of weakening their theoretical guarantees. As for MS-UCB, manages to have a lower execution time on the WLAN problem (where = 12), but a larger exccution time on Powell (where d 24).
Nevertheless, with ADD-DuMBO, having access to the true additive decomposition of the function reduces the overhead of the solution, because the decomposition does not need to be inferred any- more. On the Powell synthetic function (see Figure ((a) ADD-DuMBO even achieves the lowest wall-clock time.
27


Reviews:
[{"review_id": "tWfAxuUdW3", "reviewer": "Reviewer_q9mg", "summary": "This paper addresses a line of the high-dimensional Bayesian optimization problem under the assumption that the objective function has an additive structure. Under this line, the authors relax the assumption of the additive structure without requiring that the maximum number of dimensions for a factor of the decomposition is low as in the work of (Hoang et al., 2018). The authors propose DuMBO, a decentralized, message-passing, provably asymptotically optimal Bayesian optimization algorithm under such a relaxed assumption. They also introduce another way to approximate the GP-UCB acquisition function. Finally, they demonstrate the effectiveness of DuMBO by comparing it with several state-of-the-art BO algorithms on both synthetic and real-world problems.", "questions": "Please see my above questions. I also have other questions as follows:\n\n- Do the authors need any assumption on the function $f$ such as the Lipschitz continuous to guarantee the convergence?\n- Equation (8) seems incorrect to me. Is it a typo?", "limitations": "", "rating": 5, "confidence": 3, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "- The paper is well written in general although the related works are missing and the introduction section can be improved. \n\n- The idea of using the Alternating Direction Method of Multipliers (ADMM) proposed by Gabay & Mercier (1976) to maximize the acquisition function is new compared to the existing works.", "weaknesses": "- The related works are missing. Besides Embedding and Decomposing and Turbo, there are several approaches as in [1], [2], and [3] that do not impose assumptions on the structure of the function $f$. In particular, the authors are missing a very related paper [4] \"Are Random Decompositions All We Need in High-Dimensional Bayesian Optimisation?\".  A comparison with this work is needed. \n\n- The representation in the method is unclear to understand the contribution of this paper. For example, it is unclear to me why ADMM can solve the high-dimensional optimization problem, for example when $\\overline{d}$ is high. Could we ensure to find the arg max when the function is non-convex?\n\n- The experiments are insufficient to understand the effectiveness of the proposed method.  It is missing a baseline from [4]. \n\n[1]. Johannes Kirschner,Mojm´ır Mutny', Nicole Hiller, Rasmus Ischebeck, Andreas Krause. Adaptive and Safe Bayesian Optimization in High Dimensions via One-Dimensional Subspaces. ICML 2019.\n\n[2]. Hung Tran-The, Sunil Gupta, Santu Rana, Svetha Venkatesh. Trading Convergence Rate with Computational Budget in High Dimensional Bayesian Optimization. AAAI 2020.\n\n[3]. Linnan Wang, Rodrigo Fonseca, Yuandong Tian. Learning Search Space Partition for Black-box\nOptimization using Monte Carlo Tree Search. NeurIPS 2021.\n\n[4]. Juliusz Ziomek, Haitham Bou-Ammar. Are Random Decompositions all we need in High Dimensional Bayesian\nOptimisation? ICML 2023.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "AgW7eq5QCY", "reviewer": "Reviewer_8R9C", "summary": "The paper relaxes restrictive assumptions on the additive structure of the objective function. It proposes the DuMBO algorithm, which is a decentralized, message-passing, and asymptotically optimal BO algorithm. DuMBO can infer complex additive decompositions of the objective function without assumptions regarding Maximum Factor Size (MFS).", "questions": "(1) In Table 2, why the standard deviation is not given?\n(2) Is the algorithm sensitive to \\bar d and other hyper-parameters? \n(3) In figure 1c. The performance of DumBO is close to TurBO. Does that mean DumBO does not outperform baseline much on higher dimensional tasks?\n(4) Why the time step is only about 100? For figure 1a. Some methods's cost are still decaying.", "limitations": "", "rating": 5, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "The paper presents an innovative approach to Bayesian Optimization (BO) that relaxes assumptions about the Maximum Factor Size (MFS) and focuses on modeling and optimizing complex, high-dimensional objective functions. \nThe DuMBO algorithm introduced in the paper is asymptotically optimal, meaning it provides strong guarantees of convergence to the global optimum of the objective function over time.\nThe paper backs its claims with empirical evidence by comparing DuMBO with state-of-the-art BO algorithms on both synthetic and real-world problems. It demonstrates that DuMBO performs competitively and is particularly effective when the objective function comprises numerous factors with a large MFS.\nThe paper explores the trade-off between model complexity and the guarantee of maximization in the acquisition function, contributing to the theoretical understanding of BO algorithms in high-dimensional spaces.", "weaknesses": "The paper's experiment part is not valid enough. The baseline it compares TurBo is not that up to date. Please see:\n\nLearning Search Space Partition for Black-box Optimization using Monte Carlo Tree Search\nLinnan Wang, Rodrigo Fonseca, Yuandong Tian\n\nAnd some other trust region based high-dimensional methods. Also notice that in the paper, some other methods are mentioned, but didn't show up in the experiments part.\n\nIn general, the performance improvement to other baseline is not significant enough. I believe some other methods can outperform the baselines in a similar way.\n\nAblation study about other hyper parameters should be given.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "VhK5XwHgos", "reviewer": "Reviewer_NC5W", "summary": "The paper is concerned with the problem of optimizing a function that is noisy and costly to evaluate. The traditional way to tackle this is by assuming an additive structure for the function which imposes restrictive assumptions on the function. This paper introduces DumBO, a decentralized BO algorithm that relaxes these assumptions, albeit at the expense of weakening the maximization guarantees of the acquisition function. Additionally, the authors also claim to address the over-exploration problem in decentralized BO algorithms. Experimental evaluation suggest that their algorithm performs competitively compared to state-of-the-art BO algorithms.", "questions": "1) Are there known lower bounds for the problem? If yes, it would be nice to see how the proposed algorithm does in comparison.\n2) What were the major technical challenges the authors faced while deriving the regret bounds?", "limitations": "", "rating": 8, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "1) The paper is very well-written.\n2) The authors provide an algorithm which can be implemented in a decentralized manner, which seems to be very useful.\n3) The authors show a regret bound, which  show asymptotic optimality of their algorithm.\n4) Experiments conducted are exhaustive.", "weaknesses": "1) It would have been nice if the authors could show a proof sketch of their main theoretical result.\n2) Apart from the proof, it would be nice if the authors could highlight the main contributions and the technical (or analytical) challenges they faced.\nThese all are not major weaknesses per se, but can help the interested readers.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "xAgXudmpga", "reviewer": "Reviewer_PPCk", "summary": "The work discusses a new algorithm called DumBO for decentralized Bayesian optimization. DumBO relaxes the additivity constraints of traditional BO algorithms for high-dimensional inputs. It achieves better performance against some existing BO algorithms, especially when the additive structure of the objective function comprises high-dimensional factors. DumBO finds the maximum of the objective function while ensuring consistency between shared input components. The algorithm relies on ADMM to maximize the acquisition function and has demonstrated good performance in the numerical experiments.", "questions": "In addition, the authors mention that the decomposition needs to be inferred from the data. In this way, is the algorithm performance sensitive to the inference results of the decomposition? How to incorporate the inference uncertainty into the regret analysis? If the data for inference is not given in advance, how many rounds are required to generate the data for decomposition inference?\n\nBesides, the acquisition functions should satisfy a certain condition as in Assumption 5.1. The authors might discuss under what conditions the acquisition function satisfies Assumption 5.1.\n\nBesides, the authors might provide a more detailed comparison with the existing algorithm Add-GP-UCB [3], since the decomposition of the objective function is quite similar.", "limitations": "", "rating": 5, "confidence": 4, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "The authors have conducted a number of numerical experiments to illustrate the practicability of their algorithm. They have included state-of-the-art baseline algorithms for comparison, and have demonstrated scenarios when their approach is superior. \n\nIn addition, the authors provide explicit descriptions of optimizing the acquisition function, which is facilitated by the ADMM algorithm. The detailed procedure makes the algorithm feasible to use.", "weaknesses": "The presentation of the manuscript is not explicit enough for the audience to understand. For example, the main assumption of this work is that the objective function $f$ can be decomposed into several factors and each factor only takes some dimensions of $\\boldsymbol{x}$ as the input, as in Equation (2). However, this decomposition is not explicitly explained in Section 3.1. Actually, Figure 2 in the supplements helps the audience to understand and can be moved to the main text. In addition, to guarantee the performance of ADMM, the authors assume that the acquisition function ``is a restricted prox-regular function that satisfies the Kurdyka-Lojasiewicz condition’’. The authors should at least provide a formal definition of this condition.\n\nThe theoretical results do not exhibit sufficient novelty. For example, similar results as Theorem 3.4 have been derived, for example, in [1]. The analysis of the regret is also quite similar to that in [2], without significant novelty. \n\nReferences:\n[1] Mutny, Mojmir, and Andreas Krause. \"No-regret algorithms for capturing events in Poisson point processes.\" In International Conference on Machine Learning, pp. 7894-7904. PMLR, 2021.\n[2] Srinivas, Niranjan, Andreas Krause, Sham Kakade, and Matthias Seeger. \"Gaussian process optimization in the bandit setting: no regret and experimental design.\" In Proceedings of the 27th International Conference on International Conference on Machine Learning, pp. 1015-1022. 2010.\n[3] Kandasamy, Kirthevasan, Jeff Schneider, and Barnabás Póczos. \"High dimensional Bayesian optimisation and bandits via additive models.\" In International conference on machine learning, pp. 295-304. PMLR, 2015.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (poster)