Online Coresets for Parameteric and Non-Parametric Bregman Clustering
Authors: Supratim Shit
Anirban Dasgupta
Rachit Chhaya
Jayesh Choudhari
Venue: Accepted by TMLR ()

Abstract: We present algorithms that create coresets in an online setting for clustering problems based on a wide subset of Bregman divergences. Notably, our coresets have a small additive error, similar in magnitude to the gap between expected and empirical loss (Bachem et. al. 2017), and take update time $O(d)$ for every incoming point where $d$ is the dimension of the point. Our first algorithm gives online coresets of size $\tilde{O}(\mbox{poly}(k,d,\epsilon,\mu))$ for $k$-clusterings according to any $\mu$-similar Bregman divergence. We further extend this algorithm to show the existence of non-parametric coresets, where the coreset size is independent of $k$, the number of clusters, for the same subclass of Bregman divergences. Our non-parametric coresets also function as coresets for non-parametric versions of the Bregman clustering like DP-Means. While these coresets provide additive error guarantees, they are significantly smaller for high dimensional data than the (relative-error) coresets obtained in (Bachem et. al 2015) for DP-Means--- for the input of size $n$ our coresets grow as $O(\log n)$ while being independent of $d$ as opposed to $O(d^d)$ for points in $\~R^d$ (Bachem et. al 2015). We also present experiments to compare the performance of our algorithms with other sampling techniques. 

Published in Transactions on Machine Learning Research (07/2022)
Online Coresets for Parametric and Non-Parametric Breg- man Clustering
Rachit Chhaya DATCCT- Gandhinagor, India
rachit chhaya@dacict.oc.it
Jayesh Choudhari
CUBE, England
Anirban Dasgupta IIT Gandhinager, India
anirbandg@Gitgns.c.tt
Supratim Shit'
supratim.shii@@gmatii
Technion, Israel
Reviewed on OpenReview: Revieu
Abstract
We present algorithms that create coresets in online setting for clustering problems based on wide subset of Bregman divergences. Notably, our coresets have small additive error, similar in magnitude to the gap between expected and empirical loss Bachem et al. (2017a), and take update time (dd for every incoming point where is the dimension of the point. Our first algorithm gives online coresets of size (ppoly(k, d, C, ()) for k-clusterings according to any j-similar Bregman divergence. We further extend this algorithm to show the existence of moo--oonnaae parametric coresets, where the coreset size is independent of k. the number of clusters, for the same subclass of Bregman divergences. Our nonpparametric corescts also function as coresets for non parametric versions of the Bregman clustering like DP-Means. While these coresets provide additive error guarantees, they are significant, ly smaller for high dimensional data than the (relative-error) coresets obtained Bachem et al. (0155) for DP-Means for the input of size n our corescts grow as O(log n)) while being independent of d opposed to (dd)) for points in Rd Bachem al. (2015). We also present. experiments to compare the performance of our algorithms with other sampling techniques.
1 Introduction
Clustering is a frequently used operation in data processing. A canonical definition of the clustering problem is via the k-median, in which & possible centers need to be proposed such that the sum of distances of every point to its closest center is minimized. There has been a plethora of work, both theoretical and practical, devoted to finding efficient and provable clustering algorithms in this k-median setting. Most of this literature devoted towards dissimilarity measures that are algorithmically easier handle e.g. the various l, norms, especially Euclidean.
A mathematically elegant family of dissimilarity measures that have found wide in statistics the Breg- man divergences which include the squared Euclidean distance, the Mahalanobis distance, Kullbeck-Leible divergence, Itakuro-Saito dissimilarity and many others. While being mathematically satisfying, the chief drawback of working with Bregman divergences for clustering is algorithmic- most. of these divergences not satisfy either symmetry or triangle inequality conditions. Hence, developing efficient clustering al- gorithms for these divergences has been a much harder problem to tackle. [Baneroe al. (2005) did a
* *Corresponding author

---

Published in Transactions on Machine Learning Research (07/2022)
systematic study of the k-median clustering problem under Bregman divergences, and proposed algorithms that are generalizations of Lloyd's iterative algorithm for the Euclidean k-means problem. However, scalabil- ity remains a major issue, Given that there are no theoretical bounds on the quality of the solution obtained via the Lloyd's algorithm in the general Brogman setting, a decent solution is often achieved via running enough iterations as well as by searching over multiple initializations. This is clearly expensive when the number of data points large. This problem is further aggravated when the dimension of the input points is also high and the number of clusters is not known.
Coresets, small summaries of data to enable efficient optimization, have been successfully used in many prob- lems in computational geometry and more recently in machine learning. A coresct is a judiciously selected (and reweighted) set of points, often from the input points themselves, such that solving the optimization problem on the coreset gives a guaranteed approximation to the solution of the optimization problem on the full data (Lucic et al. 2016).
In this work we explore two specific goals in creating coresets for Bregman divergence based clustering. First, we wish to create the coresets in online setting, i.e. the decision about each point should be taken when the point is first consumed by the algorithm from an online stream. Secondly, we show the existence of a single coreset that works for all values of k, the number of clusters. We further give an algorithmic version of it under certain assumption. It is not apriori clear that either of these goals are achievable. Coreset creation strategies, e.g. (Lucic et al. 2016p, often require a rough approximation in order to construct the importance sampling distribution. This route would seem to preclude taking online decisions.
Yet another issue is the dependence of the coreset size on the number of clusters k the number of clusters can be large, and more importantly, it can be unknown, to be determined only after exploratory analysis with clustering. When the nunber of clusters is unknown, even the existence of coreset of sublinear size is unclear. Recent work by Huang & Vishnoi (2020) shows that for relative error coresets for Euclidean k-means, a linear dependence of coresct size on l is both sufficient and inevitable.
In this work, we lackle these questions for Bregman divergences. We develop coresets with small addilive error guarantees. Such results have also been obtained in the Euclidean setting by Bachem et al. (2018a). and in the online subspace embedding setting by Cohen et al. (2016). We next show that in the case of non-parametric clustering, there exists a corcset whose size is independent of k, the parameter representing number of cluster centers. We utilize the sensilivily framework of Feldman & Langberg (2011) jointly with the barrier functions method of Batson et al. (2012) in order to achieve this. Using an empirical notion of sensitivity (Baykal et al.] 2018) we present an algorithmic version of this result under certain assumptions. To the best of our knowledge this is the first. non-parametrie coreset for clustering. A non-parametric coreset will be useful in problems such as DP-Means clustering (Bachem et al. 2015)) and extreme clustering (Kobren et al. 2017), ; where number of clusters may not be known apriori. We now formally describe the setup and list our contributions.
Given A E R where rows are input points in Rdd Let &o be the mean of A, i.c., 4 Eign(a:/n)) For
query Q C Rd the clustering cost on A with respect to Q is defined as,
fa(A)= = Σ min fa(a.). qEQ
isn
where fq(a;) is chosen p-similar Bregman divergence (Definition 2.2
We present algorithms which return
coreset C and set of corresponding weights Ω such that, VX C Rd
X
= k,
fx() & (A) + fc()))
(1)
where, (2, the weighted cost on points C, i.e., (x, Ecjc wisx (cz). The weight w; Ω corresponds to the point c, E C. For points coming in streaming fashion we use A₁ E Rixd to represent the first points that have arrived. Let yo denote the mean point of A;, i.e, si = Eagr(a///i. Notice that the additive term fo (A) can be understood in the following manner when f(-) is the squared Euclidean metric, then (A) | +lB = n x avg.,lla, a, 12.
Our main contributions are as follows.
2

---

Published in Transactions on Machine Learning Research (07/2022)
We present online algorithm called BregmanFilter (Algorithm (1) which ensures property equation [ for any X E Rexdd with at least 0.99 probability. BregmanFilter takes ((d) both in update time and working space to return a coreset (C, for A. The expected size of the coreset is ( log (logn + log (A)( - log (az))) (Theorem 4.6). For the special case of k- Z/22
means clustering, this implies a online coreset of size O looook (logn +- log (J)(A)) -log (a2)))
(Corollary 4.2
In a non- non-paramelric clustering problem, the number of clusters are unknown. We first show the exis- tence of coreset for non-parametric clustering based on Bregman divergence. Under mild assump- tion on the data we also present an algorithmic Arrrion,NonParametriin which creates a coreset (C, based on importance sampling for clustering that ensures equation
(Algorithm (2)
VX E Rixd where 1 I i S n. The coreset has O (log n + log (fe( - log (fpz (a2)) ex-
pected points (Theorem 5.1p. This coreset can be used for DP-Means clustering (Theorem 5.12). For d log(d)) > (1))) the expected coreset size is smaller than e(d"k*"- ?), the current best known coresct size for DP-means obtained by Bachem et al. (2015), where k* is the optimal number of con- ters for DP-Means clustering. Further for the special case of k-means clustcring, the non-parametric coreset (C, for A will have an expected size of O 1/4 (log log (A) - log (fvz (az))) (Corol- lary 5.2
We present experimental results and compare the performance of our coresets with other known coresct building techniques. The comparison is done on real-world datasets to support our theoretical claims.
For As, the BregmanFilter maintains an online coreset C, with corresponding weights Ω4 The coreset is online in the sense that for every incoming point a, the algorithm either samples or discards the point before getting the next point. With this we can also ensure an online guarantee, i.e., (C.) fx(A:) s e e(fx(A.) fip (A))), with constant probability Vi E [n], by taking union bound over all i. Note that this is stronger guarantec and in this case the expected sample size has an excess multiplicative factor of O(log n).
Outline: In section 2 present all the notations and definitions that use in the rest of the paper. In section 3 we discuss the previous works related to the results in this paper. In section 4 we present our first result, which is an online algorithm for building coresets clustering based on p-similar Bregman divergences. In the next section we discuss coreset results for non-parametric clustcring for same class of divergences. In section G we show a bound on the uniform deviation for the same class of divergences. Finally we present some experimental results in section on real datasets.
2 Preliminary
Here we define the notation and the common terms that we use in rest of the paper. The set of the first n natural number is represented by [n]. A bold lower case letter denotes a vector or point for e.g. a, and a bold upper case letter denotes a matrix or set of points as defined by the context for e.g. A. Unless is stated otherwise, the matrix A is used to represent n points each in Rd. a; denotes the 7th row of matrix A and a denotes its jth column. We use the notation A, to denote the matrix or set, formed by the first rows points of A seen till time in the streaming setting. Given A, the smallest and the largest absolute values are defined as ||Al|min mingy jai,] and || || maxi,j la:.].
In a clustering problem, depending on the type of the input points function is used from a wide range of divergence measure called Breyman divergence.
Definition 2.1. Bregman divergence: For any strictly convea, differentiable function & : Z - R, the Bregman divergence with respect to Φ, Vx.y E Z is,
xx) =>(y)= +(() VD(())F(y
3

---

Published in Transactions on Machine Learning Research (07/2022)
We also denote fx(y) d4 x). Throughout the paper for some set of centers X in I and point E R we consider (a) as cost function based on Bregman divergence. Such X are also called query set. We define it as fx(()) = minxex (a) = minxex dg (a, x), where d+(-) is some Bregman divergence as defined above. If the set of points in A have corresponding weights {wa} then Va E A we define fx(a) = =add (a. x).
Unlike squared euclidean distance, not all Bregman divergences follow metric properties. However there a wide sub class called j-similar Bregman divergence which can relate distance measure that follows metric properties.
Definition 2.2. A Bregman divergence de on domain 2 is called u-similar Bregman divergence for some 1 > 0 if there erists a positive definile malric M such that, for each x, E 2
pdm x) S dx S dm
where dx) (y - (x- - x) is the squared Mahalanobis distance.
Going forward, we also denote fM(() dM x), and hence, we have pf S fx(a) S (M),, Vx and Va E A. Due to this we say fx(+) and (.) are p-similar. For Euclidean k-means clustering M is just identity matrix and μ 1. It is known that a large set of Bregman divergences is j-similar, inchuding KI-divergence, Itakura-Saito, Relative Entropy, Harmonic etc (Ackermann & Blömer 2009). In Table L we list the most common j-similar Bregman divergences, their corresponding M and the μ. In each case the À and v refer to the minimum and maximum values of all coordinates over all points, i.c. the input a subset of [X, 12,
Table 1: p-similar Bregman divergences LLucic et al.
2016)
Divergence
Domain
M
Squared-Euclident
Rd
I
Mahalanobiss
Rd
N
Exponential-Loss
[A C R
E (w-A)
La
Kullback-Lcibler
Dy C R
2A La
Itakura-Saito
[d C Rd
La
Harmonic, (a >> 0)
DA c R
a--
2xa12 Ia
Norm-Like, (a >
[x, c CRC
a(1 (11-a) I
Hellinger- Losss
[-v, v/ c (-1,1) 2(1 - 2(11~2)3/2
2(1 v) 33/21,
Mahalanobis bis distance is also p-similar Bregman divergence with 1 and M is the inverse of the covariance matrix.
There are two types of clustering, hard and soft clustering for Bregman divergence (Bneereee et al. 2005 In this work, by the term clustering, we only refer to the hard clustering problem.
Coresets: A coreset Har-Peled & Mazundar (2004); Agarwal al. (2005) Badoiu & Clarkson (2033) acts small proxy for the original data in the sense that it can be used in place of the original data for given optimization problem in order to obtain provably accurate approximate solution to the problem. Let
>> O. For a non-negative cost function, say fx(a), where X is query and A, a set of subsampled and appropriately reweighted points (C, is an e-coreset if VX,
Σ fx(a) AEA
Σ
wa.f((a) Se Σ fx(a).
(a. ((C.N)
acA
Typically, the samples that we will construct will satisfy this condition with desired probability.
While coresets are typically defined for relative errors, additive error coresets can also be defined similarly.
For 7 > O, (C, is an additive (e, 7) coreset of A if C contains points from A with corresponding weights in Ω and VX, EaSA fx(a) ( (( ((w,n) Wa faaf((2 fā) < EaEA fx(a) +y. The coresets that are presented here satisfy such additive guarantecs. For case of representation, sometime will just use fx (C) instcad of Σ E(awa) ((C.n) wa/x fx (ā) and (A) instead of ΣacA fx(a).
4

---

Published in Transactions on Machine Learning Research (07 (07/2022)
Sensitivity Score:
Given an imput and optimization function, sensitivity score for each imput point measures the importance of the point for that optimization function. For dataset. A, query space X' that denotes candidate solutions to an optimization problem, and a cost function fx(-), Langberg & Schulman
(2010) define sensitivity scores as follows the sensitivity of a point is defined as 8a supxex EN'EA fx(a'))
(x(a)
Note that for all points a, Sa E [0, 1]. and can be treated as a probability score. The sensitivity based coresets Langberg & Schulman (2010) are created by sampling points according to these probabilities (or their upper bounds).
While the above definition standard, we also define the following variant of scnsitivity scores as a useful tool in results.
In certain cases, for the query space X, it will be challenging to compute a reasonable upper bound to the sensitivity scores. In such cases, we will use empirical sensitivity scores fx(m)
Empirical Sensitivity Score:
8 maxxEy
where ) is finite set of queries such that y C X. La'ca fx(a²)
Online Sensitivity Scores: For inputs coming in a streaming fashion, iee, the point a, arriving at the 5th instance and so far the algorithm has received A;-1; now for a query space X' and cost function fx(-) (x(a.)
we define the online sensitivity score for every such point a, a8, $a; supxex E,g. [xla,)
We focus on creating coresets for clustering. Our first results are on k-median clustering, where the query space X' satisfies X' C &ex | One can also define clustering problem when the number of clusters are unknown. We call this as Paramerriiii Clustering. We define (C, 92) to be an (s,7)-additive error coresel for nonpparaec clustering if its size is independent of k (number of centres) and ensures (A) +y for all < n and for all query X E [Rxxd
S
The DP-Means problem, studied in Kulis & Jordan (2012), formalizes the clustering problem when the number of clusters is unknown. It can be considered to be specific case of the well-known facility location problem. Given dataset A E Raxd and a parameter k (0, n| and an X E Rexd that minimizes the cost (A, X), which is defined follows,
DP-Means:
0, the goal of the problem to find
costDp(A,X,K = Σ iS
min |a, - x|| 17++0 Ak.
xex
In this paper we consider an obvious exlension of the cost function that depends on the Bregman divergences. Given a dataset E Rd and a parameter X, the goal of the problem is to find X e Rkxd that minimizes the costpr(A (, X), defined as follows,
cost postpp(A,X) = fx(A)+ Ak.
Uniform Deviation: Given distribution D, input set A (a.,..., am where each a; is independent and identically distributed sample from D, query X and function fx fx()), the uniform deviation is defined as
1 BaeDfx(a) m fx(
Definition 2.3 (Pseudo-dimension Haussler 1992 For function family F mapping from an arbitrary inpul space X to Rzo and a distribution P on X, the pseudo-dimension of F, denoted by Pdim(F), is the largest d such there is a sequence II....,II of domain elements from X and sequence Tl, Fd of reals such that for each by....,bu ba E {above, below), there is an f E such that for all i = 1,..., d, we have (xx,) 2 r, if and only bf above.
-Certain Bregman divergences have non-negativity constraints the input.
5

---

Published in Transactions on Machine Learning Research (07/202) 2022)
3 Related Work
The initial coresets were used for making the computational geometric algorithms more efficient Badoiu & Clarkson (2003). as well to improve the running times for various clustering problems Har-Peled & Mazumdar (200 Agarwal et al. (2005). Since then there has been significant amount of work on coresets. Interested readers can look at (Woodruff et al., 2014 Bachem et al., 2017b) and the references therein. Using sensitivities to construct coresets was introduced in (Langberg & Schulman 2010) and further
generalized by (Feldman & Langberg 2011). Coresets for clustering problems such as k-means clustering has been extensively studied (eard & Mazumdar 2004 Cohen et al. 2015 Braverman al.) 2016 Feldman
ct al. 2016 Bachem et al. 2018a b Barger & Feldman 2020 Feldman et al. 2020). In (Cohen et al. 2015
the authors reduce the k-means problem to a constrained low rank approximation problem. They show that a constant factor approximation can be achieved by just O( log k) size coreset and for (1 + e) relative
error approximation they get coreset of size (). In (Barger & Feldman 2020 Feldman et al., 2016).
the authors discuss a deterministic algorithm for creating coresets for chustering problem which ensures a relative error approximation. The streaming version of (Barger & Feldman 2020) returns a coreset. of size O(k "eee""->logg which ensures a (1 + logn) relative error approximation. Feldman et al. (2016) reduce the problem of k-means clustering to E frequent item approximation. The st seamiing version of the algorithm returns a coreset of size E log" n). In (Bachem et al. 2018b), the authors give an algorithm which returns a one shot coresct for all Ep k-clustering problem, where p E [1, Pmax]. Their algorithm ereates a grid over the range [1, [max]] and based on the sensitivily at each grid point the coreset is built. It returns a coreset of size (16 dkk2) for which it takes Ö(ndk) ensuring (1= relative error approximation. In (Boutsidis &
Magdon-Ismes Ismail 2013 Cohen et al. 2015), authors show that one can use spectral approximation technique [Batson et al. 2012 for deterministic feature selection for k-means problem. In (Bachem et al., 2018a)
the huthors give an algorithm to create a coreset which only takes ((nd) time and returns a coreset of size Odkke=2 k) at a cost of small additive error approximation. Their algorithm can further be extended for clustering based Bregman divergences which are p-similar to squared Mahalanobis distance. In (Lucic et al., 2016) the authors give algorithm to create such coresets for both hard and soft clustering based on j-simillar Bregman Divergence. In this paper we present an online algorithm which is returns just Ö(dke log k) size coreset with similar guarantees.
There are several online algorithms for k-means clustering (Liberty et al. 2016 Lattanzi & Vassilvitskil 2017 Bhaskara & Rwanpathirana 2020). These algorithms do not create coresets, rather focus on giving online algorithus for the clustering problem. In (Liberty et al.] 2016) the authors give an online algorithm that maintains a set of centers such that the k-means cost on these centers is Ō(W*) where W is the optimal k-means cost. Lattanzi et.al., Lattanzi & Vassilvitskii (2017) improve this result and give a robust algorithm that can also handle outliers in the datasct. We further explore the relation of these algorithms with our online coresets empirically in the experimental section.
The coreset building methods can also be analyzed from the point of view of generalization of the resulting clustering. There are several results on uniform bound deviation for k-means clustering problem (Bau et al. 2008 Bachem et al., 2017a). The result. in Biau et al. (2008) shows that the difference between the optimal empirical loss and the optimal clustering loss (i.c., the expected excess risk) can be bounded in terms of the radius of the input data and inverse of the input size. As our main contribution in this paper is about building strong coresets, extend the results in Bachem et al. (2017a), which ensure that the difference between empirical loss and clustering loss for all possible queries are bounded.
We use Theorem 3.2 from Chhaya et.al., Chhaya et al. (2020b). where the authors show that the coreset built using sensitivity framework has a sampling complexity that only depends on O(S) instead of O(S log(S)) in [Brvvrran et al. 2016), where S the sum of sensitivity scores. Our coresct size for clustering based on p-similar Bregman divergence only has a dependence of O(1/p), unlike in (Lucic et al. 2016 Bachem et al., 2018a) where the dependence is 0(1/12).
6

---

Published in Transactions on Machine Learning Research (07/202) /202)
Algorithm BregmanFilter
Require: Streaming points a,, = 1, ,,,rr >
Ensure: (C
Co 00 Po 0; S ===00
A || mini == ||a m
while S n do
A= =min |laz///minn = max (v; ||ai|| ||ax]]
Update 14 = A/v; Update M, based on (Table !
Pi ((i (i-1))p 1) + a,//i; S = S (a.)
if = then
P: =
else
4 = 2f
+
8 ::(11)):: = min (1, rlk
148
end if
(cr,42) = (ai, 1/p:)
w. ps
(0)
clse
(c)) = (C 24-1) w;)
end while
Return (C)
4 Online Coresets for Clustering
We consider that the input points are coming in a streaming manner, i.e., each point on arrival is either selected to be in the coreset or discarded. We present our first algorithm called BregmanFilter It creates a coreset in an online manner for clustering based on Bregman divergences. The coresct built via importance sampling, which is based on sensitivity framework, i.e., we use sensitivity scores to define the sampling probability of cach point. The algorithm starts with the knowledge of Bregman divergence dg- It is important to note that for fixed dæ if the domain of the input changes, then both the parameters M and also change [Ackermann & Blömer 2009 Lucic et al. 2016) (table D This is exactly what happens in our case, because we only have access to the stream of input. These parameters are important because they are used to compute an upper bound on the scnsitivity scores of every points.
Overview: Under a fixed p-similar Bregman divergence, the input to the algorithm is a stream of points and an user defined parameter r that depends on and the VC dimension of query space of the problem, such that it returns (C, 12) which is an e coreset. Here on arrival of every input point say a, the algorithm first updates the smallest and largest absolute values as and v, such that x = [Aillmin and v = || mma It also updates the mean sos. Next it computes both the Mahalanobis matrix M, as well as pz. Fortunately, computing M, and μ4 requires maintaining only two simple statistic of the data (Table D. Using these terms it computes an upper bound for the sensitivity score, which is then used to decide whether a; should be stored in the coresct. If selected, the point a; is stored with an appropriate weight wy. At the end of the stream we get (C, 2)). Note that this algorithm is online in nature because for every point its sampling decision is taken before looking at the next incoming point. We present BregmanFilter as algorithm [
Now we present some supporting lemmas based on which we show the correctness and the corresponding guarantees of the algorithm. Note that for A, formed by first i data points. The algorithm BregmanFiltes maintains M, and ir (as per Table D such that, Mi (ay) I fx(a;) Ma,()a;, Vx and Va, A,, Using this we show useful observation that is immediate, based on M and μ defined in Table
Lemma 4.1. For all Bregman divergences in Table 4 for j $ i, My 2 #4 and M, - M,
Proof. At any thh point we have À ||A4lmiin and v ||, max, i.c., the smallest and largest absolute values in A, Further we have ||Ay||mia 2 || and |A,llmas I ||A for By using the formula for M for all Bregman divergences given in Table I we have M, A M; and μ bt to be always true for j S i. 7

---

Published in Transactions on Machine Learning Research (07 (07/2022)
For any Bergman divergence the mean of set of points always minimizes the sum of Bergman divergences between the set of points and any other point. Now recall that for all E [n], we use 9i to represent the mean of the first i points, i.e, Pi = Ejs az/i. Hence we have the following important observation.
Lemma 4.2. For points arriving in streaming manner, Vi have, fA.(A.) f1p (A,).
Proof. We have,
Sp. (A.) = (a)) Σ (a,(ar) Σ jersi
(ar)+ Σ (a)) jersi
In (i) we use the fact that Pj minimizes the sum of Bregman divergence between any point and first j points.
Due to lemma 4.1 and lemma 4.2 have the following lemma which is then used to upper bound the online scnsitivity scores with 4 as defined in BregmanF iilfFiltte ilter.
Lemma 4.3. For a fared p-similar Bregman divergence with streaming impruss, let 9i = -Eis((a/0)) and M. is the p.s.d. Mahalanobis matric for Ai (as Table 7.. i then fdd. (Ai) 2 Ejsi 1// (aj)
M,
Proof.
M. (A,)
Σ (a, -p:) - pp))
JS
(a, -p:) Mi - -pi)+
E (a,- 1 (i)) M 1,, - Pi)
j5i-1
2 (a, - M, - -Ri)+
Σ
(a, - p.) MM, - -P))
(a, - -1)) - - -pi)+
Σ
(a, - (0- ) MM - pi-1)
j
(ay ( Mi - -p)) +
Σ
(ay (,)) My - pg)
Σ MM (a,)
In (i) we used the property that M 3 M. In (ii) we used the fact that for A its mean Pi-1 minimizes the cost.
As use 4 for building our coreset, the expected coreset size depends on the sum of 4s's. In the next lemma prove that the scores 4,'s defined in BregmanFilter upper bound the online sensitivity scores of a,, i.e. fx(a:)
suPxERtxa Fx(Ai-1) and also show that the sum of I 's is also bounded.
Lemma 4.4. For every incoming points a the defined in BregmanFi Iter, upper bounds the online sensitivity score. Le., Vi [m),
fx(ai) fx(1: + for (A.) S4
sup x
(2)
Furthermore,
Σ 4 (8logn 4log (A)) 4 log (fMz(a2)) (az)) //- 65n
8

---

Published in Transactions on Machine Learning Research (07 (07/2022)
Proof. At step i, let M,) be the parameters such that, Va, A and VX, 1ufx 1u.fx. (ay)) S fx(a,) S fx (aa)
and pp E, ai Now for any query X E Rexd each point aj A has some closest point XI E X. Now for such pair 1 xi,, xi), using the property (lla+bbl)² = +|bb|)) ) we have fM (p:) S 2 (2)) fM (aj)) = ( (5x (a,) +1p
So by taking into account for all the points in A; we get ( (p.)
2 (A M. (A.-1). We use this triangle inequality in the following analysis, which holds VX E Rexd,
pi
fx, fx (A, + (A,)
K/
1x (a.)
xx + f:p: (A,)
2f Mi (a:) + 2/x (pps)
(x(A;-1) fe. (Ai)
M/ (a.) + S (Ai-1) + T-I - (Ai-1)
MM
Mi
IN
(A + fcp. (A.)
M (a.) + I-T
MM (Ai-1) + - M. (Ai-1)
( M.
(Ai-1) + M.
(A.))
x
2% (a.) +
3-1 fm (A,-1)
4
{-1 IX
MM. (A,-1)
M4 (A,-)) + S (A.))
|:(fx
(A,-1) + fM (A.))
2fM (ax) + -- (A,-1)
4
( (Ar-1)
+ f (A.))
Ms(i-1) (1)
2 (ax)
A (A;-1)
4
+
+
M.J. M. (Ai)
Me (A.)
Ms(i 1)
2 (a.)
8
H.SP MM (A,)
Mi
2 (a;)
8
IN
+
Mi E M, (ay)
Mi(6-11
The inequality (1) is due to μ similarity, i.e., fx(a:) S /M (a.). Next couple of inequalities are by applying triangle inequality on the numerator. In the (ii) inequality we use the br similarity to get lower bound on the denominator term. We get (iii inequality by upper bounding the second and third term by 4/(u( 1)). By the property of Bregman divergence we know that 9i-1 arg miny fx(A,-1) and, so we have før (A.) fo (A;-1) + Jo. (a:) 2 f (Ai-1) + Sex (a:). So by induction we get (A:(A) 2 Se,
My (ay) which can be maintained as running sum hence Vi, the score 4 can be As, (M.(A.) (A,,) 2 Ejst computed in just one pass.
Next, in order to upper bound Eisn 4, consider the denominator term of 4 as follows,
M, (ay) Σ 151
M, (ay) + eM: (a.)
=
M MM. (a.)
My (aj) 1+
Σ Σjsi-1 M, (aj)
1
S.M. (at)
Mi (a))
11 Ejsr Mi (aj)
1
Σ
Mi (a)) (1))(1 + +.))
151-1
exp(qi/2)
Σ
M (a))
151-1
9

---

Published in Transactions on Machine Learning Research (07 /022)
Mi Ejst Jog (a,)
exp(q:22
Σ jis-1 1 l:3 (pa)
po (a.)
where for inequality (i) we used that qi =
I 1 and hence we have (1+ 2 exp(q:/2). Now as
E5g, Foj (ay)
My we know that Ejst Joy (ay) 2 Ejsi-1 S4g (ay) hence the following product results into telescopic product and we get,
M:
M, Ejsn (ag)
exp(a:/2)
MMa (az)
25
So by taking logarithm of both sides we get E2sign di S 2 2og (fg (A)) 2 2og (JMa Further incor- porating the terms (1(1-13 we have 4
8
20: piff-jj Hence, Eesign 4 S 4u (log log (J& (A))
log (az))) Where μ pn S h and M = M, 2 M, for all i S n.
Note that the upper bounds and the sum are independent of k (#clusters). Now in the next Lemma we show that by sampling enough points based on 4i, we get equation [
Lemma 4.5. In BregmanFil Lter, setting r o( dolllo k) (o
the returned coreset (C, (2) satisfies the
following guorantee with at least 0.99 probability vX E Rexd
-x fx(A) S (f(( -
(3)
We proof this lemma by applying Bernstein's inequality on the following random variables
with probability with probability (1- - p.)-
w;
fx,)
A detailed proof is discussed in the appendix
A.1.1
Now using the Lemmas 4.4 and
4.5
we have the following main theorem of this section.
Theorem 4.6. For points coming in streaming fashion, BregmanFil lter returns a coreset (C, Q.) for the clustering based on Bregman divergence such that for all X E kxd, with least 0.99 probobility it ensures the following guarantee.
[x(C fx(A)l c(x(AA) fc(A))
Such coresct has 0( ddc(log k) log(1/c) (logn + log (A) log (a2(())))) expected samples. ue*
BregmanFil ter lakes (d) update time and uses (dd working space.
The expected sample size of the coreset (C, returned by BregmanFilter is bounded by Eisn 4. Using and Lemma 4.4 and Lemma 4.5 we obtain the expected sample size to be Of dd<llo k) log(1/c) (log n log (fM
we²
log (fM: (az)))) Further, by using the p-similarity expected sample size is also o( log (fo(A)) log (fez
ddk k) log(1/r)
(log +
The algorithm requires working space of O(d) which is to maintain the mean(centre) Pi; p. M, (sparse matrix) and the running sum S. Further for every incoming point BregmanF Filer only needs compute the distance between the point and the current mean henee the update time is just O(d). So the running time of the entire algorithm is ((dd), which is why is easy to scale for large n. Note that although Theorem 4.6 gives the guarantees at the last instance, but using the same analysis technique one can ensure an equivalent guarantce at every 4t instance by taking an union bound- this requires an extra multiplicative factor of log(n) in the sample size. By doing so, (C,, P4) satisfies the following for A,, Vi E [n] and AX kxd with at least 0.99 probability,
10

---

Published in Transactions on Machine Learning Research (07 (07/2022) /022)
|/x (C, -xx(()))))x(A))) x + (A,(A.))
(4)
Note that BregmanFilter returns a smaller coreset C compare to offline coresets Bachem et al. (2018b); Lucic et al. (2016) but at a cost of additive factor approximation that depends on the structure of the data. Further unlike Bachem el al. (2018a); Lucic et al. (2016) our sampling complexity only depends on 1/H. BregmanFilter can be easily generalized to create coresets for weighted clustering where each point a, has some weight w, such that fa,) w; minxex do, x). While sampling point (say a:) the algorithm BregmanFilter sets a, and W, wa/ps with probability P..
Notice that the additive term (second term) in the guarantee of Theorem 4.6 depends on the variance of the input data. So it can be significantly large compare to the relative term (first term). One way to address this issue is to use an user defined parameter T E (0, 1) to reduce the effect additive term. In the algorithm
( (a.)
BregmanFilter, one needs to update 4 P.T5 guarantee.
+ PT + 1). In the following corollary state
Corollary 4.1. For points coming in streasning fashion and with the above change in BregmanFis I tee, the algorithm returns a coreset (C,9) for the clustering based on Bregman divergence such that for all X lRkxd with at least 0.99 probability it ensures the following guarantee.
()x (x(A)l S (/x(A) + (s)(
log (JM(A)) -log (12g (22)) expected samples.
where è' c.c. Such a coreset has of b) (og( (log n +
jic
It takes (d) update time and uses (dd working space.
The proof is similar to the proof of Theorem 4.6
Here, an important change in the analysis is that instcad of equation 2 we use following sensitivity function,
fx
sup XER (x(A, + (fp.(
(5)
In the appendix we first present the upper on these scores followed by the proof of the above corollary. Note that with an increase in the coreset size by a factor of 1 one can improve the additive error guarantee by a factor of 7.
4.1 Online Coresets for k-means Clustering
In k-means clustering, most commonly used Bregman divergence measure is the squared euclidean distance. Now for squared cuclidean distance we know that, M, Ia and 14 1, Vi [n]. So in this case the algorithm BregmanFilter does not need to maintain M, and pt. In the following corollary we state the guarantee of Bregman Filter for k-means clustering.
Corollary 4.2. Let A E Baxd such that the points are coming streaming manner and fed to BregmanFilten it returns a coreset (C, which ensures the guarantee equation 1 VX E R with prob- ability al least 0.99 for the k-means problem. Such a coreset has O dk(llog k) log(1/e] (log n + log (A²(A))
log (az))) expected samples. The update time is ((d) time and uses O(d) as working space.
Proof. The proof follows by combining Lemma 4.4 and Lemma 4.5 As k-means clustering has M, = I and #4 = for all i S n, the upper bound on the sensitivity scores is just,
(a.
8
1, 4- EEst (a)
i--
It can be verified by similar analysis as in the proof of Lemma 4.4 The proof of the second part of Lemma
4.4 and Lemma 4.5) will follow as it is. Further note that k-means is a hard clustering hence the e-net
size is O(e k). Hence the expected size of C returned by BregmanFilter is Of dk(log k) log(1/e) loggn +
log (A)) log (f (a2) Further, similar other p-similar Bregman divergences, here in this case also the update time is ((d) and uses a working space of Odd).
11

---

Published in Transactions on Machine Learning Research (07 (2222
5 Coresets for Non-Parametric Clustering
For data coming in an streaming fashion, it is extremely challenging to anticipate the value of k with having some domain knowledge. For such an input one requires to solve non-parametric clustering problem, i.c., the problem is find a clustering as well as a value of k.
Our previous algorithm BregmanFilter requires such k and the size of the coreset returned by it depends on such & (#chusters). It is mainly due to the union bound we need to take over a set in the query space (e-net). Here we explore the possibility of building coreset non-parametric clustering problem. Naturally the size of such coresets are independent of any k. However, it ensures provable guarantee for any query X with al most centers.
Even showing the existence of such a coresct is not obvious. It is not difficult to realize that it is impossible to get a sublinear sized coreset for non-parametric clustering which cnsures a relative error approximation. The following example illustrates this. Let A be set of n points and let C be a set of size m with weights Q where m o(n). Now for (2) to be a relative error coreset for non-parametric clustering, it must ensure the following for all X with at most rows,
(fx (x((A
However, notice that no matter what the set C is, the above claim is false when X C. This because for such a query X the total cost (x( 0, whereas fx(A) + since m = o(n).
5.1 Existence of sublinear sized coresets for non non-parametric clustering
In this subsection, we show the existence of coreset for non-parametrie clustering that ensures an additive error approximation guarantee. The proof for this will proceed via the probabilistic method- we will design a set of sampling probabilities that will be used show the existence of the claimed coreset. The main novelty here is that the sampling scores not the usual sensitivity scores Feldman & Langberg/ (2011), which are defined for all the data points all al once. In contrasi, we define the scores iteratively for every step i, we define a score for the tt point, and this score depends on the coreset maintained by the algorithm till this step, i.e., these scores are also random variables themselves. We will then show a bound on the expected sample size.
At cach step we define two sensitivity scores called barrier sensitivity scores. We start by defining barrier sensitivity scores.
Definition 5.1 (Barrier Sensitivity Scores). Let A,- be the set first set of (i-1) points and (p; = Eise a,/i be the mean of A,. Let (C,-1,54-1) be a weighted subsample of A,-1- Al. step i, the upper barrier sensilivity s/ supx r/ (X) and the lower barrier sensitivity st supx (X), where:
fx
(X) (1+))x((A--1)
(6)
fx( (C 24-1) (A,)
fx (a:)
(X)
(7)
[x(C,-1, - (1 () + (f
here sup is over all X with at most centers.
Note that unlike the regular sensitivity scores, the above scores are neither guaranteed to be non-negative nor bounded by 1, if the sets C,-1 and weights Ω-1 arbitrary. Our algorithm will, however, maintain an invariant (which is effectively the "coreset-property" of (C-1) that guarantees the non-negativity of the scores.
We will sample points based on the upper bounds on the above barrier sensitivity, and show that the resulting set is a coresct for nonpparamctric clustering. A similar tochnique has been used in (Cohen et al.) (0166) build coresets for spectral approximation for matrices. In case of general cost functions, especially Bregman divergences, getting nontrivial upper bounds (i.e., bounds less than 1) on ay and of is very challenging.
12

---

Published in Transactions on Machine Learning Research (07 (07/2022)
In order to show the existence result, assume that have access to oracle that returns upper bound on these sensitivity scores. Utilizing these upper bounds, we show the existence of coreset. for the non- parammemiiii clustering problem. We later show that under some assumption we can get an upper bound on these scorcs and theroby getting an algorithm that returns a desired corcsct the problem.
5.1.1 Algorithm Overview:
For every point a,, asstmme that the oracle returns 3 and á such that 37 oe and b 2 st. Define pe and as follows- P: = min(1, 8² + c where c* = 2 + 1 and d' = 2 -. Define pi We sample to be in the coreset with probability pi and give it a weight wi if included. Such a sampled set of points are going to ensure the guarantee in the following theorem.
Theorem 5.1. Let A E Rnxd, for every Bregman divergence dæ as in table the above sampling technique returns a coreset (C, such that VX with at most n centers it ensures.
1/x(C,9) - (x(() S ((x((A) + (A))))
(8)
The expecled size of such coresel is 0 pe (log + log (J)) - log (J (a2)(()))
Note that the above guarantee equation is deterministic, but the coresct size is a random variable. To prove the above theorem we use the following supporting lemmas. We first show that for each point a; if अ and & upper bound the sensitivity scores Sf and sy then the sampled coreset would guarantee that equation f holds for all X with at most centers.
Lemma 5.2. Suppose the oracle returns 8 and 8 such that, Vi E [n].
fx()
sup (1+ (1+e)fx(A(-)) fx 94 (Ap, I 8)
fx(a,)
sup - -1- (Ai tE
Let é >> 0. The sampling probability for first point is p 1, and for the ith point is min(s;, 1) where 8; = 3 + c's,, such that c² = + and e' = - -1
It maintains,
(C,, R.) (4--1, 1 if sampled,
(4-1,
else.
such that VX with at most n centers it guarantees
[x(C,, -
-x fx(Ai) SEAA))EeeCCC
Proof. We show this by induction. At i this is true, as we have P1 = So we get,
- f))x((a)) S fx(c), S (1 +x)x(((a))
(9)
where C₁ = aj and W1 1. Now consider that at i the tuple (C,-1, 14-1) ensures
Ifx(A,-)) - (x, s (A,-)) + f ( (A+-1))
(10)
We show that (C,, 22) also holds a similar guarantee for A,. Recall that we need to show that upon creating the sampling probability (and weight) by using an upper bound on the barrier sensitivity scores, no matter whether the random process samples the point a, or not, the tuple (C,, 2.) will ensure the desired guarantee. Recall that the sampling probability pt min(1, c" +d3/). We first take the case when p. 1, and hence C; a, and Wi 1. So we have,
Ifx(A,-1) 1.
c(Jx(Ai-1) + S (A:,(A)))))
13

---

Published in Transactions on Machine Learning Research (07/2022)
- d + fpL (Ai-1))
(fx - fx(C
(Ax (x(C
Here, (i) is true because
/x (a:) = /x(ci, wi). In (w) we only increase the RHS, because Se. 2 fer (As-1) (Observation 4.2 and fx(a)) 2 So, finally we have,
(1-c)fx(A)) efp. (A:) - (.) S +
Next when Pi < 1 then for the upper bound we use the upper barrier sensitivity definition i.e., 8,'
2
Using the definition of 8 we have that VX,
(
fx (1 (1+))fx(A fx 1, - (A.)
pt
fx(a,)
(1+))x((A-))- fx(C (+ (Ai)
Pi
> 14-1-1, fx(a,)
()+))/x(A elp: (A:)
pi
Now, if a; is actually sampled, (4-1) fx(m)) = (4), and hence,
P
+ 2 (x, (1+ ( (A,) 2 fx (4)
This shows that the upper bound claim is true with a, is sampled in (C,, St)). In case that p and a, is not actually sampled, we have fx (C, 22) fx( 1 Q4-1 Jand hence follows immediately from above. So, when pt < 1, irrespective of being sampled in (C,, Q.) or not, the desired upper bound claim for A; holds.
For the lower bound we use the lower barrier sensitivity definition i.e, of in a similar manner-
1
fx( ((C1-1190-11)) - e) (Ai1)) + (A,)
1
2
fx -x(( (1--))-A)) (A, efp. (Ai)
2
fx(a:)
(4-1)
N
(1 -x)x((A()))) (fa, fx(a:)
1,,
(1 (1- (),x(A,) (ff;
When the point a; is not sampled in (Ci, P2) we have (C:11, = (C,, 24) and hence we have our inductive step. If a; does get sampled than (x,C,, 2 (, Hence in both the cases we have that
fx (C, 2 (1- (A.
This completes the proof of both the lower and upper bound for the ith step.
There are two important points to note from the above lemma.
Since, the oracle is giving an upper bound on the barrier sensitivity scores, so the coreset guarantees are deterministic. That is when, pj < then irrespective of a, being sampled in the (C,, or not, always ensures the guarantec. It implics that we run this process multiple times on the same data stream, then each time we get a different coreset but each coresct ensures the desired guarantee with probability
14

---

Published in Transactions on Machine Learning Research (07 (07/2022)
Due to the barrier sensitivity score based sampling, the coreset guarantee holds vX, and we do not require the knowledge of pseudo dimension of the query space. This intuition is similar to the deterministic spectral sparsification claim in (Batson et al. 2012).
Next we need to analyze the expected sample size. Note that, unlike the the online sensitivity scores in BregmanFilter, the barrier sensitivity scores themselves are random variables, and depend both on the order of the imput stream as well as the previous sampling decisions while maintaining (,,-1, Qi-1). Next, show that the expectation of these scores can be bounded, hence giving bound on the expected coreset size. We first present supporting lemma.
Lemma 5.3. Given non-negative scalars 3, u and w, where q, and w are positive, we define random variable t as,
q
with probability p.
v
with probability (1 - p)-
If q
then we get,
8 t
pu + (1 - p)u we
E
9+ w
u)(1 v) q w
The proof discussed in the appendix (A.2.1p. Let II,- E {0, 13/ be the sampling decisions (0 and 1 indi- cating the not-sampled/samee sampled decision respectively) that the algorithm made while creating (4-1), based which the sampling probability of the next point a, is being computed. The coordinates of 11, will be denoled as ,I....,7.. Wí.
Before bounding the expected barrier sensitivity scores we first show that the at any step i, the upper bound on the expected sensitivity barrier score is independent of the sampling choice made by the algorithm in the previous slep for the point a;-1- Recall, e* ? + and ex = 1, for which we show a helpful lemma.
Lemma 5.4. For any step j 2 1,
fx(a)) P)+1 (==1((//2//((A-11 + (1++/2)fx(A - $
1
ca
fx(
PS+1 (f=1 ( (1-
Again the proof delegated to the appendix [A.2.2p. p. Next we show the following lemma which provides a bound on the expected barrier sensitivity score. The detailed proof is discussed in the appendix (A.2.3).
Lemma 5.5. For points that are coming in stream, let 2 j + 1, and let πJT1 denote the sampling choice that the algorithm has made at (j + 1)th step. Then we have,
fx(ax)
fx(a:)
2 1++1 + (Ai)
2 1s + (A,(),
fx(a:)
fx(a:)
Em Enjar
- + (Ai)
M + CSa (Ai)
In the following lemma we bound the expected barrier sensitivity score with a term independent of any sampling choice made by the algorithm until then. Finally, it yields the expected sample sizc.
Lemma 5.6. Let A be set of n points each in Rdd, For point a and for all X ggxxd we have following bound Vi E [n],
fx(a:)
M (a;)
12
En
+
(1 (1+))x(AA-)) - fx 1,-1,,114111 R4-1) (A,,
p4c Σ 1 f (ay)
Hic(i -
fx,
2/M (at:)
12
Em
+
(--1-1,,9111) - x)/xx A (A
Pic Σ M,, (az)
uuveli - 1)
15

---

Published in Transactions on Machine Learning Research (07 (222)
Proof. Due to lemma 5.5 we show that expected sensitivity score for any a, is independent of the sampling choice made by the algorithm for a;-1 point. We show the result for the upper barrier sensitivity score. The analysis for the lower barrier sensitivity score is very similar which can be found in the appendix [A.244]
Let (1+ + =) (x = (x(A))) where fx(A = Ej fx(a)). Here each term fx(a)) = (1 (1+c-p7))fx(20 if a, is present in C clse fx(aa) (1+c) (x)))(aaa)) Now the expected upper bound on the upper barrier sensilivily score can be bounded as follows.
fx(a,)
M. (a.) fx (A v cf (A.)
E1:-1
ETI-1
X
(x(A + cf (A;)
2 (a:) + 1-1 Σ a. EA. (P + fx (ay))
Br--1
ITi-2
(1 + c) (A (Ai-1)
+ (Ap)
2 (a.) + 1-T E Ea,E3
Ea,EA Ea,EA.11 lp: (ay)
1T
c) 1) fx (C 94--1 + 8ppp (A:)
1x (Ai- 1)
Er--1
7-
11
(1+c)fx A 1
fx (C,-1, 24-11 + cpp (A,)
(0))
Er,
2
pc
(a.)
+ 2-
fM (Ai-1)
I
1,:1 + Spp Ai))
T- A (A;-1)
+
ET--1
11
M + Espp (A,)
(10)
2f (a.) + 8-1 s.
4
(A
Ex,-2
11--
The 1,5- + efp (Ai)
M. (A:-1)
E Ex--1
11
7--1,-2 {Sps (As)
2// M. (a:) + - A (A,
1 M.
(A,-1)
x
Ex0
E
11.0 + tffp,(A)
1 Efp. (Ai)
2 (a:) + 1- S (Ai-1)
pM.
(Ai-1)
(1-1
e/2fx (Ai-1) + Effo (Ai)
e/2fx(A,
+ Ef (Ai)
1A 3V3
2.
M. (a:) + 5-T
4 Mi (Ai-1)
I- / M. (Ai-1)
(0.5
X
M.
(A; + Ma (A:))
(c.
M. (Ai-1) ) + +-A (A.))
M (a,)
4fM
(A,-1)
81 (A;-1)
M.E PI
M. (A.)
(ie(i
1)SM
M (Ai)
mieli 1)5xx M. (Ai-1)
(144)
2 (a.)
4
+
+ ();e(i - 1)
MLE J M. (Ai)
1ucc(i 10-1 1)
2 (ag)
12
PGE Ejsi Soy M,
(ay)
Mieli - 1)
The inequality (i) is by upper bounding Bregman divergence by squared Mahalanobis distance. The inequal- ity (ii) is due to applying triangle incquality on the numerator, (a² + b²) < 2(a² + b²). The (ii)) equality is by replacing the denominator with the above definition. The (iv) inequality is by applying the supporting Lemma 5.3 By recursively applying Lemma 5.3 we get the inequality (v) which is independent of the ran- dom choices made by the algorithm. The incquality (wi) by using the lower bound on the denominator. The inequality (wii) an upper bound on the second and the third term. In the final inequality we use the fact. that for any i similar Bregman divergence from Ackermaan & Blömer (2009); Lucic et al. (2016) we
16

---

Published in Transactions on Machine Learning Research (07 (07/2022)
have M, 3 M, for j i (Lemma Further by the property of Bregman divergence we know that fe. (A,-1) 2 - (A,-1). Hence we have fpt (A,) 2 Ejgide (az). Notice that the above analysis also true for all X. Hence we have this upper bound for all X with at most n centers. So we have the,
(x:)
(a,) S Ejgi (a,) di ((--1) 1)
12
En, (1+)) (e (A.)
Note that the analysis holds for all X. Hence we get the expected upper bound on both the barrier sensitivity scores. Further, these upper bounds are independent of k, which is number of centers in or any bicreteria approximation that usually depends k. Now as the oracle returns light upper bound the sensitivily scores which is used to compute the sampling probability of streaming point, the expected sample size by bounding the sum of upper bounds of barrier sensitivity scores.
comment about
Lemma 5.7. The algorithm returns (C, Q) such that the expected size of C is O (log nogn+logg (fe
log (J (az)))
The detailed proof is discussed in the appendix A.2.5
Now we are ready to prove our main theorem.
now show that the any coreset created by the Since the coreset guarantees hold deterministically, there must exist a coreset with size less than the expected bound that satisfies the guarantees. This completes the existential guarantee stated by Theorem 5.1
Proof. of Theorem 5. Using lemma 5.2 and 5.6
algorithm satisfies the guarantees in Theorem 5.1
5.2 Coreset algorithm for non non-paramctric clustering based on empirical sensitivity
Now as it is not known how to get an oracle that upper bounds the barrier sensitivity scores, we present a houristic which works well in practice. We estimate the sensitivity scores using sampling, and call these empirical sensilinily scores.
We first give an example show that the sampling probabilities in the online setting need be upper bounds to the barrier sensitivity scores.
Example 5.1. Pir any e 1). Consider simple selup where the first point is Rdd Now the algorithm samples the point in the coreset with probability 1.
Suppose the second point is b E Rd and suppose that the upper barrier sensitivity for it, achieved by the query X", equals s. That is,
= sup (X) = (X*)
Now, suppose we sample b with some probability < 5. Thus,
fx- (b) (1+ fx (a) + + (((
p
fx-(b)
(/x-(a) + (e((((a) + [o(b))
p
(fx-(a) + (c(s((a) + fo(b)) < fx-(a) fx-(b)
which violates the coreset property. Hence, when we sample the second point, which happens with probability p, we do not have a coreset with the desired guarantee.
We next present an example which shows the difficulty of estimating the barrier sensitivity scores by sampling queries. This will motivate to make some assumptions about our data.
17

---

Published in Transactions on Machine Learning Research (07/2022)
Example 5.2. For fized point a, and query space, let ri (X) be random variable defined equation 6 where X is chosen randomly from the query space. Consider that we do not have access to the sensilinily score S; supx T." (X). Our proposed algorithm is to sample a random set of queries y uniformly at random such that the marimum value of (-) in y well approzimates 8t.
Define the empirient upper sensitivity score to be & maxxey (X). Note that if X" belongs to y, then 5; Si, but this is very low probability event in general. Consider the set B {X| r (X) 2 s for some K >> 1. If the sampled queries do not contain any element in B, then 8, 8,/ K. Thus the probability that this sampling based algorithm obtains an estimate & that sotisfies š; st/ K is eractly the some the probability mass of the set B. Note that the first enample shows that with s; = 1, if 5; 1/K, then using K&; as sampling probabililies, we fail to have coresel.
From this we conclude that, in order to use an empirically obtained upper bounds on the sensitivity scores (called empirical sensitivity scores), we need additional assumptions to show that we get valid coreset with desired guarantees. We now state the assumption, originally in (Baykal et al. 2018
Let X' represent the query space where each query X E X' has at most n centers. Now, for each point a; and X, we consider the following two random variables, r.,( and r((X) defined as follows,
fx (a:)
(X) = (1+,)(((A,-)) /x (C,-1, 94-1) + (S
fx(a:)
(X) =
- -1-x)x)A-)))x(
where the randomness over X E X. We assume that the CDF of both r.) and rí(-) are bounded. The assumption stated below is for (.). A similar assumption is also considered for r.()). Assumption 5.1. There is pair of universal constants K and K' such that for each i E [n], the CDF of the rundom variable r (X) for X E X denoted by G.() satisfies,
Gz(z" /K) S
where x²' = min E [0, G.(y)= 1}.
Further, we consider the above assumption is true for all a, E A. Now the following two lemmas are similar to lemma 6 and 7 in (Baykal et al. 2018), using which get the upper bounds on the sensitivity scores. Here we state them for completeness. Lemma 5.8 is stated for all i S n.
Lemma 5.8. Let K, K' > O be universal constants and let X be the query space as defined above with CDF G.() salisfying the ussumplion 5.1, Led y [X,, X Xm) be a set of m i.i.d. sumples each drawn from
X. Let X be an i. sample from X then,
PP(K max r. (X) (X 1)) exp(-mm/ (a)mm//KP(() K' max (x) (((m))))) S exp(-mm) XEY
Xey
Proof. Let Xmax = arg maxxey, ri (X), then
[ P(r (Xmax) S K|r (Xm+1) w)dP(1)
P(K max (X) 5 r3 (Xm+x)) X
P(r (X S RM dP((y)
(4)
(k(z"/K)" [-" dP(v)
Gi(z"/K)a
< exp(-m/K")
Here (i) is because (X,,X, ..., X are i.i.d. from y. Further (ii) is due to the assumption 5.1
18

---

Published in Transactions on Machine Learning Research (07/2022)
Algorithm 2 NonPaaaaettricPilter
Require: a; ,,,......., n;t > 1; (); (X1, X....., (o(log(n/6))
Ensure: (C,9)
e² =2/c + 1; 2/c 1:40 0,5 C ... 2 = 0
A = ||a |miii // |ai |max
while i S n do
A= min || v= = max (v; ||ai||max
Update M; 144 = A/v
;i = ((i - 1) + a;)/i; S (.p.(aa)) (
if 1 then
P; =
else
F maxxxy)::0 (X)
7 = mAxxEy (X)
= min(1, (c" + c
end
(ap))((p))
if a, is sampled
(c)
())
else
(C,, 1, 22-1)) (c,,w,)
end while
Return (C)
Similarly, it is also proved for r¹0. Let there is a finite set y C X' from which we get empirical sensitivity scores Fy = maxxgyr;( and F. = r( Our algorithm uses these scores. Now with the following lemma we establish that empirical sensitivity scores are good approximations to the true sensitivity scores s/ and s/. It is also usod to docide the size of the finite set V.
Lemma 5.9. Let 8 (0, 1), consider the set y X of size ||] 2 [K' log(n/0)], then
Pxxx E [n] KFt < r (X)) < 6
Pxex (i [n] ki (X)) 5
Proof. The proof follows from lemma 5.8 Let the event & be the event that K mmxx xx S (X). Now,
P(EE) = Pxxx
max r (X') S r (X)) S exp(-1D'//k) X'EY
Hence, by taking union bound over all i E [n], we have that Pl-(U,&)] 2 1 n exp( exp((-)))/"'). By choosing DI [K' log(n/6)],, we get that P[-(U,&,] 2 1- 6. Hence with probability least 1 6, the score Ft upper bounds the true score. We can show similar claim for r/.
So with high probability we have an upper bound on s|) using empirical sensitivity scores (FY, (P). Al- though the above two lemmas are stated for upper barrier sensitivity scores, they are also true for lower barrier sensitivity scores. Now we present our second algorithm 2 called NonParametricFilted which returns a coreset for non-parametric clustering via. Bregman divergence. Note that without the above as- sumption s. algorithm acts as heuristic. The algorithm requires the query set y which has (log(n/6)) queries.
The coreset from the above algorithm ensures the guarantee.
Theorem 5.10. Let A E Baxd for every Bregman divergence dæ as in table 1 MonParraettricFittee re- turns a coreset (C, Ω) for non parametric clustering based on do such that VX with most n centres in Rd it ensures equationn 7 with at least 1 probability.
[x(C)= [x(A)) (((x(()) + (c(A))
(11)
19

---

Published in Transactions on Machine Learning Research (07/2022)
The size of such a coreset 0 ( nez logn + log (A)) - log (f (ae))) expected samples.
Proof. This is proved by combining the claims of Theorem and Lemma
Again the additive error factor can be further improved using an user defined parameter E (0,1), 1). In the barrier sensitivity scores equation and equation 7 we multiply T with the additive term, i.e., efp, (Ai) is replaced with Tefp, (At). We get the following corollary.
Corollary 5.1. Let A E Ruxd, for every Bregman divergence d& in table 7 NonParametricFiiler re- turns coresct (C,0) for non parametric clustering based on do such that VX with at most centres in E it ensures equation 7 with at least 1- 8 probability.
(x(C)-fx(A)) S SEfx(A) (efx(A)+eTT(AA))
-
(12)
where e' T. The size of such a coreset is O 1ue (logn+
-log log (A)( -log (12g
(ax))) (10)((zz) )) expected samples.
This can be proved by a similar analysis as of Corollary
5.2.1 Nan-merrc Clustering via Squared Euclidean Distance
As MonParametricF1let filter returns a coresct for non-parametric clustering, hence it can also be used for k-means clustering. In this case our algorithm (2) returns a coreset (C, for squared euclidean Bregman divergence. The algorithm simply uses Ia as M, and 1 as p4. In the following corollary we state the guarantees that NonParametricciitee ensures for k-means clustering that follows from Theorem 5.1
Corollary 5.2. Let A Raxd be the points fed to NonParametricct ller for the k-means problem. It relurns coresel (C, which ensures the guaranlee equalion | for any X with at most n centers. The coresets has 0 logn + log (fo(A)) - -log (fez (a2))) expected samples.
This directly follows from Theorem 5.1 and discussed in the appendix A.2.6
5.2.2 Coresets for DP-Means Clustering
DP-Means clustering is a parameetii clustering. Here we discuss how NonParametriiFiiterr can also be used to approximate DP-Means clustering Bachem et al.) (2015). The problem was originally defined for squared euclidean distances which has a valid generalization in other Bregman divergences. For an input A, query X with at most n cost of DP-Means cost is defined as follows,
costpr(A, = fx(A) + x
Here fx(A) is the cost on the entire A based on some Bregman divergences introduced carlier. It is not difficult to see that the coresel from NonParametri wet.mmrricllleerrree ensures an additive error approximation ion for this definition DP-Means clustering based on j-similar Bregman divergence. Now we claim that by allowing a small additive error approximation our coreset size significantly improves upon the coresets for relative error approximation for DP-Means clustering Bachem et al. 2015 as in practice (ddt) > O(logn). We first the state the following result.
Lemma 5.11. The coreset (C, from NonParametricFi ensures the following for all X with at most centers in Rdd
|costpr(C. (A) S f(
Proof. Notice that if one applies DP-Means on the corcsct from MonParanetricFilterr get the following,
poost (C, (C,X)
=(f (f
The last inequality by Theorem 5.1
20

---

Published in Transactions on Machine Learning Research (07 (0222)
Now due to Lemma 5.11 we have the following Theorem.
Theorem 5.12. For CE (0, 1) the corsset (C, ensures, costDr (A, I (Ast + cffx (A) fxA (A)+ with high probability, where Xc and XA are the optimal cluster centers for the DP-Meens clustering on (C, Q) and A. The expected size of the coresel is O logg+log (JO² (A)) -log (J0z (az))
Proof. Let X and XA are the optimal centers for DP-Means clustering on C and A respectively. Now we know that,
(sstrr(AXee) c(xx + +
costpr Costpr(C,Xel C,Xc)
costpr costDp(C,XA) (C,XA)
(astpp(AXt) XA) + e(fxx (A)+ fc(A))
costDP(A,
costpp(A, (eeXxx+((((xxce)
e(/ (Ax (56(A)).
6
Uniform Deviation
Our first result showed an additive error coreset for Bregman clustering. It is natural question ask whether additive error that is function of (A( is useful. In this section we provide evidence that when looking at Bregman clustering from the generalization perspective, the generalization error obtained is also function of (A). This implies that clustering by using coresets of the training data (rather than the full data) does not increase the generalization gap.
For a given distribution of input sets and a learnt model, the uniform deviation is the difference between the expected loss and the average empirical loss over set of samples from the distribution of inputs. is used understand the generalization error by trained model. In this section we show that for clustering based any p-similar Bregman divergence the uniform deviation is bounded. For distribution D over input space in R4 and some j-simmilar Bregman divergence (Table D let & EEED [a] and o² = (aED)/{(a)] Bachem et al. (2017a) showed that for k-means clustering using Euclidean distance, if Ene < t < co, then with sufficiently large number of samples A = {ai...., am where each a, is an i.i.d. sample from D we get the following VX E Rxd with a constant probability,
and m =
[tkdlog 1lk log
22
m Σ fx(a) E[fx < E[fx(a)))
(13)
m
This essentially implies that there an additive error approximation on the generalization error by a model trained on large input set. We show that similar result is also true for other p-similar Bregman divergence. The additive term (c-o2) in the generalization crror is very similar to the additive term (e fc(A) in coresets guaranlees equation D
Given the D, the randomness is always over the samples from D. So we use E[| instead of E.cp[:]. We consider that for any 4-similar Brogman divergence we know the paramcters M and (1) for D such that for all a ~ D and x E Rd, uf (a) $ fx())= s fM (a). We also consider the following assumption true.
E (a)2
<0
(14)
12os
112
Here, = E[a], oM = - M(a {) -
and for all a ~ D, (a) = (a- - E). Consider A = (ai,..., } be m independent samples from D.
We analyze a family of functions 9 mapping from an input space Ied Rgo that captures a mcasure between the cost of a point discussed in the appendix A.3.1
D and statistical cost of D. We first state the following lemma, whose proof is
21

---

Published in Transactions on Machine Learning Research (07/2022)
Lemma 6.1. Let k EENNN N. Let D be distribution on R with μ and o² same as defined above. For p--similor Bregman divergence, for any point a ~ D, and any X E RRoxd we define 9x (a) as,
fx(a) 9x(a)= = 0² E[f((a)
(15)
Let s(a) 10
2fe(a)
+ S. Then we have (x(a) S s(a) for all X E Rkxd and =[s(a)"]=O01
For the family of function G (xx(-) X E [ J, let Pd) S Now due to above lemma can use the main framework of Bachem et al. (2017a) which is stated as follows,
Theorem 6.2. Let e (0,1) and G be a family of functions from to R20, where a D. Let p be such that Pdli((g) S < 00 and t be such that [[(s(a)] = (t).. For every a and X E Bexdd let s(a) be a function such that, supx 9x (a) S s(a). Let a.,..., a2m be 2m i.i.d samples from D where m = O ((4) such that
# S and P( 2m Emm s(a,)² > t) S 1/4. Then for all X E Rkxd with at least 0.99 probability
we have,
m
(a:) - S <elo2+B[fxx ([(((a))
(16)
m
The proof of can be found in the appendix A.3.2
7 Experiments
We now show the empirical performance of BregFilter (our BregmanFilter) well as heuristic version of NonParametricFiiter (NP-Filter). Since there are no existing online baselines for this problem, we compare it against the offline coreset algorithms on real datasets. It is important to note that thcoretically our coreset. can never perform better than the oflline coreset algorithm. Intuitively this simply is because an offline algorithm has more knowledge from the complete data before deciding the sampling probability. Here we investigate whether the performance of the BregFilter and the NP-Filter matches the performance of the offiine algorithms. We compare against the following coreset algorithms:
1) TwoPass: It is two pass algorithm similar to BregmanFilter. Here the algorithm knows y from pass and in the second pass it computes the sampling probability by using yp instead of yps for all i E [n].
2) LWCS: It is the offline lightweight coreset algorithm as stated in Bachem et al. (2015).
3) RelCoreset: It is an Offline sampling method that uses bi-criteria approximation Lucic et al. 2016 The resultant coreset ensures relative error approximation.
4) Leverage: It is just heuristic online sampling algorithm. Here we do Online leverage score sampling method as in Chhaya et al. (2020a). Note that leverage score sampling is only guaranteed to preserve the rank of the matrix, not the cluster structure.
5) Onl let al. (016)) which returns Ō(k) for centers. We consider the returned set as our subset of data and compare its performance with our coreset. In order to make this subset meaningful for the comparison we reweigh the selected points with inverse of the sampling probability (just like other sampling techniques). Notice that while the Ō(k) points returned by the algorithm have a bicriteria approximation guarantee, there is no theoretical guarantee that is available after doing k-clustering of these points.
This is also a heuristic online sampling algorithm. We run the Algorithm-3 in Liberty
Please note that except for Leverage and Online-K-Meand none of the other sampling method qualify as a baseline for comparison with our method BregFilter. Further, note that even though any oflline sampling method can be treated as a streaming sampling method using merge-and-reduce technique, however as these mothod allows the algorithm to discard a sample which might have been selected in the coresct at some previous step, so these sampling methods do not qualify as baselines for our online sampling method. As there are very limited baselines, so we compare with other offline methods such as LWCS and RelCoreset.
22

---

Published in Transactions on Machine Learning Research (07 (2222)
We compare the performance the following datasets:
1) KDD TRIINTRAIN); 145, 751 points with 74 features. We consider h = {100, 200} and squared Euclidean as the Bregman divergence (see Figure D. We further consider that the data points are arriving in streaming fashion. On this dataset we compare the performance of BregFilter with other algorithms.
2) MNIST: 60, 000 points 784 dimension digits dataset. Here we consider k {5, 10, 25, 50) and rel- alive entropy Bregman divergence (see Figure 2) On this dataset we compare heuristic version of NonParametricFilter with Uniform and TwoPass sampling algorithms.
Using each of the above described algorithm, we first subsample corescts of different sizes. Once we have the coreset, we run the weighted k-means++ Arthur & Vassilvitskii (2007) on them to obtain the centers. We then use these centers and compute the quantization error (Cs) on the full data set. We also compute quantization error by running k-means++ on the full data set (Cy). Finally we report the Relative-Frror y= -=IC,-Cyl/CC
In the figure ! the Y-axis represents the relative error 7 and the X-axis represents the expected sample size which is in terms of percentage of the full data, For every expected sample size, run 10 random instances. Using a parameter that controls the sample size, we ensure that the expected sample size of the 10 random instances are equal. Based on these we compute the average of these 10 events and report it in the plot. The figure shows the change in 7 with the increase the coreset size for = {100, 200} on KDD (BIO-TRAINN) datasets for k-means clustering. As the coreset size increases the 1 decreases for all the algorithms. As expected, the offline methods LWCS and RelCoreset perform relatively better than our BregFilter. BregFilter clearly outperforms the baseline Maline-K-Meand in terms of relative error at all sample sizes. We also compare with online version of Leverage score sampling which, empirically, appears to be competitive with our method. However, recall that the coresets from Leverage do not have any provable guarantee and it is not difficult to show bad input where Leverage will fail to return reasonable clusters, c.g. if the data spans a low rank space but has a large number of clusters. We present a toy example in the appendix.
Also note that Leverage and Online-k-Means have update times of (df) and O(kd) respectively, as opposed to the (d) update time of BregFilter On (DDIBIITTAAIN) for k 100 and expected corcset size as 1% of the data, the average running time of BregFilter is 2 seconds, Leverage is 5264 seconds.
is 379 seconds and
TwoPass
LWCS
Online-K-Means
Leverage
RelCoreset
BregFilter
KDD: BIO-TRAIN (k=100)
KDD: BIO-TRAIN (k=200)
0.5
0.4
Relative Error n
Relative Error n
0.4
0.3
0.3
0.2
0.2
0.1
0.1
1
2
3
1
2
% of data
% of data
Figure 1: Relative error v/s coreset size for squared Euclidean k-means clustering. We do not hope to beat the offline methods. However, we are at par with them. We are one pass.
23

---

Published in Transactions on Machine Learning Research (07 (07/2022)
For comparing the performance of hon-parametric coreset We run TwoPass, Uniform and MP-Filter MNIST. To the best of our knowledge there are no other baselines to compare with. In Uniform we sample each point with probability r/n, where r is a parameter used to control the coreset size and n is the number of input points. Now to capture the notion of coresct for non-parametric clustering we run k-means+++ on every coreset from each method for various values of compute the relative error 7) as described above. The computation of empirical scnsitivity scores makes the NonParammerricFltter computationaly expensive. The running time is Ö(n²). So run NP-Filter (heuristic version of NonParametricFiltee where use the upper bound of the expected barrier sensitivity
(5, 10, 25, 50}. Finally we
2/ (a.)
scores as in Lemma 5.6 to sample every point, ie., F. = = puc ". Joj (az) mel(i-1) for all i [n]. Hence
the running time of NP-Filter is just O(nd) and the sampling complexity of the returned coreset is controlled by the distortion parameter e. Now for every value of e we run 5 instances of the algorithms and report the average for every value of k. Notice that as we increase e, the also increases. This is due the fact that the coreset size inversely depends on e, so a high e results to a smaller coreset and as a result it incurs higher 7. It is evident from figure that even our heuristic perforrsss the Uniform and performs equivalent TwoPass.
E 0.25
E= 0.5
Relative Error
0.10
Uniform TwoPass
NP-Filter
Relative Error
0.2
Uniform
NP-Filter
TwoPass
0.05
0.1
0.0
10
20
40
50
20
50
Number of Centers (k)
Number of Centers (k)
0.75
Relative Error n
1
Relative Error
Uniform TwoPass
NP-
0.75
Uniform TwoPass
NP-Filter
0.2
0.50
0.25
10
20
30
40
50
10
20
30
40
50
Number of Centers (k)
Number of Centers (k)
Figure 2: Change in 17 with respect to #centers k for various
Please note here compare the performance in terms of relative error approximation, which is stronger than our actual additive error theoretical guarantees. The plot shows that even with small coreset sizes we get tight relative error approximations and thus supporting the theoretical guarantees.
8 Conclusion
Here we presented online coreset for clustering based on Bregman divergences. We also present the first algorithm for non-paramttric coreset for the same problem. The algorithm leverages upon additive error approximation, and uses barrier functions and empirical sensitivity scores.
Broader Impact Statement
We do not foresee any potential negative impact.
2coreset non-parametric clustering.
24

---

Published in Transactions on Machine Learning Research (07 (0222)
Acknowledgments
Anirban would like to acknowledge the following grants and the corresponding funding agencies Google India Faculty Award, Cisco University grant, SERRE-ATRICS grant, SERB-CORE research grant. Supra- tim acknowledges the generous funding from the European Union's Horizon 2020 research and innovation programmod under grant agrecment No 682203 -ERC-[ Inf-pooed-Tradcoff.
References
Marcel R Ackermmann and Johannes Blömer. Coresets and approximate clustering for bregman divergences. In Proceedings of the twentieth annual ACM-SIAM symposium Discrete algorithms, pp. 1088-1097. STAM, 2009.
16 and 33
Pankaj K Agarwal, Sariel Har-Peled, Kasturi R. Varadarajan, et al. Geometric approximation via coresets.
Combinatorial and computational geometry, 52:1-30, 2005. and 6
David Arthur and Sergei Vassilvitskii. k-means+ the advantages of careful seeding. In Proceedings of the
eighteenth annual ACM-SIAM symposium on Discrete algorithms, pp. 1027-1035, 2007. 23 and 37
Olivier Bachem, Mario Lucic, and Andreas Krause.
Coresets for nonparametric estimation-tha case of dp-
means. In ICML, pp. 209-217, 2015.
1
2
3
20
and 22
Olivier Bachem, Mario Lucic, S Hamed Hassani, and Andreas Krause. Uniform deviation bounds for k-means clustering, In International Conference on Machine Learning, pp. 283 291. PMLR, 2017a. and 36
6
21
22
Olivier Bachem, Mario Lucic, and Andreas Krause. Practical coreset constructions for machine learning. stat, 1050:4, 2017b. G]
Olivier Bachem, Mario Lucie, and Andreas Krause. Scalable k-means clustering via lightweight coresets. Tn Proceedings of the 24th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining,
pp. 1119-1127, 2018a.
2 and 39
Olivier Bachem, Mario Lucic, and Silvio Lattanzi. One-shot coresets: The case of k-clustering. In Interna- tional conference on artificial intelligence and statistics, pp. 784-792, 2018b. and 11
Mihai Badoiu and Kenneth L Clarkson. Smaller core-sets for balls. In SODA, volume 3, pp. 801 802, 2003. and
Arindam Banerjee, Srujana Merugu, Inderjit S Dhillon, and Joydeep Ghosh. Clustering with bregman divergences. Journal of machine learning research, 6(0ct):1705-1744) 2005. and
Artem Barger and Dan Feldman. Deterministie coresets for k-means of big sparse data. Algorithms, 13(4): 92, 2020.
Joshua Batson, Daniel Spielman, and Nikhil Srivastava. TaicenRamannjaa Sparsifiers. SIAM Journal on Computing, 41(6):1704 1721, 2012. 2
6 and
Cenk Baykal, Lucas Liebenwein, Tgor Gilitschenski, Dan Feldman, and Daniela Rus. Data-dependent coresets for compressing neural networks with applications to generalization bounds. International Conference on Learning Representations, 2018. and 18
Aditya Bhaskara and Aravinda Kanchana Rwanpathirana Robust algorithms for online k-mcans clustering. In Algorithmic Learning Theory, pp. 148 173, 2020. 6
Gérard Biau, Lue Devroye, and Gábor Lugosi. On the performance of clustering in hilbert spaces. IEEE Transactions on Information Theory, 54(2):781 790, 2008.
Christos Boutsidis and Malik Magdon-Ismail. Deterministic feature selection for k-means clustering. JEEE Transactions on Information Theory, 59(9):6099 61 10, 2013.
25

---

Published in Transactions on Machine Learning Research (07/2022)
Vladimir Braverman, Dan Feldman, and Harry Lang. New frameworks for offiiee and streaming coresct constructions. arXiv preprinl Xrxi 161:0062,00089, 2016.
Rachit Chhaya, Jayesh Choudhari, Amirban Dasgupta, and Supratim Shit. Streaming coresets for symmetric tensor factorization. In International Conference on Machine Learning, pp. 1855-1865. PMLR, 2020a. 22
and 38
Rachit Chhaya, Anirban Dasgupta, and Supratim Shit. On coresets for regularized regression. In Interna- tional Conference on Machine Learning, pp- 1866-1876. PMLR, 2020b. and
Michael В Cohen, Sam Elder, Cameron Musco, Christopher Musco, and Madalina Persu. Dimensionality reduction for k-mcans clustering and low rank approximation. In Proceedings of the ferty-seuenth annual ACM symposium on Theory of compuling, pp. 163 172, 2015.
Michael B Cohen, Cameron Musco, and Jakub Pachocki. Online row sampling. In Approzimation, Ran- domization, and Combinatorial Optimization. Algorithmss and Techniques (APPROX/RANDOM 2016).
Schloss Dagstahl--Lcibniz-Ze Zentrrrr fuer Informatik, 2016. 2 and
Devdatt P Dubhashi and Alessandro Panconesi. Concentration of measure for the analysis of randomized algorithms. Cambridge University Press, 2009. 28
Dan Feldman and Michael Langberg. A unified framework for approximating and clustering data. Tn Proceedings of the forty-third annual ACM symposium on Theory of computing, pp. 569 578. ACM, 2011.
and 12
Dan Feldman, Mikhail Volkov, and Daniela Rus. Dimensionality reduction of massive sparse datasets using coresets. In Advances in Neural Information Processing Systems, pp. 2766 2774, 2016. 6
Dan Feldman, Melanie Schmidt, and Christian Sohler. Turning big data into tiny data: Constant-size coresets for k-means, pea, and projective clustering. SIAM Journal on Computing, 49(3):601 657, 2020.
Sariel Har-Peled and Soham Mazumdar. On coresets for k-means and k-median clustering. In Proceedings of the thirby-sioth annual ACM symposium on Theory of computing, pp. 291-300. ACM, 2004. and
David Haussler. Decision theoretic generalizations of the pac model for neural net and other learning applications. Information and computation, 100(1):78-150, 1992. 5
Lingxiao Huang and Nisheeth K. Vishnoi. Coresets for clustering in euclidean spaces: Importance sampling
is nearly optimal, 2020. 2]
Ari Kobren, Nicholas Monath, Akshay Krishnamurthy, and Andrew McCallum. A hierarchical algorithm for extreme clustering, In Proceedings of the 23rd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pp. 255-264, 2017. 2
Brian Kulis and Michael I Jordan. Revisiting k-means: new algorithms via bayesian nonparametrics. In Proceedings of the 29th International Coference on International Conference on Machine Learning, pp. 1131-1138, 2012.
Michael Langberg and Leonard J Schulman. Universal s-approximators for integrals. In Proceedings of the bwenly-first anneaal ACM-STAM symposium on Discrele Algorithmss, pp. 598 907. STAM, 2010. 5 and 6
Silvio Lattanzi and Sergei Vassilvitski.. Consistent k-clustering, In International Conference on Machine Learning, pp. 1975-1984, 2017.
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), pp. 81-89.
STAM, 2016. and 22
26

---

Published in Transactions on Machine Learning Research (07/2022)
Mario Lucic, Olivier Bachem, and Andreas Krause. Strong corescts for hard and soft bregman clustering
with applications to exponential family mixtures. In Artificial intelligence and statistics, pp- 1-9, 2016.
16 22
29
and 33
Jack Sherman and Winifred J Morrison. Adjustment of an inverse matrix corresponding to change in element of given matrix. The Annals of Mathematical Statistics, 21(1):244-277, 1950. 30
David Woodruff et al. Sketching as a tool for numerical linear algebra. Foundations and Trends0 in Theoreticol Computer Science, 10(1-2)11-17, 2014. and 29
27

---

Published in Transactions on Machine Learning Research (07 (022))
A Appendix
In this paper we use the following theorems in our analysis.
Theorem A.1 (Bernstein's incquality 2009). Let the scalar random variables 21, P2. En be independent that salisfy Vi E [n], [[a]] < b. Let X E; zi and let o² = Di be the variance of X. Then for ony
> 0,
Pr + exp 4
12
Theorem A.2 (202bb). Let A be the dataset, X be the query space of dimension D, and for E X, let fx()) be the cost function. Let 8j be the sensitivity of the jth row of A, and the sum of sensitivities be S. Let (c,6) E (0, 1). Let r be such that
M 0 ( (Dlog - + log )
1
C be matric of r rows, each sampled i. from A such that each à; E C is chosen to be ag, with weight 8 with probabilily 3 for E [n]. Then C is an e-coresel of A for function SO, with probabilily at least 1-6.
We use the above Theorem to bound our coreset size. Note that the Theorem considers a multinomial sample where a point å, in coreset C is a, and weight raj approach get å; as a, with weight 1/ rss], with probability ms, or it is with weight with probability 1- m1, r8:). However, the same Theorem above applies.
_ for [n] with probability 3. Instead in our
A.1
Online Coresets for Clustering
Here we discuss the proofs of the supporting lemmas claim of the main theorem
A.1.1 Proof of Lemma 4.5
Proof. For some fixed (query) X E Rexd consider the following random variable.
(1/p--1))) 1)5x(a)) with probability pi W4 fx(a))
with probability (1 - ps)
Note that [[w,] = 0 and with = 1 we get |wy] 0. The algorithm uses the sampling probability P. = min min(r1, 1}. Now we bound the term |ws/- In the case when pe < and a, is sampled we have,
1
-
(x(
pi
[x(a:)
rk
(Ax(A, 1) for (A.))
rfx(a:)
(Ax(A, 1) Soz (Ai)) r (fx(A) + (a))
(i) is by replacing 4 with smaller term, Tx(A, 1- (A.)) In the last inequality is because fa(A) 2 for (Ai).
(x(),)
Here = PP is the mean of the entire data A. Next the point a, is not sampled then we know for sure that P. < 1, hence we have that,
rk
28

---

Published in Transactions on Machine Learning Research (07/2022)
(a, 2 (fx (A + fea (Ai)) (Ax(A) + fa(A))
:. fx (a:)
Say, b b= (Ax(A) + (A)))) |wM|
- b. Next we bound the var var(E Wi) Eiss B[wi), Note that for
single term when P4 1, B[wf] is,
E Eluf]
+ = (pi(1/p:-1)" + - (x=p)))
S [x((a)²
Di
fx(a,)2
r4
(xx(A--1) + Sox (A))
(f,(
(X((A-)) + (Ai))
(x(a)(((AA)+ + +c(AA)
So we get,
Σ
Σ
E Elwsl
w/
in
(fx + f((A))
fx(A)(fx(A) + (((A
(fx(A) fa(A))
r
Now by applying Bernstein's inequality A.1
on Eign w. with t= c(fx(A) + fa(()) we bound the proba- fs(A)) as follows,
bility P = Pr((f((C,))) fx(A) 2 (A (A)
+
P
& exp
c(fx(A) + f3 +((x(A)))))))))))))) - -rE?
exp
(e/3+2)
So to get the above event with least 0.99 probability is enough to to be o (z). Note that the above is guaranteed for fixed E R
Now we show that coreset (C, can be made strong coreset by taking union bound over a set of queries. We take union bound over the e/2-net of k Woodruff al. (2014); Lucic et al. (2016). Such net will have at most O logk) queries. To ensure strong a coreset guarantee: it is enough to set r
O dkllog k) 1//()
Intuition for log(f((A)): Consider the following input stream - every that is multiple of vn has the property that fx (a:) = (x;A;))), i.e. this point's contribution to the current cost is more than the total contributions of all the previous input points. For all other j, fx(a)) is, say, small. Any online algorithm (i.c. one that makes irrevocable decisions without looking at the future) will need assign a constant probability to every that multiple of vn. Hence the resulting coresct size is least vn. Note that (x(A) O(evR), and hence log(fx(A)) is tight bound on the coreset size in this example.
29

---

with probability Published in Transactions on Machine Learning Research (07 (07/2022)
Lemma A.3. For p-stmilar Bregman dévergence, for all E [n]] every incoming points a have,
fx(a:)
2fa (a.)
8
sup XERexa ()(A (Ai)
P4T Ejst 1 (0,((a))
+
MuT(i 1)
(17)
Proof.
fx(a) fx (A, TT (Ai)
10
Xx
M.
(a.)
(A pfp (Ai)
25 (a.) + 2/x (p:)
(x(Ai-)) + T (Ai)
2 (a:) + - S (A; + T (Ai-1)
M.
fx
Sp. (A:)
(8)
2 M. (a.) + T M. (A:
- (Ai-1)
m Mi (Ai-1) + T M.
-5p (Ai))
2f (a.) + 4 sM; (A,-1)
M, (A,-1)
Pi (A,-1) + (.Ai((A)))
M.
(Ai-1)
M, (A.))
M (ax) + SM (A,-1)
4
Pilfx M.
(At-1) + T (A.)
p((i-1) 1)
2 (a:)
SM
(Ai-1)
4
N&T S.. (A,)
P&T
M. (A:)
146i - 1)
2
4
(+
PLT J (Ai)
MM:
M (a,)
N4T(i - 1) -
4
+
P.T Ejsi Jop (ay)
Further with an analysis similar to second claim in lemma 4.4
we gel Eign 4 < 8 8log +
4log (A)) -llog ( Now the algorithm samples point based on its 4 score. Then, applying Bern- stein's inequality of all the random variables defined as,
HT
(1/p: 1)fx(a) (a:)
wi
with probability (1- - p.).
Finally, by taking union bound over e-net can prove the claim in corollary 4.1
A.2 Coresets for Non-Paramens Parametric Clustering
A.2.1 Proof of Lemma 5.3
Proof. The proof is fairly straight forward. Using simple algebra (similar (hherman & Morrison 1950) we have,
1
+ ur ur(g + w)-
q + W
ur
q +
w
ur(q + w) (g + w)
1
+
q
30

---

Published in Transactions on Machine Learning Research (07 (07/2022)
1
er + w) -2
+ W
UP
q +
w
vr + w) -
1
+
(g + w) -
q +
w
1
So we get,
pu + (1 p)v uv
E
1 w
g + w
(1 - u) - v)
q + w
A.2.2 Proof of Lemma 5.4
Proof. In order lo show this we define the following notations. Let A; represent the set of i points seen by the algorithm so far. For some X and for some j I n, we define two scalars CP and Ci as follows,
c -x((A))))))))))))))))) (1 ()fx(A,) and - + (1-5))x((A)
So we have Ch = (x+)))((A) and C = (1 ()x(()) It is clear that for S i - 1 we have C 2 5% and G-1 S G/ Further two more scalars 7ht and Thy are defined as follows,
Ti. Th Sh (x(C),
and
Thes fx - Si.
Note that 7h, = c) - fx 24) and 7h. = (1- Wh-1. 2 Tho and 7-11 2 Th. Let, djt1 fx(a++1) hence we have the following for upper barrier,
For j S i - 1 we get If Tf < 1, then we have pj+1 2 G, 2 G,8 and
Pi+t
c" cx(x(aa+1)
cd cxxx(aj+1)
e² c((x(1)+1)
Pj+1 2
2
G5 + Ef (A411)
1- + ef (Aj-1)
T M-11 I tf
Therefore,
dj+1
Thi + (Ai)
d,+1 T-11 te/e, (A.) = h341, which bounded by 1. Similarly for the lower barrier we have,
Let
(x(()))) Pj+1
(x
e'f((1)+1) M- + tfp. (Ai)
93s + ef (As+1)
M- + cforr (Aj-1)
So we get,
d++1 S c
1- + Ef (Ai)
A.2.3 Proof of Lemma 5.5
Proof. For brevity, going forward, we denote 1//1
di+s te (A.) Recall that Lemma showed that
1141 < J.
To apply Lemma 5.3 we set q = 1:
fx(a;) and w = cfo, (A,). Further let u
h Pp+i((1 + c/2)). 1P c/2) and p Pj+1- Note that from the above substitution we
get g+w 1 and t 1-1,1 To prove the corollary need the RHS of the lemma p1+(1-p)o-ur uv < 0. (1-w)(1-o)
After substituting every term we get, P (1 (itp:///2mmmm((///2))-)))))) Now if PJ+1 1/(1 + e/2)
(1-w)(1-))
31

---

Published in Transactions on Machine Learning Research (07 (07/2022)
then this term is non positive, clse when c* 1 the term remains non-positive. As Tyt1 {0,1) is the sampling choice made by the algorithm for aj+1- So we have,
fx(a.)
fx
E Bay+1 M-1.5+1 ct (A,)
I M-1 ef (A,)
A similar analysis also follows for the lower barrier. We use Lemma 5.3 by setting g = 1-11 d (x.))) and w = <fp Further let = - h1)1
Ps+1 1001--pp e/2)), 11/+1/t+111 - e/2))
and p P-+1- By these substitution we have, g+ aj+1 E (0, 1} is the random sampling choice made by the algorithm for aj+1- Now for d' = 2 - 1 we get,
_ 1 and the random variable
71-15+1 Let
fx(a,)
fx(a,)
E B
S M +
/ + tcpp (A.)
A.2.4 Proof of Lemma 5.6
Proof. We use Lemma
5.5 to get the expected upper bound on the sensitivity scores i.e.,
fx (a:)
sup (1+)) fx ((-1)
+
fx (a,)
sup
((CC--1 - (1 - x)xx(((xxx))) +
Let (1 + =) - (.-)) = fx(A))) where fx(A Ejsi-i fx())) Here each term fx(a))) = (1+C-D7')xx(a) a, present in C else fx(a)) = (1+e)fx(aa)) Now the expected upper bound the upper barrier sensitivity score can be bounded as follows.
fx(a:) +
Mi (a:) fx (A (A.)
En,-1
En.-1
ix(AA cfp
2 2 (a:) + - En,EA:
[MM (a,) M. (a,))
(12) I
Ex.-1
11
(1 fx (A-
- ppp (Ai)
M/ pi (a:) + 5-1 Ea,EA PM (a,)
4
Ex,-1
11
fx (x(C,_11 Pi- Elpp (Ai)
1
M. (A,-1)
+ Ex,-1
1-1
11
(1 (1+e)fx(A) A
fx fx(C, (C, 1,, Pi-
+ Es (A:)
(sit)
Ex.-1
M (a.)
i-1
1
4
MM, (Ai-1)
I1
ا Ef. (Ai)
8- f (A:-1)
Ex--1
11
1--1-11 Espp (A:)
(ie)
M (a,) + - I/M
M
1
(A²-)
Ex
11
TH + efe. (A,)
Mi (A:-1)
+
E Ex
II:
14 efis (As)
2 Mi (a:) + 1-1 Jip
eMi (Ai-1)
M: (A,-1)
Ex
E
J-1
Nh10 + (A,)
7f-110
Esp (A.)
32

---

Published in Transactions on Machine Learning Research (07/2022)
2f (ax) + 1-1 Jpp. MM (A)
M. (Ai-1)
c/2fx (A;-)) + cf (A,)
c/2fx
+ Efp (A,)
2 (a.) + 11
fMM (A,-1)
1)xx
M.
(Ai-2)
(0,e0..5 MM:
(A,-1) + for (A:))
(4
5x (Ai-1) f (A,))
2 (as)
4f (Ai-1)
85x (Ax-1)
HEEfiPE (A.)
Hie(i - 1)5 M (A,)
pse(i 1) (Ai-1)
(v24)
25 (as)
4
8
+ pise(i -
fEEfip (Ai)
Mie(i
1)
2. (a:)
12
IA
+ psc(l - 1)
FGE Ejsi 14; (aj)
The inequality (i) is by upper bounding Bregman divergence by squared Mahalanobis distance. The inequal- ity (ii) is due to applying triangle inequality on the numerator, (a² + 12) S 2(a² + 12). The (iii) equality is by replacing the denominator with the above definition. The (iv) incquality is by applying the supporting Lemma 5.3 By recursively applying Lemma 5.3 we gel the inequality (c) which is independent of the ran- dom choices made by the algorithm. The inequality (vi) is by using the lower bound on the denominator, The incquality (vii) an upper bound on the second and the third term. In the final incquality we use the fact that for any j similar Bregman divergence from Ackermann & Blömer (2009); Lucic et al. (2016) we have M2 3 M. for j S i (Lemma 4.1. Further by the property of Bregman divergence we know that (A,-1) 2 f (A,-1). Hence we have AM (A.) 2 Ejsites f6o (a,). Notice that the above analysis also true for all X. Hence we have this upper bound for all X with at most n centers. So we have the,
(ax)
(a.)
12
En.-1 (1+c) fx (C,11, Q4-1) + for (A,)
S EEis (2,(
+ c(i-1) 1)
Now let (fx(C,- Q4-1)
- -1--))))---)))----))----
where fx(A Exgi-1 Here each term
[x(a ( - (a,) if aj is present in C:-1 else fx (aa)) = (xxx)x((aa))) Now the expected upper
bound on the lower sensitivity score is,
fx:):)
fx (as)
En,
Eng
[x(A
ff (A:)
[x ef (A.))
(i)
M. (a:) + T-1 Σaj CayeA: A IMM. (a,)
X
M. (a,))
E ExI-1
11,
[x 1, R4-1) (1 c) M. (Aç-1) + Cf (A,)
(yMi((a)) + 1-1 - pM: (A,-1)
= B
11:
Tx(C l4-1) - (1 c)fx ( 1A,1) + Epp (A) (A:)
4 MM (A;-1)
di-1))
5x
+ ExI-1
11:2
[x(Cr_1, Pi- 1) - (1 ))xx (A
+ El (Ai)
MfM (a,) + 1 fM. (A,
(18)
Ex.-1
II
N Cpp (Ai)
T-T - Mi (A;-1)
+ ExI-1
11:-2
M + cfp. (A,)
(iv)
2 M/ (a.) + أ 1
4 S. (A:-)
z Ex
II
N + Spp (Ai)
H - 1 M. (Aç-1)
+ E
11,
1 + pfog (A,)
33

---

Published in Transactions on Machine Learning Research (07 (07/2022)
2 (a:)
+ I-
4 MM (Ai-))
R M. (Ai-1)
R
+ RE
1/-1,00 + Ef (Ai)
T + E (A:)
2 2f
M. (a.) + SP: PM, (Ai-1)
(A,-1)
(1-1)
f/2/x A (Ai1)) + t.p (Ai)
(/2(x(((-))
+ clp (A:)
(v))
21 25 (a:) + 3-1
4 MM. (A,-1)
Tr-ly 1x (Aa-1)
(G0(0.55f Mi (As-1) + for
(A:))
pcc(0.5ff
M: (Ai-1) f (A,))
2 (a.)
12
IA
+
MGE Ejsi M (aj) pse(i - 1)
The inequality (i) is by upper bounding Bregman divergence by squared Mahalanobis distance. The in- equality (ii) is due to applying triangle inequality on the numerator. The (iii) equality is by replacing the denominator with the above definition. The (iv) inequality by applying the supporting Lemma 5.3 By recursively applying Lemma 5.3 get the inequality (v) which is independent of the random choices made by the algorithm. The inequality (vi) is by using the lower bound the denominator and from here the analysis is same as the upper bound analysis. So we have the following.
fx(a:)
2f M, (aj) ueeli
12
En (1)+)) (x- (4-1) (a.)
+
p4z EjsiJe)
A.2.5 Proof of Lemma 5.7
Proof. First we bound the expected sampling probability of cach a, i.c., En,,,pp
En, [p:]
ET
+
e [331
n0
M.
(a.)
12c
2c MM (a.)
12c useli - 1)
1 Ejs:
J4,
Mi
(aj)
Mie(i-1)
Mi Ejji
(2g)
8 Mi (a:)
48
+
Mj 24:2 Ejs J0j
(aj)
(1e((i-)
The inequality (1) is because the oracle returns tight upper bound on the actual barrier sensitivity scores. Now we bound the total expected sample size,
8fM:(ay) (a;)
48
Epd
<
+
u4e2 Ejsi
(aj)
uiel(i - 1)
3sisn
48 log n
8fM, (as)
<
2
1GEE Ejsı
M: (aa)
3EiS
Because of the subtlety that Elpa] 2 1, hence in the above analysis we bound sum from to n. Let the term (i))
Ensr So (ag) g: 1. In the following analysis we bound summation of this term i.c., Eisn Li- For that
consider the term Egs foy
My M) (ay) as follows,
(M,
MM,
Σ Ma
Σ
f
Ma
1+
2i
Σ Ejsi-1
S:p (aj)
M,
1
/ (ai)
Σ
1/ (az)
1+
Eyst (ay)
1
34

---

Published in Transactions on Machine Learning Research (07 (07/2022)
E
M (aj)(1 +:)
J
explq:/2)
Σ (aj)
15i-1
exp(x:2) I Ejsi J0j (aj)
M,
M, Ej 183 (ay)
In (i) we use the fact that, for q: S 1, (1 + q:) 2 exp(a./2). Now as we know that Σ Σjs Mi (ay) 2
Ejsi-1 1b/ (a,) hence following product results into a telescopic product and we get,
M, Ejsn Jos (a,)
II exp(n:2) 35t5n
MM (az)
(A)
f (az)
Now taking log in both sides we get Essign di & 2 log (A)) 2 log (a2)) Now with p =p have the following bound on the expected samples.
Σ 1315
Elp:] 2
32 nc²
3log + log (Jo - -log (a2))()))
Here we consider that Vi E [n] we have μ pn S l4 and M = MM = M, as the j-similar Bregaman divergence parameters for A. Note that the coreset size is independent of k and d. Hence the resultant coreset ensures the desired guarantee equation [ for all X with at most n centers in Rd. The expected size
of the coreset is O pez logn log (MM(() log (AMa (az))
A.2.6 Proof of Lemma 5.2 k i-mans Clustering
Proof. We prove it using the Lemmas 5.2 5.6 and 5.8 As for k-means clustering we have M; = L2 and
P 1 for each S n, hence vi [n] the expected upper bound on both lower and upper barrier sensitivity
scores are,
2f (a.)
12
+ <(i - 1)
Ens Se (aj)
It can be verified by a similar analysis as in the proof A.2.1 and A.2.4 of Lemin 5.3 and 5.6 The rest of the lemma's proof follows as it is and we get required guarantee. The NonParametric returns a coreset of O logg + log (fe(A)) log (fra expected samples.
A.3 Uniform Deviation
A.3.1 Proof of Lemma 6.1
Proof. For any Rd and X kg have,
fx(
SV WV9
f Ma)
+
p(OM EI MM (a)))
2 Ma) 2 (E)
p(om + +EI (a)])
2/M + (
plom + E (a)))
35

---

Published in Transactions on Machine Learning Research (07/2022)
(10) (a) + 2 PM [a)] +
OMMM E PM (a))
2 (a) + 40 4 X (a)
M + 1 M (a)))
( (a) 8
μOM
/
Here (i) is by using upper bound (on the numerator) and lower bound (on the denominator) of the Bregman divergence using squared Mahalanobis distance. In (ti) and (izi) we use the fact that (a+ b)2 - 2 + b²). Next we bound [[)(a)?].
M (a)
B[s(a) = E
NOM
11
4f (a)
64
f2 (a)
= E
122
P2OM
B[4f$ M (a)
64
32E f (a))
142
P2OM
A M (a)²1
96
12003
We get the last equality because (
OM and by the assumption equation 14
A.3.2 Proof of Theorem 6.2
Proof. The proof of is same as the proof of Theorem 5 in Bachem et al. (211aa). Hence, here we only present proof sketch.
As B[s(a)) S t, hence on 2m ii.d. samples (a..... } by Markov we get 1 Emm s(a,)2 < Ott) with at least a constant probability.
2m
The rest of the proof is based independent samples from D and let h, .., Am be independent random variables uniformly sampled from (11, If [[s(())]] S i, the probability of equation 16 not holding can be bounded by the probability that there exists 9x
double sampling approach. Let a Am ... a2m be additional
9x(-) (-) E G such that
Σ h4 (gx(a;) 9x (am-i))
2e
(18)
We first provide the intuition for some function g and then show how we extend it to all g G. While the function g(a) is not bounded, for given sample a1 a2..... agm. each g(a,) is contained within [0, sa:)). Given the sample a2,a2,.... a2m, the random variable h; (g(a;) g(as+m) is bounded in 0 + max(s(at s(a;+m)) and has zero mean. Hence, given independent samples a1, a....., a2m, the probability of equation 18 occurring for a single E G can be bounded using Hoellding's inequality by,
22m2 Dism max (x(x)))()))))))))))))))) (a((a),)(aaaaa)) s(artm))
IP
Σ hs (ox(a:) - -9x(am+t)) Sc im
< 2 cxx
m Σ
< 2 exp
237 Σ
Eiszm s(a;)
36

---

Published in Transactions on Machine Learning Research (07 (022)
From lemma 6.1 we know E[s(a)²) S for E (2)) ensure above event with at least 0.99 probability. Finally using Pg) I p we take a union to ensure that the above event with at least. 0.99 probability. So we get m E E (te).
A.4 Experiments on MNIST and Song Data
Here we discuss some more experimental results. We run our algorithms to compare with other bascline coreset creation algorithms. Once the coreset is obtained from each the sampling methods, we run weighted +-means++ clustering (Arthur & Vassilvitskii 2007) on them for various values of and get the centers. These centers are considered as initial centres while running k-means clustering on the coreset and finally obtain the centres. Once these centers are obtained, we compute the quantization error on the entire dataset Cs, with respect to the corresponding centers. We also run similar k-means clustering on the entire data for the same values of k and get the quantization error from those centres, i.e., Cy. Finally report the relative error 17, i.e, 1 1C-00
C
A.4.1 BregmanFilter
We compare the performance of BregFilter (our BregmanFilter) with Uniform and TwoPass on the fol- lowing datasets.
1. MNIST: 60, 000 points in 784 dimension digits dataset.
KDD(BIO-TRAIN): 145, 751 points with 74 features.
SONGS: 515, 345 songs from the Million song dataset with 90 features.
In the figure 3 we show the change in relative error (1) with respect the change in the coreset size (% of data). Here consider relative entropy (or KL divergence) as Bregman divergence and the sampling methods the MNIST dataset. As the data has natural clustering of 10 digits, hence we use k = (5, 10). We run the sampling algorithms for varions coreset sizes. We run 5 random instances for each each coreset size and here we report the average of their 77.
MNIST (K=10)
MNIST (K=5)
Uniform
Uniform
0.10
TwoPass
0.040
TwoPass
BregFilter
BregFilter
0.035
0.08
0.030
0.025
0.04
0.015
0.02
0.010
0.5
2.0
2.5
3.0
0.5
1.0
1.5
2.0
2.5
3.0
% of data
of data
Figure 3: Relative error v/s coreset size for KL divergence.
We also run the sampling methods on KOD(BIO-TRAIN and SONGS, considering squared Euclidean distance as the Bregman divergence. In the figure 4 we report the average n of the 5 runs, for k {100, 200). The plot shows the change in relative error (1)) with change in coreset size (% of data).
37

---

Published in Transactions on Machine Learning Research (07 (07/2022)
KDD: BIO-TRAIN (K=100)
KDD: BIO-TRAIN (K=200)
Uniform TwoPass BregFilter
Uniform
Relative Error
TwoPass BregFilter
2
1
0
SÓNGS (K=100)
SÓNGS (K=200)
0.30
Relative Error n
Uniform TwoPass BregFilter
Uniform TwoPass BregFilter
0.25
0.20
0.15
0.10
0.25
0.50
0.75
1.00
0.25
0.50
0.75
1.00
% of data
% of data
Figure 4: Relative error v/s coreset size. Squared Euclidean Distance Bregman Divergence.
In all these cases, as per the expectation we do see an improvement in 7 as coresel size increases. Fur- ther also notice that the performance of the BregFilter is equivalent TwoPass and outperforms the performance of Uniform.
Bad example for Leverage: In the datasets considered, the empirical performance of the leverage score is similar to that of the provable sampling strategy that propose. Tt. is useful to recall that this is not always the case. The following example shows when leverage score can perform really badly.
Consider 4 points in R' as (1000), (1000), (1000) and (1) coming in this order. On these we are interested in a 2-means clustering, iee, = 2. Clearly the cluster centers are (1000) and (1). Now the online leverage scores (as defined in Algorithm 1 in Chhaya al. (2020ap) of these points will be 1000? 1000" 1000² 3-1 Tet. be the parameter that controls the expected coreset size. So the points are sampled with r.
10002: 2-1000 3-10002, and
and 3:000=4T respectively. Now based on this, if we build a coreset, say with r= 3, then with a very high probability we will not sample any representative from the (1) cluster (this example can easily be generalized to coresets of a general size). Now with our sensitivity upper bound (refer 4 in algorithm [ depends on how much current point far from the previous points. In this example, the online sensitivity score of the first point (1000) will be 1 and point will be sampled with probability r The second point (1000) is just copy of the first point, and hence the mean of the first two points is equal to the second point itself. As result its online sensitivity will be 1 (which is due to the second term in the algorithm) and even this point will be sampled with probability r 1. For the next point (1000), also the mean does not move, so ils online sensitivity score will be 1/2 and its sampling probability will be r 0.5. Now for the final point (1) the mean moves from (1000) to (750.25). So its ouline sensitivity scores will 749.25
probability r -.5--.5, - 0.33
749.25 and sampling probability be (749.25 + 1), which bigger than 1. So for any the final point will be sampled in our coreset with higher probability than the third point in the stream. As result our coreset, even if it is of size three, will have representatives from each cluster.
38

---

Published in Transactions on Machine Learning Research (07 (022))2
The main insight from the above toy example is that leverage score sampling only tries to preserve the rank of the data, and not the cluster structure. Hence, if the data spans only low rank space but has a large number of clusters then Leverage sampling will likely perform worse compared to our BregFilter.
A.4.2 NomParametricFiiterr
Now we compare the performance of a heuristic version of NonParametricFiiteer called NP-Filter with Uniform, Offline and TwoPass on KDD KDD(BIOTRAIIN) dataset. The Offline the lightweight coreset from (Bachem al. 2018a). Here for the comparison we do not consider the assumption 5.1 Instead use simply use the expected upper bounds as shown in lemma 5.6 Further for NP-Filter the coresct size is controlled set the desired parameters of other sampling mot
by Now once get coreset from NP-Filter, to get similar coreset size. Here once the coreset is obtained from each of the sampling methods, we get the relative error as described above. Now on each coreset, we run k-clustering for various values of = (50, 100, 200, 300} to capture the non-parametric nature the coreset.
1.00
0.75
Uniforn
Uniform
Offline
Offline
TwaPass
TwaPass
NP-Filter
Relative Error
Relative Error
120
150
2ic
250
160
190
k Number of Centers
Number of Centers
0.50
==
Uniform TwoPass NP-Filter
Relative Error
Offline
TwoRass NP-Fitter
Relative
34.
30
100
150
206
180
150
200
Number of Centers
k -Numeer of Centers
Figure 5: Change in Relative Error v with respect to number of centers k for various values of
For each of the algorithms and for each value of run 5 random instances, compute |Cs-Crl UF and report the average n value. We consider (1.0, 0.75, 0.5, 0.25). for which we have (500, 850, 1650, 5500} expected samples. Figure 5 shows the change in the value of Relative Error with respect to the change in number of centers k, for various values of e. With decrease in e we can note that the value of also decrcases. This bocause as the incrcascs, the coresct size reduces, which results a high r). Now an interesting point note is that the 7) remains significantly smaller than for the same coresct across various values of k. Even though algorithm is heuristic, but this plot reflects the non-parametric nature of our
39

---

Published in Transactions on Machine Learning Research (07 (07/2022)
coreset from importance sampling. Note that, even though Offline outperforms NP-Filter, but they are very close.
40


Reviews:
[{"review_id": "6biP8yyo1q", "reviewer": "Reviewer_CfBV", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n\n+ Overall well-written paper with clear goals\n+ Solid technical (theoretical) contributions\n+ Addressing a natural question in the clustering literature\n\nWeaknesses:\n\n+ without the knowledge of the previous work it is not easy to say which technical ideas are new \n+ theoretical results are not sufficiently contrasted with previous work\n+ the presentation of the paper can be improved (see below suggestions)", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The authors propose an online methods for finding coresets for clustering with respect to miu-similar Bregman divergences. These are coresets with respect to additive error (as opposed to coresets that guarantee a 1+eps approximation guarantee). The authors provide two methods, one for usual clustering with k centers, and one for what they call non-parametric (where finding the number of centers is part of the optimization problem). The authors instantiate their general results for special cases of k-means and DP-means (a nonparametric version of k-means) clustering. Based on my understanding, the main contribution compared to previous work is proposing an \"online\" method.\n\n", "claims_and_evidence_yn": "", "claims_explanation": "", "audience_yn": "", "audience_explanation": "", "requested_changes": "+ Adding an outline of different sections can improve the readability a lot. \n+ The size of corsets in your main theorems depend on a number of factors such as log[f(A)] and log[n]. Do we know if these dependencies necessary? Can you add a discussion? [there is some discussion in section 6; perhaps you can link to those]\n+ It is mentioned in the related work that there are online corsets for k-means in the literature. Can you compare your (theoretical) results with those in more details? What is their coreset size? In what parameter regimes you get an improvement? Perhaps you can compare with them in details after stating your own theorems?\n+ The discussion of the uniform deviation bound in section 6 relies on an upper bound. But it is not clear if that upper bound itself is tight and therefore it is not clear if it shows that the dependence on f[A] is necessary. In the absence of some kind of lower bound, the claims should be somewhat weakened.\n+ Was there a reason that in section 6 you didn't use classical deviation bounds such as those in this? Biau, Gérard, Luc Devroye, and Gábor Lugosi. \"On the performance of clustering in Hilbert spaces.\" IEEE Transactions on Information Theory 54, no. 2 (2008): 781-790.\n+ In section 5.2.1, why do we need a non-parametric method for k-means? isn't k fixed? \n+ page 5: the reference for pseudo-dim is not correct \n+ please fix the typos through out the paper (including the abstract: a non-parametric coresets..)", "broader_impact_concerns": "No concerns here.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "7d5Mo8cqph", "reviewer": "Reviewer_3Wo5", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "(S) in score of TMLR\n(S) no correctness issues detected\n(S) well-written paper with rigorously proven bounds.  \n\n(W) the experiments are small, and do not show that these methods will have a large impact.  [This paper addresses an interesting space in the score of TMLR, and is mostly theoretical, so not a big concern.]", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The paper describes new coresets for k-assignment-based clustering under Bregman divergences.  These include non-parametric variants (where k is not know a-priori) and streaming algorithms.  What distinguishes this work from prior work is the streaming nature of the coresets and the additive error, instead of the more common and stronger relative error.  This is a quite reasonable trade-off, and reflects the sort of methods users of such methods may want to actually do, for instance, if only restricted to one pass.  \n\nThe paper is clearly in scope for TMLR.  \nNo correctness issues were detected.  \n\nThe writing is generally good and clear.  The proofs and arguments appear rigorous and careful.  The comparison to prior work is fair, and the paper clearly discusses how its ideas build on and relate to those used in other paper.  The assumptions under which the main results are stated are made clear, and motivated.  The experimental sections shows that the coreset sort of results in space/error trade-offs are on par with other methods and heuristics, and supersede random sampling.  \n\nI have two (small) suggestions for the authors to chance.  Given the care taken in the rest of the paper, I assume they can do these without being checked.  \n\n\n1. The function f_psi shows up in equation (1), and is used throughout the paper.  While f_q and psi are both defined individually, this function is so prevalent and essential to interpretation of the bounds that I would suggest a sentence or two specifically discussing how to think about it (the sum of divergences from the average point).  Perhaps even for the special case of k-means clustering this term could be replaced by something not relying on the f functions, since we just have Euclidean distance then.  \n\n2.  On page 20 between equations (12) and (13) there is partial sentence\n  \"Now for a point a~D and X in R^{kxd} we define\" ", "claims_and_evidence_yn": "", "claims_explanation": "", "audience_yn": "", "audience_explanation": "", "requested_changes": "I have two (small) suggestions for the authors to chance.  Given the care taken in the rest of the paper, I assume they can do these without being checked.  \n\n\n1. The function f_psi shows up in equation (1), and is used throughout the paper.  While f_q and psi are both defined individually, this function is so prevalent and essential to interpretation of the bounds that I would suggest a sentence or two specifically discussing how to think about it (the sum of divergences from the average point).  Perhaps even for the special case of k-means clustering this term could be replaced by something not relying on the f functions, since we just have Euclidean distance then.  \n\n2.  On page 20 between equations (12) and (13) there is partial sentence\n  \"Now for a point a~D and X in R^{kxd} we define\" ", "broader_impact_concerns": "no broader impact concerns.  ", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "qtTYlGXoCP", "reviewer": "Reviewer_XJ2S", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "* Strengths:\n    1. The paper provides improved online coreset construction for parametric and non-parametric clustering via Bergman divergences. The coresets admit deterministic guarantees whereas the randomness is with respect to the coreset size.\n    2. The coreset sampling attribute is analyzed via Bernestien's inequality leading to better and more interesting results.\n    3. The notion of \"barrier sensitivity\" is certainly interesting and quite useful in the analysis of the paper. I anticipate that such a notion will be very useful in the literature of coresets as it provides leanness and as well as interesting, out-of-the-norm, provable guarantees.\n    4. Elegant proofs throughout the paper.\n\n* Weaknesses:\n    1. Written typos\n    2. Insufficient experimental comparison against online coresets for clustering problems based on Bergman divergences. The authors claim insufficiency towards the existence of online coreset that are applicable for comparison against their methods. Offline coresets can be made online rather easily through the use of the merge-and-reduce tree where coresets will be made applicable towards handles stream of points. In addition, such coresets can also adapt to the dynamic setting where points can be removed from the current stream/offline batch of points. \n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The paper suggests the first coreset for online non-parametric clustering based on Bergman divergencies and offers improved coresets for the online parametric clustering based on Bergman divergencies.", "claims_and_evidence_yn": "", "claims_explanation": "", "audience_yn": "", "audience_explanation": "", "requested_changes": "* Please fix the following typos:\n    - the dimension of the input points are -> the dimension of the input points is (first page)\n    - The comparison are done on real -> The comparison is done on real (third page)\n    - One can also define A clustering problem is called -> One can also define a clustering problem as (fourth page)\n    - Note that this algorithm is online is nature because for -> Note that this algorithm is online in nature because for (sixth page)\n    - We present BregmanFilter as algorithm equation 1. -> remove equation (sixth page)\n    - add a comma when trying to explain the transitions in any equation, and a dot to the end of equations when ending without any explanations.\n    - sampling enough points based on $l_i$, we get equation 1 ->  add a dot to the end. (ninth page)\n    - What is $t$ in equation 12? is it the total sensitivity? please add a brief explanation.\n    - where BregFilter will out perform Leverage -> where BregFilter will outperform Leverage.\n    - Page 26, in the appendix, please remove the additional $($ from the definition of $\\mathbb{P}$\n    - Please make Figure 5 more understandable, i.e., make it bigger for instance.\n\n* More experimental results:\n    - Please compare against the online versions of the coresets you have chosen to compete against by using the merge-and-reduce tree. \n\n* Discuss more regarding how hard is to approximate an upper bound on the barrier sensitivity, to better elevate the use of empirical bounds on this type of sensitivity.", "broader_impact_concerns": "There are none.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "tjvsnoOA9L", "reviewer": "Reviewer_QNv9", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n\n(+) The authors provide a thorough study of online coreset problem for Bregman clustering. The new theoretical results show the better (smaller) coreset size in expectation at a cost of newly introduced additive error in the approximation. These are supported by the theories and analysis in Section 4 and 5.\n\nWeaknesses:\n\n(-) The proposed algorithm shows little or no improvement compare to the baselines in the experiment. Also, claims in the experiment section are not well supported. For example, the authors claim \"Our online sampling method BregFilter shows competitive performance with the best known offline methods\". However, this is not true by examining Figure 1. I do not consider the results of BregFilter (proposed by the authors) as competitive to offline methods such as LWCS. In fact, I feel the performance of BregFilter is roughly the same as Leverage, which is an online method. Also, I have some questions about Figure 1, see Requested Changes section below.\n\n(-) The writing of the paper can be improved. There are typos and undefined notations in the paper. For example, in page 4, what is the notation of $A_{i-i}$? Also, in page 5 definition 2.3, the notation $\\leftrightarrow$ is undefined. Furthermore, it is unclear whether ${above; below}$ is a set of two reals or not. If it is, then should not it be using comma \",\" instead of semicolon \";\"?\n\n(-) The baseline to be compared in the experiment section is very limited. The authors mention many more of the online methods in the related work section. Why not also compare with them?\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The authors study the problem of constructing coresets for Bregman Clustering in an online setting. The approximation guarantee is in both relative and additive errors with high probability. Compare to the previous works, the size of the coreset constructed by the authors has better dependency on the parameters $d,k,\\epsilon$ and independent of $n$. The authors also consider the case where the optimal cluster size is unknown, which they refer to as non-parametric clustering.", "claims_and_evidence_yn": "", "claims_explanation": "", "audience_yn": "", "audience_explanation": "", "requested_changes": "1. Fix the typo and notation issues as mentioned in the previous section.\n\n2. Either provide more evidence in practice that BregFilter outperforms baselines, or tone down the claim in the experiment section. Even without strong experiment results the theory part seems convincing.\n\n3. Add more online methods as baselines, such as those mentioned in the related work section.\n\n4. For Figure 1, since the method proposed by the authors will either keep a streaming point in coreset or discarding it, I wonder how can the authors make all methods have the same coreset size? It seems to me that all points in Figure 1 are aligned, which implies them having the same coreset size. Please explain this issue.\n\n5. For experiment in non-parametric case (Figure 2), I wonder if Uniform and TwoPass are the only two possible baselines? Does that mean all previous methods can not take care of this case? Please confirm.\n\n6. In the first paragraph (page 1), the authors write “A canonical definition of the clustering problem is via the **k-median**, in which k possible centers need to be proposed such that the **sum** of distances of every point to its closest center is minimized.” Should not k-means corresponds to sum/mean and k-median corresponds to the median?\n\n7. If possible, can the authors design some experiments to actually verify their theorem? So far it I did not notice any of them. One of such example can be comparing with the theoretical bound or trends.\n", "broader_impact_concerns": "N/A", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper presents novel algorithms for finding coresets for clustering in an online setting. The focus is on k-clustering problems with respect to general Bregman divergences and developing coresets with small additive error. This allows for coresets with a size that is independent of k. 

Overall a good paper with solid technical contributions. I recommend that the paper be accepted with minor revisions. These include fixing the typos and providing clarifications as requested by the reviewers, but also changes that the authors have agreed to incorporate in the final version; some of the notable ones are as follows:

a) Add an outline of different sections to improve the readability; 

b) Discuss how the size of coresets depends on various factors and if such dependencies are necessary. In general, please comment on the tightness of your results;  

c) Add further discussion of related work on online coresets for k-means clustering, and how existing work is different from your work here (building on your response to reviewers CfBV and QNv9); 

d) Add empirical comparisons for BregFilter with the online clustering algorithm of Liberty, Edo (2016). 

Decision: Accept (poster)