# The Power of Human-Algorithm Collaboration in Solving Combinatorial Optimization Problems
## 4 Human-Algorithm Collaboration in Bayesian Optimization
The expected approximation ratio in [27] is given as  
\[normregret\geq 1-\frac{\sqrt{\log_{2}(T)}}{\sqrt{\log_{2}(N)}}-\epsilon \tag{7}\]1  
which is  
\[normregret\geq 1-\frac{\sqrt{\log_{2}(T)}}{\sqrt{\log_{2}(N)}}-\epsilon \tag{7}\]2  
This is upper bounded by  
\[normregret\geq 1-\frac{\sqrt{\log_{2}(T)}}{\sqrt{\log_{2}(N)}}-\epsilon \tag{7}\]3  
which is because bound in Equation (7) is for every constant \(\epsilon>0\). Based on McDiarmid's inequality, the mean approximation ratio tends to be in between these bounds in \(m:=S\). Note that these upper and lower bounds are not asymptotic. The cell with the highest upper bound is always expanded. Thus, the upper, and lower bounds imply that the cell that does not contain the expected global optimizer might be expanded instead of the cell with the optimizer--some cells might have lower approximation errors and only slightly smaller expected optimums, and hence, there is a larger \(ub\). This is limited by  
\[normregret\geq 1-\frac{\sqrt{\log_{2}(T)}}{\sqrt{\log_{2}(N)}}-\epsilon \tag{7}\]4  
which is  
\[normregret\geq 1-\frac{\sqrt{\log_{2}(T)}}{\sqrt{\log_{2}(N)}}-\epsilon \tag{7}\]5  
where \(F_{local}\) is a maximum of a cell other than the expected global optima, and \(\epsilon\) is a small constant from McDiarmid's inequality's convergence error. Equation (20) gives a limit for the \(\epsilon\) optimal solution. This implies that even for a cell without any approximation error, if the found value is less than (20) the factor from the expected global maximum, then the cell will not be expanded because it will be _dominated_ by at least the cell with the expected global optimizer. These prove that--with probability in \(m:=S\)--only optimal cells will be expanded. Lemma 2: _Algorithm 3 will, with very high probability, find at least the \(\epsilon\) optimal solution to any optimization problem derived from some Gaussian process and Algorithm 1._  
Proof: When running Algorithm 3 for a sufficient number of iterations, the values found by UCB2 and EI2 increase, as cells' size decrease [27], and tend the to cell's expected optimum. The probability \(x\) of _always_ selecting the optimal cell is propositional to McDiarmid's inequality, \(m:=S\), but decreases exponentially based on the depth of the tree and tends to 0:  
\[normregret\geq 1-\frac{\sqrt{\log_{2}(T)}}{\sqrt{\log_{2}(N)}}-\epsilon \tag{7}\]6  
where \(h\) is the maximum depth of the tree. On the other hand, because  
\[normregret\geq 1-\frac{\sqrt{\log_{2}(T)}}{\sqrt{\log_{2}(N)}}-\epsilon \tag{7}\]7\(P[x]\) increases exponentially in \(m\) and tends to 1; the expected required samples from Algorithm 1 to obtain \(P[x|h]>0.5\) is bounded polynomially in \(m:=O(log_{2}(D))=O(h)\). **Lemma 3**: _Expected run time of Algorithm 3 to find at least the \(\epsilon\) optimal solution is \(O(S\cdot A\cdot K\cdot C\cdot log_{2}(D))\) (the time complexity of UCB2 or EI2 is omitted here) if the function has \(K\) number of \(\epsilon\) optimal solutions, where \(D\) is the domain size, \(A\) is the number of variables in the combinatorial optimization problem, and \(C\) depends on the function values and \(X\)._  
By Lemma 4.3, the algorithm always expands the optimal cell with high probability in \(S\). Because the expansion procedure always divides the cell into two equally sized halves and because the \(\epsilon\) optimal cell is expanded with high probability, the convergence rate is \(O(2^{-n})\). Upon fixing \(N=log_{2}(D)\), we have \(O(S\cdot A\cdot K\cdot C\cdot log_{2}(D))\). \(C\) depends on when Algorithm 3 is able to distinguish the expected global optimum from similar values of the objective function. This further depends on parameter \(X\) for UCB2 or EI2. This completes our proof. Of course, the approach provided here is merely theoretical. Here, the first assumption is that all functions are indeed realizations of the Gaussian processes (which might not be the case). The second is that, as the domain size increases, the more priors (even in the best possible case) the expert has to provide.