Venue: NeurIPS 2022 Conference

Reviews:

final_score: rating: 7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
review_content: summary: This paper considers using predictions to improve algorithm running time via warm start as in the recent work due to Dinitz et al. 2021.  The authors propose a framework based on discrete convex analysis which applies a discrete steepest decent approach to go from an initial feasible solution to a global optimum.  Each iteration requires solving a local optimization problem to find a descent direction and the number of iterations can be bounded by $O(||p-p^*||_{\infty})$, where $p$ is the initial solution and $p^*$ is an optimal solution.  Algorithms for projecting infeasible predicted solutions onto the feasible set (with respect to the $\ell_\infty$) norm and efficiently learning an initial predicted solution are also given to complete the framework.

Using this framework the authors give warm-start-with-predictions algorithms for:
- weighted bipartite matching (improving the result of Dinitz et al. 2021)
- weighted matroid intersection
- Discrete energy minimization
- The more general class of L/L♮-convex functions.


strengths_and_weaknesses: This paper gives a nice improvement over Dinitz et al 2021 for weighted bipartite matching and also extends the ideas to other problems.  The writing is a bit dense, but overall well explained.  An experimental evaluation may be interesting, but is probably not necessary for the current submission.
questions: - How does the proposed approach for weighted bipartite matching compare experimentally to Dinitz et al. 2021?
limitations: N/A
review_title: null

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: summary: This paper extends recent work by Dinitz et al. on using the learning-augmented algorithms model to speed up graph algorithms by warm-starting the dual solutions (in particular, they focused on the Hungarian algorithm for minimum-cost bipartite matching). In this paper, the authors interpret this idea of warm-starting in the context of discrete convex analysis, inspired by the idea that warm-starting is a well studied concept in convex optimization. Through this lens, they give an improvement in the min-cost matching problem, reducing the dependence on the prediction error from linear in the $\ell_1$ error to linear in the $\ell_\infty$ error. Their framework is rather general and the authors apply it to get learning-augmented algorithms and bounds for weighted matroid intersection and discrete energy minimization as well. The authors also provide PAC bounds on learning predictions for these problems under the $\ell_\infty$ norm.
strengths_and_weaknesses: Strengths
- The connection between warm-starting in Dinitz et al and in the framework of discrete convex analysis is interesting and general.
- The improvements in the bounds from prior work are significant, changing the error dependence from $\ell_1$ to $\ell_\infty$.
- I thought the discussion of learning primal vs. dual solutions in Section 5 was very interesting. It is worthwhile to consider what factors make some predictions useful or not for algorithms with predictions.

Weaknesses
- For large graphs, the PAC bounds require many samples. In particular, if we set $C=n\|w\|_\infty$, we need at least $\frac{n^2 \|w\|_\infty^2}{\epsilon^2}$ sample instances which for large graphs seems extreme. The bounds are a significant improvement over the bounds given in prior work but I'm not sure how informative they actually are.
- It seems that many of the techniques used in this paper come almost directly from prior work. Nonetheless, I think the application and combination of these ideas makes for some interesting insights and results on learning-augmented algorithms.
- Perhaps most importantly, seeing as both this and the prior work are in some sense not comparing themselves to the best theoretical algorithms for matching (even if the predictions are near-perfect, the theoretical bounds will be worse), it would be more compelling if some experiments were done to show that the this discrete convex analysis approach is actually a better way to approach the problem than Dinitz et al.
questions: Do you think that the DCA-based algorithms actually improve on the work of Dinitz et al in practice, or is it rather the case that you can give a tighter analysis of these algorithm than they could?
limitations: I found the discussion of limitations to be adequate. I do not foresee any specific negative impacts of this work as it is quite theoretical and abstracted away from applications.
review_title: null

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: summary: This paper presents results illustrating the possible benefits of initializing learning algorithms based on predictions. By using a discrete convex analysis framework, the results indicate improved bounds for the sample and time complexity. The usefulness of the framework is shown by applications to weighted perfect bipartite matching, weighted matroid intersection, and discrete energy minimization. Finally, whereas the choice whether to learn primal or dual solutions has typically been made somewhat heuristically, the paper uses the proposed framework to give principled guidelines.
strengths_and_weaknesses: The paper is clearly written and structured, addresses a pertinent issue, and seems to provide novel improvements on prior work. The presentation is neat.  
The improvements over prior results are significant; for instance, the time complexity of some algorithms is improved by up to a factor $n$, where $n$ is the number of vertices.

One weakness of the results is that, unlike many previous analyses where the possible performance of learning algorithms due to the use of predictions, the analysis is unable to recover optimal worst-case bounds.  
A more extensive discussion of the applicability of the given convexity assumptions and how these contrast with other notions of convexity could be beneficial in order to more clearly motivate the work and clarify the benefits and limitations.
questions: What is the reason that your approach is unable to recover optimal worst-case bounds? Is this inherent to the approach, or can it be alleviated? (I understand that this is not crucial, as discussed in the end of the paper)  
You discuss in Section 6 that the issue above can be mitigated by running a standard algorithm in parallel. It seems as if the time complexity of such an approach would, compared to alternatives, never be worse by more than a constant factor 2. Is this a correct interpretation? What is the worst case?    
Can similar lower bounds be shown for the time complexity?  

Minor things:   
line 28: worse->worst  
line 113: "the the"
limitations: The authors clearly state the limitations, but an extended discussion on what classes of problems enjoy the different convexity notions could be beneficial.
review_title: null

Meta-review: metareview: In this paper, the authors provide new theoretical guarantees for augmenting algorithms with learned predictions. Based on discrete convex analysis (DCA), they generalize previous results of Dinitz et al, and obtain better time complexity bounds for a number of online problems. The application of DCA to online algorithms with predictions is interesting, and the improvements in the bounds are significant.
confidence: Certain
Decision: Accept