Venue: NeurIPS 2022 Conference

Reviews:

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: The paper considers online algorithms for classic graph problems when predictions regarding the requests are provided to the algorithm. The key contribution of the paper is to define a new notion of error to measure the quality of predictions provided for such problems. The new error attempts to capture the intuition that if following the predictions leads to substantially worse performance than the optimal solution, then such predictions should suffer from large errors. To make this notion precise, the paper defines the error as the size of the minimum cost edge cover in an associated hypergraph where the edge costs capture the amount of excess cost required to satisfy incorrectly predicted requests.

For the online traveling salesman problem (and its dial-a-ride generalization), the paper provides a framework to “combine” a known robust online algorithm with an offline TSP algorithm on the predicted requests to obtain consistent and robust algorithms. As in many prior work, the algorithm is parameterized by an alpha that represents the trust of the decision maker in the predictions and simultaneously provides a competitive ratio of (1+alpha) if the predictions are correct, and also O(\rho/\alpha) if the predictions are incorrect where \rho is the competitiveness of the base algorithm. 

Using the new error measure, the paper also reanalyzes the algorithm by Azar et al for online steiner tree / forest with predictions and show that it obtains a total cost of at most O(1) OPT + f(k, error) [as opposed to the logarithmic dependence on the error in the multiplier for OPT in Azar et al.] yielding tighter guarantees for certain predictions.

strengths_and_weaknesses: The paper is well motivated and the new error formulation is pretty intuitive for graph problems.
Overall I quite like the paper and find the contributions to be non-trivial and interesting. The paper is well-written and reads well. The experimental section is also well written and the experiments are pretty comprehensive for a primarily theoretical paper.

questions: 1. In the definition of Cover Error in section 2, it is not mentioned how the hyperedges are constructed. Does the hypergraph G_k have all possible hyperedges of the specified size?
2. Related to the point above, since the hyperedges (and their costs) are not defined yet, the statement that \Gamma_i((A,B) >= \Gamma_{i+1}(A,B) [on line 179] is not well justified.

limitations: None
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 introduces a new notion of error for algorithms with predictions in the context of online metric graph problems. The predictions considered are the set of all requests, e.g., the offline problem instance. At a high level, the "cover error" introduced in this paper measures the optimal solution cost on the set of requests that appear in the prediction but not in the real instance and vice versa. This is formalized as a min-cost bipartite hypergraph cover problem to account for these two types of error via "detours" from the true instance. The authors give instantiations of this general error measure to online TSP, online Steiner tree/forest, and online facility location and develop algorithms that use predictions and whose performance is parameterized by the cover error.
strengths_and_weaknesses: Strengths
- The cover error has several benefits, which the authors do a good job highlighting. In particular, it accounts for the asymmetry in the impacts of the errors in which we predict requests that aren't there and errors in which we miss real requests in our predictions.
- The authors develop algorithms parameterized by the cover error for various online graph problems, achieving bounds that can significantly improve on the worst-case if the cover error is small.
- I think that this error measure and the resulting algorithms will be of interest to those working on algorithms with predictions.

Weaknesses
- Naturally, more complex error measures can more precisely capture the performance of algorithms with predictions. I worry that in some sense the definition of this error measure almost makes the fact that there exist good algorithm if this error is small a tautology. More basic error measures may be loose in certain respects, but they tell us something clear about the relation between the prediction and instance which we may or may not be able to leverage algorithmically: they have some meaning somewhat separate from the algorithmic task. It seems that saying the cover error is basically an algorithmic fact: there are a small set of errors which we can cover by work which we must do anyway.
questions: Could the authors please elaborate on the weakness discussed above? In some sense, it seems like this paper brings the error to the algorithm as opposed to the more natural idea of designing an algorithm to work better with some standalone notion of error.
limitations: I think the discussion of limitations is adequate.
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: This paper gives a new error measure for online algorithms with predictions for metric problems of two kinds: (a) online TSP and Dial-a Ride, and (b) online Steiner tree and forest. The two categories differ in their notion of online: the first category has requests released over (continuous) time, while the second category just has an online sequence of requests but no actual notion of time. The error measure is innovative and tries to address some shortcomings of previous measures. In particular, the paper compares to two papers from AAAI 22 and SODA 22. The first paper uses set differences to characterize error and the non-errorneous part of the prediction needs to exactly match the actual input locations. The second paper relaxes this notion by allowing the common set between predictions and actual input to not match exactly and uses a minimum cost matching between these points to quantify the quality of the match. At a high level, the deficiency being addressed in this paper is that this minimum cost matching (or the stricter requirement that the common part matches exactly) forces the cardinality of the common parts of the predicted and actual sets to be equal. So, for example, if there are many real input locations that are all close to a single predicted location, the previous error measures have large error while one can argue that the prediction is actually a good one in a qualitative sense. To address this, the new error measure being introduced in this paper (roughly speaking) replaces the edges in the matching with hyperedges with one point on one side (predicted or actual) and multiple points on the other side. The cost of the hyperedge is defined in a natural way based on the problem at hand. 

Using this new measure, the paper gives the following results: (a) for online TSP and Dial-a-Ride, it gives online algorithms that degrade gracefully with the new notion of error, and (b) for Steiner tree and forest, it shows that the algorithm from the previous SODA 22 paper gracefully degrades with this notion of error. Although the algorithm in (b) is the one from the previous paper, the analysis with respect to the new error is new.
strengths_and_weaknesses: Strengths:

1. I think the online algorithms with ML predictions (or more generally data-driven algorithms) area is a very important one. This paper is exactly in the direction that is particularly important for this area, which is to explore new paradigms and frameworks that are natural and have interesting technical challenges. As the paper correctly claims, there is no unanimity on what the correct measure of error is (as against fairly universal acceptance of the notions of consistency and robustness) and this is a significant handicap because each problem requires its own specialized techniques to showing smoothness bounds with error. So, I really like what the paper sets out to do, which is to give a reasonable notion of error that applies to many (at least metric) problems, and then give somewhat general techniques for obtaining smooth algorithms with respect to this error measure (at least techniques that extend beyond single problems).

2. The algorithms for online TSP and Dial-a-Ride with predictions are new. These are important problems in their own right, so initiating the study of online algorithms with predictions for these problems is an important step irrespective of the particular error measure being used here.

Weaknesses:

1. I did not completely understand why the paper eliminates the difference sets in the error measure that existed in the previous definitions. For instance, if the predictions are completely bogus, then it seems the actual location of the predictions should not matter. In particular, one should be able to recover robustness guarantees from error dependent bounds, but that does not seem to be the case here. I suspect it is possible to keep the current definition but only apply it to a common part (chosen in an adversarial manner) and allow difference sets outside the common part, thereby recovering robustness.
questions: 1. Can you say more on the asymmetry of your error measure (using $\Lambda_\infty$ and $\Lambda_k$ in the two directions)? Is this necessary, i.e., does something go wrong if you defined the error measure symmetrically? This asymmetry actually shows up in other places as well (e.g., in the Almanza et al. work on online facility location with predictions where the bounds apply to the case when predictions contain all the actual requests but not vice-versa). So, I suspect this is an important (and necessary) asymmetry. The paper should include a discussion about this.

2. Theorems 1 and 2 should be replaced by informal statements if possible. At this point, $\Lambda_1$ hasn't even been defined formally, and as such, it is difficult to interpret the formal bounds of these theorems without knowing this definition precisely. I believe $C^*$ wasn't defined before the theorems either (but this is easier to fix by just adding the definition).
limitations: There is no explicit discussion of limitations. This can be included, perhaps in the conclusions section.
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: The paper studies learning-based online graph problems, focused on online TSP and its variants, online Steiner tree and forest, and online facility location. In each problem, there is a sequence of node requests arriving online, and an algorithm must move or select certain edges to serve these requests. Moving or buying edges come with costs, so the goal is to minimize the total cost, measured against the offline OPT. 

Classic algorithms are focused on the worst-case competitive analysis and generally do not consider real world data distributions. In the algorithms with prediction model, the algorithm is instead provided with a predicted sequence of requests. We’d like to show that if the prediction is good, a learning-augmented algorithm can improve upon the classic worst-case guarantee. Otherwise, the algorithm should be robust and retain a worst-case competitive ratio.

The main contribution of the paper is a new error metric of the learned predictions (based on hypergraph edge cover). The paper claims that this metric bypasses some difficult cases of prior related work, and provides algorithms that work well given good predictions under this metric. Empirical evaluations demonstrate that the algorithms achieve good performance on real data.

strengths_and_weaknesses: 
Strengths:
-----

The paper gives a novel notion of error metric of learned predictions in online graph problems.  Given the “dummy request example” (line 189 below), I think this new notion is reasonably motivated.  In particular, this example demonstrates a difficult case where the prediction is conceptually good, but not captured by the error metric of recent work, including Azar et al. [Online graph algorithms with predictions. SODA 22]. 

The technical claims in the full paper are sound (but I have not checked the proof details in the supplement). 

The paper also gives experimental evaluations. 


Weaknesses:
------

The paper is not well written, particularly the early sections. Some statements appear vague and only get specified (much) later, and sentences hard to parse. Below, I list a few for the author(s) to fix. I find they seriously obstruct my reading. 

* Line 90: “Since we can use cost functions based…”  This sentence seems very vague to me. Is it a feature that prior work such as [12] doesn’t have? My understanding is that the matching-based error of [12] is also rather general and independent of the problem (but can be applied to all these node-arrival online graph problems). 
* Line 92: “Further, it allows to integrate both actual and predicted release dates for online-time problems.” How? Up to this point, the cover error has not been fully specified, so I couldn’t tell why this is true. 
* Line 97: “Although previously studied…” Regarding this dummy requests example, I suggest it’s written concretely right here in the intro. (I get that it’s defined later in line 189 and below)
* C* is undefined in Theorem 1.
* Line 131: “These bounds hold simultaneously for [...] the bounds provided in [12]” — What does this mean? (I get that it holds for any k, but not the second part.) Is it suggesting that these bounds recover some of the results in [12]?

Finally I suggest that the definition of the cover error be given earlier in the intro section. 

Minor errors: 
-----
Line 77: “In all our problems the cost of a hyperedge [...]”   In my first reading, this sentence feels long and a bit hard to parse. (What does “anchor” mean here?) 

Line 80: “E.g….” This is not a complete sentence.

Line 85: “unavoidably” -> “unavoidable”

Line 89: I suggest using an itemize here to list these points

Line 90: “problem-independent” -> “problem-independently”

Figure 1: maybe state that the numbers on the nodes are just indices, and do not correspond to the order of the request sequence. 

questions: 
Algorithm 2 requires “predicted optimal cost C hat” as its input. I’d like to clarify that this is the OPT value of the predicted request sequence Rhat. Moreover, we know that optimally solving TSP is NP-hard. Can we solve C hat approximately up to a small constant? Based on the proof of lemma 6, I think we can actually provide a C hat that is, say, 3/2, approximation of the optimal Chat. This would worsen the final bound by only a fixed constant, though. Is that correct? 

limitations:  
Overall, I believe the paper is technically novel and has potential to make an impact. However, as it currently stands, it likely requires significant revision to improve its presentation. I have listed some concrete suggestions above.
review_title: null

Meta-review: metareview: "Algorithms via (ML-based) predictions"---especially for online problems---is a young, fast-growing, important area. Of course, the predictions will usually not be perfect and will involve some sort of error. As this area is nascent, it is vital to develop and analyze different forms of error and for various fundamental problems, which this paper does well. In particular, this work develops a new notion of error for two types of "metric" problems in the above genre: online TSP and Dial-a Ride, and online Steiner tree/forest. The first type has arrivals over continuous time, while the second has an online request-sequence (as is typical in the algorithmic study of online problems). The error measure addresses some shortcomings of previous measures, and compares to recent works from Xu et al. (AAAI '22) and Azar et al. (SODA '22). Xu et al. use set-differences to characterize error; the non-erroneous part of the prediction has to exactly match the input locations. Azar et al. relax this by allowing the common set between predictions and actual input to not match exactly and use the cost of a min-cost matching between these points to quantify the extent of the match. The gap addressed in the present paper is that these two types of works force the cardinality of the common parts of the predicted and actual sets to be equal. The present paper's error measure essentially replaces the matching with hyperedges e with one vertex on one side (predicted or actual) and multiple vertices on the other side; cost of e is defined based on the problem.

This paper develops the following results parametrized by this error: online TSP and Dial-a-Ride---online algorithms that degrade gracefully with the error, and Steiner tree/forest---showing that the algorithm of Azar et al. does indeed gracefully degrades with this error. 

The paper was generally appreciated by the reviewers; the authors are encouraged to take the review comments into account. 
confidence: Certain
Decision: Accept