Distributionally Robust Bayesian Optimization with $\varphi$-divergences
Authors: Hisham Husain
Vu Nguyen
Anton van den Hengel
Venue: NeurIPS 2023 poster (2023)
Keywords: Bayesian Optimization
Distributionally Robust Optimization
φ-divergences
TL;DR: We tackle distributionally robust bayesian optimization where uncertainty sets are constructed with phi-divergences and derive a tractable algorithm with regret bounds.

Abstract: The study of robustness has received much attention due to its inevitability in data-driven settings where many systems face uncertainty. One such example of concern is Bayesian Optimization (BO), where uncertainty is multi-faceted, yet there only exists a limited number of works dedicated to this direction. In particular, there is the work of Kirschner et al., which bridges the existing literature of Distributionally Robust Optimization (DRO) by casting the BO problem from the lens of DRO. While this work is pioneering, it admittedly suffers from various practical shortcomings such as finite contexts assumptions, leaving behind the main question \textit{Can one devise a computationally tractable algorithm for solving this DRO-BO problem}? In this work, we tackle this question to a large degree of generality by considering robustness against data-shift in $\varphi$-divergences, which subsumes many popular choices, such as the $\chi^2$-divergence, Total Variation, and the extant Kullback-Leibler (KL) divergence. We show that the DRO-BO problem in this setting is equivalent to a finite-dimensional optimization problem which, even in the continuous context setting, can be easily implemented with provable sublinear regret bounds. We then show experimentally that our method surpasses existing methods, attesting to the theoretical results.

Distributionally Robust Bayesian Optimization with g-divergences
Hisham Husain
Vu Nguyen Amazon vutngn@amazon. com
Anton van den Hengel
Amazon hushisha@amazon com
Amazon hengelah@@amzon..om com
Abstract
The study of robustness has received much attention due to its inevitability data-driven settings where many systems face uncertainty. One such example of concern Bayesian Optimization (BO), where uncertainty multi-faceted, yet there only exists a limited number of works dedicated to this direction. In particular, there the work of Kirschner et al. [26], which bridges the existing literature Distributionally Robust Optimization (DRO) by casting the BO problem from the lens of DRO. While this work is pioneering. it admittedly suffers from various practical shortcomings such finite contexts assumptions, leaving behind the main question Can one devise a computationally tractable algorithum for solving this DRO-BO problem? ? In this work, we tackle this question to large degree of generality by considering robustness against data-shift in p-ddieeggeness, which subsumes many popular choices, such the x² -iveeeegeee Total Variation, and the extant Kullback-Leibe Leibler (KL) divergence. We show that the DRO-BO problem finite dinee-dimeniional optimization problem which, even in the continuous context setting, can be easily implemented with provable sublinear regret bounds. We then show experimentally that our method surpasses existing methods, attesting to the theoretical results.
in this setting is equivalent
Introduction
Bayesian Optimization (BO) [29, 25, 52, 49, 34] allows model black-box function that is expensive to evaluate, in the case where noisy observations are available. Many important applications of BO correspond situations where the objective function depends on an additional context parameter [27, 57], for example in health-care, recommender systems can be used to model information about certain type of medical domain. BO has naturally found success in number of scientific domains [56, 20, 30, 18, 55] and also a staple in machine learning for the crucial problem of hyperparameter tuning [44, 36, 40, 41, 59].
As with all data-driven approaches, BO is prone to cases where the given data shifts from the data of interest. While BO models this in the form of Gaussian noise for the inputs to the objective function, the context distribution assumed to be consistent. This can be problematic, for example in healthcare where patient information shifts over time. This problem exists in the larger domain of operations research under the banner of distributionally robust optimization (DRO) [46], where one is interested in being robust against shifts in the distribution observed. In particular, for given distance between distributions D, DRO studies robustness against adversaries who are allowed to modify the observed distribution p to another distribution in the set:
{q D(p g) <e),
for some 5 > O. One can interpret this as ball of radius for the given choice of and the adversary perturbs the observed distribution p to g where form of "budget".
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

Distributional shift is a topical problem in machine learning and the results of DRO have been specialized in the context of supervised learning [12, 13, 11, 10, 7, 16, 22], reinforcement learning [21] and Bayesian learning [51], as examples. One of the main challenges however is that the DRO is typically intractable since in the general setting of continuous contexts, involves an infinite dimensional constrained optimization problem. The choice of D is crucial here as various choices such as the Wasserstein distance [6, 7, 9, 48], Maximum Mean Discrepancy (MMD) [53] and yp- divergences [12, 13] allow for computationally tractable regimes. In particular, these specific choices of have shown intimate links between regularization [22] which is a conceptually central topic of machine learning.
More recently however, DRO has been studied for the BO setting in Kirschner et al. [26], which as one would expect, leads to complicated minimax problem, which causes computational burden practically speaking. Kirschner al. [26] makes the first step and casts the formal problem however develops an algorithm only in the case where D has been selected as the MMD. While, this work makes the first step and conceptualizes the problem of distributional shifts in context for BO, there are two main practical short-comings. Firstly, the algorithm is developed specifically to the MMD, which is easily computed, however cannot be replaced by another choice of whose closed form is not readily accessible with samples such as the y-divergence. Secondly, the algorithm is only tractable when the contexts are finite since at every iteration of BO, it requires solving an M -immensional problem where M is the number of contexts.
The main question that remains is, can we devise an algorithm that is computationally tractable for tackling the DRO-BO setting? We answer this question to large degree of generality by considering distributional shifts against ye-divergences a large family of divergences consisting of the extant Kullback-Leibler (KL.) divergence, Total Variation (TV) and >ivdiverg,, among others. In particular, we exploit existing advances made in the large literature of DRO to show that the BO objective in this setting for any choice of yp-divergence yields computationally tractable algorithm, even for the case of continuous contexts. We also present a robust regret analysis that illustrates sublinear regret. Finally, we show, along with computational tractability, that our method is empirically superior on standard datasets against several baselines including that of Kirschner et al. [26]. In summary, our main contributions
1. A theoretical result showing that the minimax distributionally robust BO objective with respect to o divergences is equivalent a single minimization problem.
2. An efficient algorithm, that works in the continuous context regime, for the specific cases of the x² diveieegen and TV distance, which admits a conceptually interesting relationship to regularization of BO.
3. A regret analysis that specifically informs how we can choose the DRO e-budget to attain sublinear regret.
2 Related Work
Due to the multifaceted nature of our contribution, we discuss two streams of related literature, one relating to studies of robustness in Bayesian Optimization (BO) and one relating to advances in Distributionally Robust Optimization (DRO).
In terms of BO, the work most closest to ours is Kirschner et al. [26] which casts the distributionally robust optimization problem over contexts. In particular, the work shows how the DRO objective for any choice of divergence D can be cast, which is exactly what we build off. The main drawback of this method however is the limited practical setting due the expensive inner optimization, which heavily relies on the MMD, and therefore cannot generalize easily to other divergences that are not available in closed forms. Our work in comparison, holds for a much more general class of divergences, and admits a practical algorithm that involves a finite dimensional optimization problem. In particular, we derive the result when D is chosen be the x² >dviieegeee which we show performs the best empirically. This choice of divergence has been studied in the related problem of Bayesian quadrature [33]. and similarly illustrated strong performance, complimenting our results. There also exists work of BO that aim to be robust by modelling adversaries through noise, point estimates or non-cooperative games [37, 32, 3, 39, 47]. The main difference between our work and theirs is
as known fdiverggences in the literature
2

---

that the notion of robustness we tackle is at the distributional level. Another similar work to ours that of Tay et [54] which considers approximating DRO-BO using Taylor expansions based on the sensitivity of the function. In some cases, the results coincide with ours however their result must account for an approximation error in general. Furthermore, an open problem as stated their work is to solve the DRO-BO problem for continuous context domains, which is precisely one of the advantages of our work.
From the perspective of DRO, our work essentially is an extension of Duchi et al. [12, 13] which develops results that connect ---iivegeence DRO variance regularization. In particular, they assume admits a continuous second derivative, which allows them to connect the y-divergence to the x2 d--verreence and consequently forms general connection to constrained variance. While the work is pioneering, this assumption leaves out important ç-divergences such as the Total Variation (TV)- a choice of divergence which we illustrate performs well in comparison to standard baselines in BO. At the technical level, our derivations are similar to Ahmadi-Javid [2] however our result, to the best of our knowledge, is the first such work that develops in the context of BO. particular, our results for the Total Variation and X -dvveeegee show that variance is key penalty in ensuring robustness which is a well-known phenomena existing in the realm machine learning [12, 11, 10, 22, IJ.
Preliminaries
Bayesian Optimization We consider optimizing a black-box function, f X R with respect to the input space X' C IRd As black-box function, we do not have access to f directly however receive input in sequential manner: at time step I, the learner chooses some input x, X and observes the reward 1/+ f(xx) + Th where the noise Vie ~ (O, of) and of is the output noise variance. Therefore, the goal is to optimize
sup f(x). x
Additional to the input space X' we introduce the context spaces C, which we assume be compact. These spaces are assumed to be separable completely metrizable topological spaces. We have reward function, X C > R which we are interested in optimizing with respect to X. Similar to sequential optimization, at time step / the learner chooses some input x, E X and receives context c. E and fx,, ct) + nh- Here, the learner can not choose a context ct, but receive it from the environment. Given the context information, the objective function is written
sup Ee-p c)].
xEx
where is probability distribution over contexts.
Gaussian Processes We follow popular choice in BO [49] to use GP as a surrogate model for optimizing f. A GP [43] defines a probability distribution over functions f under the assumption that any subset of points (x;, [(x;)} is normally distributed. Formally, this denoted as:
f(x) GP (m(x), k(x,x'))
where m (x) and & (x. x') are the mean and covariance functions, given by m(x) E (x))
and k(x, x') E [[((x) m(x))(((x') m(x))=J. For predicting S. (x.) at new data point x., the conditional probability follows univariate Gaussian distribution as p(f xx, [x],.,NN], [wI,).)))) N (μ (x.),, ox.))) Its mean and variance are given by:
(xx)) N. N.NY,
(I)
o² (x.) -ki-. K.NK N.N N.Nk
where k., k (x,, k.,N [k (x,, xx)lvigN and KN.N (x,, Xxx,x))ly As GPs give full uncertainty information with any prediction, they provide flexible nonparametric prior for Bayesian optimization. We refer to Rasmussen and Williams [43] for further details on GPs.
Distributional Robustness Let A(C) denote the set of probability distributions over C. A di- vergence between distributions D (CC) x (C) - is a dissimilarity measure that satisfies
We remark that this is an extremely mild condition, satistied by the large majority of considered examples.

---

App q) 2 0 with equality if and only if q for p.q E A(C). For function, h : C + R. base probability measure p E ACC), the central concern of Distributionally Robust Optimization (DRO) [4, 42, 5] is to compute
sup @ (p)
(g(e)((c)),
(3)
where Be,D(p) fq A(C) D(p.g) S c). is ball of distributions q that are away from p with respect to the divergence D. The objective in Eq. (3) is intractable, especially in setting where is constrained infinite dimensional optimization problem. is also clear
continuous it amounts that the choice of D is crucial for both computational and conceptual purposes. The vast majority of choices typically include the Wasserstein due to the iiisporration-thoreeee interpretation and with large portion of existing literature finding connections to Lipschitz regularization [6, 7, 9. 48]. Other choices where they have been studied in the supervised learning setting include the Maximum Mean Discrepancy (MMD) [53] and g-divergences [12, 13].
Distributionally Robust Bayesian Optimization Recently, the notion of DRO has been applied to BO [26, 54], who consider robustness with respect to shifts in the context space and therefore are interested in solving
sup inf xEX ge D(P)
Bf c)).
where is the reference distribution. This objective becomes significantly more difficult to deal with since not only does it involve constrained and possibly infinite dimensional optimization problem however also involves minimax which can cause instability issues if solved iteratively.
Kirschner et al. [26] tackle these problems by letting D be the kernel Maximum Mean Discrepancy (MMD), which is a popular choice of discrepancy motivated by kernel mean embeddings [19]. In particular, the MMD can be efficiently estimated in O(n²) where is the number of samples. Naturally, this has two main drawbacks: The first is that is still computationally expensive since is required to solve two optimization problems, which resulting algorithm is limited to the scheme where the number of contexts is finite. In our work, consider D be sp-divergence, which includes the Total Variance, x² and Kullback-Leibler (KI.) divergence and furthermore show that minmax objective can be reduced to a single maximum optimization problem which resolves both the instability and finiteness assumption. In particular, we also present a similar analysis, showing that the robust regret decays sublinearly for the right choices of radii.
lead to instability and secondly, the
4 &o Robuutt Bayesian Optimization
In this section, we present the main result on distributionally robustness when applied to BO using ip-divergence. Therefore, we begin by defining this key quantity.
Definition (<=-divergence) Let p: R (-xo, oo) be convex, lower semi-continuous function such that (11) The up-divergence between p, A(C) is defined
Dp(p. Bntte
(d)(c)
dg (0))
where dp/dg is the Radon-Nikodyan derivative if << q and D (p(pp,)) to otherwise.
Popular choices of the convex function +p include (p()) (u 1)2 which yields the x² and, (p(u) = Iu 1/, (p()) = u log u which correspond to the x2 and KI. divergences respectively. At any time step t 1, we consider distributional shifts with respect an y--divergence for any choice of şp and therefore relevantly define the DRO ball as
(p.) = {q A(C) Do(g.Pt) S seh.
where P:: = -.E 8c, is the reference distribution and &, is the distributionally robust radius chosen time 1. We remark that for our results, the choice of pt flexible and can be chosen based on specific domain application. The y divergence, noted from the definition above, is only defined

---

finitely when the measures p. are absolutely continuous to each other and there is regarded as strong divergence comparison to the Maximum Mean Discrepancy (MMD), which is utilized in Kirschner et al. [26]. The main consequence of this property is that the geometry of the ball B would differ based on the choice of i--divergence. The --diiergencc a very popular choice for defining this ball in previous studies of DRO in the context of supervised learning due to the connections and links it has found to variance regularization [12, 13, 11].
We will exploit various properties of the g-divergence to derive a result that reaps the benefits of this choice such as a reduced optimization problem development that does not currently exist for
the MMD [26]. We first define the convex conjugate of yp as ("() = supuredom (u u' (
which we note is standard function that is readily available in closed form for many choices of yp
Theorem Let y R (-50, oo] be a convex lower semicontinuous mapping such that :p(1) O.
Let I be measurable and bounded. For any e > 0, it holds that
6 b- dE AEprle)
80" ( (b- f(x, (x(0-((x))) c)
1)
sup inf Eew [f(x xEX (EB)())
sup x2X,E20,
Proof (Sketch) The proof begins by rewriting the constraint over the ş-divergence constrained ball with the use of Lagrangian multipliers. Using existing identities for f-divergences, a minimax swap yields two-dimensional optimization problem, over 2 0 and & E R.
We remark that similar results exist for other areas such as supervised learning [50], robust opti- mization [4] and certifying robust radii [14]. However this is, the best of our knowledge, the first development when applied to optimizing expensive black-box functions, the case of BO. The above Theorem is practically compelling for three main reasons. First, one can note that compared the left-hand side, the result converts this into single optimization (max) over three variables, where two of the variables are 1 1-dimensional, reducing the computational burden significantly. Secondly, the notoriously difficult max-min problem becomes only max, leaving behind instabilities one would encounter with the former objective. Finally, the result makes very mild assumptions on the context parameter space C, allowing infinite spaces to be chosen, which is one of the challenges for existing BO advancements. We show that for specific choices of yp the optimization over b and even can be expressed in closed form and thus simplified. All proofs for the following examples can be found in the Appendix Section 8.
Example 2 -ddvvergeence) Let (p()) = (u 1)?, then for any measurable and bounded f we have for any choice of Et
sup inf Eooglf(x, sup (Exx)))(((xe))) Ves Varp.te) e)l XEX (pe)
xeX
The above example can be easily implemented as it involves the same optimization problem however now appended with a variance term. Furthermore, this objective admits a compelling conceptual insight which is that, by enforcing penalty in the form of variance, one attains robustness. The idea that regularization provides guidance to robustness or generalization is well-founded in machine learning more generally for example in supervised learning [12, 13]. We remark that this penalty and its relationship to x² -dviieegee has been developed in the similar yet related problem of Bayesian quadrature [33]. Moreover, it can be shown that if to is twice differentiable then D,, can be approximated by the x" diverregee via Taylor series, which makes x" -dvveregee centrally appealing choice for studying robustness. We now derive the result for a popular choice yp that is not differentiable.
Example 3 (Total Variation) Let (p(u)= = |u 11, then for any measurable and bounded we have for any choice of E,
sup inf xEA BEB (ps)
sup xEX
8t (xx
(up cec
inf f ((x,c)) c) ))
2
SEC
Similar to the cace, the result here admits a variance-like term in the form of the difference between the maximal and minimal elements. We remark that such result is conceptually interesting
5

---

since both losses admit an objective that resembles a mean- varannva which is natural concept in ML, but advocates for it from the perspective distributional robustness. This result exists for the supervised learning in Duchi and Namkoong [11] however is completely novel for BO and also holds for a choice of non-differentiable yp, hinting at the deeper connection between jo-divergence DRO and variance regularization.
4.1 Optimization with the GP Surrogate
To handle the distributional robustness, we have rewritten the objective function using yp divergences in Theorem 1. In DRBO setting, we sequentially select a next point x, for querying a black-box function. Given the observed context c q coming from the environment, function and observe the output as = [(x,, (4) V). where the noise ÿ) ~ NO0, of) and of is the noise variance.
evaluate the black-box
As common practice in BO, at the itera-
Algorithm 1 DRBO with y--iveegennce
tion f, we model the GP surrogate model us- ing the observed data (x,, 3/ ) and make a decision by maximizing the acquisition function which build on top of the GP surrogate:
1: Input: Max iteration T, initial data Do.
for f f= 1..... do
3: Fit and estimate GP hyperparameter given D,-1
4: Select a next input X arg max (x()
5: -d-divergence: axx) == a (x) from Eq. (4)
X3 = arg max axx).
XEX
6: Total Variation: axx) := a (x) from Eq. (5)
While method is not restricted the form of the acquisition function, for conve-
7: Observe a context Gt
8: Evaluate the black-box 1/: = [xx,; (a) + Me
nience the theoretical analysis, follow
9: Augment D, = Di-1 U (X,, Ct C1,
the GP-UCB [52]. Given the GP predictive mean and variance from Eqs. (7,8), we have the acquisition function for the x" in Example 2 as follows:
10: end for
a (x)
IC| Σ [ c) (B,o((x,
Ct |C'
Σ (He(x, () -i,))
(4)
where 3r is a explore-exploit hyperparameter defined in Srinivas et al. [52], coe गे E. (x c) and y can be generated in a one dimensional space to approximate the expectation and the variance. In the experiment, we select y as the uniform distribution, but not restricted to. Similarly, an acquisition function for Total Variation in Example 3 is written
TV (x)
Σ [x(xx c) + (x, c) C
St 2
mmax /r(x. c) - min (x(x, c)).
(5)
We summarize all computational steps in Algorithm
Computational Efficiency against MMD. We make an important remark that since we do not require our context space be finite, our implementation scales only linearly with the number of context samples |C] drawing from q. This allows to discretize our space and draw as many context samples as required while only paying a linear price. On the other hand, the MMD [26] at every iteration of t requires solving an CC)-dimensional constraint optimization problem that has no closed form solution. We refer to Section 5.2 for the empirical comparison.
4.2 Convergence Analysis
One of the main advantages of Kirschner et al. [26] is the choice of MMD makes the regret analysis simpler due the nice structure and properties of MMD. In particular, the MMD is well-celebrated for 0122 convergence where no such results exist for g-divergences. However, using Theorem 1, we can show a regret bound for the Total Variation with a simple boundedness assumption and extend this result to other (p-divergences. We begin by defining the robust regret, Ry, with --divergence balls:
show how
gEB; RT(2)= = Σ inf [f inf Ef c)),
(6)
REB;

---

Rosenbrock Ax.C)
selection
2.4
different
Optmmum Stochastic Optimum
5.6-
550
-1000
context
0.5
1500
19.4
2000
-0.
-10
0.0001
0.5
adapptv
0.1
-20
attions
10
50
50
60
input x
80
Iterations
(a) Stochastic and DRO solutions different. Our methad using e {0.5, 13 result the best performance.
1.0
Cosines fix a
X; selection
DRO with different
DR Optmum
2.0
0.8-
Stechaztic Optimum
1.5
Curulaliiee Robust Regret
1.0
context
0.6-
0.6
0.4-
0.0001
0.2
-1.5
0.
0.5 adeptive
-20
0.1
0.9
1.0
40
50
input x
MND
Iterations
(b) Stochastic and DRO solutions are coincide. Our method with 0 best.
Figure 1: Two settings in DRO when the stochastic solution and robust solution different (top) and identical (bottom). Left: original function f(x, c). Middle: selection of input x, over iterations. Right: performance with different
where x arg maxxex inf DEBL Exto)[((x,c) c)]. We use K; denote the generated kernel matrix from dataset D, ((x;, X C. we introduce standard quantity in regret analysis in BO is the maximum information gain: Yt maxpcxxc:jD] log det I, + of K. where K, = ([x;, ad), [xj, Cillvisss is the covariance matrix and of the output noise variance.
Theorem (p-divergence Regret) Suppose the target function is bounded, meaning that M sup(x.c)exxxl [x c)l < co and suppose I has bounded RKHS norm with respect to k. For any lower semicontinuuus convex p R. + (-00, co) with ((1) = 0, if there exists a monotonic invertible function I
[0, 20) > TR such that TV(p, S (D. the following holds
BTT + (2M + Br)
T
RT(p)) < log(1 + t
Σ Te(e))
with probability 1- 8, where 3, 11 300 In 3 (t/8), is the maximum information gain as defined above, and a is the standard deviation of the output noise.
The full proof can be found in the Appendix Section We first remark that with regularity as- sumptions
sublinear analytical bounds for "T known for range of kernels, e.g., given X' x C C Rd+1 we have for the RBF kernel, fr S O (log(T)d+2) or for the Matérn kernel with
(d+1)(d42) 1, YT < 5 ( (P (logT)). The second term in the bound is directly consequence of DRO and by selecting
0, it will vanish since any such T will satisfy r (0) 0. To ensure sublinear regret, we can select E, -'p (vi)=) noting that the second term will reduce to
EL S VT. Finally, we remark that the existence of T not so stringent since for wide choices of sp, one can find inequalities between the Total Variation and Djp, to which we refer the reader to Sason and Verdú [45]. For the examples discussed above, we can select (() = for
TV. For the x2 and KL cases, one can choose xx= (b) = 2/ 146 and (b) = 1 exp(-bb

---

Branin
Six-hump camel 2d
Robot Bushiigg 3d
Log Robust Regret
Log of Cum Robust Regret
7.0
Log of Cum Robust Regret
6.0
8.5
6.5
8.0
6.0
5.0
5.5
4.5
7.0
6.5
DABO X'
MMD
StaticOyc
Rand
5.0
DABD x
StableOs
4.0
DIBO AND
DRBO 1
DRBO TV
Rand
BO
Stasledpe
0
20
40
60
20 Iterations
40
60
20
80
Iterations
Figure 3: Cumulative robust regret across algorithms. The results show that the proposed x2 and TV achieve the best performance across benchmark functions. Random and vanilla BO approaches perform poorly which do not take into account the robustness criteria. Best viewed in color.
5
Experiments
Experimental setting. The experiments are repeated using 30 independent runs. We set |C| = 30 iid which should be sufficient to draw ~ q in one-dimensional space to compute Eqs. (4,5). We optimize the GP hyperparameter (c.g., learning rate) by maximizing the GP log marginal likelihood [43]. We will release the Python implementation code in the final version.
Baselines. We consider the following baselines for comparisons. Rand: we randomly select irrespective of c,. BO: we follow the GP-UCB [52] to perform standard Bayesian optimization (ignoring the context et). The selection at each iteration is x, argmax (xx) + (xx Stable- Opt: we consider the worst-case robust optimization presented in Bogunovic et al. [8]. The selection at each iteration x, arginax& argmin, (xx, c) + (x c). DRBO MMD [26]: Since there is no official implementation available, we have tried our best to re-implement the algorithm.
We consider the popular benchmark functions' with different dimensions d. To create a context variable e, we pick the last dimension of these functions be the context input while the remaining d - dimension becomes the input x.
5.1 Ablation Studies
To gain understanding into how our framework works, we consider two popular settings below.
DRBO solution is different from stochastic solution. In Fig. la, the vanilla BO tends to converge greedily toward the stochastic solution tnon-distributionaalyy robust) argmax fx. Thus, BO keeps exploiting in the locality of argmax, fx, :) from iteration 15. On the other hand, all other DRBO methods will keep exploring to seek for the distributionally robust solutions. Using the high value of & E (0.5. 1} will result in the best performance.
DRBO solution is identical to stochastic solution. When the stochastic and robust solutions coincide at the same input x", the solution of BO will be equivalent to the solution of DRBO methods. This is demonstrated by Fig. 1b. Both stochastic and robust approaches will quickly identify the optimal solution (see the x, selection). We learn empirically that setting Et + 0 will lead to the best performance. This is because the DRBO setting will become the standard BO.
The best choice of & depends on the property of the underlying function, e.g., the gap between the stochastic and DRBO solutions. In practice, we may not be able to identify these scenarios in advance. Therefore, we can use the adaptive value of e, presented in Section 4.2. Using this adaptive setting, the performance is stable, as illustrated in the figures.
5.2 Computational efficiency
The key benefit of our framework simplifying the existing intractable computation by providing the closed-form solution. Additional to improving the quality, we demonstrate this advantage in terms of computational complexity. Our main baseline for comparison is the MMD [26]. As shown Fig.
2, our DRBO is consistently faster than the constraints linear programming approximation used for
hhttss//www.sfu.cd ssurjanolopimiization.nm
8

---

20
Wind Power [C] 30
Wind Power [C]=100
Wind Power |C|= 500
Cummulative Reward
15
DR80 TV
DRB0
BO
DR60 WMD
Cummulative Reward
20
15
DRAO R.
DRSO TV
DRBO
DA60 MMD
Cummullative Reward
15
20
DRB0 y
ERDO TV
BRAO
8O
DR60 HIND
10-
10
10
-5-
350
700
350
350
700
Iterations
Iterations
Iterationn
Figure 4: All divergences improve with larger C/. However, MMD comes with the quadratic cost.
MMD. This gap substantial in higher dimensions. partieular, as compared Kirschner et al. [26], our DRBO is 5-times faster in 5d and 10-times faster in 6d.
5.3 Optimization performance comparison
Computational Time
We compare the algorithms in Fig. using the ro- bust (cumulative) regret defined in Eq. (6) which commonly used in DRO literature [26, 33]. The random approach does not make any intelligent in- formation in making decision, thus performs the worst. While BO performs better than random, it is still inferior comparing to other distributionally robust optimization approaches. The reason is that BO does not take into account the context infor- mation in making the decision. The StableOpt [8] performs relatively well that considers the worst scenarios in the subset of predefined context. This predefined subset can not cover all possible cases as opposed to the distributional robustness setting.
Input dimerssion
12
8D
32
DRBO X² or TV
en
108
120
Second per 60 Iteration
Figure 2: We compare the computational cost across methods. Our proposed DRBO using x² and TV take similar cost per iteration which is significantly lower than the DRBO MMD [26].
The MMD approach [26] needs to solve the inner adversary problem using linear programming with convex constraints, additional to the main optimization step. As a result, the performance MMD is not strong our TV and x². Our proposed approach does not suffer this pathology and thus scale well in continuous and high dimensional settings context input c.
Real-world functions. We consider the deterministic version of the robot pushing objective from Wang and Jegelka [60]. The goal is to find good pre-image for pushing an object to target location. The 3-dimensional function takes input the robot location (Tx,Ty) E [-5.5] and pushing duration Ta [1, 30). We follow Bogunovic et al. [8] twist this problem which there uncertainty regarding the precise target location, one seeks a set of input parameters that is robust against number of different potential pushing duration which context.
We perform an experiment on Wind Power dataset [8] and vary the context dimensions |C| E (30, 100, 500} in Fig. 4. When |C| enlarges, the performances do not improve further when increasing |C* from 100 to 500. Similarly, MMD improves with |C], but it comes with the quadratic cost w.r.t. |C). Overall, our proposed DRBO still performs favourably in terms of optimization quality and computational cost than the MMD.
DRBO x², TV and KL improves. However,
Conclusions, Limitations and Future works
In this work, we showed how one can study the DRBO formulation with respect to ---divergences and derived new algorithm that removes much of the computational burden, along with sublinear regret bound. We compared the performance of our method against others, and showed that our results unveil deeper connection between regularization and robustness, which serves useful conceptually.
Limitations and Future Works One of the limitations of our framework is in the choice of for which we provide no guidance. For different applications, different choices of yp would prove to be more useful, the study of which we leave for future work.

---

Acknowledgements
We would like to thank the anonymous reviewers for providing feedback.
References
[1] Soroosh Shafieezadeh Abadeh, Peyman Mohajerin Mohajerin Esfahani, and Daniel Kuhn. Distributionally robust logistic regression. In Advances in Neural Information Processing Systems, pages 1576-1584 2015.
[2] Amir Ahmadi-Javid Entropic aalue-at-risk: A new coherent risk measure. Journal of Optimiza- tion Theory and Applications, 155(3)1105511223, 2012. 3, 14
[3] Justin J Beland and Prasanth B Nair. Bayesian optimization under uncertainty. In NIPS BayesOpt 2017 workshop, 2017. 2
[4] Aharon Ben-Tal, Dick Den Hertog, Anja De Waegenaere, Bertrand Melenberg, and Gijs Rennen. Robust solutions of optimization problems affected by uncertain probabilities. Management Science, 59(2):3413377, 2013. 5,5
[5] M Bennouna and Bart PG Van Parys. Learning and decision-making with data: Optimal formulations and phase transitions. arXiv preprint urXiv:2109.06911 2021. 4
[6] Jose Blanchet and Karthyek Murthy. Quantifying distributional model risk via optimal transport. Mathematics of Operations Research, 44(2):565-600, 2019. 2,
[7] Jose Blanchet, Yang Kang, and Karthyek Murthy. Robust wasserstein profile inference and applications to machine learning. Journal of Applied Probability, 56(3):830-85) -57, 2019. 2,
[8] Ilija Bogunovic, Jonathan Scarlett, Stefanie Jegelka, and Volkan Cevher. Adversarially robust optimization with Gaussian processes. In Conference on Neural Information Processing Systems (NIPS), number CONF, 2018. 8,
[9] Zac Cranko, Simon Kornblith, Zhan Shi, and Richard Nock. Lipschitz networks and distribu- tional robustness. arXiv preprint arXiv: 129, 2018. 2, 4
[10] Zac Cranko, Zhan Shi, Xinhua Zhang, Richard Nock, and Simon Kornblith. Generalised lipschitz regularisation equals distributional robustness. In International Conference on Machine Learning, pages 2178-218 2178-2188. PMLR, 2021. 2,3
[11] John Duchi and Hongseok Namkoong. Variance- srriance-bbase regularization with convex objectives.
The Journal of Machine Learning Research, 20(1):2450-25) 2504,, 2019. 2, 3, 5,
[12] John C Duchi, Michael Jordan, and Martin Wainwright. Local privacy and statistical minimax
rates. In FOCS, 2013. 2, 2,3,44 5,
[13] John C Duchi, Peter W Glynn, and Hongseok Namkoong. Statistics of robust optimization: generalized empirical likelihood approach. Mathematics of Operations Research, 46(3):
2021. 2,
[14] KD Dvijotham, Hayes, Balle, Z Kolter, C Qin, A Gyorgy, K Xiao, S Gowal, and Kohli. A framework for robustness certification of smoothed classifiers using f-divergences. In Interna- tional Conference on Learning Representations, 2020.
[15] Ky Fan. Minimax theorems. Proceedings of the National Academy of Sciences of the United States of America, 39(1):42, 1953. 15
[16] Rui Gao, Xi Chen, and Anton J Kleywegt. Wasserstein distributional robustness and regulariza- tion in statistical learning. arXiv e-prints, pages arXiv-1712, 2017. 2
[17] Ziv Goldfeld, Kristjan Greenewald, Jonathan Niles-Weed, and Yury Polyanskiy. Convergence of smoothed empirical measures with applications to entropy estimation. IEEE Transactions on Information Theory, 66(7):4368-433 4391, 2020. 20
10

---

[18] Shivapratap Gopakumar, Sunil Gupta, Santu Rana, Vu Nguyen, and Svetha Venkatesh. Al- gorithmic assurance: An active approach algorithmic testing using bayesian optimisation. Advances in Neural Information Processing Systems, 31, 2018.
[19] Arthur Gretton, Karsten M Borgwardt, Malte J Rasch, Bernhard Schölkopf, and Alexander Smola. A kernel two-sample test. The Journal of Machine Learning Research, 13(1):723-773 2012.
[20] José Miguel Bernández-Lobatee James Requeima, Edward O Tyzer-Knapp. and Alán Aspuru- Guzik. Parallel and distributed Thompson sampling for large-scale accelerated exploration of chemical space. In International Conference on Machine Learning, pages 1470-1479, 2017.
[21] Linfang Hou, Liang Pang, Xin Hong, Yanyan Lan, Zhiming Ma, and Dawei Yin. Robust reinforcement learning with wasserstein constraint. arXiv preprint arXi::2006.0094 00945, 2020.
[22] Hisham Husain. Distributional robustness with ipms and links to regularization and gans. Advances in Neural Information Processing Systems, 33:1 18:11811-1187,, 2020. 2,
[23] Hisham Husain and Jeremias Knoblauch. Adversarial interpretation bayesian inference. In International Conference on Algorithmic Learning Theory, pages 553-572. PMLR, 2022. 14
[24] Hisham Husain, Richard Nock, and Robert Williamson. A primal-dual link between gans and autoencoders. In Advances in Neural Information Processing Systems, pages 413-422, 2019.
14
[25] Donald R Jones, Matthias Schonlau, and William Welch. Efficient global optimization of expensive black-box functions. Journal of Global Optimization, 13(4):455 492, 1998.
[26] Johannes Kirschner, Ilija Bogunovic, Stefanie Jegelka, and Andreas Krause. Distributionally robust Bayesian optimization. In International Conference on Artificial Intelligence and Statistics, pages 2174-2184, PMLR, 2020. 1, 2, 4, 5, 6, 8, 17
[27] Andreas Krause and Cheng S Ong- Contextual Gaussian process bandit optimization. In Advances in Neural Information Processing Systems, pages 2447-2455, 2011.
[28] Solomon Kullback and Richard A Leibler. On information and sufficiency. The Annals of Mathematical Statistics, 22(1):79-88) 1951. 19
[29] Harold J Kushner. A new method of locating the maximum point of an arbitrary multipeak curve the presence of noise. Journal of Basic Engineering, 86(1):97-106, 1964.
[30] Cheng Li, Rana Santu, Sunil Gupta, Vu Nguyen, Svetha Venkatesh, Alessandra Sutti, David Rubin De Celis Leal, Teo Slezak, Murray Height, Mazher Mohammed, and Ian Gibson. Acceler- ating experimental design by incorporating experimenter hunches. In International Conference on Data Mining, pages 257-266, 2018.
[31] Shuang Liu and Kamalika Chaudhuri. The inductive bias of restricted f-gans. arXiv preprint arXiv:1809.04544 2018. 14, 15
[32] Ruben Martinez-Cantie Kevin Tee, and Michael McCourt. Practical Bayesian optimization in the presence of outliers. In International Conference on Artificial Intelligence and Statistics, pages 1722-1731. PMLR, 2018.
[33] Thanh Nguyen, Sunil Gupta, Huong Ha, Santu Rana, and Svetha Venkatesh. Distributionally robust Bayesian quadrature optimization. In International Conference on Artificial Intelligence and Statistics, pages 1921-1931. PMLR, 2020. 2, 5,9
[34] Vu Nguyen and Michael A Osborne. Knowing the what but not the where in Bayesian optimiza- tion. In International Conference on Machine Learning, pages 7317-7326, 2020.
[35] Vu Nguyen, Sunil Gupta, Santu Rana, Cheng Li, and Svetha Venkatesh. Regret for expected improvement over the best-observed value and stopping condition. In Proceedings of The 9th Asian Conference Machine Learning (ACML), pages 279-294, 2017. 17
11

---

[36] Vu Nguyen, Vaden Masrani, Rob Brekelmans, Michael Osborne, and Frank Wood. Gaussian process bandit optimization of the thermodynamic variational objective. Advances in Neural Information Processing Systems, 33, 2020.
[37] José Nogueira, Ruben Martinez-Cantin, Alexandre Bernardino, and Lorenzo Jamone. Unscented Bayesian optimization for safe robot grasping. In 2016 IFEE/RSI International Conference on Intelligent Robots and Systems (IROS), pages 1967-1972. TEEE, 2016.
[38] Sebastian Nowozin, Botond Cseke, and Ryota Tomioka. f-gan: Training generative neural sam- plers using variational divergence minimization. In Advances in Neural Information Processing Systems, pages 271-279, 2016. 15
[39] Rafael Oliveira, Lionel Ott, and Fabio Ramos. Bayesian optimisation under uncertain inputs. In The 22nd International Conference Artificial Intelligence and Statistics, pages 1177-1184. PMLR, 2019. 2
[40] Jack Parker-Holdet Vu Nguyen, and Stephen J Roberts. Provably efficient online hyperparam- eter optimization with population-basee bandits. Advances in neural information processing systems, 12:17200-1221,, 2020.
[41] Valerio Perrone, Huibin Shen, Aida Zolic, laroslav Shcherbatyi, Amr Ahmed, Tanya Bansal, Michele Donini, Fela Winkelmolen, Rodolphe Jenatton, Jean Baptiste Faddoul, et al. Amazon sagemaker automatic model tuning: Scalable gradient-free optimization. In Proceedings of the 27th ACM SIGKDD Conference Knowledge Discovery & Data Mining, pages 3463 3471,, 2021.
[42] Hamed Rahimian and Sanjay Mehrotra. Distributionally robust optimization: A review. arXiv preprint /908.0099950 2019. 4
[43] Carl E Rasmussen and Christopher K Williams. Gaussian Processes for Machine Learning. MIT Prees, 2006. 3, 8, 14
[44] Binxin Ru, Ahsan Alvi, Vu Nguyen, Michael A Osborne, and Stephen Roberts. Bayesian optimisation over multiple continuous and categorical inputs. In International Conference on Machine Learning, pages 8276-8285. PMLR, 2020.
[45] Igal Sason and Sergio Verdú. f-divergence inequalities. IEEE Transactions on Information Theory, 62(11):5973 6006, 2016.
[46] Herbert E Scarf. A min-max solution of an inventory problem. Technical report, RAND CORP SANTA MONICA CALIF, 1957.
[47] Pier Giuseppe Sessa, Ilija Bogunovic, Maryam Kamgarpour, and Andreas Krause. No-regret learning unknown games with correlated payoffs. Advances in Neural Information Processing Systems, 32:13624- 13633, 2019. 2
[48] Soroosh Shafieezadeh-Abadee Daniel Kuhn, and Peyman Mohajerin Esfahani. Regularization via mass transportation. Journal of Machine Learning Research, 20(103): 1-68, 2019. 2,
[49] Bobak Shahriari, Kevin Swersky, Ziyu Wang, Ryan P Adams, and Nando de Freitas. Taking the human out of the loop: A review of Bayesian optimization. Proceedings of the IEEE, 104(1):
148-175, 2016. 3, 14
[50] Alexander Shapiro. Distributionally robust stochastic programming. SIAM Journal Opti- mization, 2754)225588 2017.
[51] Alexander Shapiro, Enlu Zhou, and Yifan Lin. Bayesian distributionally robust optimization. SIAM Journal on Optimization, 3399):279-11004 2023. 2
[52] Niranjan Srinivas, Andreas Krause, Sham Kakade, and Matthias Seeger. Gaussian process opti- mization the bandit setting: No regret and experimental design. In International Conference on Machine Learning, pages 1015-1022, 2010. 1, 6, 8, 16, 17, 20
12

---

[53] Matthew Staib and Stefanie Jegelka. Distributionally robust optimization and generalization kernel methods. In Advances Neural Information Processing Systems, pages 9131-9141, 2019. 2,
[54] Sebastian Shenghong Tay, Chuan Sheng Foo, Urano Daisuke, Richalynn Leong, and Bryan Kian Hsiang Low. Efficient distributionally robust bayesian optimization with worst-case sensitivity. In International Conference Machine Learning, pages 21180-21204 PMLR, 2022. 3,4
[55] MC Tran, V Nguyen, Richard Bruce, DC Crockett, Federico Formenti, PA Phan, SJ Payne, and AD Farmery. Simulation-baser optimisation quantify heterogeneity of specific ventilation and perfusion in the lung by the inspired sinewave test. Scientific reports, 11(1):1-10, 2021.
[56] Tsuyoshi Ueno, Trevor David Rhone, Zhufeng Hou, Teruyasu Mizoguchi, and Koji Tsuda. Combo: an efficient Bayesian optimization library for materials science. Materials discovery, 18-21, 2016.
[57] Nienke ER van Bueren, Thomas L Reed, Vu Nguyen, James G Sheffield, Sanne HG van der Ven, Michael Osborne, Evelyn H Kroesbergen, and Roi Cohen Kadosh. Personalized brain stimulation for effective neurointervention across participants. PLOS Computational Biology, 1709):e008888, 2021.
[58] Cédric Villani. Optimal transport: old and new, volume 338. Springer Science Business Media, 2008. 15
[59] Xingchen Wan, Cong Lu, Jack Parker- Holder, Philip Ball, Vu Nguyen, Binxin Ru, and Michael Osborne. Bayesian generational population-based training. In International Conference on Automated Machine Learning, pages 14-1. PMLR, 2022.
[60] Zi Wang and Stefanie Jegelka. Max-value entropy search for efficient Bayesian optimization. In International Conference on Machine Learning, pages 3627-3635, 2017. 9
[61] Jingzhao Zhang, Aditya Krishna Menon, Andreas Veit, Srinadh Bhojanapalli, Sanjiv Kumar, and Suvrit Sra. Coping with label shift via distributionally robust optimisation. International Conference Learning Representations 2021. 19
13


Reviews:
[{"review_id": "DGSgOy8zae", "reviewer": "Reviewer_1hSk", "summary": "This paper provides distributional robustness in the context of the Bayesian Optimization (BO) problem. Although there is existing work in this field, such work is rudimentary, and the authors develop a more general theory that works with generic $\\varphi$-divergence-based ambiguity sets. The proposed algorithm works with familiar $\\varphi$ functions, and furthermore, the authors derive closed-form expressions specifically for total variation, $\\chi^2$, and KL-divergence functions. They then adopt existing Gaussian process-based BO solvers for the function evaluations in the reformulated expressions and derive a sublinear regret bound which differs from the existing BO regret bounds due to a new term that is the \"price of distributional robustness\". ", "questions": "- In the abstract and the following, could the authors please elaborate on `sublinear regret' -- sublinear in what? There are contexts and ambiguity (hyper)parameters.\n\n- Page 2, citation 48 is missing brackets.\n\n- Page 2, \"as one would expect\": why? There are many studies showing it does not necessarily give complicated problems.\n\n- Page 2, \"several baselines\": could the authors please be more specific?\n\n- Page 2: I don't think the first contribution listed is new. It is already established that the inner problem can be dualized in the majority of the literature. \n\n- Whenever \"performs best empirically\" is mentioned, could the authors please specify if this is out-of-sample?\n\n- In general, \"why distributional robustness\" instead of robust optimization (e.g., in the GP setting one can also think $c$ additively perturbed) is not discussed. I see the relevance, but just a discussion could be useful.\n\n- Similarly, why $\\phi$-divergences but not Wasserstein-balls? The former has some difficulties in real-life low-data settings due to the support constraints. \n\n- Section 3, \"receives a context $c_t$\": could the authors please clarify that this is independent of $x$?\n\n- Page 3, \"full uncertainty information with any prediction\": not clear\n\n- Footnote 2: please define which the \"majority of considered examples\" are.\n\n- Equation (3): firstly it is said that the interest of DRO is to \"compute\" the function, but isn't it to \"optimize\" it? There might be an $\\inf$ missing here. I don't follow why the expectations are indexed by $q(c)$ but not $q$. Afterward, it is said to be intractable, but again, there are many traceability results under different assumptions -- this is not a thorough summary.\n\n- Please also define that $\\mathbb{E}$ is over the empirical distribution; otherwise, the problems on page 4 do not have a meaning.\n\n- $p_t$ is the reference distribution: maybe state that it is the empirical distribution and give some consistency properties of this.\n\n- Page 4, $B_{\\varphi}^t(p)$: is $p$ supposed to be $p_t$?\n\n- Theorem 1, \"measurable\": according to which measure? \n\n- Theorem 1: can you please add a discussion of whether there is anything used about BO (I think not)? If not, then please let the user know that this formulation still needs computation of $f$ and for this purpose, you will revise the UCB-related algorithms from the literature.\n\n- Page 5, \"existing BO advancements\": please cite.\n\n- Examples 1-2: are these simply replacing the conjugate or are there further steps? Would be great to clarify.\n\n- Example 2: Could the authors please comment on the computational complexity of this problem?\n\n- Example 1, \"very easily implemented\": this reads a little subjective here. Please try to formalize.\n\n- Page 6, \"convenient in the theoretical analysis\": perhaps it should be 'convenience'?\n\n- I would recommend having more discussion on the second term of Theorem 2 and try and bring some insights. \n\n- Minor: In the appendix, there is a part where there is \"to to\" twice.\n\n- Why are the KL divergence results pushed to the appendix? I would have thought for most people that could be the most interesting divergence.", "limitations": "The limitations are clearly addressed in the paper. ", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "I think the paper is clear and the reader is not getting distracted. The language is clear. There are no under/overpromises. The proofs are correct to my understanding. I believe the proof of Theorem 2 is sound. I also like the discussion after Theorem 1 on how the Variance term can be related to the existing DRO papers that relate distributional robustness to some variants of regularization. ", "weaknesses": "The largest weakness in my view is the lack of a DRO literature review. The current literature review is based on BO, but regardless of what structure $f$ has (black-box or anything else really), there are thousands of papers out there, and especially $\\varphi$-divergence is an overstudied topic. I find it hard to be convinced that Theorem 1 is useful or novel. Almost none of the papers reviewed in the \"Distributionally Robust Convex Optimization\" paper by Wiesemann, Kuhn, and Sim are cited. \n\nMoreover, half of the paper is on DRO, but I don't see a connection to BO. It looks like there are two separate fields, and the connection is light. Especially Algorithm 1, if I am not wrong, already standard in the BO literature and the contribution looks like the derivation of $\\alpha(x)$.\n\nI have further suggestions and questions below.\n\nI am giving a slight acceptance decision conditional on a more thorough literature review in the rebuttal period that would potentially convince me and the readers. Except for that, I would like to thank the authors for this work and the clean paper.\n\n**Update:** The score is updated from 5 to 6. Please see the discussions.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your review and generally positive inclination of our paper regarding the clarity and novelty of our work. We apologize for the lack of references with respect to DRO and we will fix this. Indeed, Theorem 1 at a technical level may not be novel however its application Bayesian Optimization certainly is in this current form. We will cite all work from \"Distributionally Robust Convex Optimization\"  and references therein.\n\n---\n\nQuestion: In the abstract and the following, could the authors please elaborate on `sublinear regret' -- sublinear in what? There are contexts and ambiguity (hyper)parameters.\n\nAnswer: Here, we are referring to sublinear with respect to the number of iterations T similar to Kirschener et. al, Thank you for bringing this to our attention as our bounds have several other parameters at play.\n\n---\n\nQuestion: Page 2, \"as one would expect\": why? There are many studies showing it does not necessarily give complicated problems.\n\nAnswer: Indeed, however we only mean it is complicated if we are solving the DRO problem in BO exactly and directly by tackling the minimax problem since one needs to minimize while also maximizing the objective - this could lead to an unstable solution.\n\n---\n\nQuestion: In general, \"why distributional robustness\" instead of robust optimization (e.g., in the GP setting one can also think  additively perturbed) is not discussed. I see the relevance, but just a discussion could be useful.-divergences but not Wasserstein-balls? The former has some difficulties in real-life low-data settings due to the support constraints.\n\nAnswer: Yes this is a fair point. We focus on robustness at the distributional level and  phi-divergences largely due to their smooth properties such that we can exploit Fenchel duality. \n\n---\n\nQuestion: “is $p$ supposed to be $p_t$”\n\nAnswer: Yes, this is a typo.\n\n---\n\nQuestion “Theorem 1, \"measurable\": according to which measure?”\n\nAnswer: This is respect to the Borel measure so measurability becomes quite a mild condition.\n\n---\n\nQuestion: “Theorem 1: can you please add a discussion of whether there is anything used about BO (I think not)? If not, then please let the user know that this formulation still needs computation of f and for this purpose, you will revise the UCB-related algorithms from the literature.\n\nAnswer: Indeed, there is nothing specific to BO here; however the results specific to UCB and BO in combination with Theorem 1 appear in our regret analysis in Theorem 2. Thank you for pointing this out, we can have more of a discussion there stating this fact. \n\n---\nQuestion “Examples 1-2: are these simply replacing the conjugate or are there further steps? Would be great to clarify.\n\nAnswer: Yes these are specifically replacing the conjugates and further simplifying the expressions.\n\n---\nQuestion: Example 2: Could the authors please comment on the computational complexity of this problem?\n\nAnswer: For the acquisition function, this is equivalent to Equation (5) where one needs to find the min and max values across all observed contexts, and therefore is linear in the number of observed contexts.\n\n---\nQuestion: “Why are the KL divergence results pushed to the appendix? I would have thought for most people that could be the most interesting divergence.”\n\nAnswer: While our result does apply to the KL divergence, we get readily available closed forms for chi-squared and total variation as seen by the second term which forms a regularization term, which the KL divergence does not reduce to.\n\n---\nThank you for your additional comments on improving clarity and presentation. We agree that it would be interesting to have a discussion around the regularization term and the effect it was. We will also pay more respect to the DRO results as you have stated, and hope that we have addressed your concerns!"}, {"review_id": "GgXwthZqeZ", "reviewer": "Reviewer_Yhe4", "summary": "The paper proposes a new approach for Distributionally Robust Bayesian Optimization. The paper address the problem of data shift in phi divergence which generalizes better than previously studied types and subsumes other known divergences categories including chi^2 divergence, Total Variation, and the extant Kullback-Leibler. The paper proposes new expressions for acquisition functions under two types of divergences ( chi^2 divergence, Total Variation), A theoretical analysis showing the problem reduction to a minimization problem, and a regret-bound analysis.  ", "questions": "+ It is not clear if, for the experiments in figures 3 and 4, the \\epsilon was varied based on its theoretical expression or was set to a fixed value in advance\n\n+ Is there a reason for omitting some of the baselines including StableOpt from the wind power experiment and the computational time comparison? \n\n+ Why is the impact of the hyperparameter C studied only for the wind power experiment? \n\n\nPlease refer to the weaknesses ", "limitations": "Limitations are discussed", "rating": 7, "confidence": 3, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "+ The paper provides a theoretical analysis that reduces the computationally intractable problem of data shift in the context of BO to a tractable simple optimization problem. \n\n+ The paper is overall well-written and self-sufficient. The preliminaries section covers the needed technical definitions for the rest of the paper for readers unfamiliar with the problem details. Writing can be enhanced by adding comparison and discussion about contextual BO. \n\n+ Interesting and technically solid paper. The final acquisition function expressions are simple yet the impact and generality of the approaches to the new types of divergences are important. I consider this an advantage since it becomes more amenable to execution. \n\n+ The paper provides an adaptive expression for the acquisition function hyperparameter \\epsilon leading to a hyperparameter \"free\" approach when there is no prior knowledge from the user about the suitable value of \\epsilon.", "weaknesses": "+ There is common motivation with contextual BO beyond the robustness literature. This is clear in the motivation but seems to be ignored later as relevant methods for comparison both on the qualitative and quantitative levels. Please address this part. I believe it is crucial and might be confusing to readers who are familiar with only one line of work and not the other. \n\n+ The experimental setup is limited in terms of baselines and applications:\n      +  The baselines from Regular BO included only one acquisition function.\n      +  The StableOpt baseline was omitted from the power wind experiment and computational time comparison. \n      +  There are only two synthetic experiments and two real-world experiments. \n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your review and inclination to accept this paper. We will include additional motivation for contextual BO and hope that the below answers address your concerns regarding the experiments.\n\n---\n\nQuestion: “It is not clear if, for the experiments in figures 3 and 4, the \\epsilon was varied based on its theoretical expression or was set to a fixed value in advance”\n\nAnswer: Indeed, the \\epsilon is set following the theoretical expression (defined in Lines 273-274) in Figures 3 and 4.\n\n---\n\nQuestion: “Is there a reason for omitting some of the baselines including StableOpt from the wind power experiment and the computational time comparison?”\n\nAnswer: We omit the plot for StableOpt in the Wind Power to avoid occlusion from the plots as well as focusing on the behaviors of different DRBO variants.\n\n---\n\nWe will include the computational time comparison for StableOpt which relies on the worst outcome which can be readily estimated from the GP surrogate model. Therefore, StableOpt is quite efficient, like the standard BO, in terms of computational complexity.\n"}, {"review_id": "rq2povoiWV", "reviewer": "Reviewer_xPHX", "summary": "This work studies distributionally robust Bayesian optimization (DRO-BO) problems with $\\varphi$-divergences which cover $\\chi^2$-divergence, total variation distances and KL divergence. The authors show that the minimax DRO-BO problem has an equivalent minimization problem, and propose an algorithm for solving the special cases of $\\varphi$-divergences. They complement their theoretical results with numercial experiments comparing against existing methods.", "questions": "N/A.", "limitations": "Yes, the authors have addressed the limitations according to the checklist.", "rating": 5, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "* This work presents an interesting perspective of DRO-BO by offering a reformulation into an equivalent minimization problem through convex conjugates, which opens up possibilies of efficient algorithms for solving DRO-BO.", "weaknesses": "I have no major concerns.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your time in reviewing and positive comments towards our work."}, {"review_id": "7gu85YH8RK", "reviewer": "Reviewer_DEDT", "summary": "In this paper the authors extend the domain of distributionally robust bayesian optimization (DRBO) as introduced by Kirschner et al. to the case of distributions with continuous support. The focus on the case of $\\phi$-divergences and show that for these problem then DRBO problem can be reformulated in closed form using the convex conjugate of the function $phi$. They then focus on the case of $\\chi^2$-divergence and the total variation metrics and show that the distributionally robust reformulations for these problems are equivalent to regularization problems. For the general case they also provide a bound on the robust regret, The conclude by illustrating their methods through numerical experiments. \n\n", "questions": "1. I would be interested in knowing if the authors have tried to identify the structure of the worst case distribution. \n2. It would also be interesting to know how many of the $phi$-divergences can be converted into regularization problems. ", "limitations": "Not applicable. ", "rating": 8, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The results provided by the authors are novel extend the applicability of distributionally robust optimization significantly and as such form a significant contribution. \nThe paper is well written and clearly illustrates the key concepts. \n\n**Additional Comments**\n\nMost existing work that looks at distributionally robust optimization with continuous support focuses on problems with finite distributions. In this paper the authors have focused on the case of continuous support which is significantly more challenging. For this setting they have provided a general robust reformulation along with specific reformulations for specific uncertainty sets. These new reformulations cane be optimised by straightforward first order methods without compromising on the structure of the original problem. They is a key novel contribution of their work.\n\n", "weaknesses": "The numerical results while interesting didn't seem to address the benefits of extending the results to continuous support as compared to discrete support. Since this is a key contribution of this paper it would be better to see results illustrating the benefit of this. \n\n**Additional Comments** \n\nAs I said in my previous review, the numerical experimented presented by the authors seem to present a general comparison against robust methods. While this is okay, I feel it misses the key point of the work which I feel to be the reformulation of DRO problem with continuous support. As such I would have been better for the paper if the authors had numerically illustrated the benefit of such a reformulation over a continuous set. For example, is reformulation over this continuous support set better then simply reformulating over a finite set created using samples.\n\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your positive review and noting our key contributions. Regarding our numerical experiments: since existing methods only focus on finite context sets, we showcase the benefits of our methods on such datasets. We then present an additional experiment on a continuous context where $p_t$ is selected to be uniform over $[0,1]$ where we do show that indeed, reformulating over continuous support sets is better than simply creating a finite set using samples. \n\n---\n\nQuestion: I would be interested in knowing if the authors have tried to identify the structure of the worst case distribution.\n\nAnswer: In the case of KL-divergence, the worst-case distribution will resemble an exponential family whose base measure is center distribution which has been studied in the context of label-shift such as in [1]. For general $\\varphi$-divergences, we suspect the distribution will be some generalization of this under differentiable assumptions on $\\varphi$.\n\n---\n\nQuestion: It would also be interesting to know how many of the $\\phi$-divergences can be converted into regularization problems.\n\nAnswer: This is a very good question since under the assumption of $\\varphi$ being twice differentiable, a well-known study on $\\varphi$-divergences (see [2] and Remark 4 of [3]) has shown that $\\varphi$ (via Taylor expansion) can be approximated with the chi-squared divergence. Since the chi-squared divergences yields a variance regularization term, an approximation argument under the assumption that $\\varphi$ is twice-differentiable, will lead to regularization. Therefore, we conjecture under smooth choices of $\\varphi$, DRO-BO admits a regularization interpretation. Thank you for this point, we will add this discussion into the paper.\n\n---\n\n[1] Zhang, J., Menon, A., Veit, A., Bhojanapalli, S., Kumar, S., & Sra, S. (2020). Coping with label shift via distributionally robust optimisation. arXiv preprint arXiv:2010.12230.\n\n[2] Nielsen, F., & Nock, R. (2013). On the chi square and higher-order chi distances for approximating f-divergences. IEEE Signal Processing Letters, 21(1), 10-13.\n\n[3] https://people.lids.mit.edu/yp/homepage/data/LN_fdiv_short.pdf\n"}, {"review_id": "eGK924rjk9", "reviewer": "Reviewer_NSv3", "summary": "The authors extend the framework of distributionally robust Bayesian optimization to the case where the distribution distance notion amounts to $\\phi$-divergences, which encompasses the Kullback-Leibler divergence, total variation and $\\chi^2$-divergence. In particular, the paper aims at  providing a computationally tractable algorithm for the maximization of a reward function that additionally depends on a context parameter that is drawn from a distribution with respect to which the procedure is supposed to be distributionally robust.\n\nThey build on the paper [23] by Kirschner et al., where a similar problem was considered and where an efficient algorithm based on convex optimization was developed for the said problem if robustness is considered with respect to the maximum mean discrepancy distance.\n\nThe main result of the paper is Theorem 1, which allows to rewrite the maximization of the distributionally robust objective (DRO) as maximization of a standard stochastic optimization objective correct by a variance term in the cases of total variation and $\\chi^2$-divergence. This is the result of a characterization of the infimum in the DRO using complex conjugates of the $\\phi$-function. Furthermore, a robust regret bound is derived and some numerical experiments are conducted for simple, standard reference function such as the Rosenbrock and cosine functions.", "questions": "- Why is the maximum information gain defined differently than in Kirschner et al.? Elaborate.\n- Please rework the presentation of the manuscript to better clarify the underlying assumptions, missing definitions and to address grammar issues.\n- The motivation of the comparisons of the different DRBOs in Figure 2 and Figure 3 is currently unclear: The different curves correspond to different settings (balls of distributions with respect to different distance notions). Why is interesting to put the robust regret values into the same plots?\n- Why is it claimed that the algorithm works in the continuous context regime, when the quantities defining the acquisition functions assume finiteness of the context set?\n- Could you comment on the computational complexity with respect to the dimensionality or size of the input space? In the preliminaries, it is assume that the input space lives in a d-dimensional ambient space. Does d play any role in quantities estimated in the paper?\n- The paper would benefit from an elaboration on the significance of the regret bound. In this context, why is the robust regret a meaningful metric to measure the success of the procedure? Considering the definition of the DRBO problem, it might be beneficial to rather consider the (robust) objective value error of the last iteration T.\n- \"In particular, we also present a similar analysis, showing that the robust regret decays sublinearly for the right choices of radii.\" It is unclear to me why the regret bound from Theorem 2 corresponds to any type of decay. ", "limitations": "The authors mention the question of the appropriate choice of the distributional robustness distance for specific settings as future work.", "rating": 3, "confidence": 4, "soundness": 2, "presentation": 2, "contribution": 3, "strengths": "The main strength of the paper lies from my view in the fact that the authors provide tractable characterizations of the distributionally robust objective (see page 4) if the distributional robustness is measured with respect to the KL, total variation and $\\chi^2$-divergences. I consider the computations that lead to these characterizations to be technically sound.\n\nThis extends prior work by Kirschner et al. that considered only distributional robustness with respect to the maximum mean discrepancy.\n", "weaknesses": "A main weakness of the submission is that despite the claim that its results go beyond the finiteness assumption on the set of contexts  [23], this is not the case: In the definition of (4) and (5), the size of the set (which is called space) of contexts is implicitly assumed to be finite due to the summation over c and the division by the cardinality |C| of the context set.  This can be, for example, also seen in line 168 of page 4 where the finiteness assumption on the reference distribution is made explicit. A clarification or weakening of the claims that is necessary from my point of view.\n\nFor a through understanding of the bound on the robust regret presented in Theorem 2, a clear comparison to the bounds obtained in other papers such as [23] would be desirable.\n\nThe experiments that are considered appear rather consider very low-dimensional functions without a clear link to a machine learning related topic.\n\nThe presentation of the paper lacks some clarity and suffers from challenges in its use of the English language. Furthermore, at several occasions, notation is used that is not explained or only much later in the manuscript. We list a few issues below:\n- Second sentence is not grammatically correct\n- \"computed, however cannot be replaced by another choice of D whose closed form is not readily accessible with samples such as the ϕ-divergence\"\n- \"samples such as the $\\phi$-divergence\n- $\\varepsilon$ without dash in line 70, page 2\n- superfluous bracket in p. 3, line 119\n- \"include the Wasserstein\". Probably some sort of Wasserstein distance is referred to here, but is so far unclear\n- \"Total Variance\", line p.4, line 153\n- The convex conjugate would profit from an appropriate evaluation\n- \"the same optimization problem\" To which comparison optimization problem is this referencing?\n- \"that\" missing on p.6, line 253\n- In (4) and (5), a lot of quantities are not defined, including $\\mu_t$, $\\beta_t$ (in the mentioned reference [47], that parameter is not defined explicitly either) and $\\sigma_t$. \n- It is unclear what is needed exactly in Algorithm 1 to run the algorithm. Do we need to know the values of $\\varepsilon_t$, the reference distribution p_t, the kernel?\n- P. 3, line 106: $\\mathcal{X} \\in \\mathbb{R}^d$ is probably not correct here\n\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your review and pointing out the computational superiority of our method with the phi-divergence generalization. Indeed, while our work attempts to alleviate the finiteness of contexts assumption, we provide some clarification and discussion below regarding the discretization argument which will be added to the updated version - we appreciate your concern in bringing this up.\n___\nQuestion: “Do we need to know the values of , the reference distribution $p_t$, the kernel?”\n\nAnswer: Yes, these are required to compute the quantities.\n___\nQuestion: “Why is the maximum information gain defined differently than in Kirschner et al.? Elaborate.”\n\nAnswer:  The minor difference between maximum information gain in our paper and Kirschner et al. is the noise variance term $\\sigma{-2}$ for which we follow the original maximum information gain presented in Srinivas et. al.\n___\nQuestion: “Why is it claimed that the algorithm works in the continuous context regime, when the quantities defining the acquisition functions assume finiteness of the context set?”\n\nAnswer:  The theorem we develop makes no finiteness assumption of the context space and so in theory when using the proposed objective, we will be robust to other distributions with continuous support. As you mention we discretize to estimate the expectation and variance terms in practice, which seemingly appears to violate this. However, noting that since the acquisition functions are all bounded (by a constant M, which is standard as in BO), an elementary application of McDiarmind’s inequality [1] allows us to bound the difference between the discretized variation and continuous one by a factor of $O\\left(\\frac{M}{\\sqrt{n_D}}\\right)$ (with high probability) where $n_D$ is the number of discretizations we perform. Therefore, the discretization forms a very close approximation to the true quantities in Theorem 1 and can apply to continuous context regimes such as $C = [0,1]$. We remark that a similar argument can be applied to Kirschener et. al. regarding continuous contexts however will require solving a linear program whose variable size is of $O(n_D)$, and thus a linear program solver will be very expensive. Therefore, the number of discretizations in their work cannot be too large. In contrast, we can perform a much more fine-grained discretization since we have a simple expression for our DRO objective, which can be computed in linear time $O(n_D)$. Thank you for this point, we believe this discussion will clarify and strengthen the contribution.\n\n[1] Doob, J. L. (1940). \"Regularity properties of certain families of chance variables\" (PDF). Transactions of the American Mathematical Society. 47 (3): 455–486. doi:10.2307/1989964. JSTOR 1989964.\n___\n\nQuestion: Could you comment on the computational complexity with respect to the dimensionality or size of the input space? In the preliminaries, it is assumed that the input space lives in a $d$-dimensional ambient space. Does $d$ play any role in quantities estimated in the paper?\n\nAnswer: the optimization complexity grows with the input dimension d. When d increases, our regret bound is loose. In Theorem 2, when $d$ increases, the maximum information gain \\gamma_t (defined in Line 267, 268) will increase with d and thus the upper bound will worsen.\n___\nQuestion: It is unclear to me why the regret bound from Theorem 2 corresponds to any type of decay.\n\nAnswer: We refer to this as \"decay\" since if one chooses $\\varepsilon_t = \\Gamma_{\\varphi}^{-1}\\left(\\frac{1}{\\sqrt{t} + \\sqrt{t+1}}\\right)$, then the overall regret becomes will yield a rate of $\\sqrt{T}$ which is considered state-of-the-art.\n\n___\nQuestion: “The paper would benefit from an elaboration on the significance of the regret bound. In this context, why is the robust regret a meaningful metric to measure the success of the procedure? Considering the definition of the DRBO problem, it might be beneficial to rather consider the (robust) objective value error of the last iteration $T$. “\n\nAnswer: we have followed the literature in BO/DRO to use the cumulative robust regret as a metric. Thank you for the suggestion. However, we think the robust objective value at the last iteration T may not be appropriate because the last point is not necessarily the optimal solution of the problem and we do not pick the last point, i.e. $x_T$ as the final $\\arg\\max f(\\cdot)$.\n___\n\nWe feel we have addressed all of the concerns raised. If this is not the case, please let us know so that we can have the opportunity to discuss further.\n"}]

Author rebuttal:
We would like to thank the reviewers for their time and efforts in reviewing our work. The reviewers are majority in acceptance of the work, as they have noticed our main contribution which is to provide “a theoretical analysis that reduces the computationally intractable problem of data shift in the context of BO to a tractable simple optimization problem.” (Reviewer Yhe4), develop an “efficient algorithm for solving DRO-BO” (Reviewer xPHX) specifically “on the case of continuous support which is significantly more challenging” (Reviewer DEDT) which “extends prior work by Kirschner et al. that considered only distributional robustness with respect to the maximum mean discrepancy.” (Reviewer NSv3). Thus the reviewers have particularly commended the novelty and clarity. However, it has come to our attention that there are certain points of clarifications regarding the discretization of contexts and missing references that the reviewers have pointed out. We will add these points and hope we have addressed the concerns of the reviewers. If this is not the case, please let us know so that we can have the opportunity to discuss further.

Meta-review: This meta review is based on the reviews, the authors rebuttal and the discussions with the reviewers, discussions with the SAC, and ultimately my own judgement on the paper. There was a consensus that the paper contributes sound and interesting contributions. I feel this work deserves to be featured at NeurIPS and will attract interest from the community. I would like to personally invite the authors to carefully revise their manuscript to take into account the remarks and suggestions made by reviewers - in particular, making the paper more friendly to DRO researchers and highlighting their contributions in DRO and BO. Congratulations!
Decision: Accept (poster)