Learning augmented algorithm - Revision history

Citation bot: Altered isbn. Add: url, isbn. Upgrade ISBN10 to 13. | Use this bot. Report bugs. | Suggested by Dominic3203 | Category:Theoretical computer science | #UCB_Category 4/137

2025-03-26T02:25:58Z

Altered isbn. Add: url, isbn. Upgrade ISBN10 to 13. | Use this bot. Report bugs. | Suggested by Dominic3203 | Category:Theoretical computer science | #UCB_Category 4/137

← Previous revision		Revision as of 02:25, 26 March 2025
Line 1:		Line 1:
	A '''learning augmented algorithm''' is an [[algorithm]] that can make use of a prediction to improve its performance.<ref name="MitzenmacherVassilvitskii2020">{{cite book \| title = Beyond the Worst-Case Analysis of Algorithms \| last1 = Mitzenmacher \| author-link1 = Michael Mitzenmacher \| first1 = Michael \| last2 = Vassilvitskii \| first2 = Sergei \| chapter = Algorithms with Predictions \| date = 31 December 2020 \| pages = 646–662 \| publisher = Cambridge University Press \| doi = 10.1017/9781108637435.037 \| arxiv=2006.09123 }}</ref>		A '''learning augmented algorithm''' is an [[algorithm]] that can make use of a prediction to improve its performance.<ref name="MitzenmacherVassilvitskii2020">{{cite book \| title = Beyond the Worst-Case Analysis of Algorithms \| last1 = Mitzenmacher \| author-link1 = Michael Mitzenmacher \| first1 = Michael \| last2 = Vassilvitskii \| first2 = Sergei \| chapter = Algorithms with Predictions \| date = 31 December 2020 \| pages = 646–662 \| publisher = Cambridge University Press \| doi = 10.1017/9781108637435.037 \| arxiv=2006.09123 \| isbn = 978-1-108-63743-5 }}</ref>
	Whereas in regular algorithms just the problem instance is inputted, learning augmented algorithms accept an extra parameter.		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 extra parameter often is a prediction of some property of the solution.
Line 30:		Line 30:
	=== More examples ===		=== More examples ===
	Learning augmented algorithms are known for:		Learning augmented algorithms are known for:
	* The [[ski rental problem]]<ref name="WangLiWang2020">{{cite book \| title=NIPS'20: Proceedings of the 34th International Conference on Neural Information Processing Systems \| chapter = Online Algorithms for Multi-shop Ski Rental with Machine Learned Advice \| date=2020 \| isbn=1-71382-954-1 \| oclc=1263313383 \| arxiv = 2002.05808 \| first1 = Shufan \| last1 = Wang		* The [[ski rental problem]]<ref name="WangLiWang2020">{{cite book \| title=NIPS'20: Proceedings of the 34th International Conference on Neural Information Processing Systems \| chapter = Online Algorithms for Multi-shop Ski Rental with Machine Learned Advice \| date=2020 \| isbn=978-1-71382-954-6 \| oclc=1263313383 \| arxiv = 2002.05808 \| first1 = Shufan \| last1 = Wang
	\| first2 = Jian		\| first2 = Jian
	\| last2 = Li		\| last2 = Li
Line 52:		Line 52:
	\| date = 2021		\| date = 2021
	}}</ref>		}}</ref>
	* The weighted [[Page replacement algorithm#The (h,k)-paging problem\|paging problem]]<ref name="BansalCoesterKumar2022">{{cite book \| title = Proceedings of the 2022 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) \| last1 = Bansal \| first1 = Nikhil \| last2 = Coester \| first2 = Christian \| last3 = Kumar \| first3 = Ravi \| last4 = Purohit \| first4 = Manish \| last5 = Vee \| first5 = Erik \| chapter = Learning-Augmented Weighted Paging \| date = January 2022 \| pages = 67–89 \| publisher = Society for Industrial and Applied Mathematics \| doi = 10.1137/1.9781611977073.4 \| arxiv = }}</ref>		* The weighted [[Page replacement algorithm#The (h,k)-paging problem\|paging problem]]<ref name="BansalCoesterKumar2022">{{cite book \| title = Proceedings of the 2022 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) \| last1 = Bansal \| first1 = Nikhil \| last2 = Coester \| first2 = Christian \| last3 = Kumar \| first3 = Ravi \| last4 = Purohit \| first4 = Manish \| last5 = Vee \| first5 = Erik \| chapter = Learning-Augmented Weighted Paging \| date = January 2022 \| pages = 67–89 \| publisher = Society for Industrial and Applied Mathematics \| doi = 10.1137/1.9781611977073.4 \| arxiv = \| isbn = 978-1-61197-707-3 \| url = https://ora.ox.ac.uk/objects/uuid:f8f430f4-23fd-49b9-9cf4-1c24230151cf }}</ref>

	== See also ==		== See also ==

82.69.116.10: /* Binary search */

2025-02-17T11:03:32Z

Binary search

← Previous revision		Revision as of 11:03, 17 February 2025
Line 14:		Line 14:
	== Examples ==		== Examples ==
	=== Binary search ===		=== Binary search ===
	The [[binary search algorithm]] is an algorithm for finding elements of a sorted list <math>x_1,\ldots,x_n</math>. It needs <math>O(\log(n))</math> steps to find an element with some known value <math>x</math> in a list of length <math>n</math>.		The [[binary search algorithm]] is an algorithm for finding elements of a sorted list <math>x_1,\ldots,x_n</math>. It needs <math>O(\log(n))</math> steps to find an element with some known value <math>y</math> in a list of length <math>n</math>.
	With a prediction <math>i</math> for the position of <math>x</math>, the following learning augmented algorithm can be used.<ref name="MitzenmacherVassilvitskii2020" />		With a prediction <math>i</math> for the position of <math>y</math>, the following learning augmented algorithm can be used.<ref name="MitzenmacherVassilvitskii2020" />

	* First, look at position <math>i</math> in the list. If <math>x_i=y</math>, the element has been found.		* First, look at position <math>i</math> in the list. If <math>x_i=y</math>, the element has been found.

GünniX: ref name

2025-02-15T10:48:06Z

ref name

← Previous revision		Revision as of 10:48, 15 February 2025
Line 35:		Line 35:
	\| first3 = Shiqiang		\| first3 = Shiqiang
	\| last3 = Wang}}</ref>		\| last3 = Wang}}</ref>
	* The [[maximum weight matching]] problem<ref name="">{{cite book		* The [[maximum weight matching]] problem<ref name="neurips_5616060fb8ae85d93f334e7267307664">{{cite book
	\| first1 = Michael		\| first1 = Michael
	\| last1 = Dinitz		\| last1 = Dinitz

Paloappie: Fixed: Multiple categories on one line

2022-06-24T06:44:20Z

Fixed: Multiple categories on one line

← Previous revision		Revision as of 06:44, 24 June 2022
Line 30:		Line 30:
	=== More examples ===		=== More examples ===
	Learning augmented algorithms are known for:		Learning augmented algorithms are known for:
	* The [[ski rental problem]]<ref name="WangLiWang2020">{{cite book \| title=NIPS'20: Proceedings of the 34th International Conference on Neural Information Processing Systems \| chapter = Online Algorithms for Multi-shop Ski Rental with Machine Learned Advice \| date=2020 \| isbn=1-~~7138~~-~~2954~~-1 \| oclc=1263313383 \| arxiv = 2002.05808 \| first1 = Shufan \| last1 = Wang		* The [[ski rental problem]]<ref name="WangLiWang2020">{{cite book \| title=NIPS'20: Proceedings of the 34th International Conference on Neural Information Processing Systems \| chapter = Online Algorithms for Multi-shop Ski Rental with Machine Learned Advice \| date=2020 \| isbn=1-71382-954-1 \| oclc=1263313383 \| arxiv = 2002.05808 \| first1 = Shufan \| last1 = Wang
	\| first2 = Jian		\| first2 = Jian
	\| last2 = Li		\| last2 = Li
Line 63:		Line 63:
	* [https://algorithms-with-predictions.github.io/ An overview of publications about learning augmented algorithms]		* [https://algorithms-with-predictions.github.io/ An overview of publications about learning augmented algorithms]

	[[Category:Algorithms]] [[Category:Theoretical computer science]]		[[Category:Algorithms]]
			[[Category:Theoretical computer science]]

Plusminusone: Add link to list of publications on topic

2022-05-26T13:25:42Z

Add link to list of publications on topic

← Previous revision		Revision as of 13:25, 26 May 2022
Line 60:		Line 60:
	{{Reflist}}		{{Reflist}}

			== External links ==
			* [https://algorithms-with-predictions.github.io/ An overview of publications about learning augmented algorithms]

	[[Category:Algorithms]] [[Category:Theoretical computer science]]		[[Category:Algorithms]] [[Category:Theoretical computer science]]

AnomieBOT: Dating maintenance tags: {{Fact}}

2022-05-23T21:08:08Z

Dating maintenance tags: {{Fact}}

← Previous revision		Revision as of 21:08, 23 May 2022
Line 10:		Line 10:
	* '''Robustnesss.''' An algorithm is called robust if its worst-case performance can be bounded even if the given prediction is inaccurate.<ref name="MitzenmacherVassilvitskii2020" />		* '''Robustnesss.''' An algorithm is called robust if its worst-case performance can be bounded even if the given prediction is inaccurate.<ref name="MitzenmacherVassilvitskii2020" />

	Learning augmented algorithms generally do not prescribe how the prediction should be done. For this purpose [[machine learning]] can be used.{{fact}}		Learning augmented algorithms generally do not prescribe how the prediction should be done. For this purpose [[machine learning]] can be used.{{fact\|date=May 2022}}

	== Examples ==		== Examples ==

Dl2000: /* Binary search */ fix refpunct

2022-05-23T20:34:09Z

Binary search: fix refpunct

← Previous revision		Revision as of 20:34, 23 May 2022
Line 15:		Line 15:
	=== Binary search ===		=== Binary search ===
	The [[binary search algorithm]] is an algorithm for finding elements of a sorted list <math>x_1,\ldots,x_n</math>. It needs <math>O(\log(n))</math> steps to find an element with some known value <math>x</math> in a list of length <math>n</math>.		The [[binary search algorithm]] is an algorithm for finding elements of a sorted list <math>x_1,\ldots,x_n</math>. It needs <math>O(\log(n))</math> steps to find an element with some known value <math>x</math> in a list of length <math>n</math>.
	With a prediction <math>i</math> for the position of <math>x</math>, the following learning augmented algorithm can be used<ref name="MitzenmacherVassilvitskii2020" />:		With a prediction <math>i</math> for the position of <math>x</math>, the following learning augmented algorithm can be used.<ref name="MitzenmacherVassilvitskii2020" />

	* First, look at position <math>i</math> in the list. If <math>x_i=y</math>, the element has been found.		* First, look at position <math>i</math> in the list. If <math>x_i=y</math>, the element has been found.

Dl2000: fix refpunct; need ref; tidy

2022-05-23T20:25:31Z

fix refpunct; need ref; tidy

← Previous revision		Revision as of 20:25, 23 May 2022
Line 1:		Line 1:
	A '''learning augmented algorithm''' is an [[algorithm]] that can make use of a prediction to improve its performance		A '''learning augmented algorithm''' is an [[algorithm]] that can make use of a prediction to improve its performance.<ref name="MitzenmacherVassilvitskii2020">{{cite book \| title = Beyond the Worst-Case Analysis of Algorithms \| last1 = Mitzenmacher \| author-link1 = Michael Mitzenmacher \| first1 = Michael \| last2 = Vassilvitskii \| first2 = Sergei \| chapter = Algorithms with Predictions \| date = 31 December 2020 \| pages = 646–662 \| publisher = Cambridge University Press \| doi = 10.1017/9781108637435.037 \| arxiv=2006.09123 }}</ref>
	<ref name="MitzenmacherVassilvitskii2020">{{cite book \| title = Beyond the Worst-Case Analysis of Algorithms \| last1 = Mitzenmacher \| author-link1 = Michael Mitzenmacher \| first1 = Michael \| last2 = Vassilvitskii \| first2 = Sergei \| chapter = Algorithms with Predictions \| date = 31 December 2020 \| pages = 646–662 \| publisher = Cambridge University Press \| doi = 10.1017/9781108637435.037 \| arxiv=2006.09123 }}</ref>.
	Whereas in regular algorithms just the problem instance is inputted, learning augmented algorithms accept an extra parameter.		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 extra parameter often is a prediction of some property of the solution.
Line 8:		Line 7:
	A learning augmented algorithm typically takes an input <math>(\mathcal{I}, \mathcal{A})</math>. Here <math>\mathcal{I}</math> is a problem instance and <math>\mathcal{A}</math> 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:		A learning augmented algorithm typically takes an input <math>(\mathcal{I}, \mathcal{A})</math>. Here <math>\mathcal{I}</math> is a problem instance and <math>\mathcal{A}</math> 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<ref name="MitzenmacherVassilvitskii2020" />. Usually, this is quantified by giving a bound on the performance that depends on the error in the prediction.		* '''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.<ref name="MitzenmacherVassilvitskii2020" /> 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<ref name="MitzenmacherVassilvitskii2020" />.		* '''Robustnesss.''' An algorithm is called robust if its worst-case performance can be bounded even if the given prediction is inaccurate.<ref name="MitzenmacherVassilvitskii2020" />

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

	== Examples ==		== Examples ==
Line 28:		Line 27:
	So, when the error is small, the algorithm is faster than a normal binary search. This shows that the algorithm is consistent.		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 <math>n</math>. Then the algorithm takes at most <math>O(\log(n))</math> steps, so the algorithm is robust.		Even in the worst case, the error will be at most <math>n</math>. Then the algorithm takes at most <math>O(\log(n))</math> steps, so the algorithm is robust.

	=== More examples ===		=== More examples ===
	Learning augmented algorithms are known for:		Learning augmented algorithms are known for:

Plusminusone: Create page

2022-05-23T20:03:55Z

Create page

New page

A '''learning augmented algorithm''' is an [[algorithm]] that can make use of a prediction to improve its performance
<ref name="MitzenmacherVassilvitskii2020">{{cite book | title = Beyond the Worst-Case Analysis of Algorithms | last1 = Mitzenmacher | author-link1 = Michael Mitzenmacher | first1 = Michael | last2 = Vassilvitskii | first2 = Sergei | chapter = Algorithms with Predictions | date = 31 December 2020 | pages = 646–662 | publisher = Cambridge University Press | doi = 10.1017/9781108637435.037 | arxiv=2006.09123 }}</ref>.
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.

== Description ==
A learning augmented algorithm typically takes an input <math>(\mathcal{I}, \mathcal{A})</math>. Here <math>\mathcal{I}</math> is a problem instance and <math>\mathcal{A}</math> 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<ref name="MitzenmacherVassilvitskii2020" />. 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<ref name="MitzenmacherVassilvitskii2020" />.

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

== Examples ==
=== Binary search ===
The [[binary search algorithm]] is an algorithm for finding elements of a sorted list <math>x_1,\ldots,x_n</math>. It needs <math>O(\log(n))</math> steps to find an element with some known value <math>x</math> in a list of length <math>n</math>.
With a prediction <math>i</math> for the position of <math>x</math>, the following learning augmented algorithm can be used<ref name="MitzenmacherVassilvitskii2020" />:

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

The error is defined to be <math>\eta=|i-i^*|</math>, where <math>i^*</math> is the real index of <math>y</math>.
In the learning augmented algorithm, probing the positions <math>i+1,i+2,i+4,\ldots</math> takes <math>\log_2(\eta)</math> steps.
Then a binary search is performed on a list of size at most <math>2\eta</math>, which takes <math>\log_2(\eta)</math> steps. This makes the total running time of the algorithm <math>2\log_2(\eta)</math>.
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 <math>n</math>. Then the algorithm takes at most <math>O(\log(n))</math> steps, so the algorithm is robust.
=== More examples ===
Learning augmented algorithms are known for:
* The [[ski rental problem]]<ref name="WangLiWang2020">{{cite book | title=NIPS'20: Proceedings of the 34th International Conference on Neural Information Processing Systems | chapter = Online Algorithms for Multi-shop Ski Rental with Machine Learned Advice | date=2020 | isbn=1-7138-2954-1 | oclc=1263313383 | arxiv = 2002.05808 | first1 = Shufan | last1 = Wang
| first2 = Jian
| last2 = Li
| first3 = Shiqiang
| last3 = Wang}}</ref>
* The [[maximum weight matching]] problem<ref name="">{{cite book
| first1 = Michael
| last1 = Dinitz
| first2 = Sungjin
| last2 = Im
| first3 = Thomas
| last3 = Lavastida
| first4 = Benjamin
| last4 = Benjamin
| first5 = Sergei
| last5 = Vassilvitskii
| title = Advances in Neural Information Processing Systems
| publisher = Curran Associates, Inc.
| chapter = Faster Matchings via Learned Duals
| url = https://proceedings.neurips.cc/paper/2021/file/5616060fb8ae85d93f334e7267307664-Paper.pdf
| date = 2021
}}</ref>
* The weighted [[Page replacement algorithm#The (h,k)-paging problem|paging problem]]<ref name="BansalCoesterKumar2022">{{cite book | title = Proceedings of the 2022 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) | last1 = Bansal | first1 = Nikhil | last2 = Coester | first2 = Christian | last3 = Kumar | first3 = Ravi | last4 = Purohit | first4 = Manish | last5 = Vee | first5 = Erik | chapter = Learning-Augmented Weighted Paging | date = January 2022 | pages = 67–89 | publisher = Society for Industrial and Applied Mathematics | doi = 10.1137/1.9781611977073.4 | arxiv = }}</ref>

== See also ==
* [[Machine learning]]

== References ==
{{Reflist}}

[[Category:Algorithms]] [[Category:Theoretical computer science]]