Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 5: Marginally below the acceptance threshold
review_content: summary: This paper is about online algorithms augmented with predictions of the future input. In particular, the authors examine the problem of online facility location. In the classical version of this problem, there is a sequence of points in a metric space that arrive in an online fashion and represent the location of a client. The algorithm has to irrevocably decide to either connect each of those clients to an existing facility paying some “service cost” proportional to the distance from it, or a new one that would incur an additional “facility cost” $f$ to be created. 
The authors here consider a version of the problem where the algorithm is provided with advice from multiple sources. Each piece of advice $S_i$ consists of a set of points where the optimal locations of the facilities are predicted to be. The first algorithm proposed uses the union of those predictions $\mathcal{S}=\cup_i \{S_i\}$ and incurs a cost which scales proportionally to $\log|\mathcal{S}|$ and the optimal cost given that only facilities in $\mathcal{S}$ can be used. 
The algorithm and its proof is quite technical and makes use of hierarchically separated trees, that had been also used in the classical version of this problem. Matching lower bounds up to a $\log\log |\mathcal{S}|$ factor are also provided as well as experimental results to compare with prior work. 

main_review: This paper looking at a very important classical online algorithms problem from a novel perspective, and got some interesting both positive and negative results. However, the theoretical part seems to be a bit lacking because the cost of the algorithm is not compared to the offline optimal cost, but rather to the optimal cost given that the facilities can only be opened in a location that has been predicted. Thus, this is equal to the offline optimal cost only if the union of the prediction sets contains all optimal locations for facilities. I think an attempt need to be made to relate the cost of the algorithm to the offline optimal algorithm, as it is the standard for online algorithms. Additionally, the presentation could also be improved. For example, Algorithm "TakeHeed" only uses the union of the advice sets and therefore some statements could be simplified. If I understand correctly, the separate advice sets are only relevant for "Robust-TakeHeed", which is not described in the main body of the paper. 


Comments:
- Line 124: the variable $k$ is overloaded here. It has already been used for the number of advice sets and this could create confusion. 
- Theorem 3.1: This theorem should probably be rephrased such that the advice is a single set $\mathcal{S}$ and is can just be applied on $\mathcal{S}=\cup_i \{S_i\}$ when needed, since the separate sets $S_k$ are not used.

limitations_and_societal_impact: The authors as well as myself do not see any potential negative societal impact from this work.
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: The paper looks at the problem of online facility location with multiple advice.

In the online facility location problem points of a metric space arrive online and once a point arrives it either has to be connected to an already open facility, or a new facility gets opened to serve it. These decisions are irrevocable and the goal is to minimise the total cost which consists of the cost for opening the set of facilities and the sum of distances from each point to the facility that serves it. The best known algorithm for the problem is due to Fotakis and obtains a competitive ratio of $O(\log(n)/\log\log(n))$. 

The current paper assumes that the algorithm has obtained $k$ different sets of points as "advice". Each such set of points $S_i$ can be thought to represent a set of suggested facilities to open, but it is unclear which -- if any -- of these sets lead to a good solution and which not. The paper uses this advice to develop algorithm TakeHeed with expected cost $O(\log|S|)\cdot OPT(S)$, where $S$ is the union of advice sets and $OPT(S)$ the best solution among the ones that are restricted to use facilities of $S$. Clearly, $OPT(S)$ cannot be worse than the optimal solution restricted to each advice set, so intuitively the algorithm is good when there are relatively few points in the advice sets and at least one of them is reasonably accurate. The algorithm can be robustified by standard techniques (Mahdian et al.) and an additional algorithm is given in the supplementary material for the (arguably not so natural case) in which $|S|$ is large. This additional algorithms compares directly to the quality of the best advice set.

The paper also contains expermints both on synthetic and real world (albeit from different settings) inputs.
main_review: Algorithm TakeHeed builds upon hierarchically separable trees and, although quite involved and non-trivial, is elegant at the same time. Furthermore the paper is really well written and the clustering problem that is studied is very interesting.

That being said, I have two concerns regarding the paper:

1. I am not fully convinced with the multiple predictions model. I would consider it more natural to have one predicted set of facilities to open and to give the competitive ratio as a function of the error (some distance measure between the predicted set and the actual optimal set of facilities). The choice of multiple predictions model seems also a bit strange given that, at least as far as I can tell, it is the union of the predicted sets that is used in the algorithm (and on top of that, that also appears in the performance guarantee of the algorithm). Although the additional algorithm actually works with individual prediction sets it is again not clear how to compare it to the best algorithm without predictions (see concern (2.) below).

2. the performance of the algorithm is given with respect to cost of the algorithm and not with respect to the competitive ratio which makes it quite hard to compare the theoretical result to other algorithms. In particular the given costs may depend among other things on the number of facilities in a predicted or optimal solution.

Finally, the experimental results are quite interesting in that they (i) support the belief that such multiple advice sets can indeed be obtained from historical data, and (ii) show that the algorithm actually outperforms other algorithms. So although I think that the prediction model is not the most natural, and the theoretical results are maybe not as meaningful to interpret as a performance guarantee, it seems that at least in practice the algorithm performs reasonably well.

I think that the paper is slightly above borderline but would be more than happy to reconsider my score after the rebuttal of the paper.

Some minor notes for the authors:
- The algorithm naming is a bit unfortunate, in particular since the robustified version of TakeHeed is called Wary, but a different algorithm is called Robust-TakeHeed.
- On line 62 you talk about the performance guarantee, but what you write is actually the cost of the algorithm.
limitations_and_societal_impact: no limitations or social impact concerns.
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: The paper studies the online facility location problem in a setting where you have multiple advice in the form of a set of lists of suggested facilities to open. They introduce an algorithm that they show to competes with the best possible algorithm for online facility location even when the advice is bad and outperforms the best possible when the advice is good.
main_review: The paper is well written and is well structured. The arguments seem to follow clearly and the structure of the arguments is clearly laid out. The paper uses the structural properties of HSTs to design and analyze a robust framework for the online facility location with advice. It seems that the advice in this setting could be adversarial. But since the advice does not change over time, the adversary is non-adaptive. I know this is out of the scope of the paper, but is it possible to say anything about what might happen if you are allowed to change some $\epsilon/n$ fraction of the advice at each time? Could this be counted towards bad advice and the robustness arguments used to say that even in this case the performance is good? Feel free to skip this question if you have to, as it is out of the scope. Also, what is the significance of Wary against Robust-Takeheed, if the best possible advice set is also an adversarial set that is large (something like $\epsilon n /k$) how would the two approaches compare? Also, how does $OPT(P,S)$ compare against the true optimal (could this cause any additional $S$ factors especially pertaining to the lower bound analysis)? Also, is there a formal definition of bad advice?

On the formatting front, it might be nice to have the pluck algorithm in a single column as double columns make it hard to compare some structural properties, i.e. indentation making it slightly harder to read. This is just a suggestion as it is not a major issue anyway. 
limitations_and_societal_impact: The advice setting in the paper while being adversarial, is not allowed to change after the initial selection though this is simply the framework considered for the scope of the paper. Also, the bounds in the paper are derived against the optimal solution restricted to $S$ and it is not clear how it compares against the true optimal. The concept of bad advice seems to be loosely defined.

As the problem itself is a classical problem I don’t think it creates any major negative societal impacts.
review_title: null

final_score: rating: 8: Top 50% of accepted NeurIPS papers, clear accept
review_content: summary: The paper studies the problem of online (uniform) facility location with multiple expert advices. Here the expert advices are given in the form of the offline optimal facility set: i.e., each advice is a set of facilities that are claimed to be open by OPT. The main result of the paper is an algorithm with cost $O(\log(|S|))\mathrm{OPT}(S)$, where $S$ is the *union* of all the expert advices, and $\mathrm{OPT}(S)$ is the best (offline) cost one may get by using only facilities from $S$. By combining with known worst-case online algorithms (e.g. Meyerson's algorithm) using standard blackbox method, one easily get an algorithm with robustness-consistency performance guarantee.

The main idea of the $O(\log|S|)\mathrm{OPT}(S)$-cost algorithm is to first embed the facility set to an HST, then run an alg similar to Meyerson/Fotakis, except for one important difference: when the algorithm decides to open a facility in some region, it (Algorithm 3) choose to open the "limit point" in that region rather than the facility giving smaller cost. In particular, this difference enables the algorithm to circumvent the classical lower bound instance given by [Meyerson'01]: the instance consists of a sequence of clients that converges to a point in the space.

Finally, notice that since the goal is to approximate $\mathrm{OPT}(S)$, one can w.l.o.g. move all clients to the location of $S$ losing only an additional $O(1)$ factor. Then using similar argument as in [Fotakis'11] one can get the $O(\log|S|)*\mathrm{OPT}(S)$ cost, which could be better than the $O(\log n)$-apx of Meyerson/Fotakis when $\mathrm{OPT}(S)$ is close to OPT.
main_review: **[Strength]**
I think the main contribution is the $O(\log|S|)*\mathrm{OPT}(S)$-cost algorithm, while the rest part is rather standard. I like the idea of using HST to identify the limit point in (a subset of) the facilities. Simple but clever. The result is also interesting even without the learning-augmented background: it implies better competitive ratio when the facilities come from a fixed set (that's much smaller than potential client sets), which is often the case in practice. The authors also provide a lower bound (almost) matched by their algorithm. I don't have time to look at the experiments, but I think it's not important for the evaluation of this paper.

**[Weakness]**
Although the lower bound Theorem 4.1 is incomparable with that given by [Fotakis'03], it is not hard to obtain by a small modification. In fact the lower bound construction given in the paper is almost identical with that of [Fotakis03].
Finally, the author should discuss a little bit more on the primal-dual algorithm by [Fotakis'05], which is not "Meyerson-like" and thus Theorem 4.2 does not directly apply.
limitations_and_societal_impact: N/A
review_title: null

Meta-review: The paper presents a learning-augmented algorithm for online facility location. The competitive ratio of the algorithm depends on the quality of the prediction, and the size of the advice; it is never worse than the competitive ratio of the best worst-case algorithm. 
There was a substantial debate about (i) the advice model - how natural/realistic it is and (ii) the approximation guarantees, esp. the possible discrepancy between OPT and OPT(P,S). Overall, however, the reviewers felt that these issues do not significantly reduce the value of the paper.

Decision: Accept (Poster)