A learning augmented algorithm is an algorithm that can make use of a prediction to improve its performance.
[1] 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.
A learning augmented algorithm typically takes an input
is the advice: a prediction about a certain property of the optimal solution.
The type of the problem instance and the prediction depend on the algorithm.
Learning augmented algorithms usually satisfy the following two properties: Learning augmented algorithms generally do not prescribe how the prediction should be done.
For this purpose machine learning can be used.
[citation needed] The binary search algorithm is an algorithm for finding elements of a sorted list
steps to find an element with some known value
, the following learning augmented algorithm can be used.
In the learning augmented algorithm, probing the positions
Then a binary search is performed on a list of size at most
This makes the total running time of the algorithm
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
steps, so the algorithm is robust.