# The Power of Human-Algorithm Collaboration in Solving Combinatorial Optimization Problems
## 4 Human-Algorithm Collaboration in Bayesian Optimization
Upper bound is calculated from the size of a cell, mean maximum found using EI2 or UCB2 from samples of Algorithm 1, and the number of iterations used by EI2 or UCB2 (\(X\)):_  
\[ub:=\frac{val}{\frac{\sqrt{\log_{2}(T)}}{\sqrt{\log_{2}(N)}}} \tag{12}\]  
_where \(val\) is the mean of values found by EI2 or UCB2 in \(S\) runs from a cell, \(T=X\), and \(N\) is the size of the cell. Ub is calculated for each cell as if there were no approximation error._  
**Definition 4** (\(\epsilon\) optimal solution). : _An expected local optimum \(\epsilon\) close to an expected global optimum._  
**Definition 5** (Optimal cell). : _Cell that contains the \(\epsilon\) optimal solution._  
**Assumption 1**. : _The expert's priors do not contradict each others at any point in the same fractions of the search space, and priors are informative._  
In Algorithm 3 we show the pseudocode of the algorithm. If the priors given by the expert are informative and consistent, then it converges on the \(\epsilon\) optimal solution in \(O(S\cdot A\cdot K\cdot C\cdot\log_{2}(D))\); for some \(C\), depending on the problem instance, \(S\) and \(X\) as well as \(K\) (the number of function values \(\epsilon\) close to global optima). This is because Algorithm 3 with high probability expands the \(\epsilon\) optimal cell into two equal sized halves--the rate of convergence is exponential. In the following lemmas, we will prove our claims. ```
1:inputs:D (domain), \(T\), \(S\), \(X\), \(V\)
2:current := \([1,D]\)
3:\(i:=0\)
4:\(j:=0\)
5: fix order of \(Vars:=V\)
6:for\(t:=1,2,3,...\) to \(\log_{2}(T)\)do
7: a := first half of current
8: b := second half of current
9: remove current cell
10: add a to cells
11: add b to cells
12:for\(s:=1,2,3,...\) to \(\log_{2}(S)\)do
13: re-sample a and b from Algorithm 1, use absolute position of a and b (in original domain) to derive a partial assignment for Algorithm 1 and \(D_{0},D_{1}\). 14: derive covariance matrices (\(\Sigma_{i},\Sigma_{j}\)), and means (\(\mu_{i},\mu_{j}\)) for a and b using query to **expert**
15: solve UCB2 or EI2 for a, use \(T:=X\) iterations, covariance matrix derived \(\Sigma_{i}\), and \(\mu_{i}\)
16: solve UCB2 or EI2 for b, use \(T:=X\) iterations, covariance matrix derived \(\Sigma_{j}\), and \(\mu_{j}\)
17:\(i:=i+1\)
18:\(j:=j+1\)
19:endfor
20: retain original order of variables for \(a\) from \(Vars\)
21: retain original order of variables for \(b\) from \(Vars\)
22: deduce \(ub\) of \(a\) from its found UCB2 or EI2 values in S samples from Algorithm 1, size of \(a\), and X
23: deduce \(ub\) of \(b\) from its found UCB2 or EI2 values in S samples from Algorithm 1, size of \(b\), and X
24: current := \(argmax\) of cells (the cell with highest \(ub\))
25:endfor
26:return max value of any cell found by UCB2 or EI2
```  
**Algorithm 3** Bayesian optimization with expert knowledge. Lemma 1: _With probability in \(S\), Algorithm 3 expands the optimal cell at any time \(t_{i}\in T,0\leq i\leq T\)_  
Proof: Based on [PERSON]'s inequality,  
\[|F(x_{1},x_{2},...,x_{m})-F(x_{1},x_{2},...,x_{i}^{\prime},...,x_{m})|\leq c_ {i} \tag{13}\]  
and  
\[P[|F(x_{1},x_{2},...,x_{m})-E[F(x_{1},x_{2},...,x_{m})]|\geq t]\leq exp(\frac{ -2t^{2}}{\Sigma_{i=0}^{m}(c_{1}^{2})}) \tag{14}\]  
the Algorithm 3 can be modified so that it passes all the \(S\) random permutations from Algorithm 1 to a black box function that optimizes permutations with EI2 or UCB2 and outputs the mean of the results. Hence, \(c_{i}\) is bounded by \(\frac{1}{m}(b-a)\), for every \(c\), where \(b\) and \(a\) are the upper bound and lower bound of the functions values, respectively. Consequently, we have the following:  
\[normregret\geq 1-\frac{\sqrt{\log_{2}(T)}}{\sqrt{\log_{2}(N)}}-\epsilon \tag{7}\]0  
This implies that the value of \(S\) UCB2 or EI2 runs converges exponentially fast to its expected value in \(m\)--the number of random permutations.