1 Introduction↩︎

Zeroth order non-convex optimization, also variously known as continuous multi-armed bandit or black-box optimization, is an important problem that naturally appears in various domains like dynamic pricing [2], reinforcement learning [3] and material science[4]. With an unknown black-box function \(f:\mathcal{X}\rightarrow \mathbb{R}\), zeroth order optimization aims to find the optimal point of the function with as few queries to (a noisy version of) \(f(x)\) as possible, with no gradient information directly available. Although zeroth order convex optimization is generally efficient [5], optimizing a non-convex \(f\) under smoothness constraints requires the same effort as estimating \(f\) almost everywhere, and usually leads to a query complexity exponential in \(d\), where \(d\) is the feature space dimensionality[6]–[10]. The prohibitive cost for non-convex optimization has motivated research on suitable assumptions, such as linear bandits [11], convex approximations [10], and optimization based on level sets [10], [12]. We propose a complementary approach, where in addition to direct queries to \(f\), one can also compare two points in feature space, and obtain the point with a larger \(f\) value. Inspired by dueling bandits in the bandit domain [13], we call our setting non-convex optimization with dueling-choice bandits; we note that different than dueling bandits, here direct queries and comparisons are both available for optimizing \(f\), and therefore duels are available as an additional choice.

In many applications, comparisons can be available at a cheaper price than direct queries. For example in preference elicitation, the user can give scores on recommended items, as well as (more easily) compare two items to choose the preferred one. Similarly, for hyperparameter search of information retrieval (IR) models, direct queries typically involve collecting relevance scores from paid workers, whereas comparisons can be obtained by interleaving the ranking of two different models, and observing user click on the retrieval results [14]. Such comparisons usually come with less cost in both time and money. As another example, in material synthesis, we aim to optimize the desired properties of materials by controlling the input parameters (temperature, pressure, etc.) [4], [15]. While material synthesis is expensive, comparisons can be carried out by asking material scientists. Related Work. There is a vast literature on zeroth order non-convex optimization [6]–[10], [16], [17]. We build our work on GP-UCB[1], a method for optimizing unknown functions under the Gaussian process (GP) assumption by optimizing the Upper Confidence Bound (UCB). Closest to our setting is a line of recent research on multi-fidelity GP optimization [18]–[20], which assumes that we can query the target functions at multiple fidelities of different costs and precisions. We detail the relation and difference of our setting with multi-fidelity optimization in Section 3.6. To briefly describe it, our setting is harder since we cannot directly query the function on which comparisons are based. Moreover, the multi-fidelity assumptions such as fidelities being close in sup-norm do not hold for our setting since any constant shift of the comparison function yields the same comparisons. We instead consider an active transfer learning setting where information from a function that can be learned using comparisons is transferred actively to optimize the target function (refer to Section 2 for details).

Optimization with comparisons has been studied under the framework of derivative-free optimization [5], [21] and continuous dueling bandits [22], [23]. Kumagai [21] obtains optimal regret rates for a convex \(f\). However to the best of our knowledge, no previous work has theoretical guarantees on optimizing a non-convex \(f\). Also, these results cannot be applied when the comparisons are biased (i.e., a Condorcet winner on comparisons might not be the best point for direct queries).

Finally, there is another line of research that combines direct queries and comparisons for classification or regression problems [24]–[26]. Our methods differ from theirs because we focus on the optimization setting, and only care about points near the optimum. These methods make direct queries across the whole feature space to learn the underlying function well, which is unnecessary for optimization.

Our Contributions. We develop and evaluate a new algorithm for non-convex optimization with dueling choices, which we refer to as Comparison-based GP-UCB (COMP-GP-UCB). Our theoretical and experimental results show the strengths of our algorithm.

• When we can obtain comparisons based on the target function \(f\), we show that comparisons can be as powerful as direct queries: COMP-GP-UCB can achieve the same rate of convergence as its label-only counterparts, while using only comparisons and no direct queries. This solves the open problem raised in [23], to develop continuous dueling bandit algorithms with no-regret guarantees.

• Next, we assume that comparisons are based on a misspecified function \(f_c\), where \(f_c\) approximates \(f\). COMP-GP-UCB in this case uses comparisons to optimize a function \(f_r\) which has the same optimizer as \(f_c\), and then use direct queries to search in a smaller region for the optimum of the target function. The regret rate of COMP-GP-UCB is then better than the label-only counterparts, and it depends on the difference between \(f_c\) and \(f\): the better the approximation, the lower the regret we can get from COMP-GP-UCB. We further demonstrate a version of the algorithm that adapts to this difference. Our algorithm also extends multi-fidelity GP optimization to the setting where information is transferred actively from a lower fidelity to a higher fidelity while only assuming that the optimizer of the lower fidelity (source function) is within a constant distance of the optimizer of the higher fidelity (target function), instead of the fidelities being close everywhere.

• In our experiments, we test COMP-GP-UCB on multi-fidelity functions from previous literature and show that it outperforms label-only algorithms and existing multi-fidelity algorithms when comparisons are cheaper than direct labels.

2 Background and Problem Setup↩︎

We aim to maximize a function \(f:\mathcal{X}\rightarrow \mathbb{R}\), where \(\mathcal{X}\subseteq [0,r]^d\) is the feature space. In each iteration \(t\) of optimization, we can query (expensive) direct queries to \(f\) at a chosen point \(x_t\), and obtain \(y=f(x_t)+\varepsilon\), \(\varepsilon\in [-\eta,\eta]\) and \(E[\varepsilon]=0\), with \(\eta>0\) a known constant⁵.

Comparison Probabilities. In addition to traditional direct queries \(y\), we can obtain (cheap) comparisons for a pair of points \((x_t,x_t')\in \mathcal{X}\times \mathcal{X}\). We assume that comparisons are based on a function \(f_c\) which can be potentially different from \(f\) (as described later in this section). A common assumption in the literature is to use a link function to assume a distribution of the comparisons, i.e., we assume \(\Pr[x\succ x']=\sigma(f_c(x)-f_c(x'))\) for some function \(\sigma\). Common link functions include logistic function (BTL model[27]), or Gaussian cdf (Thurstone model [28]).

Connecting comparisons and direct queries. To make comparisons helpful for optimization, we also require that \(f_c\) is a good approximation of \(f\). Here we differentiate between two settings:

• Dueling-Choice Bandits with unbiased comparisons: We assume comparison comes from the same function as the target function, i.e., \(f_c=f\) or, more generally, that \(f_c\) and \(f\) have the same optimizer (\(\zeta = 0\) as described below). This may be the case when comparison and direct queries come from the same agent, such as the preference elicitation example in the introduction.

• Dueling-Choice Bandits with misspecified comparisons: We assume \(f_c\approx f\). In many cases, comparisons are from a different source (e.g. experts) than direct queries (e.g. experiments), and this can result in a biased \(f_c\). To this end, we assume a bounded difference near the optimum:

  Assumption 1. Let \(f^*=\max_x f(x)\) and \(f_c^*=\max_x f_c(x)\). There exists a constants \(\zeta\) such that for any point \(x\in \mathcal{X}\) we have \(|(f_c^*-f_c(x)) - (f^*-f(x))|\leq \zeta\).

  In words, when we get \(\varepsilon\)-close to the maximum of \(f\), we are at least \((\varepsilon+\zeta)\)-close to the maximum of \(f_c\), and vice versa. Under this assumption, we would require both comparison and direct queries if we want to achieve optimization error smaller than \(\zeta\).

  We note that our results can be generalized to the case where Assumption 1 only holds for \(x\in\{x: f^*-f(x)\leq \tau \}\) for some fixed constant \(\tau\).

Smoothness Assumptions. We assume that the target function \(f\) lies in a reproducing kernel Hilbert space (RKHS) \(\mathcal{H}_\kappa\) induced by kernel \(\kappa\), and that the RKHS norm of \(f\) is bounded: \(\|f\|_{\kappa}\leq B\) for a known constant \(B\). This assumption is also analyzed in [1], [29] for traditional bandits. We note that every function \(f\in \mathcal{H}_\kappa\) has a finite kernel norm. When \(\kappa\) is the linear kernel, \(\|f\|_{\kappa}\leq B\) induces that \(f\) is \(B\)-Lipschitz.

Budgets and Regrets. We analyze the problem of optimizing \(f\) under a given cost budget \(\Lambda\). Suppose a direct query costs \(\lambda_l\) units of some resource and a comparison costs \(\lambda_c<\lambda_l\). Also, let \(\overline{n}_{\Lambda}=\lceil \frac{\Lambda}{\lambda_c}\rceil\) be the upper bound on number of queries when we use all the budget on comparisons, and \(\underline{n}_{\Lambda}=\lfloor \frac{\Lambda}{\lambda_l}\rfloor\) be the corresponding lower bound when we only use direct queries. Also let \(q_t=\text{label}\) if we make direct queries at iteration \(t\), and \(q_t=\text{comp}\) otherwise. We analyze the simple regret under budget \(\Lambda\), defined as follows: \[\begin{align} & S(\Lambda)=\min_tr_t\label{eqn:regret95def}\\ &=\min_t\begin{cases} \displaystyle f^*-f(x_t) & \text{ if } q_t=\text{label},\\ \min\{f^*-f(x_t),f^*-f(x'_t)\}, & \text{ if } q_t=\text{comp}. \end{cases}\nonumber \end{align}\tag{1}\] In words, we calculate the minimum regret achieved by either comparison or direct queries. We compute simple regret over all direct queries; for comparisons, we adopt the notion of weak regret employed in [13]. Here we choose simple regret because our target is to optimize function \(f\), and cumulative regret is typically not relevant for our setting. Our method can also be easily extended to the optimizer error setting, where the algorithm gives an estimation of the optimum when it ends. In analyzing the regret rates, we use \(O(\cdot)\) to ignore constants, and \(\tilde{O}(\cdot)\) to ignore log terms in the regret bounds.

3 Algorithm and Analysis↩︎

We describe our COMP-GP-UCB algorithm in this section. We first present the Gaussian process framework on which our algorithm is based in Section 3.1. Then we present the algorithm in Section 3.3, under the assumption that \(\zeta\) is known. This includes the unbiased comparison case, where \(\zeta=0\). We present our theoretical analysis for COMP-GP-UCB in Section 3.4. Finally, we give an extension to adapt to unknown \(\zeta>0\) in Section 3.5.

3.1 The Gaussian Process Back End↩︎

We base our methods on Gaussian Process, with kernel function \(\kappa\). If \(f\) was sampled from the Gaussian process \(\mathcal{GP}(0,\kappa)\), and the direct queries were coming from \(f\) plus a Gaussian noise, i.e., \(\mathcal{D}=\{(x_i,y_i)\}_{i=1}^t\) with \(y_i=f(x_i)+\varepsilon\), \(\varepsilon\sim \mathcal{N}(0,\eta^2)\), then the posterior distribution at \(f(x)|\mathcal{D}\) would be a Gaussian \(\mathcal{N}(\mu_t(x),\sigma_t(x))\) with \[\begin{align} \mu_t(x)&=k^T(K+\eta^2I_t)^{-1}Y,\label{eqn:bayes95update}\\ \sigma_t(x)&=\kappa(x,x)-k^T(K+\eta^2I_t)^{-1}k. \nonumber \end{align}\tag{2}\] Here \(Y=(y_1,...,y_t)^T\), \(k=(\kappa(x, x_1),...,\kappa(x, x_t))^T\), and matrix \(K\in \mathbb{R}^{t\times t}\) is given by \(K_{ij}=\kappa(x_i, x_j)\), and \(I_t\) is the \(t\times t\) identity matrix.

Remark. We note that the Gaussian noise and prior is only assumed to derive updates to the mean and variance in the algorithm, and we do not assume the actual feedbacks follow a Gaussian model, nor the functions are sampled from the Gaussian process. We only assume that \(f\) have bounded norm in \(\mathcal{H}_\kappa\) and that \(\varepsilon\) is bounded in \([-\eta,\eta]\), as stated in Section 2. This is the same as the agnostic setting in GP-UCB [1], [29].

The Maximum Information Gain. As in previous works on GP [18], [29], our results will depend on the maximum information gain [1] between function measurements and the function values, defined as below:

When \(\mathcal{X}\subseteq \mathbb{R}^d\) is compact and convex, [1] shows that i) for linear kernel \(\kappa\), \(\Phi_{n}(\mathcal{X})=O(d\log n)\); ii) for squared exponential (SE, or RBF) kernel, \(\Phi_{n}(\mathcal{X})=O((\log n)^{d+1})\); iii) For Matérn kernels \(\kappa(x, x')=\frac{2^{1-\nu}}{\Gamma(\nu)}(\frac{\sqrt{2\nu}z}{\rho})^\nu B_{\nu}(\frac{\sqrt{2\nu}z}{\rho})\), we have \(\Phi_{n}(\mathcal{X})=O\left(n^{\frac{d(d+1)}{2\nu+d(d+1)}}\log n\right)\).

Review of GP-UCB and IGP-UCB. Previous sequential optimization has adopted the upper confidence bound (UCB) principle, where we maintain a high-confidence upper bound \(\phi:\mathcal{X}\rightarrow \mathbb{R}\) for all \(x\in \mathcal{X}\), such that \(f(x)\leq \phi(x)\) with high probability. Our algorithm builds on UCB algorithms for GP, namely GP-UCB [1] and IGP-UCB [29] (the latter is an improvement of the former). In time step \(t\) of optimization, IGP-UCB queries the point that maximizes the confidence upper bound in the form \(\mu^{(l)}_{t-1}(x)+\beta_t\sigma^{(l)}_{t-1}(x)\), where \(\mu^{(l)}_{t-1},(\sigma^{(l)}_{t-1})^2\) are the posterior mean and variance function of the GP from step \(t-1\), and \(\beta_t\) is a multiplier that increases with \(t\). We describe these algorithms in detail in Appendix.

3.2 The Borda Function \(f_r\)↩︎

A straightforward way to incorporate comparisons into optimization is to use them to compute a GP posterior of either \(f\) or \(f_c\). However, we will face several difficulties. Firstly, the posterior based on comparisons cannot be analytically computed. Also, we cannot compute the joint posterior based on both direct queries and comparisons, since \(f\) and \(f_c\) can be different. Lastly, comparisons might not be truthful and can be inconsistent; i.e., human might give contradicting comparisons like \(x_1\succ x_2\succ x_3\succ x_1\) [30].

We instead consider a different function directly related to \(f_c\), defined as \(f_r(x)=\Pr[x\succ X]\), where \(X\) is randomly chosen from \(\mathcal{X}\). In words, \(f_r(x)\) is the probability that \(x\) beats a random point \(X\in \mathcal{X}\). We refer to \(f_r\) as the Borda function, inspired by Borda scores in the dueling bandits literature [30], [31]. An advantage of using \(f_r\) is that we can obtain unbiased estimates of \(f_r(x)\) by comparing \(x\) to a random point in \(X\in \mathcal{X}\).

It is easy to see that \(f_r\) should have the same optimizer as \(f_c\). We make the following assumption to ensure usefulness of comparisons:

In other words, difference in \(f_c\) will cause a difference of similar scale in \(f_r\). This requires that the comparisons induces a Borda function \(f_r\) such that \(f_r\) is close to \(f_c\) at its optimum, and that \(f_r\) and \(f_c\) has the same optimizer. We note that this is a quite weak assumption, as we do not restrict the result of comparing individual points \(x,x'\) to comply with \(f_c(x)-f_c(x')\), i.e., comparisons do not need to be consistent. We can show that Assumption 2 holds under the link function setting, when \(\sigma\) is Lipschitz continuous:

We comment that common link functions such as BTL [27] and Thurstone [28] all have bounded Lipschitz functions if \(f_c\) is bounded.

Lastly, we note that [22] also compare \(x\) to a random point \(X\), and use the feedback to update the function estimates. However, their method relies on a linear link function \(\sigma(x)=\frac{1+x}{2}\) and cannot be applied for BTL or Thurstone models.

3.3 Optimization with Known \(\zeta\)↩︎

When \(\zeta\) is known and given, COMP-GP-UCB is formally described in Algorithm 1. Our algorithm works both for unbiased comparisons (\(\zeta=0\)) and misspecified comparisons (\(\zeta>0\)). COMP-GP-UCB is an anytime algorithm, meaning that it does not need to know the total budget \(\Lambda\) before it begins. For any input \(\zeta\geq 0\), the high-level idea is to constrain the search region for \(f\) using comparisons to the set \(\mathcal{H}:=\{x: f_r(x) \geq f_r^* - L_2\zeta\}\) where \(f_r^* = \max_x f_r(x)\). \(\mathcal{H}\) is guaranteed to contain the optimizer \(f\) under our assumptions; To see this, let \(x^*\) be any optimizer of \(f\), and we have \(f_r^*-f_r(x^*)\leq L_2(f_c^*-f_c(x^*)) \leq L_2(f^*-f(x^*)+\zeta)=L_2\zeta.\) The first inequality follows from Assumption 2 and the second one follows from Assumption 1. It is easy to see that \(\mathcal{H}\) is much smaller than \(\mathcal{X}\) if comparisons are mostly correct (i.e., \(\zeta\) is small); therefore we can explore more efficiently by restricting the search on \(\mathcal{H}\).

COMP-GP-UCB takes as input \(\zeta\), a parameter \(\gamma\) to control exploration on comparisons, and a confidence level \(\delta\). We keep track of posteriors \((\mu^{(l)},\sigma^{(l)}), (\mu^{(r)}, \sigma^{(r)})\) for \(f\) and \(f_r\) respectively, and construct confidence intervals \(\mu^{(l)}_{t-1}(x)\pm \beta_t\sigma^{(l)}_{t-1}(x)\), \(\mu^{(r)}_{t-1}(x)\pm \beta^{(r)}_t\sigma^{(r)}_{t-1}(x)\). Since \(f_r\) is unknown, to approximate \(\mathcal{H}\), the algorithm adopts a two-phase approach: In the first phase (Step [step:firstphase]-[step:firstphaseends]), we optimize \(f_r\) using comparison queries until \(\beta^{(r)}_{t}\sigma^{(r)}_{t-1}(x_t)\leq \gamma\), i.e., the queried point has confidence of at least \(\gamma\). At the end of the first phase, we compute \(\hat{f}_r\) as a lower bound for \(f_r^*\). Next, we start the second phase exploring \(f\) (Step [step:secondphase]-[step:secondphaseends]). We select the query point \(x_t\) based on a filtering \(\phi^{(r)}_t(x)\geq 0\); the filtering approximates the constraint set \(\mathcal{H}\) by combining the current UCB of \(f_r\) and the LCB \(\hat{f}_r\) from the first phase. Then the algorithm optimizes the UCB of \(f\) under the constraint of \(\phi^{(r)}_t(x)\geq 0\). While doing this, we check the UCB of \(f_r\) at the maximizer \(x_t\) and if we are not confident about \(f_r(x_t)\), we query a comparison, or otherwise we make a direct query as in GP-UCB.

The query process is described in the procedure Query. For direct queries, we query \(x_t\) directly, and update the posterior of \(f\) according to (2 ); for comparisons, we compare \(x_t\) with a random point \(x'\), and use the result as feedback to update posterior of \(f_r\). We note that this comparison result is an unbiased estimate of \(f_r(x_t)\).

The Two-Phase Approach. Both phases are critical for the algorithm to succeed. The first phase is important in two ways: Firstly, it helps to get a low regret in the unbiased comparisons setting, and in the initial stages of the algorithm when only comparison queries are used for the biased (misspecified comparison) setting. Also, it gives a lower bound \(\hat{f}_r\leq f_r^*\) of the optimum of \(f_r\) at Step [step:lcb] which will be used to approximate the constraint set \(\mathcal{H}\). Then we use the second phase to obtain low regret in the biased comparison case.

Choice of \(\phi^{(r)}_t\). The choice of \(\phi^{(r)}_t\) is critical for the algorithm to succeed. We want that the region \(S=\{x: \phi^{(r)}_t(x)\geq 0\}\) is not too small or too large: we need that every maximizer \(x^*\) of \(f\) is in \(S\), while also excluding as many points as possible using the information from \(f_r\). To achieve the former, we have added \(L_2\zeta\) to the confidence interval to account for the difference in \(f_c\) and \(f\). To achieve the latter, we need both a good UCB of \(f_r\) and a good LCB of \(f_r^*=\max f_r(x)\). The good UCB is ensured by the check at Step [step:checkconf95p2]; we only make direct queries when we are confident enough about \(f_r(x_t)\). The good LCB is ensured by the first phase, where we compute \(\hat{f}_r\); without the first phase \(\hat{f}_r\) can be arbitrarily bad and it will lead to suboptimal direct queries. In the proof we show that when \(\phi^{(r)}_t(x)\geq 0\) and \(\beta^{(r)}_{t}(x)\sigma^{(r)}_{t-1}(x)\geq \gamma\), \(x\) belongs to an approximation of \(\mathcal{H}\). So the two constraints combined ensure that we use direct queries to explore \(\mathcal{H}\).

3.4 Theoretical Analysis↩︎

We now present our theoretical results. We defer full proofs to the appendix due to space constraints. We first analyze the unbiased comparison case. In this case, we have \(\zeta=0\), and we only need comparisons to achieve low regret. Therefore we run COMP-GP-UCB with \(\zeta=\gamma=0\); in this case, the algorithm only executes the first phase, and only uses comparisons to optimize \(f_r\). We obtain the following guarantee.

Remark. IGP-UCB [29] in the label-only setting has regret of form \[\begin{align} &S_{\text{IGP-UCB}}(\Lambda)\leq \label{eqn:regret95igp95ucb} \\ &C\left(B+\sqrt{\left(\Phi_{\underline{n}_{\Lambda}}(\mathcal{X})+\log(1/\delta)\right)}\right)\sqrt{\frac{\Phi_{\underline{n}_{\Lambda}}(\mathcal{X})}{\underline{n}_{\Lambda}}},\nonumber \end{align}\tag{3}\] where \(\underline{n}_{\Lambda}=\lfloor \frac{\Lambda}{\lambda_l}\rfloor\). This is the same form as (?? ), but with \(\overline{n}_{\Lambda}\) replaced with \(\underline{n}_{\Lambda}\). Recall that \(\overline{n}_{\Lambda}\) is the number of queries when we use all the budget on comparisons, and \(\underline{n}_{\Lambda}\) is the number for using all budget on direct queries. In other words, COMP-GP-UCBhas the same rate as IGP-UCB as if direct queries are as cheap as comparisons. When comparisons are much cheaper than direct queries, COMP-GP-UCB leads to a great advantage by significantly reducing the number of direct queries needed.

We then analyze COMP-GP-UCB in the misspecified comparison setting(\(\zeta>0\)). In this setting, comparisons act as a filter on \(\mathcal{X}\) to reduce the search region for direct queries. When \(f_c\) approximates \(f\) well (i.e., a small \(\zeta\)), the set \(\mathcal{H}=\{x:f_r(x)\geq f_r^*-L_2\zeta\}\) is much smaller than the feature space \(\mathcal{X}\). Therefore by using comparisons, we wish to replace the \(\Phi_{n_0}(\mathcal{X})\) term in (3 ) by \(\Phi_{n_0}(\mathcal{H})\), effectively exploring a smaller region. We show that COMP-GP-UCB can have a similar behavior by exploring on a slightly larger set dependent on \(\gamma\), defined as \(\mathcal{H}^{\gamma}=\{x\in \mathcal{X}: f_r(x)\geq f_r^*-L_2\zeta-4\gamma\}\). The following theorem characterizes the regret of COMP-GP-UCB under the misspecified comparison setting.

We discuss about the bounds and setup of parameters before coming to the proof of Theorem 3.

Remarks. The regret bound in Theorem 3 enjoys best of both worlds from comparisons and direct queries. The first bound has the same form as in Theorem 2 but with another \(2L_1\gamma+\zeta\) term. This comes from the first phase of COMP-GP-UCB, and the extra term comes from the fact that \(f_c\ne f\). In the second phase, the algorithm achieves the second bound \(S_2\), which is the rate of using \(\underline{n}_{\Lambda}\) direct queries to explore \(\mathcal{H}^{\gamma}\). Compared with (3 ), the second bound has the same rate on \(\underline{n}_{\Lambda}\), but with a reduced search region \(\mathcal{H}^{\gamma}\) and a startup budget \(\Lambda_0\) for comparisons to work. When \(f_c\) is a good approximation to \(f\), \(\mathcal{H}^{\gamma}\) is much smaller than \(\mathcal{X}\) and will lead to a great improvement in the number of direct queries needed.
Setup of parameters. 1. Setting \(\gamma\): \(\gamma\) acts as a threshold for exploring comparisons in both phases of COMP-GP-UCB. A small \(\gamma\) will lead to a small \(\mathcal{H}^{\gamma}\) and therefore better regret rates; but it will also make the algorithm spend more time on comparisons before moving to direct queries, i.e., a large \(\Lambda_0\). One plausible choice for \(\gamma\) is to set \(\gamma=\frac{1}{L_2}\zeta\), and this will make \(\mathcal{H}^{\gamma}\approx\mathcal{H}\).
2. Setting \(\beta_{t}\): The setup for \(\beta_{t}\) in Theorem 3 requires knowing \(\Phi_{t}(\mathcal{H}^{\gamma})\) before algorithm starts and this is unrealistic to set up. However, in practice the default choice for \(\beta_{t}\) is often very loose and hand-tuned values are used instead (e.g., Kandasamy et. al[18] uses \(\beta_{t}=0.2d\log(2t)\)). In this sense this setup for \(\beta_{t}\) does not affect its practical use. For theoretical purposes, we can also set \(\beta_t=\beta^{(r)}_t\); this leads to a regret rate of \(\tilde{O}\left(\frac{(B+\sqrt{\Phi_{\underline{n}_{\Lambda}}(\mathcal{X})})\sqrt{\Phi_{\underline{n}_{\Lambda}}(\mathcal{H}^{\gamma})}}{\sqrt{\underline{n}_{\Lambda}}}\right)\), slightly larger than the current rate but still smaller than GP-UCB.

3.5 COMP-GP-UCB with Unknown \(\zeta\)↩︎

In practice, we cannot know \(\zeta\) in general, and it is even hard to verify whether \(\|f_c-f\|_\infty \leq \zeta\) holds for a given \(\zeta\). On the other hand, we can often know an upper bound \(\zeta_{\max}\) such that \(\zeta\leq \zeta_{\max}\). For example, if we know both \(f\) and \(f_c\) are bounded in \([-B_{\infty}, B_{\infty}]\) we naturally have \(\|f_c-f\|_\infty\leq 2B_{\infty}\). However, Algorithm 1 is not useful if we set \(\zeta=2B_\infty\), because that will lead to a constraint set \(\mathcal{H}=\{x:f_r(x)\geq f_r^*-2L_2B_\infty \}\) that can be as large as \(\mathcal{X}\) and we have to explore the whole feature space with direct queries. We develop a slightly different method in Algorithm 2 that tries to search \(\zeta\) between an initial value \(\zeta_{0}\) and the upper bound \(\zeta_{\max}\), and adapts to the true \(\zeta\).

Algorithm 2 works in the finite-horizon scenario, where the budget \(\Lambda\) is given as input. The process of Algorithm 2 is mostly similar to Algorithm 1, except that it uses \(\zeta_{k}\) in the second phase in place of \(\zeta\). We optimize the function as if Assumption 1 holds for \(\zeta_{k}\). \(\zeta_{k}\) starts from \(\zeta_0\); at step [step:doublediff], once we have spent enough queries at the current estimate of \(\zeta\), we double the current \(\zeta_{k}\). We iterate until we reach \(\zeta_{k}>\zeta_{\max}\). The threshold for \(N_l\), \(\frac{\underline{n}_{\Lambda}}{2\lceil \log(\zeta_{\max}/\zeta_0)\rceil}\), is chosen such that we divide a label budget of \(\underline{n}_{\Lambda}/2\) direct queries equally among the \(\lceil \log(\zeta_{\max}/\zeta_0)\rceil\) possible values of the \(\zeta_{k}\)’s. The constant 2 is chosen arbitrarily here; any choice of \(\underline{n}_{\Lambda}/c\) for a constant \(c>1\) will obtain the same rate.

We present our theoretical results as a corollary to Theorem 3. Since we cannot find the exact \(\zeta\), our results depend on a slightly larger \(\bar{\zeta}=\max\{2\zeta, \zeta_0\}\). We use \(\hat{H}^{\gamma}=\{x\in \mathcal{X}: f_r(x)\geq f_r^*-2L_2\bar{\zeta}-4\gamma\}\) to represent the constraint set of interest when \(\zeta\) is replaced by \(\bar{\zeta}\).

Remark. 1. The regret rate of Corollary 1 is almost the same as Theorem 3, except the set \(\mathcal{H}^{\gamma}\) is replaced with \(\hat{H}^{\gamma}\). We note that all the terms in the regret rate depend only on \(\bar{\zeta}\) or \(\zeta\), and do not depend on \(\zeta_{\max}\). This means Algorithm 2 can adapt to unknown level of comparison bias \(\zeta\).
2. Similar to Theorem 3, Corollary 1 also requires the unknown quantity \(\Phi_{t}(\hat{H}^{\gamma})\) to set \(\beta_t\); in practice we can also use a similar hyper-parameter search to find this quantity. \(\gamma\) also takes a similar effect as in Algorithm 1, and \(\gamma=\frac{1}{L_2}\zeta_{0}\) can lead to \(\hat{\mathcal{H}}^{\gamma}\approx \mathcal{H}\) and a practical algorithm. Again, setup of these parameters only depends on \(\bar{\zeta}\) and is not affected by \(\zeta_{\max}\).

3.6 Comparison with MF-GP-UCB [18]↩︎

Our setting and method share some common characteristics as the multi-fidelity method MF-GP-UCB [18], and we formally discuss them here. Our setup is similar to MF-GP-UCB in the two-fidelity case, where the algorithm has access to the target function \(f\) and its approximation \(f^{(1)}\), with \(\|f-f^{(1)}\|_\infty\leq \zeta\) for some known \(\zeta>0\). Although we also assume \(f_c\) is a good approximation for \(f\) (in a weaker sense of being close in terms of \(f^*\) and \(f_c^*\), see Assumption 1), our setting is harder than MF-GP-UCB and their algorithm cannot be directly applied in our case. This is because we cannot directly query \(f_c\): \(f_c\) is only available through comparisons, and we will get the same set of comparisons from \(f_c\) and \(f_c+c\) for any constant \(c\). In our case, we can only get unbiased estimates for \(f_r\). However, it is unlikely that \(\|f_r-f\|_\infty\) is small, because \(f_r(x)\in [0,1]\) for all \(x\) since it is the probability of beating a random point, whereas \(f\) can have arbitrary values.

MF-GP-UCB bears some resemblance to the second phase in our Algorithm 1, but they are principally different in choosing the next query point \(x_t\). In the MF-GP-UCB algorithm, we have access to another function \(f'\) similar to \(f\). The algorithm constructs two sets of UCBs \(\phi(x), \phi'(x)\) for \(f\) and \(f'\) separately, and use \(\min\{\phi(x),\phi'(x) \}\) as a final UCB. In our case, UCBs of \(f_r\) and \(f\) are not comparable. Instead we use a novel constrained optimization approach based on observations in the first phase.

Another difference is that MF-GP-UCB needs the function difference \(\zeta\) known beforehand, whereas our modified COMP-GP-UCB(Algorithm 2) can adapt to an unknown \(\zeta\). We note that MF-GP-UCB does use a doubling mechanism in their experiments to make it practical, but they do not provide any theoretical guarantees.

4 Experiments↩︎

We perform experiments against plausible baselines to verify our theory and illustrate the efficacy of our algorithm.

Baselines. We evaluate the performance of COMP-GP-UCB against the following baselines:
GP-UCB[1]: The label-only algorithm optimizing UCB of GP posterior.
KernelSelfSparring[23]: A comparison-only algorithm that uses Thompson Sampling to optimize comparisons. We note that since \(f\ne f_c\), optimizing comparisons cannot lead to the global optimum.
MF-GP-UCB[18]: Although MF-GP-UCB is not directly applicable in our case, we try to use it by using comparisons as the lower fidelity. When the algorithm selects to query the lower fidelity on \(x_t\), we compare \(x\) to a random point \(X\in \mathcal{X}\) and use the result as feedback, the same process as COMP-GP-UCB.

Experiment Setup. We apply common techniques in Bayesian optimization to set up hyperparameters of each algorithm (we detail the implementation in appendix). The target functions \(f, f_c\) are set to functions from the multi-fidelity literature, in particular Currin exponential (CurrinExp, \(d=2\)) and Borehole (\(d=8\)) [32]. We note that \(f\) and \(f_c\) have different values and maximizers. All methods use the RBF kernel for GP. For all methods we compute the simple regret (1 ) w.r.t. \(f\) ⁶. The results are averaged over 20 runs, with a total budget of \(\Lambda=100\).

Cost Ratio. In practice, the relation between costs of labels and comparisons can be complex. We call \(\frac{\lambda_l}{\lambda_c}\) the cost ratio between labels and comparisons; the larger the cost ratio, the cheaper the comparisons. Our algorithm generally works for a cost ratio \(\frac{\lambda_l}{\lambda_c}>1\). We test the performance under various cost ratios in our experiment. For a fair comparison with MF-GP-UCB, we also use their setup of \(\lambda_c=0.1\) and \(\lambda_l=1\).

4.1 Results↩︎

The results are summarized in Figure 3. Firstly we compare the performance on CurrinExp by varying the total budget from 10 to 100 (Figure 3 (a)). COMP-GP-UCB shows the best performance over all budget setups. It is worth noting that MF-GP-UCB performs worse than label-only GP-UCB in our setting; this is because the target function of MF-GP-UCB in this case essentially optimizing the function \(f_r\), which is bounded in \([0,1]\), resulting in a very large approximation bias. In contrast, COMP-GP-UCB is able to use comparisons in an efficient way to reduce the search space for optimization.

Then in Figure 3 (b), we fix the total budget to be \(\Lambda=100\) and cost of labels \(\lambda_l=1\), and vary the cost ratio from 1 to 10 by varying comparison costs. COMP-GP-UCB achieves the best performance for all setups except when \(\lambda_c=\lambda_l=1\) and it is worse than the label-only GP-UCB algorithm. This is expected since our algorithm targets to use cheaper comparisons. Our algorithm can be more effective even with a fairly small cost ratio.

Finally, the result on Borehole is depicted in Figure 3 (c). As with CurrinExp, COMP-GP-UCB achieves the best performance with a large gap under all budget setups. Due to space limit we put the varying cost ratio result, as well as other experiments in the appendix.

5 Conclusion↩︎

We consider a novel dueling-choice setting when both direct queries and comparisons are available for non-convex optimization. We propose the COMP-GP-UCB algorithm that can achieve benign regret rates in the dueling-choice setting, and can adapt to unknown biases in the comparisons. Our algorithm can also be of independent interest for other multi-fidelity or transfer learning settings where information gleaned from one fidelity or source domain can be actively transferred to optimize the target domain function, under milder conditions than existing literature.

6 Reviews of the GP-UCB and IGP-UCB Algorithm↩︎

The GP-UCB [1] and IGP-UCB [29] can be unified as in Algorithm 4. The algorithms only differ at their assumptions and thus the choice of \(beta_t\). Our setting of \(\beta^{(r)}_t\) and \(\beta_{t}\) is similar to IGP-UCB, as we focus more on the agnostic function setting.

7 Experiment Details↩︎

We apply basic techniques in Bayesian Optimization to conduct the experiments.
Initial queries: All the algorithms were initialized with uniform random queries with an initial budget of \(\Lambda_0=10\). For multi-fidelity methods (MF-GP-UCB and COMP-GP-UCB), we use \(\Lambda_0/2\) on comparisons and \(\Lambda_0/2\) on direct queries; for GP-UCB we use all \(\Lambda_0\) on labels.
Choice of kernel parameters: We estimate the kernel bandwidth and scale by maximizing marginal likelihood with respect to the initial random queries. We also update the kernel parameters by maximizing the marginal likelihood for the GP over the lower fidelity function after every 20 iterations, and for the GP over the true function after every 5 iterations.
Setup of \(\beta_t\) and \(\beta^{(r)}_t\) We follow MF-GP-UCB and set \(\beta= 0.5*\log(2*t+\epsilon)=\beta^{(r)}_t\).
Choosing query points. We use the DiRect algorithm [33] to maximize the marginal likelihood subject to parameter bounds, and to find the next query points.

7.1 Additional Results on Borehole↩︎

Figure 5 depicts the results on Borehole function with varying cost ratio. Different than CurrinExp, COMP-GP-UCB displays an advantage over the baselines in all cost ratios including \(\lambda_l=\lambda_c\). We suspect this can be because the lower fidelity is easier to explore than the higher fidelity for the Borehole function.

7.2 Results with Single Fidelity and Same Cost↩︎

Although COMP-GP-UCB is designed for the case where comparisons are cheaper than direct queries, it is also interesting to see how it performs when comparisons and direct queries cost the same. We conduct an experiment with \(f=f_c\) and \(\lambda_c=\lambda_l=1\) in Figure 6. Note that MF-GP-UCB is not applicable in this setting since it is for multi-fidelity setting. COMP-GP-UCB performs on par (for CurrinExp) or better (for Borehole) than the baselines in our result. Note that while our theory suggests that the convergence rate of COMP-GP-UCB is the same as GP-UCB when \(\lambda_c=\lambda_l\) and \(f=f_c\), in practice the underlying function \(f_r\) (of COMP-GP-UCB) might be easier to optimize than \(f\), because it is bounded and can be smoother than \(f\). We note that cost ratio \(\frac{\lambda_l}{\lambda_c}=2\) is enough for COMP-GP-UCB to surpass the performance of GP-UCB on CurrinExp (see Figure 3 (b)).

8 Proofs↩︎

8.1 Proof of Proposition 1↩︎

Let \(x_c^*\) be a maximizer of \(f_c\). Because of the link function assumption, \(x_c^*\) is also a optimizer of \(f_r\). We have \[\begin{align} f_r^*-f_r(x)&=\mathbb{E}[\sigma(f_c(x_c^*)-f_c(X))]-\mathbb{E}[\sigma(f_c(x)-f_c(X))]\\ &=\mathbb{E}[\sigma(f_c(x_c^*)-f_c(X))-\sigma(f_c(x)-f_c(X))]\\ &\leq\mathbb{E}[L_2|f_c(x_c^*)-f_c(x)|]=L_2(f_c^*-f_c(x)).\\ \end{align}\] The lower bound can be proved similarly.

8.2 Proof of Theorem 2 and 3↩︎

We show Theorem 3 and Theorem 2 follows as a direct corollary. We first use results in IGP-UCB[29] to obtain confidence bands of \(f_r\):

Lemma 1 also applies to \(f, x\in \mathcal{H}^{\gamma}, \mu^{(l)},\sigma^{(l)}\) by setting \(\beta_t=2\|f\|_\kappa+\sqrt{2\left(\Phi_{t-1}(\mathcal{H}^{\gamma})+1+\log(1/\delta)\right)}\).

We also use the following lemma to bound the sum of posterior variances:

Suppose the event in Lemma 1 holds for \(f\) and \(f_r\). We first prove the first bound by looking at comparison queries. Firstly, in the first phase when we compute \(x_t\) in step \(\ref{step:firstphasext}\) we have \[\begin{align} f_r^*-f_r(x_t)&\leq \mu^{(r)}_{t-1}(x^*_r)+\beta^{(r)}_t\sigma^{(r)}_{t-1}(x^*_r)-(\mu^{(r)}_{t-1}(x_t)-\beta^{(r)}_t\sigma^{(r)}_{t-1}(x_t))\nonumber\\ &\leq \mu^{(r)}_{t-1}(x_t)+\beta^{(r)}_t\sigma^{(r)}_{t-1}(x_t)-(\mu^{(r)}_{t-1}(x_t)-\beta^{(r)}_t\sigma^{(r)}_{t-1}(x_t))\nonumber\\ &= 2\beta^{(r)}_t\sigma^{(r)}_{t-1}(x_t). \label{eqn:reg95sigma95} \end{align}\tag{6}\] The first inequality uses Lemma 1, and the second inequality is from that \(x_t\) is the maximizer of \(\mu^{(r)}_{t-1}(x)+\beta^{(r)}_t\sigma^{(r)}_{t-1}(x)\).

Suppose we finish phase 1 and enter phase 2. Let \(T_0\) be the time we leave phase 1, then we must have \(\beta^{(r)}_{T_0}\sigma^{(r)}_{T_0-1}(x_{T_0})\leq \gamma\). So \[\begin{align} S(\Lambda)&\leq f^*-f(x_{T_0})\nonumber\\ &\leq f_c(x^*)-f_c(x_{T_0})+\zeta\nonumber\\ &\leq f_c^*-f_c(x_{T_0})+\zeta\nonumber\\ &\leq L_1(f_r^*-f_r(x_{T_0}))+\zeta\leq 2L_1\gamma+\zeta.\label{eqn:p1b1} \end{align}\tag{7}\] The second inequality is from Assumption 1, the fourth inequality is from Assumption 2, and the last inequality is from (6 ).

If we do not finish phase 1, then the number of comparison queries is \(N_1\geq \overline{n}_{\Lambda}-1\) and \(N_1\leq \overline{n}_{\Lambda}\), and we have \[\begin{align} \left(\sum_{t} \left(f_r^*-f_r(x_t)\right)\right)^2&\leq N_1\sum_{t:q_t=\text{comparison}} \left(f_r^*-f_r(x_t)\right)^2\nonumber\\ &\leq N_1\sum_{t:q_t=\text{comparison}} 4\left(\beta^{(r)}_t\sigma^{(r)}_{t-1}(x_t)\right)^2\nonumber\\ &\leq C_1 N_1\left(\beta^{(r)}_{N_1}\right)^2 \Phi_{N_1}(\mathcal{H}^{\gamma}).\label{eqn:bound95fr} \end{align}\tag{8}\] Here \(C_1=\frac{8}{\log(1+\eta^{-2})}\). The first step is from the Cauchy-Schwarz inequality, and the second step is from (6 ); the last step uses Lemma 2.

So \[\begin{align} S(\Lambda)&\leq \frac{1}{N_1}\sum_{t} \left(f^*-f(x_t)\right)\nonumber\\ &\leq \frac{2L_1}{N_1}\sum_{t} \left(f_r^*-f_r(x_t)\right)+\zeta\nonumber\\ &\leq \frac{\beta^{(r)}_{N_1}}{N_1}\sqrt{C_1 N_1 \Phi_{N_1}(\mathcal{H}^{\gamma})}+\zeta\nonumber\\ &\leq \frac{C\beta^{(r)}_{\overline{n}_{\Lambda}}}{\overline{n}_{\Lambda}}\sqrt{ \overline{n}_{\Lambda}\Phi_{\overline{n}_{\Lambda}}(\mathcal{H}^{\gamma})}+\zeta\nonumber\\ &\leq C\left(B+\sqrt{\left(\Phi_{\overline{n}_{\Lambda}}(\mathcal{H}^{\gamma})+\log(1/\delta)\right)}\right)\sqrt{\frac{\Phi_{\overline{n}_{\Lambda}}(\mathcal{H}^{\gamma})}{\overline{n}_{\Lambda}}}+\zeta.\label{eqn:p1b2} \end{align}\tag{9}\] The second inequality follows from the same process as in (7 ); the third inequality follows from (8 ); the fourth inequality is from \(\overline{n}_{\Lambda}\geq N_1\geq \overline{n}_{\Lambda}-1\). Here \(C\) is a constant whose value may change from line to line. Combining (7 ) and (9 ) we get the first bound.

To show the second bound, we examine the regret from direct queries. We first show that \(x^*\) is never excluded from our feasible region:

Let \(N\) be the (random) total number of queries under budget \(\Lambda\). We know that the support of \(N\) lies in \([\underline{n}_{\Lambda},\overline{n}_{\Lambda}]\); we now suppose \(n\) is any number in \([\underline{n}_{\Lambda},\overline{n}_{\Lambda}]\), and prove properties of Algorithm 1 when it uses \(n\) queries.

For any set \(A\subseteq \mathcal{X}\), let \(T^r_n(A)\) be the number of comparison queries into \(A\) when the algorithm has made \(n\) queries, and \(T^l_n(A)\) be the number of direct queries. We have \[n=T^r_n(\mathcal{X})+T^l_n(\overline{\mathcal{H}^{\gamma}})+T^l_n(\mathcal{H}^{\gamma})\] since \(\overline{\mathcal{H}^{\gamma}}\cup \mathcal{H}^{\gamma}=\mathcal{X}\). We bound the first two terms using the following two lemmas:

This lemma is proved in Section 8.3.

Lemma 3 shows that we will not make too many queries on comparisons, whereas Lemma 4 shows that we always query \(x_t\in \mathcal{H}^{\gamma}\) when \(q_t=\text{label}\). Now let \(N_0\) be the smallest number such that for any \(\Lambda\geq N_0\lambda_c\) we have \[\lambda_l\left(\frac{2r\sqrt{d}}{\varepsilon_{\overline{n}_{\Lambda}}}\right)^d \left(\frac{2\eta\beta^{(r)}_{\overline{n}_{\Lambda}}}{\gamma}\right)^2=C_{\kappa}\left(\frac{\beta^{(r)}_{\overline{n}_{\Lambda}}}{\gamma}\right)^{p+2} \leq \frac{\Lambda}{2}\] where \(C_\kappa\) and \(p\) are defined in (11 ). Such \(\Lambda_0\) is guaranteed to exist, since \(\beta^{(r)}_{\overline{n}_{\Lambda}}\) grows in sublinear rate for linear, SE and Matérn kernels on \(\overline{n}_{\Lambda}\), and therefore \(\Lambda\). Thus the number of queries to \(f_c\), \(T_n^c(\mathcal{X})\), is at most \(\underline{n}_{\Lambda}/2\), and therefore we query at least \(\underline{n}_{\Lambda}/2\) times on direct queries, \(T^l_N(\mathcal{H}^{\gamma})\geq \underline{n}_{\Lambda}/2\).

We now follow a similar path as for comparison queries to bound the regret based on direct queries. Note that if we use direct query at round \(t\), we have \(x_t\in \mathcal{H}^{\gamma}\) and that \[\begin{align} f^*-f(x_t)&\leq \mu^{(l)}_{t-1}(x^*)+\beta_t\sigma^{(l)}_{t-1}(x^*)-(\mu^{(l)}_{t-1}(x_t)-\beta_t\sigma^{(l)}_{t-1}(x_t))\nonumber\\ &\leq \mu^{(l)}_{t-1}(x_t)+\beta_t\sigma^{(l)}_{t-1}(x_t)-(\mu^{(l)}_{t-1}(x_t)-\beta_t\sigma^{(l)}_{t-1}(x_t))\nonumber\\ &= 2\beta_t\sigma^{(l)}_{t-1}(x_t). \label{eqn:reg95sigma} \end{align}\tag{10}\] The first inequality uses Lemma 1, and the second inequality uses Claim 4 and that \(x_t\) is the maximizer of \(\mu^{(l)}_{t-1}(x)+\beta_t\sigma^{(l)}_{t-1}(x)\).

Now therefore \[\begin{align} \left(\sum_{t:q_t=\text{label}} \left(f^*-f(x_t)\right)\right)^2&\leq T_n^t\left(\mathcal{H}^{\gamma}\right)\sum_{t:q_t=\text{label}} \left(f^*-f(x_t)\right)^2\\ &\leq T_n^t\left(\mathcal{H}^{\gamma}\right)\sum_{t:q_t=\text{label}} 4\left(\beta_t\sigma^{(l)}_{t-1}(x_t)\right)^2\\ &\leq C_1 T_n^t\left(\mathcal{H}^{\gamma}\right)(\beta_n)^2 \Phi_{T_n^t\left(\mathcal{H}^{\gamma}\right)}(\mathcal{H}^{\gamma}) \end{align}\] Here \(C_1=\frac{8}{\log(1+\eta^{-2})}\). The first step is from the Cauchy-Schwarz inequality, and that \(T^l_n(\overline{\mathcal{H}^{\gamma}})=0\); the second step is from (10 ); the last step uses Lemma 2.

So \[\begin{align} S(\Lambda)&\leq \frac{1}{T_N^t(\mathcal{H}^{\gamma})}\sum_{t:x_t\in \mathcal{H}^{\gamma}, q_t=\text{label}} \left(f^*-f(x_t)\right)\\ &\leq \frac{\beta_N}{T_N^t(\mathcal{H}^{\gamma})}\sqrt{C_1 T_N^t\left(\mathcal{H}^{\gamma}\right) \Phi_{T_N^t\left(\mathcal{H}^{\gamma}\right)}(\mathcal{H}^{\gamma})}\\ &\leq \frac{C\beta_{\underline{n}_{\Lambda}}}{\underline{n}_{\Lambda}}\sqrt{ \underline{n}_{\Lambda}\Phi_{\underline{n}_{\Lambda}\left(\mathcal{H}^{\gamma}\right)}(\mathcal{H}^{\gamma})}\\ &\leq C\left(B+\sqrt{\left(\Phi_{\underline{n}_{\Lambda}}(\mathcal{H}^{\gamma})+\log(1/\delta)\right)}\right)\sqrt{\frac{\Phi_{\underline{n}_{\Lambda}}(\mathcal{H}^{\gamma})}{\underline{n}_{\Lambda}}}. \end{align}\]

8.3 Proof of Lemma 3↩︎

We use the following lemma from [18]⁷:

Consider the SE kernel and the comparison oracle, and a \(\varepsilon_n=\frac{\gamma}{\beta^{(r)}_n\sqrt{8C_{SE}}}\) covering \((B_i)_{i=1}^n\) of \(\mathcal{X}\). We claim that the number of comparison queries inside any \(B_i\) is at most \(\lceil 2(\frac{\eta\beta^{(r)}_n}{\gamma})^2 \rceil\): suppose we have already queried \(\lceil 2(\frac{\eta\beta^{(r)}_n}{\gamma})^2 \rceil\) samples in \(B_i\) at some time \(t<n\). By Lemma 5 we have \[\max_{x\in B_i} \kappa^{(r)}_{t-1}(x,x)\leq C_{SE}(2\varepsilon_n)^2+\frac{\eta^2}{2(\frac{\eta\beta^{(r)}_n}{\gamma})^2}\leq \left(\frac{\gamma}{\beta^{(r)}_n}\right)^2.\] Therefore \(\beta^{(r)}_n\sigma^{(r)}_{t-1}(x)\leq \beta^{(r)}_{t}\sigma^{(r)}_{t-1}(x)\leq \gamma\). Note that whenever \(q_t=\text{comp}\), we always have \(\beta^{(r)}_{t}\sigma^{(r)}_{t-1}(x_t)\leq \gamma\); so the event that \(q_t=\text{comp}\) and \(x_t\in B_i\) will not happen until time \(n\). We can obtain a similar result for Matérn kernel with \(\varepsilon_n=\frac{\gamma^2}{4C_{Mat}(\beta^{(r)}_n)^2}\). Therefore we have \[\begin{align} T^r_n(\mathcal{X})\leq \Omega_{\varepsilon_n}(\mathcal{X})\lceil 2(\frac{\eta\beta^{(r)}_n}{\gamma})^2 \rceil\leq \left(\frac{2r\sqrt{d}}{\varepsilon_n}\right)^d \left(\frac{2\eta\beta^{(r)}_n}{\gamma}\right)^2=C_{\kappa}\left(\frac{\beta^{(r)}_n}{\gamma}\right)^{p+2}. \label{eqn:cover95number} \end{align}\tag{11}\] Here \(\Omega_{\varepsilon_n}(\mathcal{X})\) is the covering number of \(\mathcal{X}\), and we bound the covering number as \(\Omega_{\varepsilon_n}(\mathcal{X})\leq \left(\frac{2r\sqrt{d}}{\varepsilon_n}\right)^d\). Here \(C_\kappa=2^{2.5d+2}r^dd^{d/2}C_{SE}^{d/2}\eta^2\) and \(p=d\) for SE kernel, while \(C_{\kappa}=2^{3d+2}r^dd^{d/2}C_{Mat}^d\eta^2\) and \(p=2d\) for Matérn kernel.

8.4 Proof of Corollary 1↩︎

References↩︎