Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 7: Good paper, accept
review_content: summary: The paper discusses the k-median algorithm under the online, no-substitution setting. The paper considers the random order arrival of the points and obtains a constant factor approximation without requiring any structural assumptions. They provide an algorithm that gives a constant factor approximation with a $k\log^2k$ centers assuming the $n$ is known (in the discussion they state about the use of doubling to get similar results with $\log n$ overhead).
main_review: The paper is well structured and well written. The claims made in the paper seem sound. The problem itself is a relatively well studied theoretical problem and they manage to give a constant factor approximation algorithm that only has a $\log^2 k$ multiplicative overhead under the random order setting, which is a relatively significant improvement on the existing research. They introduce a new concept of linear bin division to complete the analysis of the algorithm. Overall the paper looks good.

Q: How does the Phase 1 and Phase 2 selection of $P_1, P_2$ (of size $\alpha n$ each) affect the memory requirements (could it lead to memory requirement of order $n$)? 
limitations_and_societal_impact: The algorithm assumes knowledge of $n$, but the paper states how to remove this with an additional $\log n$ overhead.  They also assume random order. They leave the study of different input orders (other than random and adversarial) as a future research direction. 

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

final_score: rating: 7: Good paper, accept
review_content: summary: The authors design a sequential random-order no-substitution algorithm for k-median clustering. Their algorithm outputs O(k\log^2 k) centers and gives constant factor approximation with high probability. The algorithm does not depend on any assumption on the dataset and gives substantially better guarantees over earlier works.
main_review: The problem setup is as follows. The points to be clustered arrive one by one in a random order stream. A point arriving in a stream may or may not be chosen as a center, but if it is chosen as a center, it cannot be substituted later. The authors design a subroutine SelectProc that divides the stream into three phases, the length of each phase is a constant factor of the length of the stream. At the end of the first phase, using an offline algorithm for k-median on the points in the first phase, a set of centers is computed. This set of centers is used in the second phase to estimate the cost of clustering of the points in the second phase. In the third phase, the actual centers are selected by the subroutine. The algorithm runs O(\log k/\delta) instances of the subroutine SelectProc in parallel where each instance of the subroutine works on a different prefix of the stream, and the algorithm outputs all centers chosen by these subroutines. This set of centers give constant factor approximation with high probability for the k-median problem.

Overall, I believe this to be a nice result for a fairly important problem. I recommend acceptance of this paper.

My only comments are regarding the writing and the presentation of the paper.
  - Since the description of the algorithm uses a number of parameters, it would be helpful to define the notations appropriately. For example, k_+ is used in the description of the algorithm but it is defined only in Section 4.2.
  - The authors should highlight that the performance of an algorithm in this setting is evaluated using the notion of competitive analysis of online algorithms.


- This additional comment is to acknowledge reading author response. There is no other changes.
limitations_and_societal_impact: This work is theoretical in nature.
review_title: null

final_score: rating: 5: Marginally below the acceptance threshold
review_content: summary: This is a theoretical paper, studying sequentially assigning points as k-median cluster centers.  
It assumes a random arrival order, but has no other structural assumptions.  It offers a constant factor approximation using O(k log^2 k) centers.  This improves on a recent line of work in this model removing structural assumptions and the approximation factor.  

The main idea is using geometrically increasing prefixes of the stream to estimate the k-median solution and risk, and for each using this estimate to choose centers.  A key insight is that by increasing the size of centers maintained a bit, the risk can be approximated after excluding outliers -- which turns out to be the key step in the analysis.  

main_review: From a theoretical perspective, the algorithm is intuitive, and is well explained by the paper, with a lot of insight.  But the bulk of the analysis is left for the supplement.  
The algorithm however, appears far from practical.  
And as the most comparable work is an ALT 2021 paper that uses O(k log k) centers, but has approximation factor exponential in k (under all of the same model/data assumptions), I do not see the improvement as that substantial.  

Ultimately, I'd be ok if this paper is accepted for NeurIPS.  The work is high quality.  However, the improvement, I believe is small and theoretical, and may not have a high impact.  
limitations_and_societal_impact: The random order assumption is discussed clearly.  This was useful for the paper to do.  
This work is unlikely to have societal impact, and it was not discussed.
review_title: null

final_score: rating: 8: Top 50% of accepted NeurIPS papers, clear accept
review_content: summary: The paper studies $k$-median clustering in the random-order streaming model. In this particular setting, the input is randomly permuted and fed to the algorithm element by element. The input itself is a unknown finite set of points that together with a distance function forms a discrete metric space. The goal of the algorithm is to construct a clustering, by selecting a only small number of the input points as cluster centers, such that the cost of the clustering approximates the cost of an optimal $k$-median clustering of the whole space. Imposed restrictions are that the algorithm can only pick an input element as cluster center before it sees the next element and centers that have been chosen can not be substituted.

The paper contributes an algorithm that returns with high probability of success a clustering with $O(k \log^2(k/\delta))$ centers that approximates the cost of an optimal $k$-median clustering by a constant factor.
main_review: The problem of the paper is interesting and has a strong practical relevance. It has already been studied in the literature and the results of the paper yield a substantial progress. Furthermore, the idea of the algorithm is novel to me and the analysis seems sound and correct (I checked the proof sketches and large parts of the proofs in the appendix).

Some minor comments:

- please provide the constant of the approximation in the theorem statement (something like $728$) instead of a "universal constant $C$"
- large parts of the clustering community call the objective value the "clustering cost", I have seen that some of the related work also speak of "clustering risk", but you may consider switching to "cost" (I don't see any reason to call it risk here)
- the symbol $\equiv$ is used very rarely in mathematics (mainly in the context of logic) and can be substituted by $=$ in any case in your paper (standard notation improves comprehendability)
- line 131: write $\lvert T_{out} \rvert = O(k \log^2(k/\delta))$
limitations_and_societal_impact: The limitations are adequately addressed, as the authors do, I see no direct path to negative societal impact.
review_title: null

Meta-review: The authors present the first constant approximation factor on the optimal risk for k-median with no -substitution under a random arrival order model. The problem studied in the paper is an interesting problem and the authors present a simple and elegant algorithm that outperforms previous work. The only concern with the paper is that the problem may not be of interest for a wide audience. Nevertheless, after the discussion phase, all the reviewers agree that it should be accepted.
Decision: Accept (Poster)