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 gives a framework for learning parameters in learning-augmented algorithms. First, an upper bound is computed on the objective of interest such that this upper bound function can be optimized. If the upper bound is reasonably tight, this is also a reasonable optimization for the actual cost. Then, the parameters optimizing the upper bound of the cost function are used as learned parameters in the learning-augmented algorithm. 

Two forms of this optimization are considered in this paper: sample complexity bounds for inputs drawn from a distribution and regret bounds from online learning for adversarial inputs. In terms of applications, this idea is applied to obtain new sample complexity and online learning bounds for several problems: speeding up matching algorithms using a warm start by learned duals, online page migration, obtaining the optimal consistency-robustness tradeoff in problems like ski rental and scheduling, etc.
strengths_and_weaknesses: Strengths:

1. I like the general area of learning-augmented algorithms and data driven algorithms, and this paper makes an important contribution to this area. There is relatively little work on the learnability of predicted parameters. Instead, the focus has been on developing (robust) algorithms to exploit (noisy) predictions generated by a black box learner. This is reasonable for certain situations, e.g., if one is using a deep neural network for the purpose of generating parameters. But, in situations where we do have well-understood theoretical abstractions such as PAC and online learning, it makes sense to think of a white box approach as proposed in this paper.

2. The framework proposed is quite general and intuitive and can be applied broadly to multiple learning paradigms. In particular, the use of online learning in making predictions about algorithmic parameters is novel (to the best of my knowledge). 

Weaknesses:

1. One might complain that there is no killer application here. In particular, the improvements in sample complexity bounds are relatively modest. 
questions: I do not have specific questions. This is a nice paper overall and should be accepted.
limitations: There is some discussion about limitations and future work at the end of the paper. It reads somewhat generic though, mostly focusing on some broad future directions for the entire field of learning-augmented algorithms rather than being specific to this paper.
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 proposes a general meta-framework for improving algorithms with predictions (e.g. an initial guess). The authors propose a 2 step procedure to iteratively learn better predictions: 1. upper bound the problem's cost (or tradeoff parameter) using the prediction (e.g. distance between prediction and global optimum), then 2. update the prediction using this cost estimate via standard online learning, with the goal of minimizing expected regret and sample complexity. This framework is used to derive improved guarantees across a wide range of algorithms such as matching and scheduling.

strengths_and_weaknesses: ## Originality
- This paper presents several novel analyses under a unified framework, and cites previous work where appropriate

## Quality/Significance
- The proposed framework is interesting, well-motivated, and has potential for many follow up works
- In the beginning of Section 4, the authors claim an upper bound on parameter $q$. However the assumption in [17] implies a lower bound on $q$. I'm unsure how much this possible bug affects the rest of the analysis.
- This paper has clear, elegant theoretical contributions. However, it would be stronger if it also contained experiments that verify the regret guarantees, sample complexity bounds, and general efficacy of the new algorithms

## Clarity
- Well organized and a pleasure to read
- Clear statements of results and intuitions behind them
- Typo: on Line 89 ", nut they also" should be ", but they also"

[17] Piotr Indyk, Frederik Mallmann-Trenn, Slobodan Mitrovic, and Ronitt Rubinfeld. Online page migration with ML advice. In Proceedings of the 25th International Conference on Artificial Intelligence and Statistics, 2022.
questions: - How tight are the regret/sample complexity bounds in practice on real problem instances?
limitations: This paper describes limitations as opportunities for future work, but does not address any potential negative social impact.
review_title: null

final_score: rating: 5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.
review_content: summary: The paper studies the learnability of predictions in the field of algorithms with predictions. The authors propose a general framework to learn predictions, and show that the framework can be applied to bipartite matching and page migration. In each setting, the proposed learning method obtains statistical guarantees. Furthermore, they show that the learning framework can help to tune the robustness-consistency tradeoffs in some problems, e.g. scheduling and ski rental.
strengths_and_weaknesses: Strength:
- The learnability of predictions is a piece in the learning-augmented model which receives little attention but is very necessary. The paper makes contributions in this part. It not only improves the sample complexity given in the previous work when the instance (of bipartite matching) is sampled from a fixed distribution, but also presents theoretical bounds of the sample complexity and the average regret when instances are from an adversarial sequence. To the best of my knowledge, this is the first regret bound in the learning-augmented framework.

Weakness:
- The paper has theoretical contributions but is not that technically deep. It builds on several existing theorems to give the statistical guarantees, which makes the results technically simple.

- There is no experiment. In (Dinitz et al, NeurIPS 2021), experiments were provided to investigate the empirical performance. Since the paper introduces a new learning setting, it is expected that there are experiments to show that the new learning framework can perform better than the previous learning algorithm (empirical risk minimization) on some data sets.
questions: - The ``OnlineAlgorithm" in Algorithm 1 is unclear to me. Does this refer to the online gradient descent algorithm?

- Figure 1 is too far from where it is referenced.

- The submission should not have the appendices.
limitations: I didn't see any potential negative societal impact.
review_title: null

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: The paper studies learning-augmented algorithms, mostly focused on the online setting. A recent line of works establishes that one can improve upon classic, worst-case guarantees if the algorithm is furnished with good predictions. However, the question of when and how such good predictions can be learned from data (efficiently) is still open. 

This work presents a fairly general approach to answering this question. Prior work shows that the performance of a learning-based algorithm can be bounded by some error measure of the prediction (compared with the best prediction). This paper shows that if there's an efficiently-optimizable upper bound of the error measure, then techniques from online learning (in particular, online convex optimization) can be applied to learn good predictions. 

It is shown that this general learning-theoretic framework can be applied to matching, paging migration, scheduling and ski-rental. 
strengths_and_weaknesses: Strengths
----
The paper is solid on a technical level and the theoretical claims are sound.

Overall I find the paper very well written. 

To the best of my knowledge, the results are novel. Given the recent spate of work on algorithms with predictions, I believe it has potential to make further impact

Weaknesses
---
I am not convinced that the paper exhausts all its potential. Particularly, there should be some more problems where this general framework can be applied. I suggest a few in a later section. I encourage the author(s) to consider them in the final version or in a followup work.


In comparison with some of the prior work, the paper  does not provide experimental evaluations. 

Minor and missing references
---
Related work: “Faster Fundamental Graph Algorithms via Learned Predictions” (ICML 22) also studies bipartite matching, extending Dinitz et al.

Theorem 3.1. I suggest the author(s) switch the order of the third and second result, since the second result is obtained from the third (using online-to-batch conversion), so it’s natural to present the third first.

questions: On the technical side, can the dimension-dependence (on n) of theorem 3.1 be improved? I think using OGD on the L-infty ball constraint may be loose. Note that one sqrt n factor comes from Line 181, where the L-infty constraint is converted to L2, allowing one to apply the OGD guarantee. The author(s) may want to look into the relevant literature on online mirror descent; e.g., “On the Universality of Online Mirror Descent” (https://arxiv.org/abs/1107.4080)

limitations: In general, I feel that this approach has more potential, to be applied to more problems. Here are two concrete suggestions:

* “Permutation Predictions for Non-Clairvoyant Scheduling” (SPAA 22) studies a new prediction model for non-clairvoyant scheduling, which provides a relative order of jobs. It seems that the continuous relaxation technique of section 4 can be used to learn this permutation. I believe this could be more broadly interesting, to other online problems, such as paging and   graph problems (where vertices/edges arrive online in some order, and it would help if you can learn this order).  

* “Faster Fundamental Graph Algorithms via Learned Predictions” (ICML 22) considers speeding up other (offline) graph problems, not just matching. The techniques from section 3 can probably be used in those settings. 

Finally, I'd like to see whether the regret bounds from section 3 can be improved.
review_title: null

Meta-review: metareview: The paper introduces a general design approach for algorithms that learn predictors. This is achieved by identifying a functional dependence of the performance measure on the prediction quality, and applying techniques from online learning to learn predictors against adversarial instances, tune robustness-consistency trade-offs, and obtain new statistical guarantees. The problem is well-motivated and the proposed solution is general and interesting. Majority of the reviewers' concerns are addressed by the rebuttal. The paper will be significantly stronger if the authors benefit from the additional page to incorporate the feedback into the main paper.
confidence: Certain
Decision: Accept