A Constant Approximation Algorithm for Sequential Random-Order No-Substitution k-Median Clustering
Year: 2021

Abstract:
We study k-median clustering under the sequential no-substitution setting. In this setting, a data stream is sequentially observed, and some of the points are selected by the algorithm as cluster centers. However, a point can be selected as a center only immediately after it is observed, before observing the next point. In addition, a selected center cannot be substituted later. We give the first algorithm for this setting that obtains a constant approximation factor on the optimal cost under a random arrival order, an exponential improvement over previous work. This is also the first constant approximation guarantee that holds without any structural assumptions on the input data. Moreover, the number of selected centers is only quasi-linear in k. Our algorithm and analysis are based on a careful cost estimation that avoids outliers, a new concept of a linear bin division, and a multiscale approach to center selection.

heading: 1 Introduction
text: Clustering is a fundamental unsupervised learning task used for various applications, such as anomaly detection [Leung and Leckie, 2005], recommender systems [Shepitsen et al., 2008] and cancer diagnosis [Zheng et al., 2014]. In recent years, the problem of sequential clustering has been actively studied, motivated by applications in which data arrives sequentially, such as online recommender systems [Nasraoui et al., 2007] and online community detection [Aggarwal, 2003].
In this work, we study k-median clustering in the sequential no-substitution setting, a term first introduced in Hess and Sabato [2020]. In this setting, a stream of data points is sequentially observed, and some of these points are selected by the algorithm as cluster centers. However, a point can be selected as a center only immediately after it is observed, before observing the next point. In addition, a selected center cannot be substituted later. This setting is motivated by applications in which center selection is mapped to a real-world irreversible action. For instance, consider a stream of website users, where the goal is to instantaneously identify users that serve as social cluster centers and provide them with a promotional gift while they are still on the website. As another example, consider recruiting representative participants for a clinical trial out of a stream of incoming patients.
∗This work was done while the author was at the University of California San Diego.
35th Conference on Neural Information Processing Systems (NeurIPS 2021).
The goal in the no-substitution k-median setting is to obtain a near-optimal k-median cost value, while selecting a number of centers that is as close as possible to k. For an adversarially ordered stream, it has been shown [Moshkovitz, 2021] that an algorithm that selects a number of centers that is sublinear in the stream length cannot obtain a constant approximation guarantee, unless some structural assumptions are imposed on the input data.
In this work, we show that in contrast, when the stream order is random, a constant approximation guarantee can be obtained without imposing structural assumptions on the data. Previous works on the random-order setting provide either an algorithm with an almost-constant approximation assuming a bounded metric space [Hess and Sabato, 2020] or an algorithm with an approximation factor that is exponential in k [Moshkovitz, 2021]. Thus, our guarantees are stronger and more general than the previous guarantees. Moreover, the number of centers selected by our algorithm is only quasi-linear in k and does not depend on the stream length.
Main result. We propose a new algorithm, MUNSC (Multiscale No-Substitution Clustering), that obtains a constant approximation factor with probability 1− δ over the random order of the stream, while selecting only O(k log2(k/δ)) centers. MUNSC operates by executing several instances of a new center-selection procedure, called SelectProc, where each instance is applied to a stream prefix of a different scale. SelectProc decides which centers to select using a novel technique, in which a small stream prefix is used to estimate a truncated version of the optimal cost of the entire stream. This truncated version ignores outliers, and so can be estimated reliably. The value of the estimate is used to determine which centers to select from the rest of the stream. The multiscale use of SelectProc by MUNSC allows MUNSC to select only a quasi-linear number of centers.
As part of our analysis, we propose a new concept of a linear bin division, which allows a highprobability association of the costs of stream subsets, while selecting a number of centers that is independent of the stream length. This improves a previous construction of Meyerson et al. [2004].
The guarantees for MUNSC are provided in our main theorem, Theorem 4.1, stated in Section 4. Table 1 below compares our guarantees to previous works; See Section 2 for additional details. We note that our algorithm and guarantees are easily extendable to k-means clustering, as well as to any other clustering objective that satisfies the weak triangle inequality. MUNSC uses as a black box an offline k-median approximation algorithm with a constant approximation factor. Whenever the offline algorithm is efficient [e.g., Charikar et al., 2002, Li and Svensson, 2016], then so is MUNSC.
Limitations. The proposed algorithm is the first constant-approximation no-substitution clustering algorithm that makes no structural assumptions on the input data set. The only limitation is the assumption that the input order is random. This assumption is useful in cases where there is no adversary and any order is as likely, as in the example applications mentioned above. Moreover, a random order is a standard assumption in many streaming settings, satisfied also whenever the input stream is drawn i.i.d. from a distribution. In some cases, the randomness assumption might hold only approximately. In these cases, we expect a graceful degradation of the guarantees. We leave for future work a comprehensive treatment of input orders that are neither random nor adversarial. We expect the techniques of the current work to serve as a cornerstone in such a treatment.
Paper structure. We discuss related work in Section 2. The formal setting and notations are defined in Section 3. The algorithm and its guarantees are given in Section 4. In Section 5, we outline the proof of the main result. Some parts of the proof are deferred to appendices, which can be found in the supplementary material. We conclude with a discussion in Section 6.

heading: 2 Related Work
text: Several works have studied settings related to the no-substitution k-median clustering setting. Table 1 summarizes the upper bounds mentioned below. First, some works studied related settings under an adversarial arrival order. Liberty et al. [2016] studied online k-means clustering, in which centers are sequentially selected, and each observed point is allocated to one of the previously selected centers. The proposed algorithm can be applied to the no-substitution setting, yielding an approximation factor of O(log(n)), where n is the stream length. For this algorithm to select a sublinear number of centers, the aspect ratio of the input data must be bounded. Bhaskara and Rwanpathirana [2020] studied the same setting as Liberty et al. [2016], improving the approximation factor to a constant, under
the same assumptions. Bhattacharjee and Moshkovitz [2021] explicitly studied the no-substitution setting, and provided an approximation factor of O(k3), under a different assumption on the input data set.
The setting of a random arrival order has been studied in several recent works. Hess and Sabato [2020] proposed an algorithm that selects exactly k centers. They obtained a constant approximation factor, with an additional additive term that vanishes for large streams, under the assumption that the metric space has a bounded diameter. Their guarantee is with high probability. Moshkovitz [2021] obtained an approximation factor that is exponential in k, with a number of centers that is linear in k and logarithmic in the stream length n. Assuming a known stream length, the same work also obtained an approximation factor which is exponential in k while selecting O(k5) centers. Both guarantees hold only with a constant probability. As can be seen in Table 1, to date, the only known constant approximation algorithms for no-substitution k-median clustering impose structural assumptions on the input data.
A related sequential clustering setting is the streaming setting [e.g., Guha et al., 2000, Ailon et al., 2009, Chen, 2009, Ackermann et al., 2012, Braverman et al., 2016], in which the main restriction is the amount of memory available to the algorithm. This setting allows substituting selected centers, but algorithms in this setting can be used in the no-substitution setting, by collecting all the centers ever selected. However, we are not aware of any algorithm in this setting with a competitive bound on the total number of selected centers.

heading: 3 Setting and Notation
text: For an integer i, denote [i] := {1, . . . , i}. Let (X, ρ) be a finite metric space, where X is a set of size n and ρ : X × X → R+ is a metric. For a point x ∈ X and a set T ⊆ X , we denote ρ(x, T ) := miny∈T ρ(x, y). For an integer k ≥ 2, a k-clustering of X is a set of (at most) k points from X which represent cluster centers. Throughout this work, whenever an item is selected based on minimizing ρ, we assume that ties are broken based on a fixed arbitrary ordering. Given a set S ⊆ X , the k-median cost of T on S is cost(S, T ) := ∑ x∈S ρ(x, T ). The k-median clustering problem aims to select a k-clustering T of X with a minimal overall cost cost(X,T ). We denote by OPT an optimal solution to this problem: OPT ∈ argminT⊆X,|T |≤k cost(X,T ). In the sequential no-substitution k-median setting that we study, X is not known a priori. The points from X are presented to the algorithm sequentially, in a random order. We assume that the stream length, n, is provided as input to the algorithm; see Section 6 for a discussion on supporting an unknown stream length. The algorithm may select an observed point as a center only before observing the next point. Any selected point cannot later be removed or substituted. The goal of the algorithm is to select a small number of centers, such that with a high probability, the overall cost of the selected set on the entire X approximates the optimal k-median cost, cost(X,OPT). In other words, we seek an algorithm with a low competitive ratio, in the sense of competitive analysis [Borodin and El-Yaniv, 2005]. An offline k-median algorithm A is an algorithm that takes as input a finite set
Algorithm 1 The sequential clustering algorithm: MUNSC input δ ∈ (0, 1), k ∈ N, n ∈ N (stream length), A (an offline k-median algorithm),
sequential access to the input stream. 1: α1 ← δ/(4k); For i ∈ N, αi ← α1 · 2i−1. 2: I ← blog2(1/(6α1))c , δ′ ← δ/(I + 1). 4 I is set so that αI+1 ∈ (1/12, 1/6]. 3: Prepare I + 1 copies of SelectProc, indexed by i ∈ [I + 1], as follows:
In all copies, use inputs k, n,A, τ ← φαI+1 , and set the confidence parameter to δ′. In copy i ∈ [I + 1], set α← αi. In all but the last copy, set M ← 1 and γ ← 2αi. In the last copy (index I + 1), set M ← log(8k+/δ′), and γ ← 1− 2αI+1.
4: Read each point from the input stream and feed it to each of the copies of SelectProc. If any of the copies selected the point, then select it as a center.
of points S and the parameter k, and outputs a k-clustering of S, denoted A(S, k). For β ≥ 1, we say that A is a β-approximation offline k-median algorithm on (X, ρ), if for all input sets S ⊆ X , cost(S,A(S, k)) ≤ β · cost(S,OPTS), where OPTS is an optimal solution with centers from S. Formally, OPTS ∈ argminT⊆S,|T |≤k cost(S, T ).

heading: 4 The algorithm
text: In this section, we describe the proposed algorithm, MUNSC. MUNSC receives as input the value of k, the confidence level δ ∈ (0, 1) and the total stream length n. We further assume access to some black-box offline k-median algorithm A. The guarantees of MUNSC depend on the approximation factor guaranteed by A. MUNSC has only sequential access to the input stream. Our main result is the following theorem, showing that MUNSC obtains a constant approximation factor with a quasi-linear number of centers. A proof sketch of the theorem is given in Section 5. The full proof is provided in the supplementary.
Theorem 4.1. Let k, n ∈ N. Let δ ∈ (0, 1). Let (X, ρ) be a metric space of size n. Let Tout be the set of centers selected by MUNSC for the input parameters δ, k, n. Suppose that the input stream is a random permutation of X , and that the input black-box algorithm A is a β-approximation offline k-median algorithm. Then, with a probability at least 1− δ,
1. |Tout| = O ( k log2(k/δ) ) , and
2. cost(X,Tout) ≤ Cβ · cost(X,OPT), where C > 0 is a universal constant.
We first give, in Section 4.1, a short overview of the structure of MUNSC. A core element of the algorithm is the internal procedure SelectProc, which is used by MUNSC with several different sets of input parameters, creating a multiscale effect that we discuss below. We explain the details of SelectProc in Section 4.2. Then, in Section 4.3, we explain the design of MUNSC.

heading: 4.1 Algorithm structure overview
text: MUNSC is listed in Alg. 1. It works as follows: It initializes Θ(log(k/δ)) copies of the procedure SelectProc, each with a different set of input parameters, where we define φα := 150 log(32k/δ)/α for α > 0. It then iteratively reads the points from the input stream one by one, and feeds each point to each of the copies of SelectProc, so that each copy sequentially observes the entire input stream. Whenever any copy of SelectProc selects a point as a center, this point is selected by MUNSC as a center.
The internal procedure SelectProc uses a robust cost estimation approach to select a small number of centers. The procedure gets as input several technical parameters, in addition to the input parameters of MUNSC. We explain the procedure and the meaning of the technical parameters in Section 4.2. The values of the technical parameters set by MUNSC for each of the copies of SelectProc ensure that MUNSC select a small number of centers, while obtaining a constant approximation factor. This is done using a multiscale approach. We discuss this in detail in Section 4.3.
Algorithm 2 Internal procedure: SelectProc input δ ∈ (0, 1), k ∈ N, n ∈ N, A (an offline k-median algorithm),
sequential access to the input stream. Technical parameters: α ∈ (0, 16 ], γ ∈ (α, 1− 2α], M ∈ N, τ > 0.
1: 4 Phase 1 (Calculate an initial clustering Tα): 2: P1 ← the first αn points from the input stream. 3: Tα := {c1, . . . ck+} ← A(P1, k+) 4 Only calculation, no centers are actually selected here. 4: 4 Phase 2 (Estimate the cost of Tα on large optimal clusters): 5: P2 ← next αn points from the input stream. 6: ψ ← 13αcost2α(k+1)φα(P2, Tα) 4 ψ estimates the cost of Tα on large optimal clusters. 7: 4 Phase 3 (Select centers): 8: ∀i ∈ [k+], ni ← 0, Neari ← FALSE. 4 ni counts selected points associated with ci. Neari indicates if a point close to ci was selected. 9: for γn iterations do
10: Read the next point x from the input stream. 11: i← argmini∈[k+] ρ(x, ci). 4 Find the closet center to x in Tα. 12: if ρ(x, ci) > ψkτ or ¬Neari or ni ≤M then 13: Select x as a center. 4 This is the only line in which actual selections occur. 14: ni ← ni + 1. 15: If ρ(x, ci) ≤ ψkτ then Neari ← TRUE. 16: end if 17: end for
4.2 The internal procedure: SelectProc
In this section, we present the internal procedure, SelectProc. It has been observed in previous work [Liberty et al., 2016] that knowing in advance the optimal cost on the entire stream allows a successful center selection. Under a random arrival order, one may hope that obtaining a good estimate for the optimal cost would be straight-forward. However, since the metric space is unbounded, even a small number of outliers can bias the cost estimate considerably. We overcome this challenge by showing that it suffices to estimate a version of the optimal cost that ignores outliers, and that this version can be estimated reliably from a small prefix of the stream. Our analysis is based on a distinction between small and large optimal clusters, which we formally define in Section 5 below.
SelectProc, listed in Alg. 2, uses the following notation. For two sets S, T ⊆ X and an integer r, denote by farr(S, T ) ⊆ S the set of r points in S that are the furthest from T according to the metric ρ. If |S| < r, we define farr(S, T ) := S and call farr(S, T ) a trivial far set. Denote by costr(S, T ) := cost(S \ farr(S, T ), T ) the cost of T on S after discounting the r points that incur the most cost. Let k+ := k + 38 log(32k/δ). SelectProc receives the same input parameters as MUNSC. In addition, it requires several technical parameters, denoted α, γ,M and τ . We explain the meaning of these parameters in the proper context below.
SelectProc works in three phases. For i ∈ [3], we denote by Pi the set of points that are read in phase i. In each of the first two phases, an α fraction of the points in the stream is read. In the last phase, a γ fraction of the points in the stream is read. Note that depending on the values of α and γ, the procedure may ignore a suffix of the stream. The first two phases are used for calculations. Centers are selected only during the third phase.
In the first phase, a reference clustering Tα is calculated using the input offline algorithm A. Note that the centers in Tα cannot be selected as centers by SelectProc, since A calculates Tα only after observing all the points in the phase. In the second phase, an estimate ψ of the cost of Tα is calculated. In the third phase, SelectProc observes points from the stream one by one, deciding for each one whether it should be selected as a center. For each observed point, SelectProc first finds the center ci ∈ Tα which is closest to it. A point is then selected as a center if it satisfies one of three conditions: (1) its distance from ci is more than ψ/(kτ) (where τ is one of the input technical parameters); (2) ci does not yet have M associated points (where M is one of the technical parameters); or (3) no point close to ci has been selected so far, as maintained by the Boolean variable Neari. In Theorem 5.1 in Section 5, we provide a guarantee on the output of SelectProc, which upper bounds the number of
centers selected by SelectProc and the cost obtained by these centers, as a function of the technical parameters.
Challenges and solutions in SelectProc. We give here an informal explanation of the workings of SelectProc. The full analysis is provided in Section 5 and the supplementary. Consider the clusters induced by some fixed optimal k-median clustering onX . Call these clusters optimal clusters. Optimal clusters that are large (that is, include a sufficiently large fraction of X) are easy to identify from a small random subset of points. Therefore, approximate centers for these clusters will be identified in the first phase of SelectProc by the black box algorithm A, and will be included in Tα. Thus, the cost of Tα on the subset of points that belong to large optimal clusters will be close to optimal. Note that Tα is a clustering with k+ > k centers. This overcomes the fact that the data set might include outliers which are not proportionally represented in each phase. Searching for a k-clustering in P1 might thus lead to a clustering that is too biased towards such outliers. By increasing the size of the solution searched in the first phase to k+, this allows the solution to include the outliers as centers, while still choosing also centers that are close to the optimal centers of all large clusters. The selection conditions of the third phase further guarantee that at least M points are selected near each center ci ∈ Tα which represents a large cluster, thus making sure that a center which is very close to each such ci is selected. This allows bounding the obtained cost on points in large optimal clusters.
An additional challenge is to ensure that points in small optimal clusters are not too far from the set Tout of all selected centers. Since the metric space is unbounded, even a single such point can destroy the constant approximation factor. To overcome this, SelectProc selects a point near each center in Tα, as well as all the points that are far from Tα. The threshold ψ/(kτ), which defines a point as far, is set so that the number of points selected from large optimal clusters can be bounded. This bound crucially relies on the accuracy of ψ as an estimate for the cost of Tα on large clusters. The required accuracy is obtained by ignoring the points that are furthest from Tα when calculating the cost on P2 (see line 6). For small clusters, they hold a small number of points by definition, thus the number of such points selected as centers is also bounded.
4.3 The clustering algorithm: MUNSC
As described above, MUNSC runs several copies of SelectProc on the same input stream: each point is read from the input stream and then fed to each of the copies of SelectProc. Each of these copies selects some centers, and the set of all selected centers is the solution of MUNSC. The difference between the copies is in the value of the technical input parameters. First, the value of α (the stream fraction for the first and second phases) is progressively doubled, starting with α1 = δ/(4k) and ending with αI+1 = α1 · 2I , where I is set so that αI+1 ∈ (1/12, 1/6]. The value of τ (which controls the selection threshold) is set to φαI+1 in all copies, based on the largest value of α. In all but the last copy, γ (the stream fraction for the third phase) is set to 2αi, where i is the copy index. This means that the first and second phase of copy i are each of size αi, while the third phase is of size 2αi (the rest of the stream is ignored by copy i). Therefore, copy i observes a 4αi = 2αi+1 fraction of the stream. Thus, the first two phases of copy i+ 1 exactly overlap with the fraction of the stream observed by copy i. Figure 1 illustrates the overlap of phases in consecutive copies of SelectProc. In the last copy, indexed by I + 1, γ is set to 1− 2αI+1, thus this copy reads the entire stream. It can be seen that each point, except for the first 2nα1 points, participates in the third phase of exactly one copy of SelectProc. As our analysis below shows, this overlap between the phases guarantees that the set of centers selected by the copies of SelectProc obtains a small cost on all the small optimal clusters. The last copy is slightly different: in addition to setting the length of the third phase γ to include all the points of the stream, it also sets the technical parameter M to a number larger than 1. We show below that in this way, the selected set of centers obtains a small cost on large optimal clusters as well.
The use of several copies of SelectProc with different phase sizes ensures that MUNSC selects only a quasi-linear number of centers, by overcoming the following challenge: On the one hand, the first phase and the second phase must be small, otherwise we might miss a point that needs to be selected, since no points are selected in these two phases. On the other hand, small first and second phases lead to a poor quality of the reference clustering Tα. The multiscale approach makes sure that almost all points participate in some selection phase, while at the same time improving the quality of Tα as
α grows. Our analysis below shows that in this way, the number of centers selected by each copy remains similar, even though larger values of α lead to a larger selection phase.
Using MUNSC in a bounded memory setting. MUNSC can be used in a bounded memory setting, by using a 1-pass streaming clustering algorithm as the black-box algorithm A. For instance, the algorithm of Charikar et al. [2003] requires O(k · polylog(n)) memory. MUNSC can be implemented to require additional memory of only O(k log(k/δ)) on top of the requirements of the black-box algorithm. We now explain in full how this can be done. First, consider the memory requirements of SelectProc: In phase 1, the points can be fed to A one by one and do not need to be saved in memory. Only Tα, the k+ = O(k + log( 1δ )) output points of A, need to be saved in memory. In phase 2, calculating the truncated cost of Tα on P2 can be done by saving at most 2α·(k+1)φα = O(k log(kδ )) at any time, so as to identify the farthest points from Tα, which are the ones to disregard. In phase 3, the points are inspected one by one and do not need to be saved in memory (if one wishes to save the selected centers in memory, although this is not in principle required in our setting, then an additional O(k log(kδ )) factor is added). In total, SelectProc can be implemented using a memory size of O(k log(kδ )) + the memory requirments of A. MUNSC runs O(log( k δ )) parallel runs of SelectProc. Thus, it requires at most a memory size of O(log(kδ )(k log( k δ ) + the memory requirements of A)). In fact, this can be made even more memory-efficient, by using an algorithm A which is a streaming anytime algorithm. In this case, it is possible to use a single copy of A for all the parallel runs of SelectProc, since P1 in the i’th copy of SelectProc is the prefix of P1 in the i + 1’th copy (see Figure 1). That is, A is run on the entire stream and whenever a phase 1 of any copy ends, its current set of centers is retrieved for this copy. In this case, the memory size required by MUNSC is O(k log2(kδ )) + the memory requirements of A.

heading: 5 Analysis
text: In this section, we give an overview of the proof of Theorem 4.1. The supplementary provides the full proof. Denote the centers in the optimal solution OPT by {c∗i }i∈k, and the clusters induced by OPT (the optimal clusters) by {C∗i }i∈k. Formally, C∗i := {x ∈ X | i = argminj∈[k] ρ(c∗j , x)}. Optimal clusters with fewer than φα points are α-small optimal clusters, and the complement are α-large. Denote the indices of α-small and α-large clusters by Iαsmall := {i ∈ [k] | |C∗i | < φα} and Iαlarge := [k] \ Iαsmall, and the points in these clusters by Cαsmall := ⋃ i∈Iαsmall C∗i and C α large := ⋃ i∈Iαlarge
C∗i . To prove Theorem 4.1, we provide the following guarantee on the centers selected by SelectProc.
Theorem 5.1. Let k, n ∈ N. Let δ ∈ (0, 1). Let (X, ρ) be a metric space of size n. Let Tout be the set of centers selected by SelectProc for the input parameters δ, k, n, α ∈ (0, 1/6], γ ∈ (α, 1−2α], M ∈ N, τ > 0. Suppose that the input stream is a random permutation of X , and that A is a β-approximation offline k-median algorithm. Then, with a probability at least 1− δ/2,
1. |Tout| = O ( γ αk log(k/δ) + kτ + (k + log(k/δ))M ) ;
2. For any i ∈ [k], if c∗i ∈ P3, then
cost(C∗i , Tout) ≤ cost(C∗i , {c∗i }) + |C∗i | kτ (36β + 20)cost(X,OPT); (1)
3. If γ = 1− 2α, τ = φα and M = log(8k+/δ), then
cost(Cαlarge, Tout) ≤ cost(Cαlarge,OPT) + (468β + 260)cost(X,OPT). (2)
The proof of Theorem 4.1, provided in Appendix A, uses part 1 to bound the total number of centers, and parts 2 and 3 to bound the cost of small and large optimal clusters, respectively. The statement of Theorem 5.1 hints to the reason for the multiscale design of MUNSC: On the one hand, part 2 gives an approximation upper bound only if the cluster center appears in the third phase. For this to hold with a high probability, the third phase needs to be very large. On the other hand, for a quasi-linear bound on selected centers in part 1, the ratio between the third phase and the first phases (γ/α) needs to be small. The multiscale design overcomes this by keeping the ratio constant in each copy of SelectProc, while ensuring that the union of all third phases is almost the entire stream.
In the rest of the section, we give the proof of Theorem 5.1: In Section 5.1, we introduce the concept of linear bin divisions, and derive its properties. In Section 5.2, we give an overview of the proof of Theorem 5.1, using the results of Section 5.1. The full proof is provided in the supplementary.

heading: 5.1 Linear bin divisions
text: A main tool in the proof of Theorem 5.1 is partitioning sets of points from the input stream into subsets, such that each of the subsets is probably well represented in a relevant random subset of the stream. Meyerson et al. [2004] defined the concept of a bin division of X with respect to a clustering T , which is a partition of X into bins of equal size, where points are allocated to bins based on their distance from T . Here, we define the concept of a linear bin division, in which the bins linearly increase in size. This gradual increase allows keeping the size of the first bin independent of the stream length, while still proving that with a high probability, the overlap of each of the bins in the division with random subsets of the stream is close to expected. The fixed size of the first bin is crucial for deriving guarantees that are independent of the stream length. In addition, the ratio between adjacent bin sizes is kept bounded, which allows proving a bounded approximation factor.
Definition 5.2 (Linear bin division). Let W,T ⊆ X be finite sets, and z ∈ N. A z-linear bin division of W with respect to T is a partition B = (B(1), . . . ,B(L)) of W (for an integer L) such that:
1. If z ≤ |W |, then ∀i ∈ [L], |B(i)| ≥ z · (i+ 1)/2. Otherwise, the bin division is called trivial, and defined as B := B(1) := W .
2. |B(1)| ≤ 52z.
3. ∀i ∈ [L− 1], |B(i+ 1)|/|B(i)| ≤ 3/2.
4. ∀i ∈ [L− 1], and ∀x ∈ B(i), x′ ∈ B(i+ 1), it holds that ρ(x, T ) ≥ ρ(x′, T ).
A linear bin division exists for any size of W : For |W | ≤ z, the conditions trivially hold. For |W | ≥ z, the three first properties hold for the following allocation of bin sizes: Let L be the largest integer such thatB := ∑ i∈[L] z ·(i+1)/2 ≤ |W |. Set the size of B(i) to z ·(i+1)/2+(|W |−B)/L. Property 1 clearly holds. Property 2 holds since (|W | −B)/L ≤ (z(L+ 2)/2)/L ≤ 3z/2. Property 3 holds since (i+ 2 + a)/(i+ 1 + a) ≤ 3/2 for all i ≥ 1 and any non-negative a. To satisfy property 4, allocate the elements of W into the bins in descending order of their distance from T .
We say that a set is well-represented in another set if the size of its overlap with the set is similar to expected. This extends naturally to bin divisions. Formally, this is defined as follows.
Definition 5.3 (Well-represented). Let W be a finite set and A,B ⊆ W . We say that B is wellrepresented in A for W if |B ∩ A|/|B| ∈ [r/2, (3/2)r], where r := |A|/|W |. We say that a linear bin division B of W is well represented in A for W if each bin in B is well represented in A for W .
The following lemma shows that if A is selected uniformly at random from W , then any fixed set B is well-represented in A with a high probability. Moreover, the same holds for any z-linear bin division of W with a sufficiently large z. The proof of the lemma is provided in Appendix B.
Lemma 5.4. Let W be a finite set. Let B ⊆W be a set, and let B be a z-linear bin division of some subset of W with respect to some T , for some integer z. Let A ⊆W be a set of size r|W | selected uniformly at random from W . Then the following hold:
1. With a probability at least 1− 2e− r|B| 10 , B is well-represented in A for W .
2. If z ≥ 10 log(4/δ)/r, then with a probability 1− δ, B is well represented in A for W .
We now state and prove a main property of linear bin divisions, which will allow us to use sub-streams of the input stream to bound the cost of a clustering on X .
Lemma 5.5. Let W ⊆ X and let z ∈ N. Let B be a z-linear bin division of W with respect to some T . Let A ⊆ W and r ∈ (0, 1). If ∀i ∈ [L], |B(i) ∩ A|/|B(i)| ≤ r, then cost(A \ B(1), T ) ≤ 3 2rcost(W,T ).
Proof. Let L be the number of bins in B. We first prove the following inequality, which relates the cost of the intersection of a bin with A to the cost of the preceding bin.
∀i ∈ [L− 1], cost(A ∩ B(i+ 1), T ) ≤ 3 2 r · cost(B(i), T ). (3)
To prove Eq. (3), fix i ∈ [L − 1], and denote b := maxx∈B(i+1) ρ(x, T ). By the assumptions, we have |A ∩ B(i+ 1)| ≤ r|B(i+ 1)|. Hence, cost(A ∩ B(i+ 1), T ) ≤ r|B(i+ 1)| · b. By property 3 of linear bin divisions, |B(i + 1)| ≤ 32 |B(i)|. Therefore, cost(A ∩ B(i + 1), T ) ≤ 3 2r|B(i)| · b. In addition, by property 4 of linear bin divisions and the definition of b, ∀x ∈ B(i), b ≤ ρ(x, T ). Therefore, cost(B(i), T ) ≥ |B(i)| · b. Combining the two inequalities, we get Eq. (3). It follows that:
cost(A \ B(1), T ) = L∑ i=2 cost(A ∩ B(i), T ) ≤ 3 2 r L−1∑ i=1 cost(B(i), T ) ≤ 3 2 rcost(W,T ).
This proves the statement of the lemma.
To prove Theorem 5.1, we define an event, denoted E, which holds with a high probability. We prove each of the claims in the theorem under the assumption that this event holds. To define the event, we first provide some necessary notation. Consider a run of SelectProc with some fixed set of input parameters, and assume that the input stream is a random permutation of the points in X . Recall that Tα = {c1, . . . , ck+} is the clustering calculated in the first phase of SelectProc. Denote the clusters induced by Tα on X by C1, . . . , Ck+ , where Ci := {x ∈ X | i = argminj∈k+ ρ(cj , x)}. We define several sets and bin divisions, which will be used to define the required event. Let Ba be a (φα/15)linear bin division of X with respect to OPT. Define Fb := farkφα(X \ P1, Tα), and let Bb be a (φα/3)-linear bin division ofX\(P1∪Fb) with respect to Tα. Define Fc := far4(k+1)φα(X\P1, Tα), and let Bc be a (φα/3)-linear bin division of X \ (P1 ∪ Fc) with respect to Tα. Lastly, define Fd := far5(k+1)φα(X \ P1, Tα). Note that each of these objects may be trivial if the stream is small. The event E is defined as the following conjunction: (1) For each i ∈ Iαlarge, C∗i is well-represented in P1 and in P1 ∪ P2 for X . (2) Each of Fb and Fc is trivial or well-represented in P2 for X \ P1; Fd is trivial or well-represented in P3 for X \ P1. (3) Ba is trivial or well-represented in P1 for X; Each of Bb and Bc is trivial or well-represented in P2 for X \P1, and (4) For each i ∈ [k+], one of the first log2(8k+/δ) points observed from Ci in P3 is closer to ci than at least half of the points in Ci ∩ P3. The following lemma, proved in Appendix C, shows that E holds with a high probability.
Lemma 5.6. Consider a run of SelectProc with fixed input parameters. Assume that the input stream is a random permutation of the points of X . Then E holds with a probability at least 1− δ/2.

heading: 5.2 Theorem 5.1: proof overview
text: In this section, we give an overview of the proof of Theorem 5.1. The full proof is given in Appendix D. In the first phase of SelectProc, the clustering Tα is calculated using the offline algorithm A. We first bound the cost of Tα on points in α-large optimal clusters.
Lemma 5.7. If E holds, then cost(Cαlarge, Tα) ≤ (18β + 10)cost(X,OPT).
In the second phase of SelectProc, the goal is to estimate a truncated version of the cost of Tα on X . This truncated version ignores the cost on the outliers, which are the kφα furthest points from Tα in X . Setting the estimate to ψ = 13αcost2α(k+1)φα(P2, Tα) ignores the furthest 2α(k + 1)φα points in P2, which with a high probability include all the kφα outliers in X . The following lemma bounds ψ between two versions of a truncated cost of Tα.
Lemma 5.8. If E holds, then 19cost5(k+1)φα(X \ P1, Tα) ≤ ψ ≤ costkφα(X,Tα).
The proof of this lemma uses the linear bin divisions studied in Section 5.1. In particular, the upper bound uses Lemma 5.5, and the lower bound uses the specific construction of the bin sizes.
From the lemmas above, it can be seen that ψ is also upper bounded by the optimal cost, as follows. α-small optimal clusters are smaller than φα, thus their total size is less than kφα. It follows that
costkφα(X,Tα) ≤ cost(X \ Cαsmall, Tα) = cost(Cαlarge, Tα). (4)
Combining Lemma 5.7, Eq. (4) and Lemma 5.8, we get that ψ is upper bounded by the optimal cost.
In the third phase, the points selected as centers include (among others) all the points with a distance of more than ψ/(kτ) from Tα. This allows bounding the cost of Tout on points in some of the optimal clusters by a linear expression in ψ/(kτ). Combined with the upper bound on ψ, this allows proving part 2 of Theorem 5.1. Part 3 bounds the cost of Tout on large optimal clusters, for specific settings of the technical parameters of SelectProc. To prove this part, we show that under these parameter settings, the centers selected based on the reference clustering Tα include sufficiently many points around each large optimal cluster. We then show that one of these points is close to the optimal center.
Lastly, part 1 of Theorem 5.1 upper bounds the number of centers selected by SelectProc. The following lemma upper-bounds the number of points that are selected because they are far from Tα.
Lemma 5.9. Let N := |{x ∈ P3 | ρ(x, Tα) > ψ/(kτ)}|. Under E, N ≤ 8(k + 1)φα γ1−α + 9kτ .
The proof Lemma 5.9 uses the lower bound on ψ shown in Lemma 5.8, to conclude that there cannot be too many points that are more than ψ/(kτ) far from Tα, since this would make the truncated cost in the lower bound larger than ψ. We note that the resulting upper bound is independent of the stream size, due to the specific construction of the bin sizes in the linear bin division. Using this lemma, we can prove part 1 of SelectProc. The full proof of Theorem 5.1 is given in Appendix D.

heading: 6 Discussion
text: In this work, we provided MUNSC, the first constant-approximation algorithm for sequential nosubstitution k-median clustering that does not require structural assumptions on the input data. Moreover, the number of centers selected by MUNSC is only quasi-linear in k.
MUNSC can also be used when the stream length n is not known in advance, using a simple doubling trick. Moshkovitz [2021] showed that an unknown stream length with an approximation factor that does not depend on n require a logarithmic dependence on n in the number of selected centers. Indeed, a doubling trick for MUNSC would preserve the approximation factor, increasing the number of selected centers only by the unavoidable Θ(log(n)) factor.
Funding Transparency Statement
Sivan Sabato and Tom Hess were supported in part by the Israel Science Foundation (grant No. 555/15) and by the United-States-Israel Binational Science Foundation (BSF) (grant no. 2017641). Michal Moshkovitz has received funding from the European Research Council (ERC) under the European Union’s Horizon 2020 research and innovation program (grant agreement No. 882396), by the Israel Science Foundation (grant number 993/17), Tel Aviv University Center for AI and Data Science (TAD), and the Yandex Initiative for Machine Learning at Tel Aviv University.

Review summaries:
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.

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).

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.

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.