acceptodds
Under review as a conference paper at ICLR 2027

Learning-Augmented Facility Location with Samples

Abstract

Facility location is a fundamental problem in clustering and unsupervised learning. We consider the stochastic setting in which the clients arrive online from a sequence of unknown distributions. It is known (Gupta, Kehne, and Levin, SODA '24) that learning augmentation in the form of just a *single offline sample* from each distribution can significantly improve performance guarantees over the worst-case. However, this algorithm is non-robust: noisy samples invalidate the algorithmic guarantees. In this paper, we address this gap by designing the first *robust* learning-augmented algorithm for online facility location with samples. Our algorithm is robust to two natural forms of noise: adversarial corruption, in which individual samples may be manipulated, and distributional noise, in which samples are drawn from distributions that do not exactly match the corresponding input distributions. We complement our theoretical results with numerical simulations that empirically evaluate the performance and robustness of our algorithm.

Primary area:
learning theory
Keywords:
Learning-Augmented Algorithms, Facility Location, Online Algorithms

Reviews

Among:
Shape:
1234this paper, Top 15%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 3.00 over 3 reviews, above 85% of the others.
Reviewer_FDWjOpenReview ↗
Rating
3
Confidence
3
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

The paper studies online facility location with non-uniform opening costs, where requests are drawn independently from arbitrary distributions and the algorithm receives one offline sample per request distribution. It considers distributional mismatch and adaptive adversarial corruption of the samples. The proposed algorithm achieves an error-dependent competitive ratio of O(log⁡ℓ/log⁡log⁡ℓ)O(\log \ell/\log\log \ell), with constant competitiveness for small error and optimal worst-case robustness. Matching lower bounds and synthetic experiments complement the analysis.

Critical strengths
  1. The paper considers a general model of online facility location. Requests are drawn independently from arbitrary, not necessarily identical distributions, so the model subsumes arbitrary deterministic request sequences. The results also hold for non-uniform opening costs, a substantially more challenging setting than the uniform-cost case. The underlying problem is therefore general, and the prediction and noise models are reasonably well motivated.

  2. The paper obtains strong competitive guarantees. In particular, its worst-case robustness matches the optimal competitive ratio for online facility location without predictions.

Critical weaknesses
  1. The model assumes that the entire prediction sequence is available offline, before any requests arrive. This is a strong assumption on access to advice and substantially reduces the uncertainty faced by the online algorithm. Furthermore, while the distributional noise model is well motivated, the motivation for the adversarial contamination model is less clear. Allowing the adversary to inspect the sample before corrupting it destroys independence and introduces substantial technical difficulties. However, an exactly matched clean sampling process followed by sparse adversarial replacements seems less representative of practical prediction errors.

  2. The single-sample assumption would benefit from further justification. If the predictor provides sampling access to a distribution, it is natural to ask why the algorithm is restricted to one sample. A discussion of whether additional samples improve the competitive ratio, or whether the lower bounds extend to this setting, would strengthen the motivation for the prediction model.

Questions for authors

See Critical Weaknesses.

2 comments

We thank the reviewer for carefully reading the paper, and for their positive assessment. We respond to the questions/weaknesses below; we have added these clarifications to the paper. New text in the revised paper is marked in green.

R: The model assumes that the entire prediction sequence is available offline, before any requests arrive. This is a strong assumption on access to advice and substantially reduces the uncertainty faced by the online algorithm.

A: Our model is standard for online problems with offline samples. For instance, it is used in the following papers, all of which are now cited in the revised paper.

  1. Anupam Gupta, Gregory Kehne, Roie Levin. Set Covering with Our Eyes Wide Shut, SODA 2024 (cited as Gupta et al. (2024) in our paper).

  2. Rohan Ghuge, Sahil Singla, Yifan Wang. Single-Sample and Robust Online Resource Allocation, STOC 2025 (cited as Ghuge et al. (2025) in the revised paper).

  3. Paul Dütting, Thomas Kesselheim, Brendan Lucier, Rebecca Reiffenhäuser, Sahil Singla. Online Combinatorial Allocations and Auctions with Few Samples, FOCS 2024 (cited as Dütting et al. (2024) in the revised paper).

  4. Aviad Rubinstein, Jack Z. Wang, S. Matthew Weinberg. Optimal Single-Choice Prophet Inequalities from Samples, ITCS 2020 (cited as Rubinstein et al. (2020) in the revised paper).

  5. Constantine Caramanis, Paul Dütting, Matthew Faw, Federico Fusco, Philip Lazos, Stefano Leonardi, Orestis Papadigenopoulos, Emmanouil Pountourakis, Rebecca Reiffenhäuser. Single-Sample Prophet Inequalities via Greedy-Ordered Selection, SODA 2022 (cited as Caramanis et al. (2022) in the revised paper).

  6. Pranav Nuti, Peter Westbrook. Static Pricing for Single Sample Multi-unit Prophet Inequalities, SOSA 2026 (cited as Nuti and Westbrook (2026) in the revised paper).

The main reason that samples are assumed to be available offline is that when provided incrementally, samples usually cannot bypass worst-case lower bounds (without samples). First, note that if a sample from DiD_i is provided immediately before the actual iith online input, then the sample does not change the information state of the algorithm, and hence, the model is equivalent to a worst-case online model. Furthermore, even if the sample is revealed kk steps before the actual input, a worst-case online input can be simulated by padding each real input with kk dummy inputs. This retains worst-case performance over an input of size n/(k+1)n/(k+1), which is Ω(n)\Omega(n) for fixed kk. We have added this discussion in Appendix E of the revised paper.

R: Furthermore, while the distributional noise model is well motivated, the motivation for the adversarial contamination model is less clear. Allowing the adversary to inspect the sample before corrupting it destroys independence and introduces substantial technical difficulties. However, an exactly matched clean sampling process followed by sparse adversarial replacements seems less representative of practical prediction errors.

A: This is the standard strong-contamination model used in robust algorithmic statistics, e.g., see this book:

Ilias Diakonikolas and Daniel M. Kane. Algorithmic High-Dimensional Robust Statistics, Cambridge University Press 2023 (cited as Diakonikolas and Kane (2023) in our paper).

There are multiple papers on robust estimation and learning under adversarial contamination, such as the following (all cited in our paper):

  1. Ilias Diakonikolas, Gautam Kamath, Daniel M. Kane, Jerry Li, Ankur Moitra, Alistair Stewart. Robust Estimators in High Dimensions without the Computational Intractability, FOCS 2016 (cited as Diakonikolas et al. (2016) in our paper).

  2. Moses Charikar, Jacob Steinhardt, Gregory Valiant. Learning from Untrusted Data, STOC 2017 (cited as Charikar et al. (2017) in our paper).

  3. Jacob Steinhardt, Moses Charikar, Gregory Valiant. Resilience: A Criterion for Learning in the Presence of Arbitrary Outliers, ITCS 2018 (cited as Steinhardt et al. (2018) in our paper).

  4. Yu Cheng, Ilias Diakonikolas, Rong Ge. High-Dimensional Robust Mean Estimation in Nearly-Linear Time, SODA 2019 (cited as Cheng et al. (2019) in our paper).

  5. Ilias Diakonikolas, Daniel M. Kane, Ankit Pensia. Outlier Robust Mean Estimation with Subgaussian Rates via Stability, NeurIPS 2020 (cited as Diakonikolas et al. (2020) in our paper).

  6. Arnak S. Dalalyan, Arshak Minasyan. All-in-one robust estimator of the Gaussian mean, Annals of Statistics 2022 (cited as Dalalyan and Minasyan (2022) in our paper).

  7. Daniel M. Kane, Ilias Diakonikolas, Hanshen Xiao, Sihan Liu. Online Robust Mean Estimation, SODA 2024 (cited as Kane et al. (2024) in our paper).

We have also added citations to the following recent papers:

  1. Jasper C. H. Lee, Walter McKelvie, Maoyuan Song, and Paul Valiant. All-Purpose Mean Estimation over R\mathbb{R}: Optimal Sub-Gaussianity with Outlier Robustness and Low Moments Performance, ICML 2025 (cited as Lee et al. (2025) in our revised paper).

  2. Xabier de Juan and Santiago Mazuelas. On the Optimality of the Median-of-Means Estimator under Adversarial Contamination, NeurIPS 2025 (cited as de Juan & Mazuelas (2025) in our revised paper).

  3. Anish Acharya, Sujay Sanghavi, Alex Dimakis, and Inderjit S. Dhillon. Geometric Median (GM) Matching for Robust kk-Subset Selection from Noisy Data, ICML 2025 (cited as Acharya et al. (2025) in our revised paper).

  4. Adam Klivans, Konstantinos Stavropoulos, Kevin Tian, and Arsen Vasilyan. The Power of Iterative Filtering for Supervised Learning with (Heavy) Contamination, NeurIPS 2025 (cited as Klivans et al. (2025) in our revised paper).

We would like to note that our guarantees extend to the combined noise model: distributional mismatch followed by adversarial corruption of the resulting samples. The proof uses a coupling argument and our existing bounds for both models as black boxes. We view the adversarial model as a way to go beyond independent sample errors, allowing coordinated corruptions that depend on the entire realized sample. We have added this as Theorem D.1 in Appendix D of the revised paper.

R: The single-sample assumption would benefit from further justification. If the predictor provides sampling access to a distribution, it is natural to ask why the algorithm is restricted to one sample. A discussion of whether additional samples improve the competitive ratio, or whether the lower bounds extend to this setting, would strengthen the motivation for the prediction model.

A: Adversarial Noise: With kk independent samples per distribution and bb adversarial replacements, our guarantee extends with effective error b/kb/k by randomly permuting the nknk samples and using the first nn. The analysis has the same overall structure as in the single-sample case (Intuitively, the first nn samples contain b/kb/k corrupted entries in expectation). Similarly, the lower bound (Theorem B.12) extends using a hard instance of size b/kb/k and replacing all its (b/k)⋅k(b/k) \cdot k samples, making the sample uninformative. Thus, at a fixed global corruption fraction, additional samples do not improve the asymptotic guarantee. We have added this as Theorem F.1 in Appendix F of the revised paper.

Distributional Noise: The upper and lower bounds remain unchanged. For the upper bound, use one sample per distribution. The lower-bound construction (Theorem B.12) uses point-mass distributions, so additional samples provide no new information. We have added this as Theorem F.6 in Appendix F of the revised paper.

Reviewer_XbGSOpenReview ↗
Rating
3
Confidence
3
Informativeness
3
Presentation
3
Soundness
2
Read review
Paper summary

This paper studies online facility location when the algorithm receives one offline sample from each unknown client distribution. It considers two sources of sample error: distributional mismatch between the sample and input distributions, and adversarial corruption of sample entries. The proposed ROBUST-ONLINE algorithm combines an offline simulation of Meyerson’s algorithm on randomly ordered samples with an online execution, gradually opening facilities suggested by the simulation under a budget determined by the online costs incurred. The authors derive a competitive guarantee that interpolates between constant competitiveness with accurate samples and the optimal worst case bound with arbitrary sample noise. They also establish matching lower bounds showing that the asymptotic dependence on sample error is optimal in both noise models. Experiments on synthetic instances examine the benefits of accurate samples, sensitivity to several corruption patterns, and computational scalability.

Critical strengths
  1. A well motivated problem with strong algorithmic and theoretical contributions. The paper addresses an important limitation of prior work on online facility location with samples: the sensitivity of sample based guarantees to unreliable predictions. It proposes a unified algorithm that handles both adversarial sample corruption and distributional mismatch, and derives competitive guarantees that degrade gracefully with sample error. Matching lower bounds establish the asymptotic optimality of this error dependence, while synthetic experiments provide complementary evidence of the benefits of accurate samples and robustness under corruption. Together, these contributions offer a substantive treatment of a meaningful robustness problem.
  2. Clear and well organized presentation. The paper follows a coherent structure, progressing from the problem formulation and noise models to the algorithm, theoretical analysis, and experimental evaluation. This organization makes the motivation and main technical ideas accessible and helps readers follow how sample quality translates into performance guarantees. The clarity of the presentation facilitates understanding and assessment of the contribution.
Critical weaknesses
  1. The residual cost bound in Lemma 3.4 appears to require a constant term. Equation (5) states that E[Γζ]≤O(ℓ)E[OPT(X)]\mathbb{E}[\Gamma_\zeta]\le O(\ell)\mathbb{E}[\mathrm{OPT}(X)]. Consider a single client drawn uniformly from two points at distance 2, each with a facility of opening cost 1. Let the offline sample be drawn independently from the same distribution, so that ℓ=0\ell=0. The sample simulation opens a facility at the sampled point. With probability 1/2, the online client is at the other point and requires an additional cost of 1. Hence, E[Γζ]=1/2\mathbb{E}[\Gamma_\zeta]=1/2, whereas the stated bound would imply zero. An O(1+ℓ)O(1+\ell) dependence appears more appropriate, unless a truncation convention for ℓ\ell is intended. This issue seems fixable and may not affect the main asymptotic result, but the statement and its subsequent uses should be checked.

  2. The stopping time cost estimate in the proof of Theorem 3.1 requires additional justification. On page 7, the bound E[Bt∗]≤E[CζRO]+E[OPT(X)]\mathbb{E}[B_{t^*}]\le\mathbb{E}[C_\zeta^{RO}]+\mathbb{E}[\mathrm{OPT}(X)] is inferred from Bt∗−1<CζROB_{t^*-1}<C_\zeta^{RO} and the single step expectation bound in Lemma B.1. However, the stopping time depends on the realized costs, so the increment crossing the threshold can be biased toward large values. For example, consider at most NN independent rounds, each incurring cost NN with probability 1/N1/N and zero otherwise. Every increment has conditional expectation one. Nevertheless, stopping at the first crossing of threshold one, or at the end if no crossing occurs, gives expected accumulated cost N[1−(1−1/N)N]=Θ(N)N[1-(1-1/N)^N]=\Theta(N). Thus, bounded conditional expectations for individual steps alone do not imply a bound given by the threshold plus a constant. This example illustrates the inference issue, rather than a failure of ROBUST-ONLINE itself. Since this estimate is needed to establish the claimed competitive guarantee, the authors should provide an additional argument controlling the cost of crossing the threshold, using the specific structure of Meyerson’s algorithm. This may be fixable, but the justification is currently incomplete.

Questions for authors
  1. Clarification of the error dependence in Lemma 3.4. In Equation (5), is the sample error implicitly truncated below by one? If the original definition of ℓ\ell is intended, would the residual cost bound need to involve O(1+ℓ)O(1+\ell) rather than O(ℓ)O(\ell)? Please clarify the intended statement and whether the corrected bound preserves the claimed constant competitive guarantee when the distributional error is zero.

  2. Justification of the stopping time cost estimate. In the proof of Theorem 3.1, how does Lemma B.1 justify the bound on the accumulated cost at the first threshold crossing? Since t∗t^* depends on the realized cost increments, the conditional expectation bound for a fixed step does not immediately control the cost of the crossing step. Could you provide the additional property of Meyerson’s algorithm, or an explicit bound on the overshoot, that establishes this estimate?

Please feel free to correct me if I have misunderstood any part of the proof. If all of my concerns are satisfactorily addressed or shown to stem from a misunderstanding on my part, I would consider raising my score in light of the scope and quality of the work.

2 comments

We thank the reviewer for carefully reading the paper, and for their positive assessment. New text in the revised paper is marked in green.

R: Clarification of the error dependence in Lemma 3.4.

A: Of course, when we say E[Γζ]≤O(ℓ)E[OPT(X)]\mathbb{E}[\Gamma_\zeta]\le O(\ell) \mathbb{E}[\mathrm{OPT}(X)], we do mean that E[Γζ]≤O(1)E[OPT(X)]\mathbb{E}[\Gamma_\zeta]\le O(1) \mathbb{E}[\mathrm{OPT}(X)] when ℓ<1\ell < 1. This is a standard convention, e.g., we often say an algorithm is O(log⁡n)O(\log n)-competitive, even though n=1n=1 is possible. We have made this explicit at the end of Section 2 of the revised paper.

R: Justification of the stopping time cost estimate.

A: We thank the reviewer for pointing this out. Instead of using Lemma B.1 here, use the following slight variant (Lemma B.11 in the revised paper):

Lemma. Let costt\mathsf{cost}_t denote the cost incurred by ON (Meyerson's algorithm) when client vt∈Xv^t\in X arrives at time tt. Then,

E[max⁡1≤t≤ncostt]=O(1)⋅EX[OPT(X)].\mathbb{E}\left[\max_{1\le t\le n}\mathsf{cost}_t\right] = O(1) \cdot \mathbb{E}_X[\mathrm{OPT}(X)].

The proof of this lemma is very similar to that of Lemma B.1. We have added this lemma and its proof in Appendix B of the revised paper.

Please let us know whether the clarified convention and the additional lemma and proof satisfactorily address your concerns.

Reviewer_XbGSOpenReview ↗

Thank the authors for the response.

Thank you for your thoughtful response. I am satisfied that my concerns have been largely addressed. I consider this an interesting contribution and will maintain my score and recommendation for acceptance.

Reviewer_UzQXOpenReview ↗
Rating
3(+1)
Confidence
3
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

The paper studies online facility location under two noise models. The first model is the distributional noise model, where the sequence of arriving points comes from distributions that may differ from the true distributions producing the online input. The second model is the adversarial noise model, where an adversary can replace exactly ℓ\ell points in the sequence. The authors give an online algorithm that obtains a competitive ratio of O(log⁡ℓlog⁡log⁡ℓ)\mathcal{O}(\frac{\log \ell}{\log \log \ell}) under both noise models, together with a matching lower bound.

Critical strengths
  1. The noise models proposed by the paper appear to be novel.
  2. Using samples to augment online algorithms in the considered setting also appears to be new.
Critical weaknesses
  1. The discussion related to Gupta et al. (2024) is inaccurate and incomplete. The most critical issue is that Appendix C is not sufficiently self-contained to verify its correctness, since it proves a result about the algorithm by Gupta et al. (2024) which is never even briefly described.

    • Lines 59-62 don’t put the algorithm of Gupta et al. (2024) in the correct context. It is a random-order algorithm, but the authors compare it to a worst-case result without mentioning that the competitive ratio of 66 is obtained only for the random-order model. This is misleading because no algorithm can overcome the optimal competitive ratio in the worst-case adversarial model.
    • Lines 64-65 incorrectly state that their algorithm “fails to provide performance guarantees”. First, this statement is ambiguous and incorrect, since Lemma C.1 in Appendix C explicitly states that their algorithm’s “competitive ratio is Ω(ℓ)\Omega(\ell) under either noise model”. That's not equivalent to "no performance guarantees".
    • The statement of Lemma C.1 is inaccurate, incomplete and not very self-contained. The reader is pointed to Appendix C before anything is defined formally, including ℓ\ell, the noise models and anything else. So it’s hard to understand a proof that relies on a model that hasn’t appeared yet in the main text. Also, stating a theoretical result for an algorithm that is never formally described, not even briefly, makes it hard to verify correctness. Readers are not supposed to move between the authors’ submission and the paper of Gupta et al. (2024) to verify the result. The result is already in the appendix, so the algorithm should have been described there. The authors also assume that readers are already familiar with the random-order model, so they skipped its definition. They should have at least briefly defined it by saying that the points’ locations are determined by an adversary, but their arrival order is selected uniformly at random.
  2. On top of those inaccuracies, there are other inaccurate/misleading statements throughout the paper. The most critical of them is that the adversarial noise model and Meyerson’s algorithm are not well-defined, as described below. The paper is also not very accessible for readers unfamiliar with online algorithms and the authors assume full prior knowledge about certain concepts, so the authors leave a lot of key things undefined. Given that ICLR attracts a wide audience from different fields, I suggest at least briefly defining certain key notions throughout the paper, like competitive ratio, worst-case adversarial model, random-order model and so on, as not everyone is familiar with specific concepts for online algorithms. It should also be said that algorithms make immediate and irrevocable decisions. That would make it easier to digest for readers that are less familiar with the topic. Though I am personally familiar with the topic, I suspect that the paper will be hard to follow for unfamiliar readers because of the abundance of omitted/inaccurate definitions.

    • Lines 72-73: It should be more accurately said that the adversary may corrupt exactly ℓ\ell of them by replacing them. Saying “may corrupt them before they are presented to the algorithm” is misleading and ambiguous because the actual corruption remains undefined.
    • Similarly, line 78 is vague about how ℓ\ell is actually evaluated. For the distributional noise model, it is the prediction error, while for the adversarial noise model it is the number of replaced points. Neither are clarified in the introduction properly.
    • Line 142 defines XX as a subset, but line 147 then defines it as a sequence. You should stick to one of them for consistency, or use, e.g., σ\sigma to denote the arrival order. That creates issues later when the authors write X^=Y^∪Z^\hat X= \hat Y \cup \hat Z because it is a union of sequences, while it’s supposed to be concatenation. Regardless, it’s unclear what is the arrival order in this model because the authors do not specify it. I suspect that it’s not necessarily the points in Y^\hat Y and then those in Z^\hat Z, but the notation does not clarify this. Anyway, the arrival order should be explicitly stated.
    • The description of Meyerson’s algorithm is essentially correct and captures the main idea of the algorithm for nonuniform opening costs, but a few details are needed to make it fully precise. In particular, it should specify that no facilities are initially open, define the distance to an empty set as infinity and clarify that the first client triggers a facility opening with probability one. It should also state that all opening probabilities are calculated using the set of facilities open before the current client arrives, that facility costs are normalized appropriately and that the actual opening cost is paid rather than the rounded power-of-two cost used in the probability calculation. The current description is a cost-level reformulation of Meyerson’s algorithm rather than an exact reproduction of the original algorithm, which should be said explicitly.
  3. The paper somewhat lacks technical depth (it has a single main result). Further, the use of Meyerson’s algorithm to design online algorithms for this setting is not new, but it is not acknowledged. It was already used in the paper by Jiang et al. (2022), which also reduces technical novelty. Moreover, Lemma 3.4 for example relies on the random-order guarantees of Meyerson’s algorithm, so the technical depth is further reduced.

  4. There are certain issues and inaccuracies along certain proofs. Below are some examples (the authors should go over other proofs and find possible other issues):

    • The proof of Lemma B.2 says that E[Ii⋅p(Hi−1)]=Pr[τ=i]\mathbb E[I_i\cdot p(H_{i−1})] = Pr[\tau = i], but IiI_i is an event. The authors meant to write 1τ≥i1_{\tau \ge i} instead of IiI_i.
    • The proof of Lemma B.3 is incomplete and skips several steps. First, it should explicitly be said that the probability of any event cannot exceed the total mass of the distribution from which it is measured. Therefore, the authors should write: ai(t)=∑v:OPT⁡({v})>tD~i(v)≤∑vD~i(v)=∥D~i∥1a_i(t) =\sum_{v:\operatorname{OPT}(\{v\})>t}\widetilde D_i(v) \leq \sum_v\widetilde D_i(v) =\|\widetilde D_i\|_1. Also, the interchange between summation and integration that is used afterwards should be justified formally.
  5. The experiments are restricted to synthetic datasets, while the discussion about them is also largely misleading and inaccurate (e.g., the discussion does not always honestly describe cases where other baselines outperform the proposed Robust-Online algorithm).

    • The paper “Online facility location with predictions”, for example, uses real-world datasets that the authors should include in their experiments.
    • The main text also omits critical choices of hyperparameters, like the number of points generated for each instance family.
    • The most critical flaw in the experiments is that the authors simulate Gurobi + A\mathcal A for every baseline A\mathcal A, but don’t simulate Gurobi + Robust-Online to test the performance of their own algorithm in that setup. Specifically, all the simulated Gurobi + A\mathcal A baselines perform the best, so the authors should have also compared Gurobi + Robust-Online to those baselines.
    • Another unfair comparison is for the corrupted samples experiments, where the authors only discuss which baselines are outperformed by Robust-Online, but for obvious reasons say nothing about the baselines that beat Robust-Online. For example, in Equidistant Cluster Corruption (Figure 2(a)), Fotakis, Fotakis PD and Meyerson all surpass Robust-Online (it’s hard to see whether Greedy also outperforms it here because it is possibly overlapped by other baselines). Other plots show similar trends.

Minor comments

  • The introduction is not structured in the correct chronological order. It introduces clustering in the first line and then immediately jumps to online settings, learning-augmented algorithms and so on before actually defining the problem itself (in offline settings). The problem in offline settings is only presented in the second paragraph. The introduction should start from the offline version (specifically, the second paragraph should be converted to become the first one). Afterwards, the introduction should transition to an online setting. Then, statements like “where the set of points to be clustered arrives over time” will be clearer since they are currently presented only in the second paragraph. Regardless, it makes more sense to define the problem before discussing its extensions. Currently, the introduction jumps back and forth between offline and online settings, so this will create a clearer separation.

  • I suggest writing, e.g., “Appendix C” instead of “Section C”, for appendices. That way, “ Section C of the appendix” can be reduced to “Appendix C”.

  • If Theorem B.11 in Appendix B is classified as part of the contributions in the introduction, why is it completely in the appendix? Its statement should at least appear in the main text.

  • Lines 143-144 discuss the objective function in plain words, but it is only defined in lines 151-153. Why not define it when it is first discussed?

  • It should be explicitly said that DiD_i is a distribution over VV.

  • Line 170: say that GiG_i is the binary indicator, because simply saying “indicate that” is ambiguous.

  • Certain equations in the appendix overflow outside the right margin (e.g., equation (16), the second displayed equation in the proof of Claim B.5 and so on).

  • The proof of Lemma B.1 seems to redefine several notations, but now with few changes (e.g., δj\delta_j instead of δj(v)\delta_j(v)).

  • Line 300: the text in brackets shouldn’t be in brackets.

Questions for authors
  1. In both noise models, how do you define the arrival order of points?
  2. To fully validate the empirical results in, e.g., Figure 1, the authors should have tested Gurobi + Robust-Online, the method in the paper “Online facility location with predictions” cited above and real-world datasets to show that the method is practically relevant (e.g., the authors should have considered the datasets used in “Online facility location with predictions”).
  3. I would appreciate any more accurate and honest discussion on where Robust-Online fails in the experiments, and not just about where it succeeds.
9 comments

We thank the reviewer for the detailed review. We address the major comments below, and the changes made in response to them. We have also addressed the minor changes suggested by the reviewer in the revised paper. New text in the revised paper is marked in green.

R: The discussion related to Gupta et al. (2024) is inaccurate and incomplete. The most critical issue is that Appendix C is not sufficiently self-contained to verify its correctness, since it proves a result about the algorithm by Gupta et al. (2024) which is never even briefly described.

A: We have added the details of the Gupta et al. (2024) algorithm in Appendix C of the revised paper.

R: Lines 59-62 don’t put the algorithm of Gupta et al. (2024) in the correct context. It is a random-order algorithm, but the authors compare it to a worst-case result without mentioning that the competitive ratio of 66 is obtained only for the random-order model. This is misleading because no algorithm can overcome the optimal competitive ratio in the worst-case adversarial model.

A: The 66-competitive guarantee of Gupta et al. (2024) is for worst-case online arrival order, with a single offline sample from the distributions. This guarantee is not for the random-order model (see Corollary 6.2 of their paper). This is clarified in Appendix C of the revised paper.

R: Lines 64-65 incorrectly state that their algorithm “fails to provide performance guarantees”. First, this statement is ambiguous and incorrect, since Lemma C.1 in Appendix C explicitly states that their algorithm’s “competitive ratio is Ω(ℓ)\Omega(\ell) under either noise model”. That's not equivalent to "no performance guarantees".

A: We have revised the text to clarify that the Gupta et al. algorithm can have competitive ratio Ω(ℓ)\Omega(\ell) on instances with sample noise ℓ\ell, whereas our algorithm achieves an exponentially better (and optimal) Θ(log⁡ℓ/log⁡log⁡ℓ)\Theta(\log \ell/\log\log \ell) dependence. Even for ℓ=nc\ell=n^c, where 0<c≤10<c\leq1 is any fixed constant, their ratio can be exponentially worse than the optimal worst-case guarantee of O(log⁡n/log⁡log⁡n)O(\log n/\log\log n) achievable without samples. These clarifications appear in the introduction and Appendix C of the revised paper.

R: The statement of Lemma C.1 is inaccurate, incomplete and not very self-contained. The reader is pointed to Appendix C before anything is defined formally, including ℓ\ell, the noise models and anything else. So it’s hard to understand a proof that relies on a model that hasn’t appeared yet in the main text. Also, stating a theoretical result for an algorithm that is never formally described, not even briefly, makes it hard to verify correctness. Readers are not supposed to move between the authors’ submission and the paper of Gupta et al. (2024) to verify the result. The result is already in the appendix, so the algorithm should have been described there. The authors also assume that readers are already familiar with the random-order model, so they skipped its definition. They should have at least briefly defined it by saying that the points’ locations are determined by an adversary, but their arrival order is selected uniformly at random.

The paper is also not very accessible for readers unfamiliar with online algorithms and the authors assume full prior knowledge about certain concepts, so the authors leave a lot of key things undefined.

A: We have added the details of the Gupta et al. (2024) algorithm in Appendix C.

Note that the noise models are introduced in Section 1, and formally defined in Section 2 of the main body of the paper. In Section 2, we have also added brief definitions of online algorithms, competitive ratio, the worst-case adversarial model, and the random-order model.

R: Lines 72-73: It should be more accurately said that the adversary may corrupt exactly ℓ\ell of them by replacing them. Saying “may corrupt them before they are presented to the algorithm” is misleading and ambiguous because the actual corruption remains undefined. Similarly, line 78 is vague about how ℓ\ell is actually evaluated. For the distributional noise model, it is the prediction error, while for the adversarial noise model it is the number of replaced points. Neither are clarified in the introduction properly.

A: We formally define both the distributional and adversarial noise models in Section 2, and have also clarified this in the introduction.

R: Line 142 defines XX as a subset, but line 147 then defines it as a sequence. You should stick to one of them for consistency, or use, e.g., σ\sigma to denote the arrival order. That creates issues later when the authors write X^=Y^∪Z^\hat{X}=\hat{Y}\cup\hat{Z} because it is a union of sequences, while it’s supposed to be concatenation. Regardless, it’s unclear what is the arrival order in this model because the authors do not specify it. I suspect that it’s not necessarily the points in Y^\hat{Y} and then those in Z^\hat{Z}, but the notation does not clarify this. Anyway, the arrival order should be explicitly stated.

A: The online requests arrive in a sequence X=(v1,…,vn)X = (v^1,\ldots,v^n) (viv^i arrives at time ii) whereas the offline sample X^\hat{X} is a set since it does not arrive in any order. The decomposition X^=Y^∪Z^\hat{X} = \hat{Y} \cup \hat{Z} partitions this set into two sets, with no ordering on them. This is clarified in Section 2 of the revised paper.

R: The description of Meyerson’s algorithm is essentially correct and captures the main idea of the algorithm for nonuniform opening costs, but a few details are needed to make it fully precise. In particular, it should specify that no facilities are initially open, define the distance to an empty set as infinity and clarify that the first client triggers a facility opening with probability one. It should also state that all opening probabilities are calculated using the set of facilities open before the current client arrives, that facility costs are normalized appropriately and that the actual opening cost is paid rather than the rounded power-of-two cost used in the probability calculation. The current description is a cost-level reformulation of Meyerson’s algorithm rather than an exact reproduction of the original algorithm, which should be said explicitly.

A: We have clarified the initialization and empty-set conventions for Meyerson's algorithm, including why the first client triggers an opening with probability 11, along with the other implementation details noted by the reviewer. This is given in Section 3.1 of the revised paper.

R: Further, the use of Meyerson’s algorithm to design online algorithms for this setting is not new, but it is not acknowledged. It was already used in the paper below (which is uncited for some reason), which also reduces technical novelty.

Jiang, S. H. C., Liu, E., Lyu, Y., Tang, Z. G., & Zhang, Y.. Online facility location with predictions. ICLR 2022.

A: The original submission included citations to Jiang et al. (2022) in Section 1 (at the top of page 2 and again in related work). Note, however, that the prediction models are very different: their paper uses predictions of the optimal facility serving each client, whereas our paper uses an offline sample of the client distributions as a prediction. Furthermore, the use of Meyerson’s (or Fotakis') algorithm is a necessary component of any online algorithm for this problem with prediction, since robustness requires that any such algorithm extrapolate to a worst-case algorithm if the predictions are incorrect. We have also cited Jiang et al. (2022) before Lemma 3.3 in the revised paper to acknowledge related refinements of Meyerson’s analysis.

Dimitris Fotakis. On the Competitive Ratio for Online Facility Location, Algorithmica 2008 (cited as Fotakis (2008) in our paper).

R: Moreover, Lemma 3.4 for example relies on the random-order guarantees of Meyerson’s algorithm, so the technical depth is further reduced.

A: Meyerson’s random-order guarantee only controls the cost of the uncorrupted prefix, which is the easier part of Lemma 3.4. The main contribution of Lemma 3.4 is to bound the residual cost of the online input starting with the solution on the uncorrupted prefix of the sample. This is technically much more involved and is unrelated to Meyerson's (or Jiang et al.'s) analysis. Note that this analysis is given in full in Appendix B.

R: The proof of Lemma B.2 says that E[Ii⋅p(Hi−1)]=Pr⁡[τ=i]\mathbb{E}[I_i\cdot p(H_{i-1})]=\Pr[\tau=i], but IiI_i is an event. The authors meant to write 1τ≥i\mathbf{1}_{\tau\ge i} instead of IiI_i.

A: We have added the additional details noted by the reviewer. This is in the proof of Lemma B.2 in Appendix B of the revised paper.

R: The proof of Lemma B.3 is incomplete and skips several steps. First, it should explicitly be said that the probability of any event cannot exceed the total mass of the distribution from which it is measured. Therefore, the authors should write: ai(t)=∑v:OPT(v)>tD~i(v)≤∑vD~i(v)=∣D~i∣1a_i(t)=\sum_{v:\mathrm{OPT}(v)>t}\widetilde{D}_i(v)\le\sum_v\widetilde{D}_i(v)=|\widetilde{D}_i|_1. Also, the interchange between summation and integration that is used afterwards should be justified formally.

A: We have added the additional details noted by the reviewer. This is given in the proof of Lemma B.3 in Appendix B of the revised paper.

We can interchange the summation and integral by linearity of integration and because, for finitely many terms, the limit of the sum is the sum of the limits. Moreover, the individual limits exist and their sum is well defined, as they represent expectations of a bounded nonnegative quantity.

∫0∞∑i=1nai(t)dt=lim⁡R→∞∫0R∑i=1nai(t)dt=lim⁡R→∞∑i=1n∫0Rai(t)dt=∑i=1nlim⁡R→∞∫0Rai(t)dt=∑i=1n∫0∞ai(t)dt.\int_0^\infty\sum_{i=1}^n a_i(t)dt =\lim_{R\to\infty}\int_0^R \sum_{i=1}^na_i(t)dt =\lim_{R\to\infty}\sum_{i=1}^n\int_0^R a_i(t)dt =\sum_{i=1}^n\lim_{R\to\infty}\int_0^R a_i(t)dt =\sum_{i=1}^n\int_0^\infty a_i(t)dt.

R: The paper “Online facility location with predictions”, for example, uses real-world datasets that the authors should include in their experiments.

A: Thanks for the suggestion. Our main contribution in this paper is the algorithm and its theoretical analysis, and the numerical simulations provide complementary evidence of its performance and robustness. While real-world datasets do provide additional experimental evidence, we note that many papers on online algorithms with predictions in ICML, NeurIPS, and ICLR either perform experiments only on synthetic data or do not perform experiments at all. We include some examples below:

  1. Silvio Lattanzi, Debmalya Panigrahi, and Ola Svensson. Online Rounding and Learning Augmented Algorithms for Facility Location, ICLR 2026.

  2. Tianming Zhao and Albert Y. Zomaya. On Smoothness Bounds for Non-Clairvoyant Scheduling with Predictions, ICLR 2026.

  3. Ziyad Benomar, Romain Cosson, Alexander Lindermayr, and Jens Schlöter. Non-Clairvoyant Scheduling with Progress Bars, NeurIPS 2025.

  4. Matei Gabriel Coşa and Marek Eliáš. Learning-Augmented Algorithms for MTS with Bandit Access to Multiple Predictors, ICML 2025.

  5. Antonios Antoniadis, Christian Coester, Marek Eliáš, Adam Polak, and Bertrand Simon. Mixing Predictions for Online Metric Algorithms, ICML 2023.

  6. C. J. Argue, Alan M. Frieze, Anupam Gupta, and Christopher Seiler. Learning from a Sample in Online Algorithms, NeurIPS 2022.

R: The main text also omits critical choices of hyperparameters, like the number of points generated for each instance family.

A: The full details of all hyperparameters are given in Appendix A. We have added the instance sizes to Section 4 of the main body of the paper. The number of points generated varies across experiments, but is at least 20,00020,000 in the cluster-based experiments.

R: The most critical flaw in the experiments is that the authors simulate Gurobi + A\mathcal{A} for every baseline A\mathcal{A}, but don’t simulate Gurobi + Robust-Online to test the performance of their own algorithm in that setup. Specifically, all the simulated Gurobi + A\mathcal{A} baselines perform the best, so the authors should have also compared Gurobi + Robust-Online to those baselines.

A: Note that Gurobi is used to compute an optimal solution for the offline sample. In contrast, Robust-Online runs a random-order algorithm on the offline sample. So, there is no situation where Gurobi and the Robust-Online algorithm can be combined, since they explicitly run different algorithms on the offline sample.

One thing to note is that although using Gurobi performs well on uncorrupted samples, computing an optimal solution using Gurobi is computationally much more expensive than running a random-order algorithm on the offline sample. Therefore, the performance gain due to Gurobi comes at a high computational cost. This is in addition to the main point of the paper, which is that even a small amount of corruption can render Gurobi-based baselines uncompetitive, as we show in Figure 2(a).

Comments on the paper

1 comment

We thank the reviewers for their careful reading and detailed feedback. We have revised the paper in response to their comments and provide detailed responses to each reviewer separately. The main revisions are marked in green in the revised paper.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.