Pareto-Optimal Learning-Augmented Algorithms for Online Conversion Problems
Authors: Bo Sun, Russell Lee, Mohammad Hajiesmaili, Adam Wierman, Danny Tsang
NeurIPS 2021 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Experimental | 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 worstcase 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. We end with a case study on the exchange of Bitcoin (BTC) to USD. This case study is timely since the rapid growth of cryptocurrency has left many traders eager to profit from rising and falling of exchange rates in average-case scenarios, while the uncertainty and volatility of cryptocurrency have made many traders cautious of unforeseeable crashes in worst-case scenarios. Our results answer two questions: (Q1) How does the learning-augmented OTA compare to pure online algorithms with different prediction qualities and drastic exchange rate crashes? (Q2) How should the OTA select the robustness parameter λ, and especially, would an online learning algorithm work in practice? Setup. We use historical BTC prices in USD of 5 years from 2015 to 2020, with exchange rates collected every 5 minutes from the Gemini exchange. |
| Researcher Affiliation | Academia | Bo Sun ECE, HKUST bsunaa@connect.ust.hk Russell Lee CICS, UMass Amherst rclee@cs.umass.edu Mohammad Hajiesmaili CICS, UMass Amherst hajiesmaili@cs.umass.edu Adam Wierman CMS, Caltech adamw@caltech.edu Danny H.K. Tsang ECE, HKUST eetsang@ust.hk |
| Pseudocode | Yes | Algorithm 1 Online threshold-based algorithm with threshold function φ (OTAφ) 1: input: threshold function φ( ), and initial resource utilization (i.e., traded dollar) w(0) = 0; 2: while price vn is revealed do 3: determine resource allocation xn = arg maxxn Xn vnxn R w(n 1)+xn w(n 1) φ(u)du; 4: update the utilization w(n) = w(n 1) + xn. 5: end while |
| Open Source Code | No | The paper does not explicitly state that source code for their methodology is provided or made publicly available. |
| Open Datasets | No | We use historical BTC prices in USD of 5 years from 2015 to 2020, with exchange rates collected every 5 minutes from the Gemini exchange. |
| Dataset Splits | No | The paper does not provide explicit details about train/validation/test dataset splits, or any other data partitioning strategy for reproducibility. |
| Hardware Specification | No | The paper does not provide specific hardware details (e.g., CPU/GPU models, memory, or cloud instance types) used for running its experiments. |
| Software Dependencies | No | The paper does not provide specific software dependency details with version numbers (e.g., library or solver names with version numbers) needed to replicate the experiment. |
| Experiment Setup | Yes | Setup. We use historical BTC prices in USD of 5 years from 2015 to 2020, with exchange rates collected every 5 minutes from the Gemini exchange. We assume one BTC is available for trading during 250 instances of length one week. Since BTC is traded in the unit of satoshi (i.e., 0.00000001 BTC), this problem fits the fractional conversion setting and we apply the LOA for the one-way trading problem in the following experiments. We set L and U as the historical minimum and maximum prices over the entire 5 years.1 To generate a prediction P, we simply use the observed maximum exchange rate of the previous week. To evaluate the impact of prediction quality, we adjust the error level between 0.0 to 1.0, where 0.0 indicates perfect predictions and 1.0 indicates unadjusted predictions. To evaluate the performance in worst-case settings, we also introduce a crash probability q, where the exchange rate of BTC at the last slot will crash to L with probability q. |