Learning augmented algorithm

The binary search algorithm is an algorithm for finding elements of a sorted list ${\displaystyle x_{1},\ldots ,x_{n}}$. It needs ${\displaystyle O(\log(n))}$ steps to find an element with some known value ${\displaystyle x}$ in a list of length ${\displaystyle n}$. With a prediction ${\displaystyle i}$ for the position of ${\displaystyle x}$, the following learning augmented algorithm can be used.[1]

• First, look at position ${\displaystyle i}$ in the list. If ${\displaystyle x_{i}=y}$, the element has been found.
• If ${\displaystyle x_{i}<y}$, look at positions ${\displaystyle i+1,i+2,i+4,\ldots }$ until an index ${\displaystyle j}$ with ${\displaystyle x_{j}\geq y}$ is found.
  • Now perform a binary search on ${\displaystyle x_{i},\ldots ,x_{j}}$.
• If ${\displaystyle x_{i}>y}$, do the same as in the previous case, but instead consider ${\displaystyle i-1,i-2,i-4,\ldots }$.

The error is defined to be ${\displaystyle \eta =|i-i^{*}|}$, where ${\displaystyle i^{*}}$ is the real index of ${\displaystyle y}$. In the learning augmented algorithm, probing the positions ${\displaystyle i+1,i+2,i+4,\ldots }$ takes ${\displaystyle \log _{2}(\eta )}$ steps. Then a binary search is performed on a list of size at most ${\displaystyle 2\eta }$, which takes ${\displaystyle \log _{2}(\eta )}$ steps. This makes the total running time of the algorithm ${\displaystyle 2\log _{2}(\eta )}$. So, when the error is small, the algorithm is faster than a normal binary search. This shows that the algorithm is consistent. Even in the worst case, the error will be at most ${\displaystyle n}$. Then the algorithm takes at most ${\displaystyle O(\log(n))}$ steps, so the algorithm is robust.

Learning augmented algorithms are known for:

• The ski rental problem[2]
• The maximum weight matching problem[3]
• The weighted paging problem[4]