CaltechAUTHORS
  A Caltech Library Service

Pareto-Optimal Learning-Augmented Algorithms for Online Conversion Problems

Sun, Bo and Lee, Russell and Hajiesmaili, Mohammad and Wierman, Adam and Tsang, Danny H. K. (2021) Pareto-Optimal Learning-Augmented Algorithms for Online Conversion Problems. . https://resolver.caltech.edu/CaltechAUTHORS:20220304-172334654

[img] PDF - Submitted Version
See Usage Policy.

818kB

Use this Persistent URL to link to this item: https://resolver.caltech.edu/CaltechAUTHORS:20220304-172334654

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.


Item Type:Report or Paper (Discussion Paper)
Related URLs:
URLURL TypeDescription
https://doi.org/10.48550/arXiv.2109.01556arXivDiscussion Paper
ORCID:
AuthorORCID
Sun, Bo0000-0003-3172-7811
Lee, Russell0000-0001-9016-5973
Hajiesmaili, Mohammad0000-0001-9278-2254
Wierman, Adam0000-0002-5923-0199
Tsang, Danny H. K.0000-0003-0135-7098
DOI:10.48550/arXiv.2109.01556
Record Number:CaltechAUTHORS:20220304-172334654
Persistent URL:https://resolver.caltech.edu/CaltechAUTHORS:20220304-172334654
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:113731
Collection:CaltechAUTHORS
Deposited By: George Porter
Deposited On:07 Mar 2022 20:30
Last Modified:07 Mar 2022 20:30

Repository Staff Only: item control page