- 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 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 but the actual algorithms used in the literature just pick an arbitrary solution for each training instance. The paper proposes to attack the objective 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 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 distance. Mathematically,
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
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.
Please see our response to Reviewer RMNG.
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.
Please see our response to Reviewer e7ZE.
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 over predictions y^, intermediate suboptimal duals y’ and optimal duals y. However, by triangle inequality, the direct distance ∣∣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’. Therefore, including approximate intermediate solutions in our training problem would not bring better results.
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.
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.