Pareto-Optimal Learning-Augmented Algorithms for Online Conversion Problems
Bo Sun, Russell Lee, Mohammad Hajiesmaili, Adam Wierman, Danny Tsang
Abstract
This paper leverages machine-learned predictions to design competitive algorithms for online conversion problems with the goal of improving the competitive ratio when predictions are accurate (i.e., consistency), while also guaranteeing a worst-case competitive ratio regardless of the prediction quality (i.e., robustness). We unify the algorithmic design of both integral and fractional conversion problems, which are also known as the 1-max-search and one-way trading problems, into a class of online threshold-based algorithms (OTA). By incorporating predictions into design of OTA, we achieve the Pareto-optimal trade-off of consistency and robustness, i.e., no online algorithm can achieve a better consistency guarantee given for a robustness guarantee. We demonstrate the performance of OTA using numerical experiments on Bitcoin conversion.
BibTeX
@inproceedings{
sun2021paretooptimal,
title={Pareto-Optimal Learning-Augmented Algorithms for Online Conversion Problems},
author={Bo Sun and Russell Lee and Mohammad Hajiesmaili and Adam Wierman and Danny Tsang},
booktitle={Advances in Neural Information Processing Systems},
editor={A. Beygelzimer and Y. Dauphin and P. Liang and J. Wortman Vaughan},
year={2021},
url={https://openreview.net/forum?id=ycmcCSoNBx8}
}