Venue: ICLR 2022 Conference

Reviews:

final_score: rating: 8: accept, good paper
review_content: summary_of_the_paper: This paper considers the online facility location problem with predictions.  In this problem, there is a sequence of points which arrive online and the algorithm must either open a facility to serve each point, paying the facility opening cost plus the distance to the opened facility, or it can assign the point to an already open facility, paying the distance only.  Additionally, each arriving point is given a prediction of a facility which serves it in an optimal solution. The goal is to be competitive with the offline optimal solution, and the competitiveness is parameterized by the error in the predictions.  Here, the prediction error is the maximum distance between a predicted facility and the facility in the optimal solution which serves a point.

The main result is an algorithm which is $O(\min (\log n, \log \frac{n\eta_{\infty}}{OPT}))$-competitive, where $\eta_\infty$ is the max error and $OPT$ is the optimal cost.  This improves over worst case lower bounds when $\log \frac{n\eta_{\infty}}{OPT} = o(\frac{\log n}{\log\log n})$, and nearly matches worst case bounds otherwise.  At a high level the algorithm first follows Meyerson's algorithm, then opens some additional facilities by taking into account the predictions.  In order to get the stated bound, the predictions are "calibrated" so that $\eta_\infty = O(OPT)$ so that $\log \frac{n\eta_{\infty}}{OPT} = O(\log n)$, thus it suffices to only prove the bound of $O(\log \frac{n\eta_{\infty}}{OPT})$.  A lower bound is also given, showing that the result is nearly tight.

Additionally, an experimental validation is carried out, comparing the proposed algorithm with Meyerson's algorithm and a naive algorithm which follows the predictions.  The experiments are performed on datasets where the underlying metric is either Euclidean or a graph metric.  The predictions are simulated to have a given level of error.  While the proposed method underperforms against blindly following the predictions when the error is small, it is more robust to large prediction errors and often comes close to Meyerson's algorithm when the prediction error is large.
main_review: This paper follows a recent line of work in considering online algorithms with error-prone predictions.  The main results are an online algorithm for online facility location in this setting and a nearly matching lower bound, which are interesting.  The experimental evaluation is reasonable, but not overly exciting since the improvement over Meyerson's algorithm seem to be very narrow in some cases.  The presentation is mostly clear, but some improvements could be made, especially to the analysis.  Overall, I would be okay with accepting this paper.  See below for some further comments/suggestions.

This paper considers the predictions as coming from an oracle.  Recent work has started to explore the question of how to construct predictions for online algorithms from past data, e.g. [1,2,3] below.  It would be interesting to explore how to construct predictions for online facility location from past data, especially for an empirical evaluation.

[1] - Customizing ML Predictions for Online Algorithms.  Anand et al. ICML 2020

[2] - Learning Online Algorithms with Distributional Advice.  Diakonikolas et al. ICML 2021

[3] - Learnable and Instance Robust Predictions for Online Matching, Flows, and Load Balancing.  Lavastida et al. ESA 2021

Some suggestions for the related work section, which could be fleshed out more:
 - Purohit et al. 2018 also considers non-clairvoyant scheduling on a single machine
 - Secretaries with Advice.  Dütting, et al. EC 2021. also considers the secretary problem with predictions.
 - Flow Time Scheduling with Uncertain Processing Time. Azar et al. STOC 2021 and Online Scheduling via Learned Weights. Lattanzi et al. SODA 2020 consider flow time scheduling and online load balancing, respectively, in settings with error-prone predictions.

Minor comments/suggestions
 - At the end of page 1, "such as experts' advices" -> "such as expert advice"
 - In the "Calibrating predictions" paragraph, "second last" -> "second to last"
 - In the "Calibrating predictions" paragraph, $\frac{n \eta_\infty}{OPT} = O(\log n)$ should probably be $\frac{n \eta_\infty}{OPT} = O(n)$
 - In the proof of lemma 3.6, "the fact that we does not" -> "the fact that we do not"
 - Paragraph before lemma 3.8, "let $\bar{\ell}$ be the integer that" -> "let $\bar{\ell}$ be the integer such that"
 - In the experiments, the four plots seem to have different scales on the x-axis.  This seems to be due to the differing distance scales across each dataset.  It might be helpful for the presentation to either explain this in the text or maybe present the plots with something like $n\eta_\infty / OPT$ on the x-axis.

------------------------------

Edit after reading author responses:

The author's responses have cleared up my questions.  I appreciate the experiments with the simple predictor, which seems reasonable to implement in practice and performs well on the considered datasets.  I have raised my score to accept.

summary_of_the_review: This paper considers a fundamental online problem in the presence of predictions with a nearly tight result for this setting.  The experimental validation is reasonable.  Some improvements could be made to the presentation, but it is currently clear.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: This paper studies the classical online facility location problem in a metric space. Given a new demand in this space, the algorithm will either open a new facility by paying an opening cost $w(f)$ and assign the demand node to this facility, or it will assign the demand node to an existing open facility. The cost incurred by the algorithm is the sum of all the opening costs and assignment costs.

In this paper, the authors consider the setting where, along with every demand node, we are also given a prediction on which facility it gets assigned to in the optimal. Such predictions can potentially be acquired through historical data. 

Their main contribution is an online algorithm for facility location with predictions that has a near-optimal competitive ratio. The competitive ratio relies on a parameter $\eta_\infty$ which is simply the largest prediction error, where prediction error for any demand point is the distance between the predicted facility and the facility that is assigned to the demand in the optimal solution.
Intuitively, the authors show that if the predictions are accurate (i.e., $\eta_\infty$ is small), then their algorithm is $O(1)$-competitive. On the other hand, if the predictions are highly inaccurate, the algorithm will become $O(\log n)$ competitive. 

The algorithm relies on an $O(\log n)$ competitive worst-case optimal (randomized) online algorithm by Meyerson. The idea becomes very simple when facilities have uniform opening costs: Suppose Meyerson’s algorithm opens a facility, one can simply also open a facility at the predicted location. By doing so, the cost incurred will not be more than twice that of Meyerson’s algorithm which is $O(\log n)$-competitive. However, when the predictions are accurate, opening the facilities at predicted locations lead to better future assignments leading to $O(1)$-competitive algorithm.

They extend this approach in a non-trivial way to the case with non-uniform opening costs.

main_review: Strength of this paper: The paper gives a natural relation between prediction error and competitive ratio for a classical online problem. Furthermore, the lower bound presented in the paper makes the competitive ratio of their algorithm near-optimal. Due to this, I find overall result in this paper to be a nice one. 

On the technical side, the authors present a fine-grained analysis of Meyerson’s algorithm parameterizing the competitive ratio on the prediction error. Although it appears somewhat straight-forward, it seems to be a nice contribution.

Weakness:

I have three sets of concerns/criticisms.

a)	Their algorithm uses the worst-case algorithm by Meyerson as a black box to guide its decisions. A more natural approach would have been to incorporate predictions within Meyerson’s algorithm. Their experiments seem to suggest that even with perfect predictions, the empirical gains over Meyerson’s algorithm seem only minor. I suspect that relying on Meyerson’s cost as a black box may be the main reason for this. Indeed, the authors explicitly state that they do not make any attempt to reduce the hidden constant within the big-O notation of the competitive ratio. So, there may be other algorithms that have a similar theoretical trade-off but do significantly better in practice.

b)	There are several presentation issues in the paper. These include undefined notations, typos, and (minor) inaccurate lemma/theorem statements. I point some of them out below. These issues make it challenging to fully verify and appreciate the theoretical claims, especially in a short time frame. Experimental result section is somewhat confusing as well. The authors do not explain their choice of data sets and what makes these data sets “real” for the facility location problem. Also, how are the non-uniform costs assigned to facilities for the non-uniform data set?
 
c)	Finally, I do not see why this prediction model is natural for this problem. How can we use historical data to generate predictions with small \eta value?


Presentation issues are listed below:

1)	OPT is defined to be a value sometimes and a set of facilities on some other occasions (For instance in the statement of theorem 1.1)
2)	Can $\eta_\infty$ be 0? If so, how should we interpret your competitive ratio?
3)	Section 1.2 paragraph 2, there is a missing \log is the competitive ratio of Meyerson’s algorithm
4)	Section 1.3 determined -> deterministic
5)	$f_{open}$ is not initialized in the procedure PRED. L23 of the algorithm uses it without any initialization
6)	A short overview of Meyerson’s algorithm in the Preliminaries can be very helpful.
7)	Lemma 3.5 $X(f^*)$ is undefined.
8)	Theorem 1.2 Should it be for $\eta_{\infty} > 0$?
9)	Page 6: “we does” does not seem correct.
10)	Page 6, line 1 “that” -> “such that”. This seems to be a recurring issue.  
11)	There are several other typos. A careful proofreading of the paper is necessary for it to be of publishable quality. 

summary_of_the_review: Due to the weaknesses mentioned above, I do not believe the paper is ready for publication.

Update: Thank you for addressing my concerns. After reading the new version, I am happy to update my score.
review_title: null

final_score: rating: 8: accept, good paper
review_content: summary_of_the_paper: The paper studies a variant of the online facility location problem where each demand point arrives with a prediction of which facility it is assigned to in an optimal solution. In line with recent work on learning-augmented algorithms, the paper designs an algorithm whose performance degrades gracefully with the quality of the predictions and yet retains an almost optimal worst-case guarantee.
main_review: Overall, the paper is very well-written and does a good job of explaining the key ideas behind the algorithm and proof techniques. The algorithm itself is quite natural and also likely to be useful to practitioners - essentially, the proposed algorithm is to use Myerson's algorithm for online facility location and then open an additional facility at the predicted location whenever Myerson decides to open one. The key technical contributions are for the variant when facilities have non-uniform costs, in which case the additional facilities are opened "near" the predicted location. 

The proposed algorithm obtains a competitive ratio of $O(log (n \eta_\infty/OPT))$ where $\eta_\infty$ is the maximum prediction error. So the algorithm only improves upon the worst-case setting as long as each prediction is $<< OPT$. The authors also demonstrate a matching lower bound though, and in particular show that the dependence on $n \eta_\infty$ is unavoidable.

Q. Is it easy to compute the "consistency" of the algorithm, i.e., the competitive ratio when the predictions are perfectly accurate? Can one try to obtain a $(1+\epsilon)$-consistent (but also robust) algorithm?
Q. Can the robustness bound be improved to $O(\log n / \log \log n)$?

Minor comments:
- Abstract: The last sentence of the first paragraph needs some punctuation
- Page 4: Last line of Section2. "0\leq k \leq L" --> "1 \leq k \leq L" ?
- Page 5. Last line. "in by Lemma 3.5" --> "is by ..."
- The statement of Lemma 3.6 bounds $cost_M()$, but the proof only bounds $cost_P()$. It will be good to remind readers that the expected cost is the same.
 



summary_of_the_review: Overall the paper is a nice addition to the new area of learning-augmented algorithms. The proposed algorithm is practical and almost optimal, though it would be nice to obtain the optimal robustness bound of $O(\log n / \log \log n)$. The paper seems to be a good fit for ICLR.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: The paper studies the classic problem of Online Facility Location augmented with a prediction model. The main contribution is a logarithmic competitive ratio algorithm for the case where facility opening costs are non-uniform.
main_review: Strengths of the paper:
The paper is reasonably well written for most parts -- except perhaps please provide a bit more description of the algorithm instead asking users parse through the pseudocode. The non-uniform case requires a non-trivial amount of analysis and may be of interest to the community.

Weaknesses of the paper:

While theoretically the problem is interesting -- I am not convinced of the practicality of the model. How will you construct a model that can predict what facilities an optimal solution would pick -- it depends on the other facilities that have already been chosen -- so what dataset would you use to train such a model?   In the "real datasets" based experiments, this important aspect is simulated using a 3-approximation algorithm to find the optimal solution and then randomized in accordance with "prediction error" n_\infty.  This needs to be clarified. 
While the non-uniform case is interesting -- as opposed to the uniform case, which is down right trivial, and needs a good bit of work to prove, the idea is quite straightforward and predictable. Indeed, the doubling trick (used because, we do not need n_\infty) is quite common place in the field of approximation algorithm -- ski-rental problem (Purohit et al) for example uses a similar trick. 
Lastly, as a pedantic issue, I would really question the suitability of this work in ICLR. There is no ML/AI, if one discounts the vague motivation (which I have issues with as well). 

summary_of_the_review: The key issue that needs to be addressed is the motivation for assuming that new facility locations can be predicted using a machine learning model. I feel this is quite unrealistic and significantly diminishes the value of the paper. It would be great if the authors could address this issue in the rebuttal phase. Otherwise, I think theoretically the paper is worth publishing, albeit at a more theoretical computer science (such as ESA, or APPROX ).
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: This paper presents an algorithm for online facility location with predictions. The prediction model is that on the arrival of each client, the prediction provides a facility to connect this client to. The quality of the prediction is quantified in the result by the maximum prediction error, i.e., the maximum distance between the locations of the predicted facility and a facility serving the same client in a fixed optimal solution. The main result is that the competitive ratio is constant (which is the best offline ratio) when the maximum prediction error is small (e.g., when it is a 1/n-fraction of the optimal cost, which of course if true when the predictions are precisely correct), and O(log n) (which is the best online ratio, ignoring lower order terms), when the prediction error is large. The algorithm is an augmentation of an online algorithm for the problem by Meyerson that obtains a competitive ratio of O(log n), where in each step in addition to running Meyerson's algorithm, the algorithm uses a second copy of the incremental cost in Meyerson's step to preemptively open more facilities "close" to the predicted facility for the current client. In addition to the theoretical analysis, the paper includes an experimental evaluation of the algorithm comparing it to baselines produced by an algorithm that blindly trusts the prediction and Meyerson's algorithm.
main_review: Strengths:

1. The paper is technically solid, and the analysis, although it builds heavily on Meyerson's analysis, is non-trivial. I would say that from a purely technical perspective, the paper passes the bar for the conference.
2. The facility location problem is an important one. While I am generally inclined more toward papers that develop general purpose tools for the online algorithms with predictions area instead of giving very specific algorithms for particular problems, I think online facility location is a problem that is fundamental enough that it merits study in this framework. (As the paper mentions, this is not the only recent paper on this very problem, although the results are in this paper are more general in that they apply to on-uniform opening costs.)

Weaknesses:

1. I am really not convinced by the error model in this paper. It bases the error on the worst prediction, which means a large error even with one bad prediction (and every other prediction is precisely correct). The paper tries to justify this by showing that the worst case error cannot be replaced by the sum of prediction errors. But, to me, the right solution to this would be to have two components of the error: one component that counts the number of mispredictions (where the distance by which the prediction missed is irrelevant), and the other that captures the $\ell_1$ distance for the correct predictions (that might still not be exact). (Of course, what is counted as a misprediction and what is counted as a correct prediction is not canonical, but the algorithmic guarantee can hold for any such choice.) This would naturally interpolate between robustness (where all predictions are counted as mispredictions) and consistency (where all predictions are correct predictions and the error distance is 0). Instead, this paper replaces $\ell_1$ error with a very loose upper bound of $n$ times the $\ell_\infty$ error, which as I mentioned above, wouldn't give anything better than an online algorithm (without predictions) even if one prediction is badly off.

2. My second concern (and question to the authors) is the dependence of this algorithm on Meyerson's algorithm. The way the algorithm is set up, it takes the solution produced by Meyerson's algorithm and uses the budget provided by this algorithm to essentially reduce future costs by buying facilities "near" the predicted facility. What if we replaced Meyerson's algorithm with another competitive  facility location algorithm? If the algorithm can use any competitive facility location algorithm, that has multiple benefits: (a) the algorithmic framework being designed is more flexible, and can be applied to other similar problems instead of designing another algorithm from scratch, and (b) much of the analysis, which at the moment reprove properties of Meyerson's algorithm, can be eliminated and simplified. As stated, the current algorithm seems to rely on specific properties of Meyerson's algorithm, but is that really necessary?

3. One minor gripe is the way the algorithm is presented in this paper. Could you please include a text description (perhaps in addition to the pseudocode) so that one doesn't have to understand the algorithm solely from the pseudocode?
summary_of_the_review: This is a credible paper on online facility location with predictions. The problem considered is important and relevant, and the results obtained are tight in the sense that consistency and robustness results in the right ballpark. But, I have concerns about the error metric, which is the most important parameter here - with the current error metric, the very realistic possibility of having a single bad prediction is also going to relegate the guarantees of the algorithm to those of having no prediction at all. I would also have been happier with an algorithm that can use an online algorithm for the problem in a more black box manner - this would make the framework more generally applicable (and I suspect this is possible even with the current framework, or some modification of it, because I don't see the framework as conceptually using anything specific about Meyerson's algorithm, although I might be wrong on that last point).
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: The paper considers the online facility location problem with predictions. In this problem, there is a set of facilities given offline on a metric and a sequence of demand points appearing online. When a demand point arrives, we must either route it to a facility we have previously opened, or open new facilities and route the demand to one of the new facilities. The total cost of a solution is the total cost of facilities opened, plus the total distance between each demand point and the facility it was routed to. In the learning-augmented setting, when each demand point arrives we are also given a prediction, in the form of a facility we believe it is routed to in an optimal solution. Let $\eta_\infty$ be the maximum distance between any the facility we predict a demand point is routed to in the optimal solution, and the facility it is actually routed to in the optimal solution. The authors give a $O(\log \frac{n \eta_\infty}{OPT})$-competitive algorithm, where $n$ is the number of demand points and $OPT$ is the cost of the optimal solution - without loss of generality, we can assume $\eta_\infty = O(OPT)$, so this is at worst an $O(\log n)$-competitive algorithm. They also show that this is the optimal competitive ratio up to $O(\log \log n)$ factors, even if $\eta_1$ (the total distance between predictions and OPT's facilities rather than the maximum) is constant. The authors also give experiments showing that on real-world data sets with synthetic predictions that have a bounded $\eta_\infty$ value, their algorithm outperforms Meyerson's when the prediction error is low, outperforms following the predictions when the prediction error is high, and is not too much worse than Meyerson's when the prediction error is high.

The algorithm the authors use first uses the algorithm of Meyerson for the setting without predictions. In this algorithm, for each power of 2 $2^k$, we consider opening the closest facility to the demand point whose cost is at most $2^k$, or that is already in our set of open facilities. Let $\delta_k$ be the distance from the demand point to this facility. We open this facility with, roughly speaking, probability proportional to $\frac{\delta_{k-1} - \delta_k}{2^k}$. Intuitively, we will never open a facility that is further from the demand point from a previously opened facility, and the probability we open a facility closer than the best previously opened facility is roughly proportional to the decrease in connection cost from opening this facility versus the best facility costing half as much, divided by this facility's opening cost. Following a round of Meyerson's algorithm, we use a "prediction step" to possibly open more facilities, whose expected cost is at most the increase in facility and connection cost in the round of Meyerson's algorithm. To do so, we consider facilities in a ball around the predicted facility whose radius is proportional to the distance from the predicted facility to the nearest facility opened in a previous prediction step, and consider opening the cheapest one. We will definitely open it if doing so would not cause the cost of the prediction step to exceed the cost of the round of Meyerson's algorithm, otherwise we open it with some probability, such that the prediction step's expected cost is exactly the cost of the round of Meyerson's algorithm. 
main_review: The main contribution of the paper is giving a near-optimal result for online facility location with predictions, along with a nearly-matching lower bound. The only other result is the Fotakis et al. paper the authors discuss in the intro, which only considers the setting where all facilities have opening cost 1, whereas this paper handles non-uniform opening costs; even ignoring the correctness issues of the Fotakis et al. paper brought up by the authors, the algorithm's prediction step is to the best of my knowledge a novel one, i.e. it is not simply lifting a technique from another paper, and the difference between the weighted and unweighted setting is a key technical challenge in their results. So I would view this as a substantial improvement over the Fotakis et al. paper, even if the Fotakis et al. paper is correct/gets a better competitive ratio in the setting where $\eta_1$ is small (although I agree with the authors that the bound claimed in the Fotakis et al. paper is somewhat fishy due to the fact that it could be negative when $\eta_1$ is large compared to $\eta_\infty$, and was not able to discern from reading that paper where the catch is). Furthermore, the design of the prediction step is fairly non-trivial to me, but after reading the paper I felt I had some good intuition for why this was the right way to use the predicted facilities, i.e. that the prediction step had a nice intuitive explanation. The experiments also nicely supplement the theoretical results. While the lower bound construction is not particularly novel by itself (I believe it is a modification of a lower bound proof for OFL without predictions), the bound itself nicely complements the upper bound as well. 

My main criticism of the paper is the presentation of the lower bound, in particular the claim that the lower bound shows that a bound on $\eta_1$ instead of $\eta_\infty$ is unlikely to offer substantial improvements. The authors state that their lower bound holds even when $\eta_1 = O(1)$. However, in the lower bound example, the distances in the metric could be smaller than one, i.e. the ratio $\eta_1/\eta_\infty$, which is e.g. not changed by just rescaling the metric, and is in my view the right quantity to look at, might still be quite large. So this doesn't say anything about the relation between $\eta_1$ and $\eta_\infty$, i.e. this ratio can vary depending on the setting of $\eta_\infty$ in their example (roughly, $\eta_1$ is fixed but $\eta_\infty$ can be varied). I think if $\eta_\infty$ is sufficiently small in their lower bound one gets $\eta_1 = O(\eta_\infty)$, which shows that in general no $o(\frac{\log n\eta_1/OPT}{\log \log n})$-competitive algorithm is possible, which would e.g. say that one can't get a better asymptotic ratio by replacing $\eta_\infty$ with $\eta_1$, but I'm not completely sure if this is the right takeaway, and the authors don't spell out any argument like this. I would like to see the relationship between $\eta_1$ and $\eta_\infty$ stated more clearly in this lower bound, as well as a discussion of what this relationship implies about bounds depending on $\eta_1$, if the authors wish to make claims that $\eta_1 \ll \eta_\infty$ is unlikely to help like they do in the introduction.

Also, I don't believe it is mentioned anywhere that OPT does not have to be the offline optimal solution in the analysis, which is implicitly being used in the lower bound - in this lower bound, $\eta_\infty$ is the distance between the predictions and a solution which may be optimal. For clarity's sake it would be good to either mention this somewhere, or the lower bound construction should prove the one-facility solution is optimal; if anything the former should strengthen the upper bound result by making it more general, and it would be more in line with the empirical results, which don't find an exact solution to base predictions off 

Lastly, less so a weakness than a lack of strength, while online facility location is a fairly fundamental question in the online algorithms space, I don't think that compared to e.g. "The Primal-Dual method for Learning Augmented Algorithms" by Bamas et al., this paper's techniques are fundamentally breaking new technical ground in the learning-augmented space that could offer insights into other problems. Again, I wouldn't view this a weakness, just a reason why I don't feel I can rate this paper highly despite enjoying reading it.
summary_of_the_review: Overall I think the paper is a weak accept, if the aforementioned concerns with the presentation of the lower bound construction can be resolved (if they are not resolved in the rebuttal period, I would rate at a weak reject). I think the algorithm and its analysis are fairly non-trivial but intuitive and enjoyable to read about, the problem being addressed is one of interest, and the lower bound/empirical results nicely complement the upper bounds. However, it is not clear to me if this paper stands out in particular amongst other papers in the learning-augmented online algorithms literature, and there are some concerns with the presentation of the lower bound I wish to see addressed before publication.
review_title: null

Meta-review: This paper considers the recent line of work on algorithms with predictions.  They give new results on the online facility location problem. Overall, the reviewers felt the topic was of interest to the community.  There were some concerns about the error metric used and the overall framework. However, the majority of reviewers still felt the paper was interesting and I think the paper can be accepted.
Decision: Accept (Poster)