Multisection: Parallelized Bisection
Effectively Using Asynchronous Information
Stephen Pallone
Peter Frazier
Shane Henderson
School of Operations Research and Information Engineering,
Cornell University
Deterministic Waiting Times
Corollary 1: Equally Spaced Queries are Optimal
Suppose function evaluations take a deterministic and equal amount of time to compute, and let \(R(\cdot)\) be defined as before. If \(X_j = (X_j^{(0)},X_j^{(1)},\dots,X_j^{(n+1)})\) is defined as
\[ X_j^{(i)} = A_j + \frac{i}{n+1} \left(B_j-A_j\right), \] then \(X_j\) is an optimal allocation for \(S_j = (A_j,B_j)\).
Optimal Stacking Policy
Theorem 3: Midpoint Stacking Policy
When stacking is allowed, stacking all queries at the midpoint is the optimal allocation for independent exponentially distribution waiting times with uniform rates. Equivalently, for states \(S_j = (A_j,B_j)\), the optimal allocation \(X_j\) is such that
\[ X_j^{(i)} = A_j + \frac{1}{2}(B_j - A_j) \quad\quad \forall i=1,\dots,n.\]
Larger Numbers of Cores (n>2)
Can we find policies similar to Golden Section for larger values of \(n\)?
- In general, we cannot rely on one allocation to define a policy.
- What if we instead look for a policy that visits a finite number of states?
Consider the case n=3:
\begin{equation}
Y = \left(0,\frac{1}{3},\frac{1}{2},\frac{2}{3},1\right) \quad\quad Z = \left(0,\frac{1}{4},\frac{1}{2},\frac{3}{4},1 \right)
\end{equation}