Robi Bhattacharjee<EMAIL_ADDRESS>
UCSD and Jacob John Imola<EMAIL_ADDRESS>
UCSD

# No-Substitution $k$-means Clustering with Optimal Center Complexity and Low
Memory

###### Abstract

We consider $k$-means clustering in the online no-substitution setting where
one must decide whether to take each data point $x_{t}$ as a center
immediately upon streaming it and cannot remove centers once taken. Our work
is focused on the _arbitrary-order_ assumption where there are no restrictions
on how the points $X$ are ordered or generated. Algorithms in this setting are
evaluated with respect to their approximation ratio compared to optimal
clustering cost, the number of centers they select, and their memory usage.

Recently, Bhattacharjee and Moshkovitz (2020) defined a parameter,
$Lower_{\alpha,k}(X)$ that governs the minimum number of centers any
$\alpha$-approximation clustering algorithm, allowed any amount of memory,
must take given input $X$. To complement their result, we give the first
algorithm that takes $\tilde{O}(Lower_{\alpha,k}(X))$ centers (hiding factors
of $k,\log n$) while simultaneously achieving a constant approximation and
using $\tilde{O}(k)$ memory in addition to the memory required to save the
centers. Our algorithm shows that it in the no-substitution setting, it is
possible to take an order-optimal number of centers while using little
additional memory.

###### keywords:

$k$-means; No-substitution clustering; approximation algorithms; online
algorithms.

##  1 Introduction

Clustering is an indispensable tool in unsupervised learning. The goal of
$k$-means clustering is to find centers that partition a dataset into $k$
clusters in a way that minimizes the $k$-means cost. It is well-known that
this problem is NP-hard [Aloise et al. (2009), Dasgupta (2008)], and there is
no known algorithm that will find the minimum cost clustering. However, many
approximation algorithms promising to find a clustering with cost at most
$\alpha$ times the optimal cost, are known, e.g. [Aggarwal (2007), Arthur and
Vassilvitskii (2006), Kanungo et al. (2004)]. The best of these algorithms can
find approximations for constant $\alpha$ regardless of the input dataset.

In this work, we consider the online, no-substitution setting, a term
introduced in [Hess and Sabato (2020)]. In this setting, data points are
streamed one by one, and for each point we decide whether or not to include it
as a center. The size of the data stream is unknown, and our decisions are
final in that a point is gone forever if we do not select it and can’t be
later removed if we do select it. The objective is a bi-criteria: we must (1)
select enough centers so that the resulting k-means cost of clustering the
entire dataset with the chosen centers is at most $\alpha$ times the optimal,
where $\alpha$ is any fixed constant, and (2) minimize the number of centers
chosen. This setting has applications where center selection is mapped to some
irreversible action, such as patient selection for a clinical trial.

In this general setting, [Bhattacharjee and Moshkovitz (2020)] show a lower
bound $\text{Lower}_{\alpha,k}(X)$ such that any $\alpha$-approximation
algorithm must select $\Omega(\text{Lower}_{\alpha,k}(X))$ when streamed on
$X$. While the same paper presents an $O(k^{3})$-approximation algorithm that
selects $\tilde{O}(k^{2}\text{Lower}_{k^{3},k}(X))$, this algorithm uses
$O(n)$ memory and runs an offline clustering algorithm each time a new point
is streamed. However, this result does show that it is possible to be tight
with the lower bound up to factors of $k,\log n$. In addition, the best true
online $\alpha$-approximation algorithm selects $\tilde{O}(k\log\gamma^{*})$
centers where $\gamma^{*}$ is the maximum ratio between the furthest two
points and closest two points in an optimal cluster (Bhaskara and
Rwanpathirana, 2020; Liberty et al., 2016). However, there exist datasets
where $\gamma^{*}$ is arbitrarily large, yet $\text{Lower}_{\alpha,k}(X)$ is
small for any $\alpha$. Thus, this algorithm does not achieve optimal center
complexity.

We provide a new online, no-substitution algorithm that achieves a $9$
approximation and selects $\tilde{O}(k\text{Lower}_{9,k}(X))$ centers, which
is order-optimal with the best known lower bound. Our algorithm uses
$O(\tilde{k})$ memory in addition to the centers it selects, and its running
time for each streamed point is no more than the number of centers it selects.
While the aforementioned algorithms were able to achieve either order-optimal
center complexity or low memory, our algorithm is the first to provide both
guarantees.

###  1.1 Summary of Our Results

We begin with our main result which governs the performance of OnlineCluster
(Algorithm 1). We use $\mathcal{L}$ to denote the cost function (formally
defined in Section 2), and we let $\mathcal{L}_{k}(X)$ denote the optimal
$k$-means cost of clustering $X$.We also let $S$ denote the set of cluster
centers outputted by OnlineCluster.

###### Theorem 1

For any input $X=\\{x_{1},x_{2},\dots,x_{n}\\}$, Algorithm 1 has the following
properties (with all probabilities taken over its own randomness).

  1. 1.

(Approximation Factor) With probability at least $0.95$, $\mathcal{L}(X,S)\leq
9\mathcal{L}_{k}(X)$.

  2. 2.

(Center Complexity) With probability at least $0.95$, $|S|\leq O(k\ln
k\log^{2}n\text{Lower}_{9,k}(X))$.

  3. 3.

(Auxiliary Memory) Algorithm 1 always uses at most $\tilde{O}(k)$ additional
memory.

OnlineCluster combines ideas from both Liberty et al. (2016) and Bhattacharjee
and Moshkovitz (2020) to achieve its guarantees. Now we describe the
processing methods that the existing algorithms use to decide if an incoming
point $x_{t}$ should be a center. Since we will extensively refer to these
processing methods later, we give them names.

In a type 1 processing (Liberty et al., 2016), $x_{t}$ is selected with
probability $\frac{D_{t}^{2}}{R_{t}}$, where $D_{t}$ is the distance between
$x_{t}$ and the nearest center, and $R_{t}$ is a “threshold” at time $t$. If
$R_{t}$ is appropriately chosen, the expected center complexity will be
$O(k)$, and an $O(1)$-approximation factor is possible. However, the
appropriate value of $R_{t}$ depends on the entire stream, and cannot be
computed. Instead, Liberty et al. use a doubling scheme that doubles $R_{t}$
when too many centers are being selected and show that this converges to the
appropriate value of $R_{t}$ while incurring a center complexity of
$\tilde{O}(k\log\gamma^{*})$.

In a type 2 processing (Bhattacharjee and Moshkovitz, 2020), $x_{t}$ is
selected with probability inversely proportional to the size of the offline
cluster containing $x_{t}$. These offline clusters are recomputed before
processing $x_{t}$, at each time $t$. This method is able to quickly adapt to
changing data scales: if data suddenly becomes extremely spread out, the
offline clustering will immediately detect this change, whereas the algorithm
of Liberty et al. may take many points as it updates to an appropriate value
of $R_{t}$.

The key new innovation of our algorithm is that OnlineCluster leverages a
modified version of the classic $k$-centers clustering algorithm both to
decides when to apply which type of processing, and to execute each type of
processing based on of Charikar et al. (2003). Charikar et al. (2003)’s
algorithm can easily maintain a low memory nearly optimal $k$-center
clustering. While this clustering is relatively poor for $k$-means, it is
nevertheless able to give a good indication on when the data is extremely
spread out, meaning that a type 2 processing is necessary, or when the data is
more mixed, meaning that a type 1 processing is necessary. Furthermore, our
modified version of this algorithm allows us to provide rough estimates on the
optimal value of $R_{t}$ (for type 1 processings) as well as the sizes of an
offline clustering (for type 2 processings).

We now include a comparison of Algorithm 1’s performance with the other main
algorithms in this setting. The key takeaway is that our algorithm is the
first algorithm to achieve success simultaneously across all 3 criteria. While
Bhaskara and Rwanpathirana (2020) achieves a good approximation ratio and
(additional) memory requirement, their center complexity has a dependence on
the aspect ratio which can be quite poor (as discussed in Bhattacharjee and
Moshkovitz (2020). By contrast, Bhattacharjee and Moshkovitz (2020) achieves
an order optimal center complexity (up to factors of $k^{2}\log^{2}n$) but has
a high approximation factor and a very high memory requirement.

| Approx. Ratio | Center Complexity | Additional Memory
---|---|---|---
Bhaskara and Rwanpathirana (2020) | $O(1)$ | $O(k\log n\log\gamma^{*})$ | $\tilde{O}(k)$
Bhattacharjee and Moshkovitz (2020) | $O(k^{3})$ | $O(k^{2}\log k\log n\cdot\text{Lower}_{k^{3},k}(X))$ | $O(n)$
Our result | $9$ | $O(k\log k\log^{2}n\cdot\text{Lower}_{9,k}(X))$ | $O(k)$
Table 1: Comparison of existing no-substitution algorithms with our algorithm.
The memory column contains memory in addition to the selected centers. Thus,
the total memory used by each algorithm is the sum of its memory and its
center complexity.

As a final note, our algorithm actually improves on the center complexity
given in Bhattacharjee and Moshkovitz (2020) by reducing the quadratic
dependence on $k$ to a linear dependence. This improvement can be non-trivial
if $k$ is set to be substantially larger than $\log n$.

###  1.2 Related Work

#### No-substitution setting.

Perhaps the most well-known example of the no-substitution setting for an
online algorithm is the secretary problem (Babaioff et al., 2009). The setting
has also been used in online submodular maximization (Buchbinder et al.,
2018). For the $k$-means problem, existing work makes assumptions about the
dataset $X$. First, Hess and Sabato (2020) and Moshkovitz (2019) assume $X$ is
generated by some random process rather than an arbitrary stream as we have
here. Also, Hess and Sabato (2020) and Bhaskara and Rwanpathirana (2020)
assume the aspect ratio of $X$ is bounded.

Lower bounds for online, no-substitution $k$-means are known as well.
Moshkovitz (2019) show that there exist datasets for which any algorithm must
take $\Omega(n)$ centers. Bhattacharjee and Moshkovitz (2020) improve this by
showing a dataset-specific lower bound of
$\Omega(\text{Lower}_{\alpha,k}(X))$.

#### Online facility location.

Online facility location is similar to no-substitution $k$-means and was first
studied in a classic work by Meyerson (2001). In online facility location,
facilities are created immediately when streamed and cannot be closed later.
There are two significant differences between this and our setting. First, the
cost incurred by the algorithm upon opening a set of facilities $F$ is
$|F|+\sum_{t=1}^{n}d(x_{t},F_{t})^{2}$, where $F_{t}$ is the set of facilities
at time $t$. Our cost function does not have a factor of $|F|$ in it which can
be significant: if distances are of order $n$, then a trivial solution with
$|F|=n$ becomes optimal. Furthermore, a point $x_{t}$ is charged using its
distance to the facilities that currently exist, $F_{t}$, whereas in the no-
substitution setting, $x_{t}$ is charged using its closest distance to all the
centers eventually chosen. Several works (Lang, 2018; Fotakis, 2011; Feldkord
and Meyer auf der Heide, 2018) consider variants of online facility location.

#### Streaming with limited memory.

Data streaming algorithms for a wide range of problems are known; for a full
discussion, see Aggarwal (2007) and Guha et al. (2003). Algorithms for
$k$-means in the streaming model are known such as those by Braverman et al.
(2011), Shindler et al. (2011), and Ailon et al. (2009). However, this setting
is much different from the online, no-substitution setting because they permit
previous points to be added to or removed from the set of centers.

##  2 Preliminaries

For a dataset $X\subset{\mathbb{R}}^{d}$, the $k$-means cost of $X$ with
respect to a set $S\subseteq{\mathbb{R}}^{d}$ is defined as

$\mathcal{L}(X,S)=\sum_{x\in X}\min_{c\in C}d(x,c)^{2},$

where $d(x,y)$ denotes Euclidean distance. For a natural number $k$, we denote
$\mathcal{L}_{k}(X)$ as the smallest achievable $k$-centers cost out of all
sets of size $k$. Formally, $\mathcal{L}_{k}(X)=\min{|S|=k}\mathcal{L}(X,S)$.

The following is a folklore lemma that allows us to bound $k$-means costs in
many situations.

###### Lemma 2

(Center Shifting Lemma) Let $X\subset{\mathbb{R}}^{d}$ be a finite set of
points, and let $\mu=\frac{1}{|X|}\sum_{x\in X}x$ be its average. Then for any
$s\in{\mathbb{R}}^{d}$,
$\mathcal{L}(X,\\{s\\})=\mathcal{L}(X,\\{\mu\\})+|S|d(s,\mu)^{2}.$

When $k=1$, this lemma establishes that the best $k$-means cost of $X$ is its
centroid. We will use this lemma extensively in later analyses.

Next, we review the online, no-substitution framework. In this setting, one
streams through a dataset $X=\\{x_{1},\ldots,x_{n}\\}$, one point at a time.
At each time step, an algorithm must choose whether to accept the new point,
which means that it will be used a center in the eventual output, or to reject
the new point, which means that this point can no longer be used as a center.
In this work, we assume that $n$ is not known ahead of time.

Algorithms are evaluated with a bi-criteria: in terms of their approximation
factor and in terms of their center complexity. More precisely, we say that an
online algorithm $A$ is an $\alpha$-approximation if for any input $X$ and any
ordering of that input, it returns a set $S\subseteq X$ such that
$\mathcal{L}(X,S)\leq\alpha\mathcal{L}_{k}(X)$ with probability at least
$0.95$, where the probability is taken over the randomness in $A$. Similarly,
we say that $A$ has center complexity $\beta$ on input $X$ if with probability
at least $0.95$ it returns a set of clusters $S$ such that $|S|\leq\beta$. As
before, the probability is taken over the randomness in $A$. Note that the
choice of $0.95$ is arbitrary: it is not difficult to apply standard
amplifying techniques to increase this probability to $1-\delta$ at the cost
of increasing the number of centers chosen by a factor of
$\log\frac{1}{\delta}$.

#### Additional Notation:

We let $X=\\{x_{1},\dots,x_{n}\\}$ be our input dataset, and let
$X_{t}=\\{x_{1},\dots x_{t}\\}$ denote the first $t$ elements of $X$. We also
let $C_{t}^{1},C_{t}^{2},\dots C_{t}^{k}$ denote the optimal $k$-means
clustering of $X_{t}$. Namely, if $S_{t}=\\{s_{t}^{1},\ldots,s_{t}^{k}\\}$
achieves $\mathcal{L}(X_{t},S_{t})=\mathcal{L}_{k}(X_{t})$, then $C_{t}^{i}$
are those points which are closest to $s_{t}^{i}$ out of all points in
$S_{t}$.

In general, we refer to the value of any parameter in Algorithm 1 at time $t$
by adding a subscript $t$. For example, $R_{t}$ denotes the value of $R$ after
the point $x_{t}$ has been processed.

#### Lower Bounds:

We now briefly review the parameter $\text{Lower}_{\alpha,k}(X)$ introduced in
Bhattacharjee and Moshkovitz (2020). We begin by defining the $l$-fold
diameter $\text{diam}_{l}(X)$ of a set $X\subseteq{\mathbb{R}}^{d}$ as the
smallest real number $D$ such that $X$ can be partitioned into $l$ disjoint
sets each of which have diameter at most $D$.

Using this notion, for any $\alpha>1$, we define $\text{Lower}_{\alpha,k}(X)$
as the longest sequence of points $y_{1},y_{2},\dots,y_{r}$ where $y_{i}$ are
distinct elements of $X$ that satisfy

$d(y_{i},\\{y_{1},\dots,y_{i-1}\\})>\sqrt{i\alpha}\text{diam}_{k-1}(\\{y_{1},\dots,y_{i-1}\\})$

for all $2\leq i\leq r$.

Bhattacharjee and Moshkovitz (2020) showed that this parameter gives a lower
bound on the center complexity of any $\alpha$-approximation algorithm run on
$X$ in worst case order. The intuition here is that the points
$y_{1},y_{2},\dots,y_{r}$ become increasingly spread out at an exponential
rate. As a consequence, any online algorithm must select all of them (when
presented in that order) in order to maintain an approximation factor of
$\alpha$. Formally, we have the following theorem:

###### Theorem 3

Bhattacharjee and Moshkovitz (2020) Let $X$ be an arbitrary set of points.
There exists an ordering of $X$ such that any online $\alpha$-approximation
algorithm has center complexity at least
$\frac{18}{19}\text{Lower}_{\alpha,k}(X)$ when run on that ordering.

Full details regarding this definition and lower bound can be found in
Appendix A. This theorem gives the best possible center complexity we can hope
to achieve in the no-substitution setting. While Bhattacharjee and Moshkovitz
(2020) provide an algorithm which achieves center complexity of
$\text{Lower}_{k^{3},k}(X)$ and a $k^{3}$-approximation, our algorithm is the
first to use just $\tilde{O}(k)$ additional memory.

##  3 Algorithm Description

Input: A stream of points $X=\\{x_{1},x_{2},\dots,x_{n}\\}$

Output: A set of cluster centers $S\subseteq X$

1 $S\leftarrow\\{x_{i}:1\leq i\leq k\\}$;

2 $R,F\leftarrow 0$;

3 $P,Q,Z\leftarrow\text{Online\\_k\\_centers}(\\{x_{1},\dots,x_{k}\\})$;

4 for  _$t=k+1,\dots,n$_ do

5 $P,Q,Z\leftarrow\text{Online\\_k\\_centers}(x_{t})$;

6

7 if  _$Q\leq 4(t+2)P$_ then

8 if  _$\frac{P^{2}}{24k\ln(k+10)} >R$_ then

9 $R\leftarrow\frac{P^{2}}{24k\ln(k+10)}$;

10

11 $F\leftarrow 0$;

12

13 with probability $\frac{d(x_{t},S)^{2}}{R}$, $S\leftarrow
S\cup\\{x_{t}\\}$;

14 $F\leftarrow F+1_{x_{t}\in S}$;

15

16 if  _$F >289k\ln(k+10)\log t$_ then

17 $R\leftarrow 2R$;

18

19 $F\leftarrow 0$;

20

21

22 else

23 $(z,m)\leftarrow\operatorname*{arg\,min}_{Z}d(z,x_{t})$;

24

25 with probability $\frac{12\ln(k+10)}{m}$, $S\leftarrow S\cup\\{x_{t}\\}$;

26

27

28 end for

29return $S$;

Algorithm 1 $\textrm{OnlineCluster}(X)$

We now describe OnlineCluster, our no-substitution $k$-means clustering
algorithm. The pseudocode for OnlineCluster appears in Algorithm 1. The main
idea behind OnlineCluster is to perform a type 1 or type 2 processing,
depending on a property of the online $k$-center clustering of the current set
of points. We now describe the variables and the three main components of
OnlineCluster in detail.

#### Algorithm Variables

Lines 1-4 initialize the main variables of Algorithm 1. The variable $S$ is
the cluster centers that our algorithm selects for the its $k$-means
clustering. Because we are in the no-substitution setting, points are never
removed from $S$. Line 1 initializes $S$ by setting it to be the first $k$
points. This forms a trivial clustering for the first $k$ points.

The variables $R,F$ are used for type 1 clusterings as a selection threshold
and a doubling counter, respectively. The variable $R$ inversely influences
the probability of selecting a new point in a type 1 processing. In Line 2,
$R$ is initialized to $0$, as there is no obvious way to set $R$ without
knowing anything about $X$, and its value is updated later before doing any
type 1 processings. The variable $F$ counts how many points were selected
since $R$ was last doubled. This is used to help $R$ converge to its “best”
value, as if many points are being taken, then $R$ is set too low.

The variables $P,Q,Z$ contain information about an online $k$-centers
clustering of $X_{t}$. They are computed using a classic online $k$-centers
clustering algorithm Charikar et al. (1997) which we denote by
Online_k_centers. The variable $Z$ is the set of $k$ centers returned by the
algorithm, the variable $P$ is the $k$-centers cost of these centers, and the
variable $Q$ is the minimum distance between two centers in $Z$. These
variables are used to decide which type of processing to perform and are used
in type 2 processings. Using results from Charikar et al. (1997), the
variables $P,Z$ satisfy:

###### Theorem 4

Charikar et al. (1997) Let $Z_{t}$ and $P_{t}$ denote the values of $Z$ and
$P$ returned by Online_k_centers when called at time $t$. Let
$OPT_{t}^{k,center}$ denote the optimal set of $k$ centers for $k$ centers
clustering at time $t$. Then the following hold:

  1. 1.

$|Z_{t}|\leq k$.

  2. 2.

$\max_{1\leq s\leq t}d(x_{s},Z_{t})\leq 4P_{t}$

  3. 3.

$\max_{1\leq s\leq t}d(x_{s},OPT_{t}^{k,center})\geq\frac{P_{t}}{2}$

  4. 4.

There exists $k+1$ distinct points in $X_{t}$ whose pairwise distances are all
at least $P_{t}$.

###### Corollary 5

For all times $t$, $\frac{P_{t}^{2}}{2}\leq\mathcal{L}_{k}(X_{t})\leq
16tP_{t}^{2}$.

######  Proof 3.1.

By part 4 of Theorem 4 and the pigeonhole principle, there exists two points
of distance least $P_{t}$ that are clustered together in any $k$-means
clustering. This gives a minimum cost of at least $\frac{P_{t}^{2}}{2}$ with
equality holding only when the cluster center is the midpoint of these points,
implying the first inequality.

By parts 1 and 2 of Theorem 4, we see that the points in $Z_{t}$ immediately
give a $k$ clustering where each point induces cost at most $16P_{t}^{2}$. The
second inequality follows.

#### Deciding Processing Type

The logic for deciding the type of processing to perform appears in lines 5-6
of Algorithm 1. Line 5 simply updates the $k$ centers, and line 6 does a type
1 processing if and only if $Q\leq 4(t+2)P$. This condition roughly means that
$X_{t}$ is not too spread out, and in this case, OnlineCluster processes the
next point with a type 1 processing. When $Q\geq 4(t+2)P$, then intuitively
the points easily spread out into $k$ well-separated clusters. In this case,
OnlineCluster processes the next point with a type 2 processing. Section 4
contains a full discussion of why type 1 and type 2 processings work in their
respective scenarios.

#### Type 1 Processings

Pseudocode for Type 1 processings appears in lines 7-14 of Algorithm 1. In a
type 1 processing, $x_{t}$ is selected with probability
$\frac{d(x_{t},S)^{2}}{R}$. The rest of the code in type 1 processings is used
to find a good value for $R$, since if $R$ is too small, then many centers are
taken, and if $R$ is too large, then points which could form good centers to
new clusters may be missed. We will later show that when $R$ reaches a sweet
spot of $R^{*}=O(\frac{\mathcal{L}_{k}(X_{t})}{12k\ln(k+10)})$, type 1
processings will not take too many centers and achieve a good approximation
ratio. This is a critical step of our analysis of type 1 processings.

In order to quickly converge to $R^{*}$, type 1 processings use two methods.
First, in lines 11-14, OnlineCluster updates the counter $F$ that grows
whenever a point is taken with a type 1 processing. When this counter is too
high, OnlineCluster doubles $R$ (as too many centers are being taken) and
resets the counter. Second, in lines 7-9, OnlineCluster increases $R$ to be at
least $\frac{P^{2}}{24k\ln(k+10)}$. By Corollary 5,
$\frac{P^{2}}{2}\leq\mathcal{L}_{k}(X_{t})$. Thus, $R$ is never set above
$\frac{\mathcal{L}_{k}(X_{t})}{12k\ln(k+10)}$, meaning this increase does not
set it above $R^{*}$. Lines 7-9 ensure that $R$ increases quickly when distant
points are encountered.

#### Type 2 Processings

Pseudocode for Type 2 processings appear in lines 16-17 of Algorithm 1. In a
type 2 processing, OnlineCluster computes the size $m$ of the $k$-center
cluster closest to $x$ and selects $x$ with probability
$\frac{12\ln(k+10)}{m}$. The key intuition behind type 2 processings is that
if an optimal $k$-means clustering $C^{1}_{t},\ldots,C^{k}_{t}$ is known in
advance, then selecting point $x_{t}$ with probability
$\tilde{O}(\frac{1}{|C^{*}_{t}|})$, where
$C^{*}_{t}=\min_{i=1}^{k}d(x_{t},C^{i}_{t})$, produces a set of centers with
size $\tilde{O}(k)$ and good approximation factor. We do not know an optimal
clustering in advance, but we are able to modify Online_k_centers to keep
estimates $m^{1},\ldots,m^{k}$ of the sizes of its $k$-_center_ clustering.
This modified algorithm appears in Appendix B. The modified algorithm
represents the set $Z$ as $Z=\\{(z^{1},m^{1}),\ldots,(z^{k},m^{k})\\}$, where
$m^{i}$ is the estimated size of the size of the cluster with center $z_{i}$.
The modification satisfies the following:

######  Proposition 6.

Let $Q$ denote the distance between the nearest two centers in $Z$. Suppose
that $Q>4(t+2)P$. Let $C^{1}_{t},C^{2}_{t},\dots,C^{k}_{t}$ denote the optimal
$k$-means clustering of $\\{x_{1},x_{2},\dots,x_{t}\\}$. Then $Z$ consists of
$k$ pairs, $(z^{1},m^{1}),(z^{2},m^{2}),\dots(z^{k},m^{k})$ such that the
following hold for all $1\leq i\leq k$: $z^{i}\in C^{i}$, $m^{i}=|C^{i}|$, and
$d(z^{i},x)\leq 4P_{t}$ for all $x\in C^{i}_{t}$.

######  Proof 3.2.

See Appendix B.

It may seem strange that this proposition applies to the optimal $k$-_means_
clustering of $X_{t}$ given that Online_k_centers is a $k$-center algorithm.
However, when $Q>4(t+2)P$, the optimal $k$-center clustering and $k$-means
clustering are the same because the points are so spread out. Using
Proposition 6, Line 16 finds $m=|C^{*}_{t}|$, and thus line 17 selects $x_{t}$
with probability $\tilde{O}(\frac{1}{|C^{*}_{t}|})$. This produces our desired
bounds on approximation ratio and center complexity.

##  4 Proof of Theorem 1

The auxiliary memory of Algorithm 1 is clearly $\tilde{O}(k)$: we only store
$k$ additional points $(Z)$ and maintain integer counts assigned to each
point. The variables $R,F$ constitute just $\tilde{O}(1)$ additional memory as
well. Thus, to prove Theorem 1, it suffices to understand the approximation
factor and the center complexity. We will consider both of these quantities
separately in Sections 4.2 and 4.3. Now, we prove an important result about
$R$ that will be used in both later sections.

###  4.1 Proving a Bound on $R$

Our later proofs about type 1 processings depend on $R$ neither being too
large or too small, and lying in a sweet spot value of
$O(\frac{\mathcal{L}_{k}(X_{t})}{12k\ln(k+10)})$. The following lemma helps us
establish that $R$ likely does not grow beyond this value.

######  Proposition 7.

Let $R_{t}$ denote the value of $R$ after the point $x_{t}$ is processed by
Algorithm 1. With probability at least $1-\frac{1}{120k}$ over the randomness
of the algorithm,$R_{t}\leq\frac{\mathcal{L}_{k}(X_{t})}{12k\ln(k+10)}$ for
all $k\leq t\leq n$.

Observe that this proposition holds simultaneously over all times $t$. That
is, there is a large chance ($1-\frac{1}{120k}$) that all values of $R$ during
the course of the algorithm will be appropriately bounded. Also, note that for
our purposes, we optimize $R$ to be
$\frac{\mathcal{L}_{k}(X_{t})}{12k\ln(k+10)}$. The additional factor of $12\ln
k$ is helpful for bounding constants throughout both the approximation factor
and the center complexity. The proof of this proposition follows the ideas
from Liberty et al. (2016) in a relatively straightforward manner. The main
difference is that some extra care is needed to bound all values of $R_{t}$
rather than the last one. A full proof can be found in Appendix C.

###  4.2 Bounding the Approximation Factor

We begin by proving that Algorithm 1 is an $O(1)$-approximation algorithm.
Broadly speaking, our strategy will be to show that we are highly likely to
select points that are “close” to the optimal cluster centers of $X$. We refer
to such points as “good.”

#### Good points:

For any finite set $C\subset{\mathbb{R}}^{d}$, we let $g\in C$ be a good point
if $\mathcal{L}(C,g)\leq 3\mathcal{L}(C)$. By the Center Shifting Lemma, this
is equivalent to $d(g,\mu)^{2}\leq\frac{2\mathcal{L}(C)}{\mu}$, where $\mu$
denotes the optimal $k$-means center of $C$. Because
$\mathcal{L}(S)=\sum_{s\in S}d(s,\mu)^{2}$, Markov’s inequality implies that
at least half the points in $C$ are good (see Bhattacharjee and Moshkovitz
(2020) for a complete proof).

Recall that Algorithm 1 deals with points through either type 1 or type 2
processings. Crucially, the decision of whether or not to apply a type 1
processing or a type 2 processing is uniquely determined by the values of
$P,Q,Z$ and the point in question $x_{t}$. Since $P,Q,Z$ are all deterministic
functions of $X$ (i.e. Charikar et al. (1997)’s algorithm is not randomized),
it follows that the type of selection made is deterministic as well. We will
make use of this fact by handling the cases of type 1 and type 2 processings
separately. We now give a lemma that governs the behavior of type 1
processings.

######  Lemma 8.

Let $C\subseteq X$ be a subset, such that at least half of the good points in
$C$ are type 1 processed. Then with probability at least $1-\frac{1}{60k}$
over the randomness of Algorithm 1,

$\mathcal{L}(C,S)\leq 5\mathcal{L}(C)+\frac{2\mathcal{L}_{k}(X)}{k}.$

######  Proof 4.1.

For any time $t$, define $\Gamma_{t}=d(x_{t},S_{t-1})^{2}$ to be the squared
distance used for type 1 selecting $x_{t}$. $\Gamma_{t}$ is a random variable
because the set $S_{t-1}$ is stochastically determined by the randomness in
Algorithm 1. Let $x_{l_{1}},x_{l_{2}},\dots,x_{l_{p}}$ denote the good points
in $C$ that are type 1 processed. Since at least half of all points in $C$ are
good, it follows that $p\geq\frac{|C|}{4}$. Then we let $A$ denote the event
that one of the following two things occur:

  1. 1.

Some point among $x_{l_{1}},\dots,x_{l_{p}}$ is selected in $S$.

  2. 2.

$\min(\Gamma_{l_{1}},\Gamma_{l_{2}},\dots,\Gamma_{l_{p}})\leq\frac{\mathcal{L}_{k}(X)}{k|C|}$.

$A$ can be thought of as a desirable event. The first condition would imply a
good point is chosen, meaning that the cost of clustering $C$ is small, and
the second condition would imply that some point we have already selected is
close to a good point. We will show that if $A$ is likely to occur, and that
if so our cost of clustering $C$ is small.

#### Claim 1:

$\Pr[A]\geq 1-\frac{1}{60k}$.

For any event $B$, observe that
$\Pr[\overline{A}]\leq\Pr[\overline{B}]+\Pr[\overline{A}\cap B]$ where
$\overline{A},\overline{B}$ denote the complements of $A,B$. Let $B$ denote
the event that $R_{n}\leq\frac{\mathcal{L}_{k}(X_{n})}{12k\ln(k+10)}$. By
Proposition 7, $\Pr[\overline{B}]\leq\frac{1}{30k}$. Thus, it suffices to
bound $\Pr[\overline{A}\cap B]$.

For $1\leq j\leq p$, let $E_{j}$ denote the event that
$\Gamma_{l_{j}}\leq\frac{\mathcal{L}_{k}(X_{n})}{k|C^{i}|},R_{l_{j}}\leq\frac{\mathcal{L}_{k}(X_{n})}{12k\ln(k+10)}$,
and let $F_{j}$ denote the event that $x_{l_{j}}$ is not selected as a center.
Then $\overline{A}\cap B$ occurs only if $E_{1},F_{1},\dots,E_{p},F_{p}$ all
occur. Thus, it suffices to bound the probability of all these events
simultaneously occurring. To that end, for any $j\geq 1$,

$\Pr[F_{j}|E_{1},F_{1},\dots,E_{j-1},F_{j-1}]\leq\max(0,1-\frac{\mathcal{L}_{k}(X_{n})/(k|C^{i}|)}{\mathcal{L}_{k}(X_{n})/(12k\ln(k+10)})\leq\exp(-\frac{12\ln(k+10)}{|C^{i}|}).$

This is because the distribution of the event $F_{j}$ is entirely determined
by the values of $\Gamma_{l_{j}}$ and $R_{l_{j}}$, and thus
$\frac{\Gamma_{l_{j}}}{R_{l_{j}}}$ is bounded if we condition on $E_{j}$.
Multiplying this equation over all $j$, we find that $\Pr[\overline{A}\cap
B]\leq\exp(\frac{-12p\ln(k+10)}{|C|})\leq\exp(-3\ln(k+10))=\frac{1}{(k+10)^{3}}$
since $p\geq\frac{|C|}{4}$. Substituting this, we find that

$\Pr[\overline{A}\cup\overline{B}]=\Pr[\overline{A}\cap
B]+\Pr[\overline{B}]\leq\frac{1}{(k+10)^{3}}+\frac{1}{120k}\leq\frac{1}{60k}.$

#### Claim 2:

If $A$ occurs, then $\mathcal{L}(C,S)\leq
5\mathcal{L}(C)+\frac{2\mathcal{L}_{k}(X)}{k}$.

Let $c$ denote the optimal cluster center of $C$. Then by the definition of a
good point, we see that
$d(c,x_{l_{j}})\leq\sqrt{\frac{2\mathcal{L}(C)}{|C|}}$. Since $A$ occurs,
either one of these good points is selected in $S$, or something close to one
of them is. It follows that there is some $x\in S$ such that $d(c,x)\leq
d(c,x_{l_{j}})+\sqrt{\frac{\mathcal{L}_{k}(X)}{k|C|}}$. Substituting this and
applying the Center Shifting Lemma, we have

$\begin{split}\mathcal{L}(C,S)&=\mathcal{L}(C,x)\\\
&=\mathcal{L}(C)+|C|d(c,x)^{2}\\\
&\leq\mathcal{L}(C)+|C|\left(\sqrt{\frac{2\mathcal{L}(C)}{|C|}}+\sqrt{\frac{\mathcal{L}_{k}(X)}{k|C|}}\right)^{2}\\\
&\leq 5\mathcal{L}(C)+\frac{2\mathcal{L}_{k}(X)}{k}.\end{split}$

Next, we handle type 2 processings. We begin with a useful lemma.

######  Lemma 9.

Suppose $x_{t}$ and $x_{t^{\prime}}$ are type 2 processed where
$t<t^{\prime}$. Let $C_{t}^{1},\dots,C_{t}^{k}$ and
$C_{t^{\prime}}^{1},\dots,C_{t^{\prime}}^{k}$ denote the optimal $k$-means
clusterings of $X_{t}$ and $X_{t^{\prime}}$ respectively. Then for all $1\leq
i\leq k$, there exists $1\leq j\leq k$ such that $C_{t}^{i}\subseteq
C_{t^{\prime}}^{j}$.

######  Proof 4.2.

Assume towards a contradiction that there exists $i$ such that
$C_{t}^{i}\not\subseteq C_{t^{\prime}}^{j}$ for all $1\leq j\leq k$. Then
there exists $x,y\in C_{t}^{i}$ with $x\in C_{t^{\prime}}^{a}$ and $y\in
C_{t^{\prime}}^{b}$ for $a\neq b$. Let $z_{t^{\prime}}^{1},\dots
z_{t^{\prime}}^{k}$ and $z_{t}^{1},\dots z_{t}^{k}$ denote the points of $Z$
at times $t^{\prime}$ and $t$ respectively. By repeatedly using Proposition 6
and the triangle inequality, we have

$\begin{split}d(z_{t^{\prime}}^{a},z_{t^{\prime}}^{b})&\leq
d(z_{t^{\prime}}^{a},x)+d(z_{n^{\prime}}^{b},y)+d(x,y)\\\ &\leq
4P_{t^{\prime}}+4P_{t^{\prime}}+d(x_{t},z_{t}^{i})+d(y,z_{t}^{i})\\\ &\leq
8P_{t^{\prime}}+4P_{t}+4P_{t}\\\ &\leq 16P_{t^{\prime}}.\end{split}$

The last inequality holds since $P$ is monotonically non-decreasing. Because
$x_{t^{\prime}}$ was type 2 processed,
$Q_{t^{\prime}}>4(t+2)P_{t^{\prime}}>16P_{t^{\prime}}$. This contradicts the
definition of $Q_{t^{\prime}}$ which implies our claim.

Let $n^{\prime}\leq n$ denote the last time during which $x_{n^{\prime}}$ is
type 2 processed, and let
$C_{n^{\prime}}^{1},C_{n^{\prime}}^{2},\dots,C_{n^{\prime}}^{k}$ denote the
optimal $k$ means clustering of $X_{n^{\prime}}$.

######  Lemma 10.

Fix $1\leq i\leq k$. Suppose that at least half of the points in
$C_{n^{\prime}}^{i}$ are type 2 processed. Then with probability at least
$1-\frac{1}{60k}$ over the randomness of Algorithm 1,
$\mathcal{L}(C_{n^{\prime}}^{i},S)\leq 3\mathcal{L}(C_{n^{\prime}}^{i})$.

######  Proof 4.3.

Let $x_{l_{1}},x_{l_{2}},\dots,x_{l_{p}}$ denote all the good points in
$C_{n^{\prime}}^{i}$ that are type 2 processed. By the definition of a good
point, if any of these points are chosen, then
$\mathcal{L}(C_{n^{\prime}}^{i},S)\leq 3\mathcal{L}(C_{n^{\prime}}^{i})$.
Thus, it suffices to bound the probability that at least one of these points
is chosen.

For any $1\leq j\leq p$, let $C_{l_{j}}^{1},\dots C_{l_{j}}^{k}$ denote the
optimal $k$-means clustering of $X_{l_{j}}$. Since $x_{l_{j}}$ is type 2
processed, it is selected with probability
$\frac{12\ln(k+10)}{|C_{l_{j}}^{a}|}$ where $x_{l_{j}}\in C_{l_{j}}^{a}$.
Since $x_{l_{j}}\in C_{n^{\prime}}^{i}$, by Lemma 9,$C_{l_{j}}^{a}\subseteq
C_{n^{\prime}}^{i}$. Thus, $x_{l_{j}}$ is selected with probability at least
$\frac{12\ln(k+10)}{|C_{n^{\prime}}^{i}|}$. As a result, the probability that
no $x_{l_{j}}$ is selected is at most

$\left(1-\frac{12\ln(k+10)}{|C_{n^{\prime}}^{i}|}\right)^{p}\leq\exp\left(-\frac{12p\ln(k+10)}{|C_{n^{\prime}}^{i}|}\right)\leq\exp\left(-3\ln(k+10)\right)\leq\frac{1}{60k}.$

We are now prepared to prove that Algorithm 1 is an $O(1)$-approximation
algorithm.

######  Proposition 11.

With probability at least $\frac{19}{20}$ over the randomness of Algorithm 1,
$\mathcal{L}(X,S)\leq 9\mathcal{L}(S)$.

######  Proof 4.4.

Let $D^{1},D^{2},\dots D^{k}$ denote the optimal $k$-means clustering of
$\\{x_{n^{\prime}+1},x_{n^{\prime}+2},\dots x_{n}\\}$, where $x_{n^{\prime}}$
is the last point to be type 2 processed. Then by definition, all points in
$D^{i}$ are type 1 processed for $1\leq i\leq k$. By Lemma 8, with probability
at least $1-\frac{1}{60k}$, $\mathcal{L}(D^{i},S)\leq
5\mathcal{L}(D^{i})+\frac{\mathcal{L}_{k}(X)}{k}$. Applying a union bound, we
see that with probability at least $\frac{59}{60}$, this holds simultaneously
over $1\leq i\leq k$.

Next, for each $C_{n^{\prime}}^{i}$, either at least half the good points in
it are type 1 processed, or half the good points in it are type 2 processed.
By applying Lemmas 8 and 10, we see that in either case,
$\mathcal{L}(C_{n^{\prime}}^{i},S)\leq
5\mathcal{L}(C_{n^{\prime}}^{i},S)+\frac{\mathcal{L}_{k}(X)}{k}$ with
probability at least $1-\frac{1}{60k}$. Applying a union bound, we see that
with probability at least $\frac{1}{60}$, this holds simultaneously over
$1\leq i\leq k$.

Applying a union bound over both the $D^{i}$s and the $C_{n^{\prime}}^{i}$, we
see that with probability at least $\frac{29}{30}\geq\frac{19}{20}$,

$\begin{split}\mathcal{L}(X,S)&=\sum_{1}^{k}\mathcal{L}(D^{i},S)+\sum_{1}^{k}\mathcal{L}(C_{n^{\prime}}^{i},S)\\\
&\leq\sum_{1}^{k}5\mathcal{L}(D^{i})+\frac{2\mathcal{L}_{k}(X)}{k}+\sum_{1}^{k}5\mathcal{L}(C_{n^{\prime}}^{i})+\frac{2\mathcal{L}_{k}(X)}{k}\\\
&=5\mathcal{L}_{k}(\\{x_{n^{\prime}+1},\dots
x_{n}\\})+5\mathcal{L}_{k}(\\{x_{1},\dots,x_{n^{\prime}}\\})+4\mathcal{L}_{k}(X)\\\
&\leq 9\mathcal{L}_{k}(X).\end{split}$

###  4.3 Bounding the Center Complexity

We bound the number of points selected through type 1 and type 2 processings
separately.

#### Type 1 processings:

Let $1\leq t_{1},t_{2},\dots t_{r}\leq n$ be defined so that $t_{1}$ is the
first time in which we perform a type 1 processing, and for $i\geq 1$,
$t_{i+1}$ is the first time after $t_{i}$ for which we perform a type 1
processing and $P_{t_{i+1}}>8\sqrt{t_{i+1}9}(t_{i+1}+5)P_{t_{i}}$. If no such
$t_{i}$ exists, we terminate the sequence.

These times are instances in which the parameter $P$ increases by a
significant amount, and consequently between any $t_{i-1},t_{i}$, the
parameter $P$ stays relatively bounded. This implies that the desired value of
$R$ during this time period stays relatively bounded implying that relatively
few centers are chosen through type 1 processings in this interval.

######  Lemma 12.

For $1\leq i\leq r$, let $T_{i}=\\{x_{t_{i}},\dots x_{t_{i+1}-1}\\}$ where
$t_{r+1}-1$ is defined as $n$. Then with probability at least
$1-\frac{1}{120k}$, there are at most $O(k\ln k\log^{2}n)$ type 1 selections
made in $T_{i}$ for all $1\leq i\leq r$.

######  Proof 4.5.

By Proposition 7, with probability at least $1-\frac{1}{120k}$,
$R_{t}\leq\frac{\mathcal{L}_{k}(X_{t})}{12k\ln(k+10)}$ for all $k\leq t\leq
n$. It suffices to show that if this occurs, the number of type 1 selections
made in each $T_{i}$ is bounded as desired.

Fix any $i$ and let $t=t_{i}$ and $t^{\prime}=t_{i+1}-1$. Then by the
definition of $\\{t_{j}\\}$, $P_{t^{\prime}}\leq
8\sqrt{9t^{\prime}}(t^{\prime}+5)P_{t}$. By step 8 in Algorithm 1,
$R_{t}\geq\frac{P_{t}^{2}}{24k\ln(k+10)}$. Applying Corollary 5, we have

$R_{t^{\prime}}\leq\frac{\mathcal{L}_{k}(X_{t^{\prime}})}{12k\ln(k+10)}\leq\frac{16t^{\prime}P_{t^{\prime}}^{2}}{12k\ln(k+10)}\leq\frac{32\cdot
64(9t^{\prime})(t^{\prime}+5)^{2}P_{t}^{2}}{24k\ln(k+10)}\leq
2048(t^{\prime}9)(t^{\prime}+5)^{2}R_{t}.$

This implies that $R$ can be doubled at most $\log
2-48(9t^{\prime})(t^{\prime}+5)^{2}$ times in $T_{i}$. Since every
$289k\ln(k+10)\log n$ type 1 selections corresponds to a doubling, by
multiplying these we see that at most $O(k\ln k\log^{2}n)$ type 1 selections
can be made in $T_{i}$.

Lemma 12 bounds the number of type 1 selections made between any 2 times
$t_{i}$ and $t_{i+1}$. To bound the total, we now bound the number of
intervals, $r$, in terms of the parameter $\text{Lower}_{9,k}(X)$. Recall that
this parameter, defined in Bhattacharjee and Moshkovitz (2020), gives a lower
bound on the number of centers any $9$-approximation algorithm must take on
input $X$. Full details about it can be found in Appendix A.

######  Lemma 13.

$r\leq\text{Lower}_{9,k}(X)$.

######  Proof 4.6.

By the definition of $\text{Lower}_{9,k}(X)$, it suffices to show that for all
$i$, there exists $b\in\\{t_{i}+1,t_{i}+2,\dots,t_{i+1}\\}$ such that for all
$x_{a}\in X_{t_{i}}$,
$d(x_{a},x_{b})>\sqrt{9t^{\prime}}\text{diam}_{k-1}(X_{t_{i}}),$ as this will
allow us to construct a $(9,k)$-sequence with precisely $r$ elements (simply
keep selecting the appropriate point $x_{b}$ from each interval
$[t_{i}+1,t_{i+1}]$).

Fix $i$ and for convenience let $t$ and $t^{\prime}$ denote $t_{i}$ and
$t_{i+1}$. Assume towards a contradiction that no such $x_{b}$ exists, that
is, for all $x_{b}\in X_{t^{\prime}}$, there exists $x_{a}\in X_{t}$ such that
$d(x_{a},x_{b})\leq\sqrt{9t^{\prime}}\text{diam}_{k-1}(X_{t})$. Let
$z_{t}^{1},z_{t}^{2},\dots,z_{t}^{k}$ denote the $k$ centers that are in
$Z_{t}$. While it is possible that $Z_{t}$ contains fewer than $k$ centers,
this case is easy to handle.

By Theorem 4, for all $x_{a}\in X_{t}$, there exists $j$ such that
$d(x_{a},z_{t}^{j})\leq 4P_{t}$. Since there exist $z_{t}^{j}$ and
$z_{t}^{j^{\prime}}$ such that $d(z_{t}^{j},z_{t}^{j^{\prime}})\leq Q_{t}$, it
follows that $X_{t}$ can be partitioned into $k-1$ regions each of which have
diameter at most $Q_{t}+8P_{t}$.

It follows that for all $x_{b}\in X_{t^{\prime}}$, there exists $1\leq j\leq
k$ such that

$d(x_{b},z_{t}^{j})\leq
d(x_{b},x_{a})+d(x_{a},z_{t}^{j})\leq\sqrt{9t^{\prime}}(Q_{t}+8P_{t})+4P_{t}\leq
4\sqrt{9t^{\prime}}(t+5)P_{t},$

with the last inequality holding since $t^{\prime}$ is a type 1 selection
meaning $Q_{t}\leq 4(t+2)P$. This implies that the $k$-centers cost of
clustering $X_{t^{\prime}}$ is at most $4\sqrt{9t^{\prime}}(t+5)P_{t}$ which
implies $\frac{P_{t^{\prime}}}{2}\leq 4\sqrt{9t^{\prime}}(t+5)P_{t}$ (Theorem
4). However, this is a contradiction, because $t$ and $t^{\prime}$ are
consecutive elements in the sequence $\\{t_{i}\\}$ which means
$P_{t^{\prime}}>8\sqrt{9t^{\prime}}(t+5)P_{t}$.

#### Type 2 Processings:

Let $k\leq s_{1}<s_{2}<\dots<s_{q}\leq n$ be defined as follows. Let $s_{1}$
be first time that we do a type 2 processing. For $i\geq 1$, let $s_{i+1}$
denote the first time for which $x_{s_{i+1}}$ is type 2 processed and there
exists $1\leq a,b,c\leq k$ with $a\neq b$ such that
$C_{s_{i}}^{a},C_{s_{i}}^{b}\subseteq C_{s_{i+1}}^{c}$. If no such time
exists, we terminate the sequence.

######  Lemma 14.

Fix any $1\leq i\leq q$. Over the randomness of Algorithm 1, the expected
number of points that are selected by type 2 processings from
$\\{x_{s_{i}},\dots x_{s_{i+1}-1}\\}$ is at most $24\ln(k+10)\ln n$.

######  Proof 4.7.

Let $T\subseteq\\{x_{s_{i}},\dots x_{s_{i+1}-1}\\}$ be the set of points that
are type 2 processed. For any $x_{t}\in T$, we claim that the optimal
$k$-means clusters of $X_{t}$ can be ordered such that $C_{s_{i}}^{j}\subseteq
C_{t}^{j}$ for all $1\leq j\leq k$.

Observe that by Lemma 9, every set $C_{s_{i}}^{j}$ must be a subset of some
$C_{t}^{j^{\prime}}$. However, by the definition of the sequence $s$, it is
not possible for $C_{s_{i}}^{a}$ and $C_{s_{i}}^{b}$ to both be subsets of the
same cluster $C_{t}^{c}$ for otherwise we would have $t=s_{i}$. Thus, each
cluster $C_{s_{i}}^{j}$ is contained in a unique cluster $C_{t}^{j^{\prime}}$.
By relabeling clusters as necessary, we can force $j=j^{\prime}$ giving the
claim.

Applying this argument twice, we can also see that for
$x_{t},x_{t^{\prime}}\in T$ with $t<t^{\prime}$, $C_{t}^{j}\subseteq
C_{t^{\prime}}^{j}$ for $1\leq j\leq k$. Letting $t_{max}$ denote the last
time in $T$, we see that for all $x_{t}\in T$ and all $1\leq j\leq k$
$C_{t}^{j}=C_{t_{max}}^{j}\cap X_{t}$.

Finally, each point $x_{t}\in T$ is selected with probability
$\frac{12\ln(k+10)}{|C_{t}^{j}|}$ where $x_{t}\in C_{t}^{j}$. Thus, the
expected number of points selected from $T$ is $\sum_{x_{t}\in
T}\frac{12\ln(k+10)}{|C_{t}^{j}|:x_{t}\in C_{t}^{j}}$. Let $T^{j}=T\cap
C_{t_{max}}^{j}$, then

$\begin{split}\sum_{x_{t}\in T}\frac{12\ln(k+10)}{|C_{t}^{j}|:x_{t}\in
C_{t}^{j}}&=\sum_{j=1}^{k}\sum_{x_{t}\in
T^{j}}\frac{12\ln(k+10)}{|C_{t}^{j}|}\\\
&\leq\sum_{j=1}^{k}\sum_{f=1}^{n}\frac{12\ln(k+10)}{f}\\\ &\leq
24k\ln(k+10)\ln n,\end{split}$

where the inequality comes from the fact that each additional point must
strictly increase the size of the cluster it is in (as it is literally the new
point). We also add a factor of 2 to properly bound the harmonic sum with $\ln
n$. The lemma then follows by linearity of expectation.

######  Lemma 15.

The length $q$ of the sequence $\\{s_{1},\ldots,s_{q}\\}$ satisfies
$q\leq\text{Lower}_{9,k}(X)$.

######  Proof 4.8.

The idea of this proof follows that of Lemma 13. We claim that for all $i$,
there exists $s_{i}<b\leq s_{i+1}$ such that for all $x_{a}\in X_{s_{i}}$,
$d(x_{a},x_{b})>\sqrt{9s_{i}}\text{diam}_{k-1})(X_{s_{i}}).$ Note that this
claim implies the lemma from the definition of $\text{Lower}_{9,k}(X)$.

At time $s_{i+1}$, by Theorem 4, all of the points in $X_{s_{i+1}}$ can be
partitioned into $k$ sets each with diameter at most $8P_{s_{i+1}}$.
Furthermore, by Proposition 6, these $k$ sets are precisely
$C_{s_{i+1}}^{1},\dots C_{s_{i+1}}^{k}$.

By the definition of the sequence $s$ in conjunction with Lemma 9, all of the
points in $X_{s_{i}}$ are contained within at most $k-1$ of the clusters
$C_{s_{i+1}}^{1}\dots C_{s_{i+1}}^{k}$. This implies that
$\text{diam}_{k-1}(X_{s_{i}})\leq 8P_{s_{i+1}}$. Without loss of generality,
it follows that $C_{s_{i+1}}^{1}$ and $X_{s_{i}}$ are disjoint. In this case,
we claim that $x_{b}=z_{s_{i+1}}^{1}$ suffices.

Observe that for any $x\in X_{s_{i}}$, $d(x_{b},x)\geq
Q_{s_{i+1}}-4P_{s_{i+1}}$, since $x$ has distance at most $4P_{s_{i+1}}$ to
the cluster center $z_{s_{i+1}}^{j}$ corresponding to it. Since $s_{i+1}$ is a
type 2 selection, we have that $Q_{s_{i+1}}>4(s_{i+1}+2)P_{s_{i+1}}$. It thus
follows that $d(x_{b},x)\geq 4(s_{i+1}+1)P_{s_{i+1}}$. Substituting our
previous bound on $\text{diam}_{k-1}(X_{s_{i}})$ we see that for $s_{i+1}>36$,

$d(x_{b},x)\geq
4(s_{i+1}+1)P_{s_{i+1}}>\sqrt{9s_{i+1}}(8P_{s_{i+1}})\geq\sqrt{9s_{i+1}}\text{diam}_{k-1}(X_{s_{i}}).$

Note that any issues caused for $s_{i+1}\leq 36$ can easily be circumvented by
just selecting the first 36 points (which trivially changes our center
complexity).

#### Putting it all together:

We now bound the overall center complexity of Algorithm 1.

######  Proposition 16.

There exists a constant $\beta>0$ such that with probability at least
$\frac{19}{20}$ over the randomness of Algorithm 1, $|S|\leq\beta k\ln
k\log^{2}n\text{Lower}_{9,k}(X)$.

######  Proof 4.9.

By Lemmas 12 and 13, we immediately see that with probability at least
$1-\frac{1}{60k}$, at most $O(k\ln k\log^{2}n\text{Lower}_{9,k}(X))$
selections are made from type 1 processings. By Lemmas 14 and 15, we see that
the expected number of points chosen by type 2 processings is $O(k\ln k\ln
n\text{Lower}_{9,k}(X)))$. However, observe that every type 2 selection is in
fact an independent event. Type 2 processings have no dependence on $S$.
Because of this, we can easily apply a Chernoff bound to see that with
probability at least $1-\frac{1}{100}$, we do indeed select $O(k\ln k\ln
n\text{Lower}_{9,k}(X))$ points via type 2 processings. A union bound implies
the proposition.

## References

  * Aggarwal (2007) Charu C Aggarwal.  _Data streams: models and algorithms_ , volume 31.  Springer Science & Business Media, 2007.
  * Ailon et al. (2009) Nir Ailon, Ragesh Jaiswal, and Claire Monteleoni.  Streaming k-means approximation.  In _Advances in neural information processing systems_ , pages 10–18, 2009.
  * Aloise et al. (2009) Daniel Aloise, Amit Deshpande, Pierre Hansen, and Preyas Popat.  NP-hardness of euclidean sum-of-squares clustering.  _Machine learning_ , 75(2):245–248, 2009.
  * Arthur and Vassilvitskii (2006) David Arthur and Sergei Vassilvitskii.  k-means++: The advantages of careful seeding.  Technical report, Stanford, 2006.
  * Babaioff et al. (2009) Moshe Babaioff, Michael Dinitz, Anupam Gupta, Nicole Immorlica, and Kunal Talwar.  Secretary Problems: Weights and Discounts.  In _Symposium on Discrete Algorithms (SODA’09)_. Society for Industrial and Applied Mathematics, January 2009.  URL https://www.microsoft.com/en-us/research/publication/secretary-problems-weights-and-discounts/.  Edition: Symposium on Discrete Algorithms (SODA’09).
  * Bhaskara and Rwanpathirana (2020) Aditya Bhaskara and Aravinda Kanchana Rwanpathirana.  Robust algorithms for online $k$-means clustering.  In Aryeh Kontorovich and Gergely Neu, editors, _Algorithmic Learning Theory, ALT 2020, 8-11 February 2020, San Diego, CA, USA_ , volume 117 of _Proceedings of Machine Learning Research_ , pages 148–173. PMLR, 2020.
  * Bhattacharjee and Moshkovitz (2020) Robi Bhattacharjee and Michal Moshkovitz.  No-substitution k-means clustering with adversarial order.  _CoRR_ , abs/2012.14512, 2020.  URL https://arxiv.org/abs/2012.14512.
  * Braverman et al. (2011) Vladimir Braverman, Adam Meyerson, Rafail Ostrovsky, Alan Roytman, Michael Shindler, and Brian Tagiku.  Streaming k-means on well-clusterable data.  In _Proceedings of the twenty-second annual ACM-SIAM symposium on Discrete Algorithms_ , pages 26–40. Society for Industrial and Applied Mathematics, 2011.
  * Buchbinder et al. (2018) Niv Buchbinder, Moran Feldman, Yuval Filmus, and Mohit Garg.  Online Submodular Maximization: Beating 1/2 Made Simple.  _arXiv:1807.05529 [cs]_ , November 2018.  URL http://arxiv.org/abs/1807.05529.  arXiv: 1807.05529.
  * Charikar et al. (1997) Moses Charikar, Chandra Chekuri, Tomás Feder, and Rajeev Motwani.  Incremental clustering and dynamic information retrieval.  In Frank Thomson Leighton and Peter W. Shor, editors, _Proceedings of the Twenty-Ninth Annual ACM Symposium on the Theory of Computing, El Paso, Texas, USA, May 4-6, 1997_ , pages 626–635. ACM, 1997.
  * Charikar et al. (2003) Moses Charikar, Liadan O’Callaghan, and Rina Panigrahy.  Better streaming algorithms for clustering problems.  In _Proceedings of the thirty-fifth annual ACM symposium on Theory of computing_ , pages 30–39, 2003.
  * Dasgupta (2008) Sanjoy Dasgupta.  _The hardness of k-means clustering_.  Department of Computer Science and Engineering, University of California, 2008.
  * Feldkord and Meyer auf der Heide (2018) Björn Feldkord and Friedhelm Meyer auf der Heide.  Online facility location with mobile facilities.  In _Proceedings of the 30th on Symposium on Parallelism in Algorithms and Architectures_ , pages 373–381, 2018.
  * Fotakis (2011) Dimitris Fotakis.  Online and incremental algorithms for facility location.  _ACM SIGACT News_ , 42(1):97–131, 2011.
  * Guha et al. (2003) Sudipto Guha, Adam Meyerson, Nina Mishra, Rajeev Motwani, and Liadan O’Callaghan.  Clustering data streams: Theory and practice.  _IEEE transactions on knowledge and data engineering_ , 15(3):515–528, 2003.
  * Hess and Sabato (2020) Tom Hess and Sivan Sabato.  Sequential no-substitution k-median-clustering.  In _International Conference on Artificial Intelligence and Statistics_ , pages 962–972, 2020.
  * Kanungo et al. (2004) Tapas Kanungo, David M Mount, Nathan S Netanyahu, Christine D Piatko, Ruth Silverman, and Angela Y Wu.  A local search approximation algorithm for k-means clustering.  _Computational Geometry_ , 28(2-3):89–112, 2004\.
  * Lang (2018) Harry Lang.  Online facility location against at-bounded adversary.  In _Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms_ , pages 1002–1014. SIAM, 2018.
  * Liberty et al. (2016) Edo Liberty, Ram Sriharsha, and Maxim Sviridenko.  An algorithm for online k-means clustering.  In _2016 Proceedings of the eighteenth workshop on algorithm engineering and experiments (ALENEX)_ , pages 81–89. SIAM, 2016.
  * Meyerson (2001) Adam Meyerson.  Online facility location.  In _Proceedings 42nd IEEE Symposium on Foundations of Computer Science_ , pages 426–431. IEEE, 2001.
  * Moshkovitz (2019) Michal Moshkovitz.  Unexpected effects of online k-means clustering.  _arXiv preprint arXiv:1908.06818_ , 2019.
  * Shindler et al. (2011) Michael Shindler, Alex Wong, and Adam W Meyerson.  Fast and accurate k-means for large datasets.  In _Advances in neural information processing systems_ , pages 2375–2383, 2011.

##  Appendix A Lower bounds from Bhattacharjee and Moshkovitz (2020)

Finally, we review the center complexity lower bounds in Bhattacharjee and
Moshkovitz (2020). For any input dataset, $X$, Bhattacharjee and Moshkovitz
defined a central parameter, $OC_{k}(X)$ which they used to express both their
lower bounds and upper bounds on the center complexity of an online
$O(1)$-approximation algorithm. In this paper, we will modify their
definitions to construct a new parameter $\text{Lower}_{\alpha,k}(X)$.
$\text{Lower}_{\alpha,k}(X)$ is closely related to $OC_{k}(X)$, but enables us
to give sharper results than those in $OC_{k}(X)$. To this end, we will review
the definitions and lower bound from Bhattacharjee and Moshkovitz (2020) by
phrasing them in terms of this modified parameter,
$\text{Lower}_{\alpha,k}(X)$.

First, we define the $l$-fold diameter of a set $S\subseteq{\mathbb{R}}^{d}$
as the smallest real number $D$ such that $S$ can be partitioned into $l$
disjoint sets each of which have diameter at most $D$. That is,

$\text{diam}_{l}(S)=\min_{S^{1}\cup S^{2}\dots\cup S^{l}=S}\min_{1\leq i\leq
l}\text{diam}(S^{i}).$

Using this, we define the $(\alpha,k)$-sequences, which represent the “worst
case” input for online $k$-means clustering in the no-substitution setting.

######  Definition 17.

Fix $\alpha>1$, and let $x_{1},x_{2},\dots,x_{m}$ be a sequence of points in
${\mathbb{R}}^{d}$ such that for all $1<i\leq m$,

$\min_{1\leq
j<i}d(x_{i},x_{j})>\sqrt{i\alpha}\text{diam}_{k-1}(\\{x_{1},\dots,x_{i-1}\\}.$

Using this, we define $\text{Lower}_{\alpha,k}(X)$ for any set of points $X$.

######  Definition 18.

Let $\alpha>1$, and $X$ be any set of $n$ points in ${\mathbb{R}}^{d}$. Then
$\text{Lower}_{\alpha,k}(X)$ is defined as the length of the largest sequence
of points, $x_{t_{1}},x_{t_{2}},\dots,x_{t_{r}}$ whose elements are distinct
elements of $X$ that can be ordered to form an $\alpha,k$-sequence.

######  Proof A.1.

of Theorem 3. Let $A$ be an $\alpha$-approximation algorithm. Order $X$ so
that the first $\text{Lower}_{\alpha,k}(X)$ points that are streamed form an
$(\alpha,k)$-sequence. First, $A$ must select the first $k$ points since
otherwise it would incur a non-zero cost for a set whose optimal cost is $0$.

Next, let $k+1\leq t\leq\text{Lower}_{\alpha,k}(X)$. Suppose that $A$ does not
select $x_{t}$. Then, the cost incurred, even if all points before $x_{t}$ are
chosen, is at least $\min_{1\leq i\leq t-1}d(x_{t},x_{i})^{2}$. Since our
points form an $\alpha,k$-sequence, this cost is strictly larger than $\alpha
tD_{t}^{2}$, where $D_{t}=\text{diam}_{k-1}(\\{x_{1},\dots,x_{t-1})$.

On the other hand, observe that a cost of $\frac{tD_{t}^{2}}{2}$ is
obtainable. to see this, note that any set of $m$ elements in
${\mathbb{R}}^{d}$ with diameter $D_{t}$ has a $1$-clustering with cost
$mD_{t}^{2}$. Thus, by clustering $\\{x_{1},\dots,x_{t}\\}$ by setting $x_{t}$
as its own cluster and partitioning the rest of the points into sets of
diameter $D_{t}$, we obtain a cost of $tD_{t}^{2}$. This implies that whenever
we fail to select $x_{t}$, our cost is at least
$\alpha\mathcal{L}_{k}(\\{x_{1}\dots,x_{t}\\}$. Thus, in order to be an
$\alpha$-approximation algorithm, $A$ must select $x_{t}$ with probability at
least $\frac{19}{20}$, as $A$ is an $\alpha$-approximation.

Let $B$ denote the smallest real number such that $A$ selects fewer than $B$
points from the first $\text{Lower}_{\alpha,k}(X)$ points with probability at
least $\frac{19}{20}$. Then it follows that the expected number of points
selected by $A$ is at most
$\frac{19B}{20}+\frac{\text{Lower}_{\alpha,k}(X)}{20}$. However, since we know
that $A$ selects each point with probability at least $\frac{19}{20}$, it
follows by linearity of expectation that
$\frac{19B}{20}+\frac{\text{Lower}_{\alpha,k}(X)}{20}\geq\frac{19\text{Lower}_{\alpha,k}(X)}{20}$.
Rearranging this equation gives that
$B\geq\frac{18\text{Lower}_{\alpha,k}(X)}{19}$, which implies the desired
result.

##  Appendix B A modified online $k$-centers algorithm

Recall that the goal of $k$-center clustering is to choose $k$ centers so that
the maximum distance over all points in the dataset to their nearest center is
minimized. Charikar et al. (1997) give a classic online algorithm that
maintains an $8$-approximation to the optimal $k$ center clustering at all
times.

For our purposes, we need to augment their algorithm to maintain, in addition
to the $k$ centers at all times, an approximation to the number of points that
are “clustered” with each center. Specifically, given centers at time $t$,
$z_{t}^{1},z_{t}^{2},\dots,z_{t}^{k}$, we wish to know
$|\\{x_{s}:i=\operatorname*{arg\,min}_{j}d(x,z^{j}),1\leq s\leq t\\}|$ for all
$1\leq i\leq k$.

While directly maintaining these counts is potentially challenging, for our
purposes, an approximation suffices. We begin by first giving a modified
version of the $k$-centers algorithm of Charikar et al. (1997) that maintains
guesses for these counts at all times. The central idea is to augment each
stored center with a count that represents how many points are “assigned” to
it. When centers are changed, we “merge” counts by simply adding assignment
numbers (line 16).

1

2

3$Z\leftarrow\\{(x_{1},1),(x_{2},1),\dots,(x_{k},1)\\}$ ;

4 $P\leftarrow\min_{(z,m),(z^{\prime},m^{\prime})\in Z}d(z,z^{\prime})$ ;

5 for  _$t=k+1,\dots$_ do

6 $(z,m)=\operatorname*{arg\,min}_{Z}d(z,x_{t})$;

7 if  _$d(z,x_{t})\leq 2P$_ then

8 $m\leftarrow m+1$;

9

10 else

11 $Z\leftarrow Z\cup\\{(x_{t},1)\\}$;

12 while  _$|Z| >k$_ do

13 $Z^{\prime}\leftarrow\\{\\}$;

14 for  _$(z,m)\in Z$_ do

15
$(z^{\prime},m^{\prime})=\operatorname*{arg\,min}_{Z^{\prime}}d(z,z^{\prime})$;

16 if  _$d(z,z^{\prime}) >2P$_ then

17 $Z^{\prime}=Z^{\prime}\cup\\{(z,m)\\}$;

18

19 else

20 $m^{\prime}\leftarrow m^{\prime}+m$;

21

22

23 end for

24 $Z\leftarrow Z^{\prime}$;

25 $P\leftarrow 2P$;

26

27 end while

28

29

30 end for

31

Algorithm 2 $\text{Online\\_k\\_centers}(X)$

In Algorithm 2, we let $Z$ denote the set of $k$ augmented clusters, and $P$
denote an approximate estimate of the radius of each cluster. This algorithm
is functionally identical to Charikar et al. (1997): the selection of cluster
centers is identical in both cases. As a consequence, the approximation
guarantee of the algorithm is the same:

We now show that our augmentations, namely the integer counts that are
associated with each element of $Z_{t}$, are reasonable approximations of the
number of points that are assigned to each cluster center.

###### Proposition 6

Let $Q$ denote the distance between the nearest two centers in $Z$. Suppose
that $Q>4(t+2)P$. Let $C^{1},C^{2},\dots,C^{k}$ denote the optimal $k$-means
clustering of $\\{x_{1},x_{2},\dots,x_{t}\\}$. Then $Z$ consists of $k$ pairs,
$(z^{1},m^{1}),(z^{2},m^{2}),\dots(z^{k},m^{k})$ such that the following hold
for all $1\leq i\leq k$: $z^{i}\in C^{i}$, $m^{i}=|C^{i}|$, and
$d(z^{i},x)\leq 4P_{t}$ for all $x\in C^{i}$.

######  Proof B.1.

Let $G$ be a graph with vertices $\\{x_{1},\dots x_{t}\\}$. We construct an
edge between $x_{a},x_{b}$ in two situations.

  1. 1.

If during lines 4-5 at time $b$ of Algorithm 2
$(z,m)=\operatorname*{arg\,min}_{Z}d(z,x_{b})$ and satisfies
$d(x_{a},x_{b})\leq 2P$, then we construct an edge from $x_{a}$ to $x_{b}$.

  2. 2.

If during line 16 the augmented point $(z,m)$ has nearest neighbor
$(z^{\prime},m^{\prime})$ such that $d(z,z^{\prime})\leq 2P$, then we
construct an edge from $z$ to $z^{\prime}$ (recall that all $(z,m)\in Z$
satisfies $z\in\\{x_{1},\dots,x_{t}\\}$).

We claim that $G$ satisfies the following properties:

  1. 1.

Adjacent vertices in $G$ have distance at most $2P$.

  2. 2.

$G$ comprises of $k$ connected components, $G^{1},G^{2},\dots,G^{k}$.

  3. 3.

Each element of $Z$ corresponds to a distinct connected component with
$z^{i}\in G^{i}$ and $m^{i}=|G^{i}|$.

  4. 4.

For all $x\in G^{i}$, $d(x,z^{i})\leq 4P$.

Property 1. is trivial: $P$ is monotonically increasing, and edges are
explicitly only added if the distance between the vertices is at most $2P$. To
verify properties 2. and 3., observe that during all times $1\leq s\leq t$,
the number of connected components in the graph cannot exceed $k$. We either
just connect the new vertex to precisely 1 connected component (lines 5-6) and
update the values of $m$ accordingly. Otherwise, we repeatedly combine
components of our graph (lines 15-16) until we have at most $k$ connected
components. In all of these cases, it is easy to see that the vertices of $Z$
are selected so that no two of them are path-connected. Note that at time $t$,
by assumption $|Z|=k$ meaning that we have precisely $k$ path connected
components.

To verify property 4, observe that for all $x\in X_{t}$, $d(x,Z)\leq 4P$ by
Theorem 4. Suppose that $x\in G^{i}$ but that $x$ has nearest neighbor in $Z$
equal to $z^{j}$ for some $i\neq j$. Since $x$ is path connected to $z^{i}$ by
definition, $d(x,z^{i})\leq 2tP$ (since each edge has length at most $P$.
However, $d(z^{i},z^{j})\geq Q$ by the definition of $Q$. It follows by the
triangle inequality that

$4P+2tP=d(x,z^{j})+d(x,z^{i})\geq d(z^{i},z^{j})\geq Q,$

which clearly contradicts $Q>4(t+2)P$. Thus $z^{i}$ is the nearest neighbor of
$x$ and $d(x,z^{i})\leq 4P$.

Having verified the properties above, it suffices to show that
$G^{1},G^{2},\dots,G^{k}$ is the optimal $k$-means clustering of $X_{t}$. In
particular, this will imply that $G^{i}=C^{i}$ for all $i$. To do this, it
suffices to show that it is impossible in the optimal clustering of $X_{t}$
for any two vertices in $G$ that are not path connected to be clustered
together.

First, observe that $\mathcal{L}(X_{t},OPT_{t}^{k})\leq t(4P)^{2}$. This is
because we can easily take $z^{1},\dots,z^{k}$ to be $k$-means centers, and
then apply property 4. of $G$ to bound the $k$-means cost function. Second,
suppose that $x\in G^{i}$ and $x^{\prime}\in G^{j}$ are clustered together in
some $k$-means clustering of $X_{t}$ where $i\neq j$. Then observe that the
cost of clustering just $x$ and $x^{\prime}$ can be bounded by
$\frac{d(x,x^{\prime})^{2}}{2}$ (as they must be assigned to the same cluster
center). Using this, we observe that our induced cost is at least

$\frac{d(x,x^{\prime})^{2}}{2}\geq\frac{(d(z^{i},z^{j})-8P)^{2}}{2}>\frac{(4tP)^{2}}{2}>t(4P)^{2},$

since $t\geq 2$. This implies that $x$ and $x^{\prime}$ cannot be clustered
together in the optimal $k$-means clustering, which finishes the proof.

##  Appendix C Proving Proposition 7

We begin with the following key lemma.

######  Lemma 19.

Let $k\leq t\leq n$. Then the probability that $R_{t}$ is illicitly doubled,
that is set to twice its previous value and also set beyond its desired
threshold is small. That is,

$\Pr[R_{t}>\frac{\mathcal{L}_{k}(X_{t})}{k}\text{ and
}R_{t}>2R_{t-1}]\leq\frac{1}{500kt^{2}}.$

######  Proof C.1.

The value of $R$ only changes in two ways, it is either doubled, or it is set
to $\frac{P^{2}}{12k\ln(k+10)}$. By Theorem 4, there exist $k+1$ points at
time $t$ in $X_{t}$ with pairwise distances at least $P$. Thus, it follows
that $\mathcal{L}(X_{t},OPT_{t}^{k})\geq\frac{P^{2}}{2}$. This means that the
only way $R$ can exceed its desired value of
$\frac{\mathcal{L}(X_{t},OPT_{t}^{k})}{12k\ln(k+10)}$ is through egregiously
doubling. To this end, we see that
$R_{t}>\frac{\mathcal{L}_{k}(X_{t})}{12k\ln(k+10)}$ if and only if there
exists $t^{\prime}<t$ such that
$R_{t^{\prime}}>\frac{\mathcal{L}_{k}(X_{t})}{24k\ln(k+10)}$ and a doubling
occurs between times $t^{\prime}$ and $t$.

Next, recall that we are trying to bound the probability that not only is
$R_{t}$ large, but that it was doubled during time $t$. This can only happen
if at least $289k\ln(k+5)\log t$ centers are selected, as $R_{t}\leftarrow
R_{t-1}$ only if $F_{t-1}=289k\ln k\log t$. Thus, to bound the desired
probability, we will bound the probability that at least $289k\ln k\log(t+5)$
centers are selected conditioning on $t^{\prime}$ existing with
$R_{t^{\prime}}>\frac{\mathcal{L}_{k}(X_{t})}{24k\ln(k+10)}$.

Let $C^{1},C^{2},\dots,C^{k}$ denote the optimal $k$ clustering of $X_{t}$,
and let $c^{1},c^{2}\dots c^{k}$ denote their respective centers. Our main
idea will be to partition each $C^{i}$ into subsets based on their distance
from the center $c^{i}$, and then examine each of these smaller subsets
individually. We will argue that we are likely to select only a small number
of points from each of these smaller subsets, and then apply a Chernoff bound
over all the points to obtain our result.

Let $\gamma^{i}=\frac{\mathcal{L}(C^{i})}{|C^{i}|}$, and define

$C_{j}^{i}=\\{x:x\in C^{i},2^{j-1}\gamma^{i}\leq
d(x,c^{i})^{2}<2^{j}\gamma^{i}\\},\text{ for all }j\geq 1.$

We also let $C_{0}^{i}=\\{x:x\in C^{i},d(x,c^{i})^{2}<\gamma^{i}\\}$.
$C_{j}^{i}$ can be thought of as the $j$th “ring” of points centered around
$c^{i}$ with each ring having double the radius of the previous ring. Because
$|C^{i}|\gamma^{i}=\mathcal{L}(C^{i})$, $C_{j}^{i}$ is empty for all
$j>\log|C^{i}|+1$. Since $|C^{i}|\leq t$, and $C_{1}^{i}$ is non-empty, it
follows that we have at most $k\log t$ non-empty subsets that partition
$\\{x_{t^{\prime}+1},\dots,x_{t}\\}$.

For $t^{\prime}+1\leq s\leq t$, let $C(s)$ be the unique $C_{j}^{i}$ with
$x_{s}\in C_{j}^{i}$, and let

$E_{s}=\begin{cases}1&x_{s}\text{ is selected, }|C(s)\cap S_{s-1}|\geq 1\\\
0&\text{otherwise}\end{cases}.$

$E_{s}$ is an indicator representing that $x_{s}$ has been selected but is not
the first element of its “ring” to be selected. Since there are at most $k\log
t$ non-empty rings, it follows that the total number of selections made
between times $t^{\prime}+1$ and $t$ is at most $k\log
t+\sum_{s=t^{\prime}+1}^{t}E_{s}$. We will now analyze the latter sum using a
modified Chernoff bound.

To bound ${\mathbb{E}}[E_{s}]$, define $\gamma(s)=2^{j}\gamma^{i}$ if
$C(s)=C_{j}^{i}$. Suppose that $|C(s)\cap S_{s-1}|\geq 1$ and let $x\in
C(s)\cap S_{s-1}$. By the triangle inequality, $d(x_{s},x)^{2}\leq
4\gamma(s)$. Since $x_{s}$ is selected with probability at most
$\frac{d(x_{s},x)^{2}}{R_{s}}$, implying
$\Pr[E_{s}=1]\leq\frac{48k\ln(k+10)\gamma(s)}{R_{s}}\leq\frac{96k\ln(k+10)\gamma(s)}{\mathcal{L}_{k}(X_{t})},$
with the last inequality holding since
$\frac{\mathcal{L}_{k}(X_{t})}{24k\ln(k+10)}<R_{t^{\prime}}\leq R_{s}$.
Furthermore, this inequality holds regardless of the values of
$E_{s}^{\prime}$ are for all $s^{\prime}<s$: adding further selections can
only reduce the $\Pr[E_{s}=1]$.

This allows us to apply a modified Chernoff bound to study the concentration
of the sum $\sum E_{s}$. Bounding its expectation, we see

$\begin{split}{\mathbb{E}}[\sum_{s=t^{\prime}+1}^{t}E_{s}]&\leq\sum_{s=t^{\prime}+1}^{t}\frac{96k\ln(k+10)\gamma(s)}{\mathcal{L}_{k}(X_{t})}\\\
&\leq\frac{96k\ln(k+10)}{\mathcal{L}_{k}(X_{t})}\sum_{i=1}^{k}\sum_{j=0}^{\log
t+1}|C_{j}^{i}|2^{j}\gamma^{i}\\\
&\leq\frac{96k\ln(k+10)}{\mathcal{L}_{k}(X_{t})}\sum_{i=1}^{k}\left[\sum_{x\in
C_{0}^{i}}\gamma^{i}+\sum_{j=1}^{\log t+1}\sum_{x\in
C_{j}^{i}}2d(x,c^{i})^{2}\right]\\\
&\leq\frac{96k\ln(k+10)}{\mathcal{L}_{k}(X_{t})}\sum_{i=1}^{k}\left[\mathcal{L}(C^{i})+2\mathcal{L}(C^{i})\right]\\\
&=288k\ln(k+10).\end{split}$

The main manipulations we make in the sequence above come from the fact that
$\gamma^{i}<d(x,c^{i})^{2}\leq 2^{j}\gamma^{i}$ for all $x\in C_{j}^{i}$, and
from the definition of $\mathcal{L}(C^{i})$.

We desire the probability that $E_{total}\leq 289k\ln(k+10)\log t$. Since,
$E_{total}\leq k\log t+\sum_{s=t^{\prime}+1}^{t}E_{s}$, it suffices to bound
the probability that $\sum E_{s}\leq 288k\log t$. Using a Chernoff bound,

$\begin{split}\Pr[\sum_{s=t^{\prime}+1}^{t}E_{s}>288k\log
t]&=\Pr[\sum_{s=t^{\prime}+1}^{t}E_{s}>288k\ln(k+10)\left(1+(\log
t-1)\right)]\\\ &\leq\exp\left(-288k\ln(k+10)\left(\frac{(\log t-1)^{2}}{\log
t+1}\right)\right)\\\ &\leq\frac{1}{500kt^{2}}.\end{split}$

We now restate and prove Proposition 7.

###### Proposition 7

Let $R_{t}$ denote the value of $R$ after the point $x_{t}$ is processed by
Algorithm 1. With probability at least $1-\frac{1}{30k}$ over the randomness
of the
algorithm,$R_{t}\leq\frac{\mathcal{L}(X_{t},OPT_{t}^{k})}{12k\ln(k+10)}$ for
all $k\leq t\leq n$.

######  Proof C.2.

(Proposition 7) Suppose that after running Algorithm 1 that some $t$ satisfies
$R_{t}>\frac{\mathcal{L}_{k}(X_{t})}{12k\ln(k+10)}$. Take $t$ to be minimal so
that $R_{s}\leq\frac{\mathcal{L}_{k}(X_{s})}{12k\ln(k+10)}$ for all $s<t$.
Observe that we must have that $R_{t}=2R_{t-1}$: if this weren’t the case,
then $R_{t}=R_{t-1}$ which would contradict the minimality of $t$. By Lemma
19, the probability of this occurring for a given value of $t$ is at most
$\frac{1}{500kt^{2}}$. Thus, the probability of this occurring for some $t$
can be bounded with a union bound as at most
$\sum\frac{1}{500kt^{2}}\leq\frac{1}{120k}$, which implies the result.