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.[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. The most common application are online algorithms, where a prediction on the uncertain instance is provided.

## Contents

* 1 Description
* 2 Applications
* 2.1 Online algorithms
* 2.2 Warm starting
* 2.2.1 Data structures
* 2.2.2 More examples
* 2.3 Approximation algorithms
* 2.4 Mechanism Design
* 3 See also
* 4 References
* 5 External links

## Description

A learning augmented algorithm typically takes an input (ℐ,𝒜). Here ℐ is a problem instance and 𝒜 is the prediction. A prediction can be any object. Common are the following types:

* Prediction of an optimal solution. The prediction gives a solution to the problem or characterizes an optimal solution.
* Prediction of the input. This is mainly used for online problems.
* Prediction of algorithmic actions. A prediction tailored to a specific algorithm that suggests a specific algorithm execution.

Learning augmented algorithms usually satisfy the following three properties:[1]

* 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.
* Smoothness. A learning augmented algorithm is called smooth if its performance can be bounded by a function of the quality of the prediction. Here, the quality can be measured in a problem specific way. This is also called the prediction error.
* Robustness. A learning augmented algorithm is called robust if its worst-case performance can be bounded even if the given prediction is inaccurate.

Learning augmented algorithms generally do not prescribe how the prediction should be done. For this purpose machine learning can be used.[citation needed]

## Applications

A few examples of problems where learning augmented algorithms have been applied are the following.

### Online algorithms

* The ski rental problem[2]
* The weighted paging problem[3]
* The set cover problem[4][5]
* Nonclairvoyant scheduling[6][7]
* The online matching problem[8]

### Warm starting

#### Data structures

The binary search algorithm is an algorithm for finding elements of a sorted list x1,…,xn. It needs O(log⁡(n)) steps to find an element with some known value y in a list of length n. With a prediction i for the position of y, the following learning augmented algorithm can be used.[1]

* First, look at position i in the list. If xi=y, the element has been found.
* If xi<y, look at positions i+1,i+2,i+4,… until an index j with xj≥y is found.
* Now perform a binary search on xi,…,xj.
* If xi>y, do the same as in the previous case, but instead consider i−1,i−2,i−4,….

The error is defined to be η=|i−i*|, where i* is the real index of y. In the learning augmented algorithm, probing the positions i+1,i+2,i+4,… takes log2(η) steps. Then a binary search is performed on a list of size at most 2η, which takes log2(η) steps. This makes the total running time of the algorithm 2log2(η). 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.

#### More examples

* The maximum weight matching problem[9]

### Approximation algorithms

* The maximum cut problem[10]
* The vertex cover problem[11]

### Mechanism Design

* The facility location problem[12]

## See also

* Machine learning

## References

1. ↑ 1.0 1.1 1.2 Mitzenmacher, Michael; Vassilvitskii, Sergei (31 December 2020). "Algorithms with Predictions". Beyond the Worst-Case Analysis of Algorithms. Cambridge University Press. pp. 646–662. doi:10.1017/9781108637435.037. ISBN 978-1-108-63743-5.
2. ↑ Purohit, Manish; Svitkina, Zoya; Kumar, Ravi (2018). "Improving Online Algorithms via ML Predictions". Montréal, Canada. pp. 9684–9693. https://proceedings.neurips.cc/paper/2018/hash/73a427badebe0e32caa2e1fc7530b7f3-Abstract.html. Retrieved 18 December 2025.
3. ↑ Bansal, Nikhil; Coester, Christian; Kumar, Ravi; Purohit, Manish; Vee, Erik (January 2022). "Learning-Augmented Weighted Paging". Proceedings of the 2022 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). Society for Industrial and Applied Mathematics. pp. 67–89. doi:10.1137/1.9781611977073.4. ISBN 978-1-61197-707-3. https://ora.ox.ac.uk/objects/uuid:f8f430f4-23fd-49b9-9cf4-1c24230151cf.
4. ↑ Bamas, Étienne; Maggiori, Andreas; Svensson, Ola (2020). "The Primal-Dual Method for Learning Augmented Algorithms". Virtual conference. https://proceedings.neurips.cc/paper/2020/hash/e834cb114d33f729dbc9c7fb0c6bb607-Abstract.html. Retrieved 18 December 2025.
5. ↑ Grigorescu, Elena; Lin, Young-San; Silwal, Sandeep; Song, Maoyuan; Zhou, Samson (2022). "Learning-Augmented Algorithms for Online Linear and Semidefinite Programming". arXiv:2209.10614 [cs].
6. ↑ Im, Sungjin; Kumar, Ravi; Montazer Qaem, Mahshid; Purohit, Manish (2021). "Non-Clairvoyant Scheduling with Predictions". Virtual conference, USA: ACM. pp. 285–294. doi:10.1145/3409964.3461790. https://doi.org/10.1145/3409964.3461790. Retrieved 18 December 2025.
7. ↑ Lindermayr, Alexander; Megow, Nicole (2025). "Permutation Predictions for Non-Clairvoyant Scheduling". ACM Transactions on Parallel Computing (ACM) 12 (2): 4:1–4:26. doi:10.1145/3711872. https://doi.org/10.1145/3711872. Retrieved 18 December 2025.
8. ↑ Jin, Billy; Ma, Will (2022). "Online Bipartite Matching with Advice: Tight Robustness–Consistency Tradeoffs for the Two-Stage Model". New Orleans, Louisiana, United States. http://papers.nips.cc/paper_files/paper/2022/hash/5d68a3f05ee2aae6a0fb2d94959082a0-Abstract-Conference.html. Retrieved 18 December 2025.
9. ↑ Dinitz, Michael; Im, Sungjin; Lavastida, Thomas; Benjamin, Benjamin; Vassilvitskii, Sergei (2021). "Faster Matchings via Learned Duals". Advances in Neural Information Processing Systems. Curran Associates, Inc.. https://proceedings.neurips.cc/paper/2021/file/5616060fb8ae85d93f334e7267307664-Paper.pdf.
10. ↑ Cohen-Addad, Vincent; d'Orsi, Tommaso; Gupta, Anupam; Lee, Euiwoong; Panigrahi, Debmalya (2024). "Learning-Augmented Approximation Algorithms for Maximum Cut and Related Problems". Vancouver, British Columbia, Canada. http://papers.nips.cc/paper_files/paper/2024/hash/2db08b94565c0d582cc53de6cee5fd47-Abstract-Conference.html. Retrieved 18 December 2025.
11. ↑ Antoniadis, Antonios; Eliás, Marek; Polak, Adam; Venzin, Moritz (2025). "Approximation Algorithms for Combinatorial Optimization with Predictions". Singapore: OpenReview. https://openreview.net/forum?id=AEFVa6VMu1. Retrieved 18 December 2025.
12. ↑ Agrawal, Priyank; Balkanski, Eric; Gkatzelis, Vasilis; Ou, Tingting; Tan, Xizhi (2024). "Learning-Augmented Mechanism Design: Leveraging Predictions for Facility Location". Mathematics of Operations Research (INFORMS) 49 (4): 2626–2651. doi:10.1287/MOOR.2022.0225. https://doi.org/10.1287/moor.2022.0225. Retrieved 18 December 2025.

## External links

* An overview of publications about learning augmented algorithms

0.00

(0 votes)

Original source: https://en.wikipedia.org/wiki/Learning augmented algorithm. Read more

|

Retrieved from "https://handwiki.org/wiki/index.php?title=Learning_augmented_algorithm&oldid=4228316"