Learning augmented algorithm

A learning augmented algorithm (also called algorithm with predictions) is an algorithm that can make use of a prediction to improve its performance. Whereas in regular algorithms just the problem instance is inputted, learning augmented algorithms accept an extra parameter. This extra parameter often is a prediction of some property of the solution. This prediction is then used by the algorithm to improve its running time or the quality of its output. The most common application are online algorithms, where a prediction on the uncertain instance is provided.

A learning augmented algorithm (also called algorithm with predictions) is an algorithm that can make use of a prediction to improve its performance. Whereas in regular algorithms just the problem instance is inputted, learning augmented algorithms accept an extra parameter. This extra parameter often is a prediction of some property of the solution. This prediction is then used by the algorithm to improve its running time or the quality of its output. The most common application are online algorithms, where a prediction on the uncertain instance is provided. First, look at position i in the list. If x_i=y , the element has been found. If x_i , look at positions i+1,i+2,i+4,\ldots until an index j with x_j\geq y is found. Now perform a binary search on x_i,\ldots, x_j . If x_i>y , do the same as in the previous case, but instead consider i-1,i-2,i-4,\ldots . The error is defined to be \eta=|i-i^*| , where i^* is the real index of y . In the learning augmented algorithm, probing the positions i+1,i+2,i+4,\ldots takes \log_2(\eta) steps. Then a binary search is performed on a list of size at most 2\eta , which takes \log_2(\eta) steps. This makes the total running time of the algorithm 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 n . Then the algorithm takes at most O(\log(n)) steps, so the algorithm is robust.

Text derived from https://en.wikipedia.org/w/index.php?oldid=1336313782 under CC BY-SA 4.0; modifications have been made.