- 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 , with constant competitiveness for small error and optimal worst-case robustness. Matching lower bounds and synthetic experiments complement the analysis.
Critical strengths
-
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.
-
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
-
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.
-
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
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):
-
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).
-
Moses Charikar, Jacob Steinhardt, Gregory Valiant. Learning from Untrusted Data, STOC 2017 (cited as Charikar et al. (2017) in our paper).
-
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).
-
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).
-
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).
-
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).
-
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:
-
Jasper C. H. Lee, Walter McKelvie, Maoyuan Song, and Paul Valiant. All-Purpose Mean Estimation over : Optimal Sub-Gaussianity with Outlier Robustness and Low Moments Performance, ICML 2025 (cited as Lee et al. (2025) in our revised paper).
-
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).
-
Anish Acharya, Sujay Sanghavi, Alex Dimakis, and Inderjit S. Dhillon. Geometric Median (GM) Matching for Robust -Subset Selection from Noisy Data, ICML 2025 (cited as Acharya et al. (2025) in our revised paper).
-
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 independent samples per distribution and adversarial replacements, our guarantee extends with effective error by randomly permuting the samples and using the first . The analysis has the same overall structure as in the single-sample case (Intuitively, the first samples contain corrupted entries in expectation). Similarly, the lower bound (Theorem B.12) extends using a hard instance of size and replacing all its 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.
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.
Anupam Gupta, Gregory Kehne, Roie Levin. Set Covering with Our Eyes Wide Shut, SODA 2024 (cited as Gupta et al. (2024) in our paper).
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).
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).
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).
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).
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 Di is provided immediately before the actual ith 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 k steps before the actual input, a worst-case online input can be simulated by padding each real input with k dummy inputs. This retains worst-case performance over an input of size n/(k+1), which is Ω(n) for fixed k. We have added this discussion in Appendix E of the revised paper.