mlsanityData to 7 Oct 2026

Pareto-Optimal Learning-Augmented Algorithms for Online Conversion Problems

arXiv 2109.01556 ↗First posted 3 Sep 2021cs.LG cs.DScited by 19

Not on the map. Why?

Abstract (arXiv)

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.

Key facts. Cited by 19 papers in the map (data through 7 Oct 2026). Builds on 9 of its 27 references that are in the map. First posted on arXiv 3 Sep 2021.

Builds on

9 of 27 references.

References · 9

  1. 2018Competitive caching with machine learned advicecited by 194
  2. 2020The Primal-Dual method for Learning Augmented Algorithmscited by 78
  3. 2020Online metric algorithms with untrusted predictionscited by 74
  4. 2020Secretary and Online Matching Problems with Machine Learned Advicecited by 71
  5. 2020Optimal Robustness-Consistency Trade-offs for Learning-Augmented Online Algorithmscited by 64
  6. 2019Online Computation with Untrusted Advicecited by 42
  7. 2020Competitive Algorithms for the Online Multiple Knapsack Problem with Application to Electric Vehicle Chargingcited by 15
  8. 2020Data-driven Competitive Algorithms for Online Knapsack and Set Covercited by 14
  9. 2017Optimal Posted Prices for Online Cloud Resource Allocationcited by 8

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2022: 2; 2023: 3; 2024: 7; 2025: 6; 2026: 1.

19 papers.

Sort:

  1. 2022Smoothed Online Optimization with Unreliable Predictionscited by 10
  2. 2023Online Conversion with Switching Costs: Robust and Learning-Augmented Algorithmscited by 10
  3. 2022Online Search with Predictions: Pareto-optimal Algorithm and its Applications in Energy Marketscited by 9
  4. 2023Online Algorithms with Uncertainty-Quantified Predictionscited by 9
  5. 2024Contract Scheduling with Distributional and Multiple Advicecited by 8
  6. 2024Overcoming Brittleness in Pareto-Optimal Learning-Augmented Algorithmscited by 8
  7. 2025On Tradeoffs in Learning-Augmented Algorithmscited by 7
  8. 2024Robust Learning-Augmented Dictionariescited by 6
  9. 2024Near-Optimal Consistency-Robustness Trade-Offs for Learning-Augmented Online Knapsack Problemscited by 5
  10. 2024Chasing Convex Functions with Long-term Constraintscited by 4
  11. 2025Pareto-Optimality, Smoothness, and Stochasticity in Learning-Augmented One-Max-Searchcited by 4
  12. 2023Time Fairness in Online Knapsack Problemscited by 3
7 more
  1. 2025Learning-Augmented Online Bidding in Stochastic Settingscited by 3
  2. 2024LACS: Learning-Augmented Algorithms for Carbon-Aware Resource Scaling with Uncertain Demandcited by 2
  3. 2026The Secretary Problem with Predictions and a Chosen Ordercited by 2
  4. 2024Learning-Augmented Competitive Algorithms for Spatiotemporal Online Allocation with Deadline Constraintscited by 0
  5. 2025Decision-Theoretic Approaches for Improved Learning-Augmented Algorithmscited by 0
  6. 2025Signal-Aware Workload Shifting Algorithms with Uncertainty-Quantified Predictorscited by 0
  7. 2025Online Multi-Class Selection with Group Fairness Guaranteecited by 0