Learning Better Predictions for Warm-Starting Algorithms

Recently developed warm-starting learning-augmented algorithms offer improved running times for a number of computational problems when provided with predicted solutions that are reasonably *close* to optimal solutions. This poses a fundamental *learning problem*: Find a prediction that works well, on average, for instances drawn from a given distribution. This learning problem is typically solved under the simplifying assumption that each instance has a *unique* optimal solution, which is a strong assumption, and very far from truth in many practical scenarios. In this paper we study the more realistic learning setting that allows for the presence of multiple optimal solutions. We focus on the two most popular problems in the literature on warm start with predictions, namely *bipartite min-cost perfect matching* and *maximum flow*. For the matching problem, we show how to learn an integral dual prediction minimizing the ${\ell }_1$ distance to the closest integral dual solution, which can be fed to the warm-starting algorithm of Dinitz et al. (NeurIPS 2021). We also show NP-hardness of the analogous learning problem for the ${\ell }_0$ prediction error metric, which is used in the work of Chen et al. (ICML 2022). For the flow problem, we show that, even though the corresponding ${\ell }_1$ learning problem is NP-hard, nonetheless we can optimize a function that is a more direct and *tighter* upper bound on the running time of the warm-starting algorithm of Davies et al. (ICML 2023). We expect that our findings will inspire more research on applying combinatorial optimization toolbox to learning problems motivated by algorithms with predictions, which so far are primarily studied through the continuous optimization lens.