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. .

[img] PDF - Submitted Version
See Usage Policy.


Use this Persistent URL to link to this item:


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 Paper
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
Record Number:CaltechAUTHORS:20220304-172334654
Persistent URL:
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:113731
Deposited By: George Porter
Deposited On:07 Mar 2022 20:30
Last Modified:07 Mar 2022 20:30

Repository Staff Only: item control page