Optimal robustness-consistency tradeoffs for learning-augmented metrical task systems

Nicolas Christianson, Junxuan Shen, Adam Wierman
Proceedings of The 26th International Conference on Artificial Intelligence and Statistics, PMLR 206:9377-9399, 2023.

Abstract

We examine the problem of designing learning-augmented algorithms for metrical task systems (MTS) that exploit machine-learned advice while maintaining rigorous, worst-case guarantees on performance. We propose an algorithm, DART, that achieves this dual objective, providing cost within a multiplicative factor $(1+\epsilon)$ of the machine-learned advice (i.e., consistency) while ensuring cost within a multiplicative factor $2^{O(1/\epsilon)}$ of a baseline robust algorithm (i.e., robustness) for any $\epsilon > 0$. We show that this exponential tradeoff between consistency and robustness is unavoidable in general, but that in important subclasses of MTS, such as when the metric space has bounded diameter and in the $k$-server problem, our algorithm achieves improved, polynomial tradeoffs between consistency and robustness.

Cite this Paper

BibTeX
@InProceedings{pmlr-v206-christianson23a, title = {Optimal robustness-consistency tradeoffs for learning-augmented metrical task systems}, author = {Christianson, Nicolas and Shen, Junxuan and Wierman, Adam}, booktitle = {Proceedings of The 26th International Conference on Artificial Intelligence and Statistics}, pages = {9377--9399}, year = {2023}, editor = {Ruiz, Francisco and Dy, Jennifer and van de Meent, Jan-Willem}, volume = {206}, series = {Proceedings of Machine Learning Research}, month = {25--27 Apr}, publisher = {PMLR}, pdf = {https://proceedings.mlr.press/v206/christianson23a/christianson23a.pdf}, url = {https://proceedings.mlr.press/v206/christianson23a.html}, abstract = {We examine the problem of designing learning-augmented algorithms for metrical task systems (MTS) that exploit machine-learned advice while maintaining rigorous, worst-case guarantees on performance. We propose an algorithm, DART, that achieves this dual objective, providing cost within a multiplicative factor $(1+\epsilon)$ of the machine-learned advice (i.e., consistency) while ensuring cost within a multiplicative factor $2^{O(1/\epsilon)}$ of a baseline robust algorithm (i.e., robustness) for any $\epsilon > 0$. We show that this exponential tradeoff between consistency and robustness is unavoidable in general, but that in important subclasses of MTS, such as when the metric space has bounded diameter and in the $k$-server problem, our algorithm achieves improved, polynomial tradeoffs between consistency and robustness.} }
Endnote
%0 Conference Paper %T Optimal robustness-consistency tradeoffs for learning-augmented metrical task systems %A Nicolas Christianson %A Junxuan Shen %A Adam Wierman %B Proceedings of The 26th International Conference on Artificial Intelligence and Statistics %C Proceedings of Machine Learning Research %D 2023 %E Francisco Ruiz %E Jennifer Dy %E Jan-Willem van de Meent %F pmlr-v206-christianson23a %I PMLR %P 9377--9399 %U https://proceedings.mlr.press/v206/christianson23a.html %V 206 %X We examine the problem of designing learning-augmented algorithms for metrical task systems (MTS) that exploit machine-learned advice while maintaining rigorous, worst-case guarantees on performance. We propose an algorithm, DART, that achieves this dual objective, providing cost within a multiplicative factor $(1+\epsilon)$ of the machine-learned advice (i.e., consistency) while ensuring cost within a multiplicative factor $2^{O(1/\epsilon)}$ of a baseline robust algorithm (i.e., robustness) for any $\epsilon > 0$. We show that this exponential tradeoff between consistency and robustness is unavoidable in general, but that in important subclasses of MTS, such as when the metric space has bounded diameter and in the $k$-server problem, our algorithm achieves improved, polynomial tradeoffs between consistency and robustness.
APA
Christianson, N., Shen, J. & Wierman, A.. (2023). Optimal robustness-consistency tradeoffs for learning-augmented metrical task systems. Proceedings of The 26th International Conference on Artificial Intelligence and Statistics, in Proceedings of Machine Learning Research 206:9377-9399 Available from https://proceedings.mlr.press/v206/christianson23a.html.

Related Material