Timezone: »

 
Poster
Pareto-Optimal Learning-Augmented Algorithms for Online Conversion Problems
Bo Sun · Russell Lee · Mohammad Hajiesmaili · Adam Wierman · Danny Tsang

Tue Dec 07 04:30 PM -- 06:00 PM (PST) @ Virtual
in Poster Session 2 »

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.

Keywords: Robustness

Author Information

Bo Sun (The Hong Kong University of Science and Technology)
Russell Lee (University of Massachusetts Amherst)
Mohammad Hajiesmaili (UMass Amherst)
Adam Wierman (Caltech)
Danny Tsang (The Hong Kong University of Science and Technology)

More from the Same Authors