# The Primal-Dual method for Learning Augmented Algorithms

arXiv: https://arxiv.org/abs/2010.11632 · HTML: https://mlsanity.com/paper/2010.11632/

## Key facts

- Cited by 80 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 22 Oct 2020.

## Built on by (most cited first, 30 of 80)

- [Faster Matchings via Learned Duals](https://mlsanity.com/paper/2107.09770/) (2021)
- [Learning Predictions for Algorithms with Predictions](https://mlsanity.com/paper/2202.09312/) (2022)
- [Permutation Predictions for Non-Clairvoyant Scheduling](https://mlsanity.com/paper/2202.10199/) (2022)
- [Online Algorithms with Multiple Predictions](https://mlsanity.com/paper/2205.03921/) (2022)
- [Triangle and Four Cycle Counting with Predictions in Graph Streams](https://mlsanity.com/paper/2203.09572/) (2022)
- [Pareto-Optimal Learning-Augmented Algorithms for Online Conversion Problems](https://mlsanity.com/paper/2109.01556/) (2021)
- [Parsimonious Learning-Augmented Caching](https://mlsanity.com/paper/2202.04262/) (2022)
- [Algorithms with Prediction Portfolios](https://mlsanity.com/paper/2210.12438/) (2022)
- [A Novel Prediction Setup for Online Speed-Scaling](https://mlsanity.com/paper/2112.03082/) (2021)
- [Discrete-Convex-Analysis-Based Framework for Warm-Starting Algorithms with Predictions](https://mlsanity.com/paper/2205.09961/) (2022)
- [Improved Learning-Augmented Algorithms for the Multi-Option Ski Rental Problem via Best-Possible Competitive Analysis](https://mlsanity.com/paper/2302.06832/) (2023)
- [Online bipartite matching with imperfect advice](https://mlsanity.com/paper/2405.09784/) (2024)
- [A Regression Approach to Learning-Augmented Online Algorithms](https://mlsanity.com/paper/2205.08717/) (2022)
- [Learning-Augmented Algorithms for Online Linear and Semidefinite Programming](https://mlsanity.com/paper/2209.10614/) (2022)
- [Learning-augmented Maximum Independent Set](https://mlsanity.com/paper/2407.11364/) (2024)
- [Binary Search with Distributional Predictions](https://mlsanity.com/paper/2411.16030/) (2024)
- [Double Coverage with Machine-Learned Advice](https://mlsanity.com/paper/2103.01640/) (2021)
- [Smoothed Online Optimization with Unreliable Predictions](https://mlsanity.com/paper/2202.03519/) (2022)
- [Active causal structure learning with advice](https://mlsanity.com/paper/2305.19588/) (2023)
- [Online Algorithms with Uncertainty-Quantified Predictions](https://mlsanity.com/paper/2310.11558/) (2023)
- [Learning-Augmented Algorithms for Online TSP on the Line](https://mlsanity.com/paper/2206.00655/) (2022)
- [Beyond Black-Box Advice: Learning-Augmented Algorithms for MDPs with Q-Value Predictions](https://mlsanity.com/paper/2307.10524/) (2023)
- [Overcoming Brittleness in Pareto-Optimal Learning-Augmented Algorithms](https://mlsanity.com/paper/2408.04122/) (2024)
- [Minimalistic Predictions to Schedule Jobs with Online Precedence Constraints](https://mlsanity.com/paper/2301.12863/) (2023)
- [Online Ad Allocation with Predictions](https://mlsanity.com/paper/2302.01827/) (2023)
- [Non-clairvoyant Scheduling with Partial Predictions](https://mlsanity.com/paper/2405.01013/) (2024)
- [Learning-Augmented Priority Queues](https://mlsanity.com/paper/2406.04793/) (2024)
- [Learning-Augmented Algorithms for the Bahncard Problem](https://mlsanity.com/paper/2410.15257/) (2024)
- [On Tradeoffs in Learning-Augmented Algorithms](https://mlsanity.com/paper/2501.12770/) (2025)
- [Learning-Augmented Algorithms for Online Steiner Tree](https://mlsanity.com/paper/2112.05353/) (2021)

## Abstract (arXiv)

The extension of classical online algorithms when provided with predictions is a new and active research area. In this paper, we extend the primal-dual method for online algorithms in order to incorporate predictions that advise the online algorithm about the next action to take. We use this framework to obtain novel algorithms for a variety of online covering problems. We compare our algorithms to the cost of the true and predicted offline optimal solutions and show that these algorithms outperform any online algorithm when the prediction is accurate while maintaining good guarantees when the prediction is misleading.