# Faster Matchings via Learned Duals

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

## Key facts

- Cited by 56 papers in the map (data through 14 Oct 2026).
- Builds on 20 of its 71 references that are in the map.
- First posted on arXiv 20 Jul 2021.

## Builds on (most cited first, 20 of 20)

- [Competitive caching with machine learned advice](https://mlsanity.com/paper/1802.05399/) (2018)
- [The Case for Learned Index Structures](https://mlsanity.com/paper/1712.01208/) (2017)
- [Algorithms with Predictions](https://mlsanity.com/paper/2006.09123/) (2020)
- [The Primal-Dual method for Learning Augmented Algorithms](https://mlsanity.com/paper/2010.11632/) (2020)
- [Learning to Branch](https://mlsanity.com/paper/1803.10150/) (2018)
- [Online metric algorithms with untrusted predictions](https://mlsanity.com/paper/2003.02144/) (2020)
- [Near-Optimal Bounds for Online Caching with Machine Learned Advice](https://mlsanity.com/paper/1910.12172/) (2019)
- [Secretary and Online Matching Problems with Machine Learned Advice](https://mlsanity.com/paper/2006.01026/) (2020)
- [A Model for Learned Bloom Filters, and Optimizing by Sandwiching](https://mlsanity.com/paper/1901.00902/) (2019)
- [A PAC Approach to Application-Specific Algorithm Selection](https://mlsanity.com/paper/1511.07147/) (2015)
- [Secretaries with Advice](https://mlsanity.com/paper/2011.06726/) (2020)
- [Dispersion for Data-Driven Algorithm Design, Online Learning, and Private Optimization](https://mlsanity.com/paper/1711.03091/) (2017)
- [Online Algorithms for Weighted Paging with Predictions](https://mlsanity.com/paper/2006.09509/) (2020)
- [How much data is sufficient to learn high-performing algorithms? Generalization guarantees for data-driven algorithm design](https://mlsanity.com/paper/1908.02894/) (2019)
- [Data-Driven Clustering via Parameterized Lloyd's Families](https://mlsanity.com/paper/1809.06987/) (2018)
- [Bipartite Matching in Nearly-linear Time on Moderately Dense Graphs](https://mlsanity.com/paper/2009.01802/) (2020)
- [(Learned) Frequency Estimation Algorithms under Zipfian Distribution](https://mlsanity.com/paper/1908.05198/) (2019)
- [Partitioned Learned Bloom Filter](https://mlsanity.com/paper/2006.03176/) (2020)
- [Composable Sketches for Functions of Frequencies: Beyond the Worst Case](https://mlsanity.com/paper/2004.04772/) (2020)
- [New Deterministic Approximation Algorithms for Fully Dynamic Matching](https://mlsanity.com/paper/1604.05765/) (2016)

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

- [Tutorial on amortized optimization](https://mlsanity.com/paper/2202.00665/) (2022)
- [Learning to Warm-Start Fixed-Point Optimization Algorithms](https://mlsanity.com/paper/2309.07835/) (2023)
- [On amortizing convex conjugates for optimal transport](https://mlsanity.com/paper/2210.12153/) (2022)
- [Learning-Augmented k-means Clustering](https://mlsanity.com/paper/2110.14094/) (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)
- [Triangle and Four Cycle Counting with Predictions in Graph Streams](https://mlsanity.com/paper/2203.09572/) (2022)
- [Algorithms with Prediction Portfolios](https://mlsanity.com/paper/2210.12438/) (2022)
- [Discrete-Convex-Analysis-Based Framework for Warm-Starting Algorithms with Predictions](https://mlsanity.com/paper/2205.09961/) (2022)
- [Sorting with Predictions](https://mlsanity.com/paper/2311.00749/) (2023)
- [Online bipartite matching with imperfect advice](https://mlsanity.com/paper/2405.09784/) (2024)
- [Algorithms for Caching and MTS with reduced number of predictions](https://mlsanity.com/paper/2404.06280/) (2024)
- [(Optimal) Online Bipartite Matching with Degree Information](https://mlsanity.com/paper/2110.11439/) (2021)
- [Learning-Augmented Maximum Flow](https://mlsanity.com/paper/2207.12911/) (2022)
- [Learning-Augmented Algorithms for Online Linear and Semidefinite Programming](https://mlsanity.com/paper/2209.10614/) (2022)
- [Binary Search with Distributional Predictions](https://mlsanity.com/paper/2411.16030/) (2024)
- [Paging with Succinct Predictions](https://mlsanity.com/paper/2210.02775/) (2022)
- [Improved Frequency Estimation Algorithms with and without Predictions](https://mlsanity.com/paper/2312.07535/) (2023)
- [Single-Leg Revenue Management with Advice](https://mlsanity.com/paper/2202.10939/) (2022)
- [Sublinear Time Algorithm for Online Weighted Bipartite Matching](https://mlsanity.com/paper/2208.03367/) (2022)
- [Non-clairvoyant Scheduling with Partial Predictions](https://mlsanity.com/paper/2405.01013/) (2024)
- [Learning-Augmented Priority Queues](https://mlsanity.com/paper/2406.04793/) (2024)
- [Scheduling with Speed Predictions](https://mlsanity.com/paper/2205.01247/) (2022)
- [Learning-Augmented Private Algorithms for Multiple Quantile Release](https://mlsanity.com/paper/2210.11222/) (2022)
- [Online List Labeling with Predictions](https://mlsanity.com/paper/2305.10536/) (2023)
- [The Predicted-Updates Dynamic Model: Offline, Incremental, and Decremental to Fully Dynamic Transformations](https://mlsanity.com/paper/2307.08890/) (2023)
- [Learning-Augmented Search Data Structures](https://mlsanity.com/paper/2402.10457/) (2024)
- [Learning multivariate Gaussians with imperfect advice](https://mlsanity.com/paper/2411.12700/) (2024)
- [Approximate Proportionality in Online Fair Division](https://mlsanity.com/paper/2508.03253/) (2025)
- [On the Power of Learning-Augmented Search Trees](https://mlsanity.com/paper/2211.09251/) (2022)

## Abstract (arXiv)

A recent line of research investigates how algorithms can be augmented with machine-learned predictions to overcome worst case lower bounds. This area has revealed interesting algorithmic insights into problems, with particular success in the design of competitive online algorithms. However, the question of improving algorithm running times with predictions has largely been unexplored. We take a first step in this direction by combining the idea of machine-learned predictions with the idea of "warm-starting" primal-dual algorithms. We consider one of the most important primitives in combinatorial optimization: weighted bipartite matching and its generalization to b-matching. We identify three key challenges when using learned dual variables in a primal-dual algorithm. First, predicted duals may be infeasible, so we give an algorithm that efficiently maps predicted infeasible duals to nearby feasible solutions. Second, once the duals are feasible, they may not be optimal, so we show that they can be used to quickly find an optimal solution. Finally, such predictions are useful only if they can be learned, so we show that the problem of learning duals for matching has low sample complexity. We validate our theoretical findings through experiments on both real and synthetic data. As a result we give a rigorous, practical, and empirically effective method to compute bipartite matchings.