acceptodds
Under review as a conference paper at ICLR 2027

Learning Better Predictions for Warm-Starting Algorithms

Abstract

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 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 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 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.

Primary area:
learning theory
Keywords:
bipartite matching, maximum flow, learning-augmented algorithms, warm start

Reviews

Among:
Shape:
1234this paper, Top 30%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.67 over 3 reviews, above 70% of the others.
Reviewer_t7wgOpenReview ↗
Rating
3
Confidence
2
Informativeness
2
Presentation
3
Soundness
3
Read review
Paper summary

Recent techniques for warm-starting algorithms show that a good generalization performance requires finding a prediction xx that is close to optimal solutions of training instances on average. Mathematically,

\min_{y\in\mathrm{OPT}(I_j)} \\|x-y\\| \qquad (\ast)$$ where $I_1,...,I_k$ are training instances. The typical way to produce such solution is to assume each training instance has a single optimal solution then solve the resulting sample average approximation problem that is usually easy to solve. The paper studies $(\ast)$ in the more realistic setting where multiple optimal solutions might exist. In particular, it studies the problem for min cost perfect matching and max flow. * For min cost perfect matching: they show $(\ast)$ is solvable in quasi linear time under $\ell_1$ distance, and is NP-hard under $\ell_0$ distance. * For max flow: they show $(\ast)$ is NP-hard for $\ell_1$ distance, and show that it is solvable in almost linear time under a different objective (inspired by the analysis of Davies et al. who show that this different objective is upper-bounded by the objective in (*)). Finally, they provide numerical experiments showing that the predictions they get by solving $(\ast)$ using their algorithms are better than the naive approach of picking an arbitrary optimal solution for each training instance and solving the resulting SAA/ERM problem. They find an improvement in the performance under structured datasets where the Hungarian algorithm can converge to many different optimal solutions..
Critical strengths
  • Modeling: the techniques on warm-starting algorithms give bounds that depend on the objective value of the prediction in (∗)(\ast) but the actual algorithms used in the literature just pick an arbitrary solution for each training instance. The paper proposes to attack the objective (∗)(\ast) itself to improve the quality of predictions. I find this an interesting modeling idea.

  • Technical: The reductions and proofs and clean.

  • Practice: The paper provides numerical studies showing that using predictions resulting from solving (∗)(\ast) directly (using their algorithms) has practical value in some structured cases.

  • Writing: the paper is really well written and very easy to follow.

Critical weaknesses
  • Modeling: the model does not seem to be completely new.. it seems that Sakaue et al. have already studied this idea for the case of: real valued predictions and a modified ℓ∞\ell_\infty distance. Mathematically,
\frac{1}{k}\sum_{i=1}^{k} \min_{y\in\operatorname{conv}(Y^*(I_i))} \\|\hat y-y\\|_{\infty}^{\pm}$$ The paper still studies the problem in settings where its important to solve the integral problem, but the idea not completely new. - Technical: while I find the proofs clean, I don't think they are particularly surprising, especially the reductions to min cost flow which seem more like simple exercises on min cost flow transformations. - Empirical: since the idea of the paper is very similar to that of Sakaue et al., I am wondering why did the authors not compare to Sakaue et al. algorithms (see questions below).
Questions for authors
  • Did you compare to Sakaue et al.'s algorithms empirically? Benchmarks could be: Sakaue's prediction + rounding + Dinitz algorithm, or, Sakaue's prediction + Sakaue's algorithm directly.

  • Any thoughts on whether one could find even better predictions if we allow slightly approximate solutions for the training instances? Do your current algorithms directly generalize?

  • Why are you presenting experiments only for min cost perfect matching and not for max flow?

  • I understand that Problem 8 follows the same overarching motivation of directly optimizing the running time bounds established in prior analyses. However, the bound in problem 8 which is inspired from the analysis of Dinitz et al. seems somewhat ad hoc and difficult to interpret.. isn't there an upper-bound of it that is more interpretable/compact (maybe some other kind of norm) under which the problem is efficiently solvable? Such a formulation would make Problem 8 more conceptually aligned with the other results in the paper.

2 comments

while I find the proofs clean, I don't think they are particularly surprising

Please see our response to Reviewer RMNG.

the model does not seem to be completely new

Indeed, as discussed in Section 1.2, Sakaue and Oki already identified this issue and addressed it for fractional predictions using tools commonly employed by the learning community. However, producing the integral predictions studied in our paper requires completely different techniques, which we draw from classical combinatorial optimization. We hope to inspire further research connecting these areas. We refer to Section 1.2 for an extensive discussion of this topic.

Did you compare to Sakaue et al.'s algorithms empirically?

Please see our response to Reviewer e7ZE.

Any thoughts on whether one could find even better predictions if we allow slightly approximate solutions for the training instances? Do your current algorithms directly generalize?

We thank you for an interesting question. The objective of the learning problem formulation involving approximate dual solutions would need to include the distance of the given approximate solution to the set of the optimal solutions. In particular, we would need to minimize ∣∣y^−y’∣∣1+∣∣y’−y∣∣1||\hat y - y’||_1 + ||y’ - y||_1 over predictions y^\hat y, intermediate suboptimal duals y’y’ and optimal duals yy. However, by triangle inequality, the direct distance ∣∣y^−y∣∣1||\hat y - y||_1 is always a sharper estimate of the warm-start algorithm’s performance than the length of the trajectory via the intermediate y’y’. Therefore, including approximate intermediate solutions in our training problem would not bring better results.

Why are you presenting experiments only for min cost perfect matching and not for max flow?

Because there is an existing benchmark for batch learning predictions for warm starting matching, so we can compare directly to these results, whereas for flow similar benchmarks exist only for the online learning setting, which we do not study in this paper. Moreover, we consider our paper to be primarily of theoretical nature, and we provide the experiments only as a supplementary proof of idea; our goal was not to make an extensive empirical evaluation of known methods.

I understand that Problem 8 follows the same overarching motivation of directly optimizing the running time bounds established in prior analyses. However, the bound in problem 8 which is inspired from the analysis of Dinitz et al. seems somewhat ad hoc and difficult to interpret.. isn't there an upper-bound of it that is more interpretable/compact (maybe some other kind of norm) under which the problem is efficiently solvable? Such a formulation would make Problem 8 more conceptually aligned with the other results in the paper.

Honestly, we did not try to find a norm/bound that would be sandwiched between the current bound we use and the L1 norm (which is the cleanest but impossible to optimize), and we do not have a good intuition on whether such a bound exists. However, we do not find the current bound ad-hoc and we do not see a problem with it being difficult to interpret. This bound is almost exactly the number of iterations the algorithm makes (and not just some loose upper bound on that number), and we believe then whenever it is possible to provably optimize the actual target – which is here the case – it is a better approach then optimizing a proxy.

Thank you for your clarifications and for the added comparison with Sakaue and Oki. I understand that the paper is primarily theoretical. I will keep my positive score of 3.

Reviewer_e7ZEOpenReview ↗
Rating
3
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper studies how to learn a common warm-starting prediction vector for optimization problems that share the same graph but differ in costs or capacities, while allowing each problem to have multiple optimal solutions. Conventional Naïve ERM selects a single optimal solution for each problem and minimizes the average prediction error, potentially overlooking other optimal solutions. The authors instead consider a learning problem that minimizes the average distance from the prediction vector to the closest solution in each problem's set of integer optimal solutions. For bipartite min-cost perfect matching, they reduce the ℓ₁ learning problem for integral dual predictions to a min-cost flow problem, enabling efficient optimization, while proving that the corresponding ℓ₀ learning problem is NP-hard. For maximum flow, they establish that the ℓ₁ learning problem is NP-hard and instead optimize an alternative objective directly related to an upper bound on the running time of an existing algorithm, again through a reduction to min-cost flow. In the matching experiments, the proposed method performs similarly to Naïve ERM on the existing datasets but achieves further reductions in the number of iterations on a structured synthetic dataset.

Critical strengths
  1. The paper identifies a limitation of existing Naïve ERM, which relies on a single optimal solution selected for each problem, and presents a learning objective based on the distance to the set of integral optimal dual solutions, aligning it with existing warm-starting algorithms that require integral predictions. In particular, a theoretical counterexample shows that a prediction can have a small ℓ₁ distance to the convex hull of integral optimal dual solutions while remaining far from the closest integral optimal dual solution. In addition, the proposed method achieves fewer iterations than Naïve ERM on the structured synthetic dataset, suggesting that the learning objective can lead to improvements under certain conditions.
  2. The paper analyzes the computational complexity of learning problems under different prediction error measures for matching and maximum flow, supported by theoretical results. It shows that the ℓ₁ learning problem for matching and the alternative objective for maximum flow can be solved efficiently through reductions to min-cost flow problems, while proving that the ℓ₀ learning problem for matching and the ℓ₁ learning problem for maximum flow are NP-hard. The concrete reductions and proofs provided for each result help clarify the conditions under which the proposed approach can be applied efficiently.
Critical weaknesses
  1. On the original synthetic dataset and the UCI-based geometric dataset, Naïve ERM and the proposed method show generally similar performance, while clear additional improvements are mainly observed on the structured synthetic dataset. Although the paper explains why these differences occur, I find the evidence somewhat limited for identifying the conditions under which the proposed method offers greater benefits and assessing its practical applicability.
  2. The experiments mainly compare the number of iterations required by the Hungarian algorithm, making it difficult to fully assess the overall computational benefits, including the cost of learning. Comparing the training time and actual problem-solving time for each method would help clarify the practical efficiency of the proposed learning algorithm.
Questions for authors
  1. Could the authors quantitatively analyze how differences among independently obtained optimal dual solutions relate to the conditions under which the proposed method achieves larger improvements? Such an analysis would help clarify when the benefits observed on the structured synthetic dataset arise.
  2. Could the authors compare the learning method of Sakaue & Oki (2023) with the proposed method using the same matching data and training samples, pairing each with an appropriate warm-starting algorithm? Reporting both training time and actual problem-solving time would help clarify the overall computational costs of the two approaches.
2 comments

Could the authors quantitatively analyze how differences among independently obtained optimal dual solutions relate to the conditions under which the proposed method achieves larger improvements? Such an analysis would help clarify when the benefits observed on the structured synthetic dataset arise.

Every feasible matching instance has infinitely many optimal dual solutions. Even when all training instances share a common optimal dual solution, so that our objective (‡) has value zero, independently selected optimal duals can be arbitrarily far apart, making the minimum of objective (†) arbitrarily large. The discrepancy therefore depends on which optimal dual solutions the solver selects and we expect the largest improvement when the objective values of (‡) and (†) are far apart.

There is no reason to expect the solver, looking at each instance in isolation, to always select an optimal dual solution which is good for every instance, see Figure 2b for example. But we did observe it sometimes, see Figure 2a.

Could the authors compare the learning method of Sakaue & Oki (2023) with the proposed method using the same matching data and training samples, pairing each with an appropriate warm-starting algorithm? Reporting both training time and actual problem-solving time would help clarify the overall computational costs of the two approaches.

We have tried the learning algorithm by Sakaue&Oki together with their warm-start algorithm, as we found it in the github repository linked in their paper. On our datasets, it performed much worse than both naive ERM and our learning algorithm with the warm-start algorithm of Dinitz et al. It had a bad performance even with zero noise; the reason was that their algorithm, being a batch conversion of online gradient descent, did not converge to a good prediction after processing only once the whole (relatively small) dataset. Therefore, we have tried to run our algorithm on the datasets from their paper, which contain 1000 instances each. Again, their algorithm performed significantly worse (than ours) and its training time was around 4x higher. We have added these results together with further comparison to Sakaue&Oki to Appendix F.1 of our updated submission. (We keep the new results in a separate section for clarity; in the final version of the paper we will consolidate descriptions of experiments.)

Thank you for your responses and the additional experiments.

Regarding my first question, the explanation helps clarify the potential benefits of the proposed method, although the relationship with the observed performance improvements does not appear to have been quantitatively examined.

Regarding my second question, the additional experiments and runtime analysis have addressed my main concerns.

Based on these clarifications, I will maintain my original rating.

Reviewer_RMNGOpenReview ↗
Rating
2
Confidence
3
Informativeness
1
Presentation
3
Soundness
3
Read review
Paper summary

This paper considers the problem of learning predictions used to warm start min cost bipartite matching and max flow. The usual approach is to use PAC learning over instances drawn from the same distribution. This works when there is a unique optimal prediction vector. The current paper considers the scenario where there are multiple optimal prediction vectors. In this case, the paper gives the following results: (a) for min cost matching, the dual prediction that minimizes ℓ1\ell_1 distance to the actual optimal dual can be optimized via a min-cost flow computation (b) for min cost matching, optimizing the dual prediction that minimizes ℓ0\ell_0 distance to the actual optimal dual is NP-hard (c) for max flow, optimizing the prediction that minimizes ℓ1\ell_1 distance to the actual optimum is NP-hard (d) for max flow, there is an alternative optimization that reduces to a min-cost flow optimization and the resulting prediction can be used to obtain the same (or better) speedup as ℓ1\ell_1 minimization for the actual max flow instance

Critical strengths

The general question of trying to define and address the learning problem for obtaining predictions that can be used to warm start algorithms is an important research direction.

The paper is also very clearly written.

Critical weaknesses

The incremental contribution of the paper over prior work did not impress me. It addresses the case of multiple optimal predictions. Is there any argument for why this is indeed the common case? If the authors are interested in this research direction, it would have been much more interesting to consider radically different learning settings, such as online learning instead of PAC, or even consider not just distance to optimal predictions but something more holistic like the tradeoff between the distance to a good prediction (e.g., including approximately optimal predictions) versus the prediction quality, and the resulting net effect on the algorithm's running time. I am just giving these as examples, but the broader point is that while the research direction is interesting at a high level, the specific choice of the problem formulation seemed rather limited and incremental to me.

There is some inconsistency in how the two problems are considered. If one considers learning a good prediction for max flow ignoring the intermediate dependence on minimizing distance, why not use the same philosophy for matching? I.e., obtain the most efficient learning of a prediction that can speed up running time of the algorithm to the desired extent, without worrying about the intermediate goals of optimizing ℓ1\ell_1 or ℓ0\ell_0 distance?

The technical work is fairly straightforward. The min-cost flow uses are essentially immediate, which just leaves the NP-hardness proofs which, to my mind, have somewhat limited value.

Questions for authors

See weaknesses above. Not questions per se, but some suggestions.

3 comments

It addresses the case of multiple optimal predictions. Is there any argument for why this is indeed the common case?

Much stronger statement holds for matching: it is always the case that their number is infinite, see line 194. For Max-Flow, there can be exponentially many integral optimal flows even in simple unit-capacity networks, see Appendix D.

it would have been much more interesting to consider (...) the tradeoff between the distance to a good prediction (...) versus the prediction quality

This is essentially what we do for max flow. In the case of matching, prediction quality is also measured using the ℓ1\ell_1 distance. By the triangle inequality, the direct distance to the set of optimal dual solutions always gives a sharper bound on the number of iterations than the sum of the distances via an intermediate suboptimal dual solution. See also our answer to Reviewer e7ZE.

(...) why not use the same philosophy for matching? I.e., obtain the most efficient learning of a prediction that can speed up running time of the algorithm to the desired extent, without worrying about the intermediate goals of optimizing l1 or l0 distance?

In the case of matching there is no natural intermediate upper bound on the number of iterations in the analysis of the warm-starting, the l1 distance is used directly, so it is impossible to use the same philosophy as for flow.

The technical work is fairly straightforward.

We agree that for the matching, the formulation of the learning problem is a fairly straightforward exercise in min-cost-flow modelling (there our main contribution is formulating the learning problem with a right proxy for final cost).

However, for matching, we establish total unimodularity by showing that the transpose of the constraint matrix corresponds to a min-cost-flow problem. This connection also yields an almost-linear-time learning algorithm. Although the proof draws on classical network-flow and LP-duality tools, those tools alone do not establish integrality of our model: the essential step is identifying the auxiliary network and proving the correspondence with the original formulation. Such an approach is definitely not standard in the context of learning predictions. We view the transfer of classical combinatorial optimization techniques to this learning setting, together with the resulting efficient algorithms, as our main contribution. In this respect, we consider the simplicity and clarity of the techniques as a strength. The tailored auxiliary network, which we design, reveals the structure underlying the integrality result, and our technical insight lies in identifying and exploiting this structure (rather than in the complexity of the proof machinery).

Thanks for your response.

I do not understand the comment about infinitely many min cost bipartite matching solutions. What if there is a single matching of cost 1 edges and all other edges are cost infinity?

I don't understand why removing "distance to an optimal solution" is not possible for min cost matching. Again, the goal would be to understand the quality of the prediction measured not by a distance measure but by the running time of a min cost matching algorithm that is provided this prediction, and understand the tradeoff of this quality metric with the cost of producing such a prediction.

In any case, as I said in the review, my main concern is that the problem formulation was of limited interest to me, although the high-level premise of the paper was promising. I will keep my original score.

I do not understand the comment about infinitely many min cost bipartite matching solutions. What if there is a single matching of cost 1 edges and all other edges are cost infinity?

We explained it in footnote 5 on page 4. Even if there is a unique primal solution (as in your example), there are still infinitely many optimal dual solutions, and the prediction is a dual solution. This is because we can always add a constant to all nodes on one side and subtract the same constant from all nodes on the other side of the bipartite graph, and we obtain in this way a different dual solution, which is still optimal. In your example, for every integer x, there is an optimal dual solution that assigns x+1 to all nodes on the left and -x to all nodes on the right.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.