Learning augmented algorithm

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 ${\displaystyle ({\mathcal {I}},{\mathcal {A}})}${\displaystyle ({\mathcal {I}},{\mathcal {A}})}. Here ${\displaystyle {\mathcal {I}}}${\displaystyle {\mathcal {I}}} is a problem instance and ${\displaystyle {\mathcal {A}}}${\displaystyle {\mathcal {A}}} 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:

• Consistency. A learning augmented algorithm is said to be consistent if the algorithm can be proven to have a good performance when it is provided with an accurate prediction.^[1] Usually, this is quantified by giving a bound on the performance that depends on the error in the prediction.
• Robustnesss. An algorithm is called robust if its worst-case performance can be bounded even if the given prediction is inaccurate.^[1]

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 ${\displaystyle x_{1},\ldots ,x_{n}}${\displaystyle x_{1},\ldots ,x_{n}}. It needs ${\displaystyle O(\log(n))}${\displaystyle O(\log(n))} steps to find an element with some known value ${\displaystyle y}${\displaystyle y} in a list of length ${\displaystyle n}${\displaystyle n}. With a prediction ${\displaystyle i}${\displaystyle i} for the position of ${\displaystyle y}${\displaystyle y}, the following learning augmented algorithm can be used.^[1]

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

The error is defined to be ${\displaystyle \eta =|i-i^{*}|}${\displaystyle \eta =|i-i^{*}|}, where ${\displaystyle i^{*}}${\displaystyle i^{*}} is the real index of ${\displaystyle y}${\displaystyle y}. In the learning augmented algorithm, probing the positions ${\displaystyle i+1,i+2,i+4,\ldots }${\displaystyle i+1,i+2,i+4,\ldots } takes ${\displaystyle \log _{2}(\eta )}${\displaystyle \log _{2}(\eta )} steps. Then a binary search is performed on a list of size at most ${\displaystyle 2\eta }${\displaystyle 2\eta }, which takes ${\displaystyle \log _{2}(\eta )}${\displaystyle \log _{2}(\eta )} steps. This makes the total running time of the algorithm ${\displaystyle 2\log _{2}(\eta )}${\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}${\displaystyle n}. Then the algorithm takes at most ${\displaystyle O(\log(n))}${\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]

• Machine learning

• An overview of publications about learning augmented algorithms

• Algorithms
• Theoretical computer science

• All articles with unsourced statements
• Articles with unsourced statements from May 2022