# Rethinking Warm-Starts with Predictions: Learning Predictions Close to Sets of Optimal Solutions for Faster L-/L^natural-Convex Function Minimization

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

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- Builds on 16 of its 40 references that are in the map.
- First posted on arXiv 2 Feb 2023.

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

- [Online Learning: A Modern Introduction Using Convex Optimization](https://mlsanity.com/paper/1912.13213/) (2019)
- [Competitive caching with machine learned advice](https://mlsanity.com/paper/1802.05399/) (2018)
- [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)
- [Faster Matchings via Learned Duals](https://mlsanity.com/paper/2107.09770/) (2021)
- [A Faster Cutting Plane Method and its Implications for Combinatorial and Convex Optimization](https://mlsanity.com/paper/1508.04874/) (2015)
- [Faster Fundamental Graph Algorithms via Learned Predictions](https://mlsanity.com/paper/2204.12055/) (2022)
- [Learning-Augmented k-means Clustering](https://mlsanity.com/paper/2110.14094/) (2021)
- [Online Graph Algorithms with Predictions](https://mlsanity.com/paper/2112.11831/) (2021)
- [Learning Predictions for Algorithms with Predictions](https://mlsanity.com/paper/2202.09312/) (2022)
- [Learning-Augmented Mechanism Design: Leveraging Predictions for Facility Location](https://mlsanity.com/paper/2204.01120/) (2022)
- [Learning-based Support Estimation in Sublinear Time](https://mlsanity.com/paper/2106.08396/) (2021)
- [Discrete-Convex-Analysis-Based Framework for Warm-Starting Algorithms with Predictions](https://mlsanity.com/paper/2205.09961/) (2022)
- [Learning-Augmented Maximum Flow](https://mlsanity.com/paper/2207.12911/) (2022)
- [Learning to Hash Robustly, Guaranteed](https://mlsanity.com/paper/2108.05433/) (2021)
- [Generalized Sorting with Predictions](https://mlsanity.com/paper/2011.00172/) (2020)

## Built on by (most cited first, 3 of 3)

- [Faster Discrete Convex Function Minimization with Predictions: The M-Convex Case](https://mlsanity.com/paper/2306.05865/) (2023)
- [Online Lnatural-Convex Minimization](https://mlsanity.com/paper/2404.17158/) (2024)
- [Learning-Augmented Scalable Linear Assignment Problem Optimization via Neural Dual Warm-Starts](https://mlsanity.com/paper/2605.09382/) (2026)

## Abstract (arXiv)

An emerging line of work has shown that machine-learned predictions are useful to warm-start algorithms for discrete optimization problems, such as bipartite matching. Previous studies have shown time complexity bounds proportional to some distance between a prediction and an optimal solution, which we can approximately minimize by learning predictions from past optimal solutions. However, such guarantees may not be meaningful when multiple optimal solutions exist. Indeed, the dual problem of bipartite matching and, more generally, L-/L^natural-convex function minimization have arbitrarily many optimal solutions, making such prediction-dependent bounds arbitrarily large. To resolve this theoretically critical issue, we present a new warm-start-with-prediction framework for L-/L^natural-convex function minimization. Our framework offers time complexity bounds proportional to the distance between a prediction and the set of all optimal solutions. The main technical difficulty lies in learning predictions that are provably close to sets of all optimal solutions, for which we present an online-gradient-descent-based method. We thus give the first polynomial-time learnability of predictions that can provably warm-start algorithms regardless of multiple optimal solutions.