# The Power of Human-Algorithm Collaboration in Solving Combinatorial Optimization Problems
## 4 Human-Algorithm Collaboration in Bayesian Optimization
This is because the algorithm always randomly sorts either all or a subset of the variables (line 2 in Algorithm 1). We use that and _McDiarmid's inequality_[34] to obtain a high probability of a convergence to expected values. The constraint defined of a McDiarmid's inequality is  
\[|F(x_{1},x_{2},...,x_{m})-F(x_{1},x_{2},...,x_{i}^{\prime},...,x_{m})|\leq c_ {i} \tag{10}\]  
where a value change of a single random variable can cause a function value to change to \(c_{i}\) at most, which resembles a local Lipschitz condition. Meanwhile, the actual concentration inequality is  
\[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_{i}^{2})}) \tag{11}\]  
where \(t\) is some constant for the difference between the function of random variables and expected value of the function with random variables. Moreover, [PERSON]'s inequality is a concentration inequality that states that if a arbitrary function accepts \(m\) random variables as parameters and a value of one those random variables is changed from the original value, then the function output can only change up to some constant from its original value (Equation (10)). Equation (11) is the actual concentration inequality that states that if Equation (10) holds for any function accepting \(m\) random variables as parameters, then such a function's output converges exponentially fast to its expected value. Meanwhile, [PERSON]'s inequality [35] is a special case of [PERSON]'s inequality, where the function of random variables is their sum. In our case, we run our reduction algorithm (Algorithm 1) \(S\) times, use either UCB2 or EI2 [27] each time and finally output the mean of the found values by UCB2 or EI2. Based on [PERSON]'s inequality, the mean value converges exponentially fast to the bounds promised by UCB2 or EI2. We then branch to the optimal regions of the domain where the optimal function values are likely to reside. Hence, our algorithm follows rather popular geometric branch and bound framework used in multiple global optimization algorithms [32]. In [32], the search space is shrunk after function evaluations and the intervals where the global optimizer is not likely to reside are discarded. However, ref. [32] cannot be used as such to solve problems with exponential sized domains because constants in their algorithm depend on the domain size and the shape of the function near to optimizer(s). Because the prior given to the Gaussian process upper bounds the expected optimum and the best value found by UCB2 and EI2, at every expansion and new sample from Algorithm 1, we query a new prior from an external expert. Here, we assume that the priors queried from the expert do not contradict each others and are informative--that is, there are no conflicting choices of, say, hyperparameters, among the priors regarding the same fractions of the search space, and that the expert can gain insights on the functions. Querying informative priors from an expert is a realistic assumption--and usually made in BO literature--since the expert has access to multiple sampling heuristics, such as maximum likehood estimation, previous function evaluations, and _domain knowledge_. This differentiates querying priors from an expert from standard _oracle_ queries from the theory of computation, where the oracle is unrealistic non-deterministic entity who is always correct. Our extension to [27] algorithm can be seen in Algorithm 3. Before going into more detail, we will first introduce some definitions and an assumption. **Definition 1** (Cell). : _Interval produced when a domain or a part of the domain is divided into two halves: one division produces two new cells._  
**Definition 2** (Expansion of cell). : _Division of a cell into two intervals of equal size._  
**Definition 3** (Upper bound). : _Expected maximum of a cell.