On Generalization Bounds for Projective Clustering
Authors: Maria Sofia Bucarelli
Matilde Fjeldsø Larsen
Chris Schwiegelshohn
Mads Toftrup
Venue: NeurIPS 2023 poster (2023)
Keywords: Subspace Clustering
Learning Theory
Clustering
Error bounds

Abstract: Given a set of points, clustering consists of finding a partition of a point set into $k$ clusters such that the center to which a point is assigned is as close as possible. Most commonly, centers are points themselves, which leads to the famous $k$-median and $k$-means objectives. One may also choose centers to be $j$ dimensional subspaces, which gives rise to subspace clustering. In this paper, we consider learning bounds for these problems. That is, given a set of $n$ samples $P$ drawn independently from some unknown, but fixed distribution $\mathcal{D}$, how quickly does a solution computed on $P$ converge to the optimal clustering of $\mathcal{D}$?
We give several near optimal results. In particular,
 1. For center-based objectives, we show a convergence rate of $\tilde{O}\left(\sqrt{{k}/{n}}\right)$. This matches the known optimal bounds of [Fefferman, Mitter, and Narayanan, Journal of the Mathematical Society 2016] and [Bartlett, Linder, and Lugosi, IEEE Trans. Inf. Theory 1998] for $k$-means and extends it to other important objectives such as $k$-median.
 2. For subspace clustering with $j$-dimensional subspaces, we show a convergence rate of $\tilde{O}\left(\sqrt{{(kj^2)}/{n}}\right)$. These are the first provable bounds for most of these problems. For the specific case of projective clustering, which generalizes $k$-means, we show a converge rate of $\Omega\left(\sqrt{{(kj)}/{n}}\right)$ is necessary, thereby proving that the bounds from [Fefferman, Mitter, and Narayanan, Journal of the Mathematical Society 2016] are essentially optimal.

On Generalization Bounds for Projective Clustering
Maria Sofia Bucarelli' Matilde Fjeldsó Larsen2 Chris Schwiegelshohn" Mads Bech Toftrup²
1 Department of Computer, Control and Management Engineering Antonio Ruberti, Sapienza University of Rome, Italy
Department of Computer Science, Aarhus University, Denmark
118800991@post.o au mariasofia, (schwiegelshohn, toftrup Act.uupppccaaa
au dk
Abstract
Given a set of points, clustering consists of finding partition of a point set into k clusters such that the center which a point assigned is as close as possible. Most commonly, centers are points themselves, which leads to the famous k-median and k-means objectives. One may also choose centers be j dimensional subspaces, which gives rise to subspace clustering. In this paper, we consider learning bounds for these problems. That is, given set of n samples P drawn independently from some unknown, but fixed distribution D, how quickly does a solution computed on converge to the optimal clustering of D? give several near optimal results. In particular,
1. For center-based objectives, show a convergence rate of Ô (VKj) k/// This matches the known optimal bounds of [Fefferman, Mitter, and Narayanan, Journal of the Mathematical Society 2016] and [Bartlett, Linder, and Lugosi, IEEE Trans. Inf. Theory 1998] for k-means and extends it to other important objectives such i--median. For subspace clustering with j-dimensional subspaces, we show a convergence rate of Ô (V /k)" These the first provable bounds for most of these problems, For the specific case of projective clustering, which generalizes k-means, we show a convergence rate of /ki/n necessary, thereby proving that the bounds from [Feffferman, Mitter, and Narayanan, Journal of the Mathematical Society 2016] are essentially optimal.
Introduction
Among the central questions in machine learning is, given a sample of n points P drawn from some unknown but fixed distribution D, how well does a classifier trained on P generalize to D? The probably most popular way to formalize this question is, given loss function L and optimal solutions Sp and Sp for sample P and distribution D, respectively, how the empirical excess risk ((D,Sp) L(D, Sp) decreases as function of This paper focuses on loss functions associated with the clustering problem. Popular examples include (k, 2) clustering, which asks for a set of centers c Rdd minimizing the cost Eper min,es llp alßă and more generally, (k. 2) subspace clustering which asks for a set of & subspaces U/ == (U1, U2....U, minimizing Epep minu,eu ||[I - )elá., Special cases include (k, 1) clustering. known k-median, (k. 2) clustering known k-means and (k. 2) clustering known projective clustering. Generally, there seems to be an interest in varying z, as letting tend towards 1 tends to result in outlier-robust clusterings. The problem is less widely explored for although in particular for subspace
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

approximation there is some recent work [27 34 79 77]. Higher powers give more emphasis on outliers. For example, centralised moments with respect to the three and four norms are skewness and kurtosis, respectively, and are extensively employed in statistics, see Cohen-Addad et al. [31 for previous work on clustering with these measures. Fitting mixture model with respect to skewness minimizes asymmetry around the target center. Studing the problems for > is very well motivated, as the (1, o0) clustering equivalent to the minimum enclosing ball problem. Unfortunately, one often requires additional assumptions, as the minimum enclosing ball problem suffers from the curse of dimensionality [2]. is very prone to outliers 25
Despite huge interest and substantial amount of research, so far optimal risk bounds Ô ((Vkjv for the k-means problem have been established, see the seminal paper by Fefferman et al. [39 for the upper bound and Bartlett et al. [TO] for nearly matching lower bounds. For general (k: 2) cluusterin problems, the best known results prove risk bound of O kd/f
k/n
10
For (k, j.2) clustering, the
best known bounds of Ô ( (Rs//)) are due to Fefferman et al. 39 Thus, the following question naturally arises:
Is it possible to obtain optimal generalization bounds for all 2llustiinn objectives?
We answer this question in the affirmative whenever and are constant, which seems to be the most relevant case in practise (6]. Specifically, we show
The excess risk bound for (kc, cllusterng when given independent samples from an unknown fixed distribution D is bounded by Ô (Vk/n) matching the lower bound of [T0
The excess risk bound for (k. cllustern when given n independent samples from an unknown fixed distribution D is bounded by Ô mm
There exists a distribution such that the excess risk for the (k, 2)-clustering problem is at least ? As/n
matching the upper bound of Fefferman et al. 39 up polylog factors.
We note that assume = to be constant, which is the case for projective clustering, k-means and k-median. For non-constant 2, the dependency on z is exponential.
1.1 Related work
The most basic question one could answer if the empirical estimation performed on consistent, i.e. as n oc, whether the excess risk tends to O. This was shown in series of works by Pollard (64 [6), see also Abaya and Wise [ Subsequent work then analyzed the convergence rate of the risk. The first works in this direction proved convergence rates of the order ((1/vn) without giving
dependencies on other parameters 22 65
Linder et al. (55) gave an upper bound of (d3/2 vk/n) Bartlett et al.
Linder [54] improved the upper bound to O(d k//n.
[ showed an upper bound Motivated by applications of clustering for
O(Vkd/n and gave lower bound of Ω
k1
1/a
high dimensional kernel spaces 77] 8 20
21
37
39
[6
58
67
78 80
81] research subsequently
turned its efforts towards minimizing the dependency on the dimension. Biau al. [4 presented
an upper bound of O(k/ n), see also the work by Clémençcon [26]. Fefferman et al. [39 gave
matching upper bound of the order ( kk/n), which was later recovered by using techniques from Foster and Rakhlin (45) and Liu (57). Further improvements require additional assumptions of the distribution D, see Antos et al. [5). Levrard (52), Li and Liu (53) For subspace clustering, there have only been results published for the case = =
50 72 for which the state of the art provides
Ô / /k//f) risk bound due Fefferman al. [39] A highly related line of research originated with the study of coresets for compression. For Euclidean (k) clustering, coresets with space
bounds of Ô (k/+2+)) have been established 33 32 which roughly corresponds to a error rate of
I hides logarithmic terms, i.c. we consider O ( kk/n polylooo, m)) = =0 =0(vk/m)
(Vk/n

---

Ô 11////))) as a function of the size of the compression. For the specific case of k-median and k-means, coresets with space bounds of ( (k1 /3a) are known [33], which corresponds to a
eтror rate of Ô / /n Both results are optimal for certain ranges of E and l: 47 and
while these bounds are worse than what we hope to achieve for generalization, many of the techniques such as terminal embeddings are relevant for both fields. For jk, z) clustering, coresets are only
known to exist under certain assumptions, where the provable size is Ô (exp(k:,,,
40 44
2 Preliminaries
We use ||^||p- := V/E | to denote the lp norm of a vector x. For p - oo, we define the limiting norm ||=|||>= = max Ty. Further, we refer to the d-dimensional unit Euclidean ball by B i.e. x E By
is vector in dR and ||>||| pairwise and orthogonal columns with unit Euclidean norm. We say that UUT is the projection matrix associated with U. Let = be a positive integer. Given any S of k points in B we denote the (k, =ccluterii cost for point set P with respect to solution S as
V o? < 1. Let U be d x j orthogonal matrix, i.e., with
cost(P, = Σ
min 81β2-
#ES
pEP
Special cases include k-means (z = 2) and k-median (z 1). Similarly, given a collection 4 of orthogonal matrices of rank at most j. we denote the (k: j, cllusterngg cost of point P as
cost(P, = Σ min II(I - -U- pp
UEU
PEP
The specific case (:: 2) is often known as projective clustering in literature. The cost vector US.P E II respectively JMP Rl has entries uf min.es ||p sll.. respectively of mingeu [I(I UUT pol5 for E P. We will omit P from S.P and J.P if P is clear from context. The overall cost is || 1| - 11 minges |pp l|p-sli sl1ă and ||u Epep minveu Il [ UU pll.. The set of all cost vectors is denoted by V.
Let be an unknown but fixed distribution on B with probability density function P. For any solution S, respectively U, we define cost(D, S) == pe min |p - =|1 Ppp]dp and
OPT == mins cost(D,S) S) and respectively cost(D,24) (D,2) == Spe mingeu [I 1 P(p]dd and OPT miny cost(D, U). Let P a set of n points sampled independently from D. We denote the cost of the empirical risk minimizer on P by OPTp == 1 mins ||o0||1. and respectively, OPTp == 1 minz | || The excess risk of P with respect to set of cost vectors is denoted by
EVP[(V) Bp(p:==pppp->>>>>>>0> -
Finally, we use the notion a net. Let (V, dist) be metric space, NVV, dist, ) an e-net of the set of vectors V, if for all V 3 o' E EV(V, dist, e) such that disl(v, v') < s. We will particularly focus on nets for cost vectors induced by (k, =.clustiin and -))lustcni defined as follows, prior work has proposed similar nets for coresets and sublinear algorithms for (k,, clustering (31).
Definition 2.1 (Clustering Nets). A set N₂ of P|-dimensiooall vectors is an s-clustering net if for every cost vector obtained from a solution S 24 there exists a vector o' NV with || [uloo S
A slightly weaker condition as required by these nets requiring only ||e6 - e112 I E Ev' would also be sufficient. Nevertheless, we are not able show better bounds when relaxing the condition and having point-wise guarantec may be of independent interest.
3 Outline and technical contribution
Due to space restrictions, the full proofs are provided in the supplementary material. In this section, endeavour present complete and accessible overview of the key ideas behind the theorems.

---

Let P be set of n points sampled independently from some unknown but fixed distribution D. To show that the excessive risk with respect to clustering objectives is in (f) for some function f. it is sufficient to show two things. First, that for the optimal solution MOrT, the clustering cost estimated using P is close to the true cost. Second, any solution that is more expensive than UOFT Showing cost( (1 (OPT) cost(D, cost(D,Morr) MOPT) E O(v1/n) with good probability is typically straightforward application of concentration bounds such as Chernoff's bound. In fact, these concen- tration bounds show something even stronger. Given solutions U1 .ue we have
does not become too cheap when evaluated on P. Both conditions are satisfied if for any solution 2
cost (oot(P, (D
-ostt)cssco((uu)))) Ō(f(m)).
1 cost (P,4) cost(D,
(v 'logt n
Ep sup U.
EO
What remains is to bound the number of solutions
Clustering nets and dimension reduction for center based clustering Unfortunately. the total number of expensive clusterings in Euclidean space is infinite, making straightforward application of Juseless. Nets as per Definition 2. I.Irre are now typically used to reduce the infinite number of solutions to finite number. Specifically, one has to show that by preserving the costs of all solutions in the net, the cost of any other solution is also preserved. Using basic techniques from high dimensional computational geometry, it is readily possible prove that g-net for (k, j. clustering of size exp(k: j d 1o) exists, where d is the dimension of the ambient space. Plugging this into
Equation and setting E = ni² then yields a generalization bound of the order O (kjdlogn/n)
Unfortunately, this leads a dependency d, which is suboptimal. To improve the upper bounds, we take inspiration from coreset research. For (k, =)clusterring a number of works have investigated dimension reduction techniques known terminal embeddings.
11 46). Given a of points P E Rd, a terminal embedding f Fd + R guarantees |p 4 = (1 + E) (lf(p) - f(a) for
any E P and & E Rdd Terminal embeddings are very closely related to the Johnson-Lindenstree
lemma, [16 28 60 for applications clustering, but more powerful in key regard: only one of the points is required to be in P. The added guarantee extended to arbitrary E I due to terminal embeddings allows us capture all possible solutions. There are also even simpler proofs for k-mean that avoid this machinery entirely, see (39 45 57). Unfortunately. these arguments are heavily reliant on properties of inner products and are difficult extend other values of z. The terminal embedding technique may be readily adapted to (k, cllustrrnn, though some care in the analysis must be made to avoid the worse dependencies on the sample size necessitated for the corset guarantee, described as follows.
Improving the union bound via chaining: To illustrate the chaining technique, consider the simple application of the union bound for terminal embedding with target dimension m = O log n), see the main result of Narayanan and Nelson (62]. Replacing the dependency on d with an ap- propriately chosen parameters and plugging the resulting net N₂ of size exp(ke-2 log n log e )
yields generalization bound of O kklog"
w/n) for (ks, 2) clustering. We improve on this using chaining analysis, see 30 32 for its application to coresets for (ks, 2) clustering and [39 for (,.j,2) clusterings. Specifically, we use nested sequence nets N1/2, N1y4, Nijs...., N2-2togn. Note that for every solution S, we may now write cost(p, S) for any E P as a telescoping sum
cost(p, S)
Σ cost(p, Sar(p,S--on S2-011)) - cost(p, S2-*) h=0
with SSzn E N₁, and cost(p, Si) being set to 0. We use this as follows. Suppose for some solution S, we have solutions Sz-a Ng-n and Sz- (641) E N2-(411) Then (cost(p, Sz-a) cost(p, (p-0) S 0(2-h) cost(p, S2-1) - cost(p, S) for all p E P. Instead of applying the union bound for small set of solutions, we apply the union bound along every pair of

---

solutions appearing in the telescoping sum. Using arguments similar to Equation 1
we then obtain
Ep
sup
cost(P,, ") - cost(P, (S25()))))))))))
$3 h x (- EN XNN+1
n
= δ
log(IANal : [N+11l)
= =2 22th. Ö
0(V
h 22hh polylog(k/2) (22h))
h n
E
This is the desired risk bound for (k: =) clustering. To complete the argument a rigorous fashion, we must now merely combine the decomposition of cost(P, S) into the telescoping sum with the learning rate that we just derived. Indeed, this already provides simple way of obtaining a bound on the risk of the order Ô (v V////)) which turns out be optimal. In summary, to apply the chaining technique successfully, the following two properties are sufficient: (i) the dependency on in the net size can be at most exp(((E-))) as the increase in net size is then met with a corresponding decrease between successive estimates along the chain and (ii) the nets have to preserve the cost up to an additive for every sample point p. The second property is captured by Definition 2.1 Both properties impose restrictions on the dimension reductions that can be successfully integrated into the chaining analysis.
Dimension reduction for projective clustering: turns out that extending this analysis (k. j.2)
clustering is major obstacle. While the chaining method itself uses no particular properties of (kc 2) clustering, the terminal embeddings needed to obtain nets cannot be applied to subspaces. Indeed, terminal embeddings by the very nature of their guarantee, cannot be linea and hence linear structure such as subspace will not be preserved. At this stage, there are a number of initially promising candidates that can provide alternative dimension reduction methods. For example, the classic caaiusoon-Lindenttrne
lemma can be realized via a random embedding matrix and, moreover, preserves subspaces, see for example [69] 23 28 Unfortunately, as remarked by [66. there is an inherent difficulty in applying Lanasso--indnnstauus type embeddings even for (kt 2) clustering coresets and the same arguments also apply for generalization bounds.
An alternative dimension reduction method based on principal component analysis was initially proposed by [44] for (k, 2), see also (28 and most notably (74) for different variant that applies to arbitrary (k. 2) objectives. For (k. j. 2) clustering, states that a dimension reduction on the first O(D/E) principal components preserves the projective cost of all subspaces of dimension D. Since (k, 2) clustering is a special case of a j dimensional projection, it implies that Okk/ss) dimensions are sufficient. Given that these dimension reductions are based PCA-type methods, they are linear and therefore seem promising initially. Unfortunately, this technique has serious drawbacks. It does not satisfy the requirements for Definition 2.T only preserving the cost on aggregate rather then per individual point, and thus cannot be combined with the chaining technique" 3
Without the chaining technique, the best bound one can hope for is of the order Ô (VR2)T which falls short of what we are aiming for.
Another important technique used to quantify optimal solutions of (k. 2) clustering initially pro- posed by 73) and subsequently explored by [43 35 and has frequently seen use in coreset literature 40 46 Succinctly, it states that (1 + e) approximate solution to the (1,j, z) clustering problem of a point set P is contained in a subspace spanned by Ō(j²/=) input points of P. While this result improves over PCA for large values of k. applying it only yields a learning rate of the order O( (/t²"//). /x). It turns out that this technique has the exact same limitations as PCA, namely that costs per point are not preserved, and thus only offers a different tradeoff in parameters.
Our new insight: Given the state of the art, designing dimension reduction technique that would enable the application of the chaining technique might seem hopeless, and indeed, we were not able to prove such. The key insight that allows us to bypass these bottlenecks is to find a dimension reduction
Consider an embedding matrix S ddxm Clearly. there exists some vector E that is in the kernel of
whenever m < d, hence for any vector p. ||p (æ + p)]l2 cannot be preserved. 'PCA as well as the other potential alteraatie dimension reduction techniques also do not satisfy the relaxed detinition that would be sufficient for the analysis go through.
5

---

that applies not to all solutions U, but only to a certain subset of them. Indeed, we show that for any point set P contained in the unit ball and any subspace 2/ of dimension j. there exists a subspace S S s. This similar the guarantee provided by 73 but stronger in that it (i) applies to arbitrary subspaces, which is required for the chaining analysis, and (ii) applies to each point of P individually, rather than for the entire point set P on aggregate. We then augment the chaining analysis by applying a union bound over all (/22) possible dimension reductions, thereby capturing all solutions U. We are unaware of any previously successful attempts at integrating multiple dimension reductions within chaining analysis and believe that the technique may be of independent interest.
spanned by O(i/E²) points of P such that for every point |cost(p,L1 (() - cost(ps,243
Useful results from learning theory
Our goal is to bound the rate with which the empirical risk decreases for clustering problems. For a fixed set of n points P and a set functions F P + R, we define the Rademacher complexity (Rad,) and the Gaussian complexity (Gn) wrt F respectively as
E. sup E(O)) Rad = n FEF PEP
Gn(F)= --
1 Th
Eg sup E(D) 9p Fer PEP
where 7n are independent random variables following the Rademacher distribution, whereas Ip are independent Gaussian random variables. In our case, we can think of f as being associated to solution S (respectively a solution W) and f(p) cost(p, = min ||p- s|ß (respectively f() cost(p. 24) = mingeu [I -UTT))p )p1)). Since we associate every f with a cost vector os, we will use Rad,, (F) and Rad,, (V) as well G, (F)) and (V) interchangeably. The following theorem is due to Bartlett and Mendelson.
99.
Theorem 4.1 (Simplified variant of Theorem of Bartlett and Mendelson (9). Consider a loss
function L : A - (0. 1]. Let F be class of functions mapping from X to A and let (X,)²= be independent samples from D. Then, for any integer n and any > O, with probability at least 1 - over samples of length n, denoting by Bn the empirical risk, every f E F satisfies
8 2mm5
EL(F(X)) S BnL(f(X)) + Rad,, (F) +
7
Thus, in order to bound the excess risk, Theorem 4.1 shows that it is sufficient to bound the Rademacher complexity. It is well known (see, for example, B.3 of Rudra and Wootters (68) that Rad, (V) < V2TG,, (V). Thus sometimes more convenient. Note that if V is the set of all cost vectors, clustering nets are mere N(V. e) Using these nets, we can bound the Rademacher and Gaussian complexity. Indeed the following lemma holds.
can alternativeyy bound the Gaussian complexity, which is
Lemma 4.2. Let D be distribution over Ba and let P a set of n points sampled from D. Sup- pose that for set of n--imensional vector V, we have an absolute constant C,y > 0 such that log [V, e)) E 0(2-210 log" (CC). Then
Gv(V) (1 Clog7+2
7+2
n
The specific types of nets used in our study and the size bounds for those nets will be the key to obtaining the desired upper bounds and will be detailed in the next section.
5 Generalization bounds for center-based clustering and subspace clustering
We start by giving our generalization bounds for center based clustering and subspace clustering problems. For subspace clustering problems, we first state the result for general (k. =) clustering. An improvement for the special case z 2 will be given later.
Theorem 5.1. Let D be distribution over B and let P be a set of points sampled from D. For any set of k points S C. Bd, denote by e the n n-dimensional cost vector of P in solution S

---

with respect to the (k, cllusterrn objective. Moreover we denote by e the n n-dimensional cost vector of P in solutioo U with respect to the (k. (.,2))cluustring objective. Let Vg be the union of all cost vectors of P for the center-based clustering and Vjz the union of all cost vectors for subspace clustering. Then with probability at least
k logoo" n
log 1/6 n
(V:) EO
(2)
n
k. log jn lo
log 1/6 n
(v(V)a)) E
(3)
7
Following Theorem 4.1 it is sufficient to bound the Rademacher complexity in order to bound the excess risk. The Rademacher complexity is, up to lower order terms, equal to the Gaussian complexity, which, following Lemma 4.2 may be bounded by obtaining small nets with respect to the I1-I|so norm, We believe that the results on the bounds of the nets, may be of independent interest and we'll Il state these results in the following Lemma.
Lemma 5.2. Let D be a distribution over B and let P a set of n points sampled from D. let V2 be defined as Theorem 3.1 let V,,= be defined as in Theorem 5.1
Then
(V,,,, I1-llo,, e)1 S exp(O(1)=*) k- log n. (log(z) + (og)
(4)
[VV,,,, I1- e) exp(O
+2 k- j-j.e "logn + jlo[(j ")) log=
(5)
Combining Lemma 5.2 with Lemma 4.2 now yields the immediate bound on the Rademacher and Gaussian complexity. Following the discussion from Section 3 we use terminal embeddings to prove the part of Lemma 5.2 pertaining to (k; z) clustering, see Appendix B Unfortunately, the terminal embedding technique is not admissible for obtaining nets for subspace clustering as clarified in Section 3 Thus, we use an entirely different approach. We show the existence of collection of dimension reducing maps with subspace preserving properties. Fortunately, the number of dimension reducing maps is small. Our desired net sizes then follow by enumerating over all of these dimension reducing maps, and for the candidate solutions covered by each such dimension reducing map, can find an efficient net. First, we introduce a slightly different, but closely related notion to (1, 2) -nets.
Definition 5.3 (Projective Nets). Let P C. B3 be set of points, and let z be positive integer. For a d X j matrix S with columns that have at most unit norm and any point p P. define the projective cost as costpraj (p, 5) = ||5 pllz. Let V be the set of all projective cost vectors induced by such matrix S. We call a (VV. I1- E) a -projecvve net of P.
On high level, the proof largely relies the following decomposition. Let U be a candidate subspace and let be a projection matrix used to approximate [[ UU yll We have
( (d- U1pl - |UT - - - NUU - 11)p (6)
(3)
(4)
(5)
Here, we wish to select II such that (I 1)pp12 is small for all p E P. Note that this implies that the terms 2p TTTTTTT (I - Typ and |JUUT( pll are small. For the term (2), we merely have to show that projective nets exist. If the number of II is small, we can further construct good nets for the terms (1) and (3). We start by giving a bound for the projective nets. Our first Lemma 5.4 shows that if the points lie in sufficiently low-dimensional space, such net can be obtained by constructing a net N BB 11-112, e') for a sufficiently small e'.
Lemma 5.4. Let P C B be a set of points, and & be a positive integer. Then there exists an (e, -projecvve net of size [V,V, (l-Ilxx;)) S exp(O(1) d j -logje-))).
To reduce the dependency on the dimension, we now use the following lemma. Essentially, it shows that in order to retain the properties of U, we can find projection matrix II of rank at most O(je ?).
Lemma 5.5. Let P C By. For any orthogonal matrix U E RRixd, there exists M S P, with
MM O(j E =2)) such that Vp E P, (I 11M)ppl S [|(1 - H1r))pl.
7

---

We now use this lemma as follows. We can efficiently enumerate over all candidate II. as Lemma 5.5 guarantees us that we only have to consider (f-5" =) S exp(j E 2 log n) many different M inducing projection matrices. This immediately gives us O-nets for the terms (1) and (3). For each IT, we then apply Lemma which gives us net for term (2). Finally, by choice of II, we can show that terms (4) and (5) are negligible.
5.1
Tight generalization bounds for projective clustering
For the specific case of j,, 2) clustering, also known as projective clustering, we obtain an even better dependency on j. similar bound can likely also be derived using the seminal work of [39], though the dependencies on log and log 1/5 are slightly weaker. The proof uses the main result by 45), itself heavily inspired by [39] and arguments related to bounding the Rademacher complexity of linear function classes. Crucially, it avoids the issue of obtaining explicit dimension reduction entirely, but the approach cannot be extended to general (k, z) clustering.
Theorem 5.6. Let D be a distribution over B2 and let P a set of points sampled from DD For any
set u of k orthogonal matrices of rank at most j, we denote by vet the n-dimensional cost vector of
P in solution U with respect to the (k. j. -)-clsteringg objective, i.e. oo = mingeu [[T UU yp
Let V2 be the union of all cost vectors of P. Then with probability at least 1 8 for any y > 0
(V
(V EO
kjj
log2+7
3+7
11
log 1/6
Finally, we also show that the bounds from Theorem 5.6 and factors.
33 are optimal up to polylogarithmic
Theorem 5.7. There exists a distribution D supported on B such that E, (Vi22) E Q (V(ki)/m)
The rough idea is define distribution D supported the nodes of 2kj-dimensional simplex with some points having more probability mass and some points having smaller mass. Using the tightness of Chernoff bounds, we may then show that the probability of fitting a subspace clustering to good fraction the lower mass points is always sufficiently large.
Experiments
Theoretical guarantees are often notoriously conservative compared what is seen in practice. In this section, we present empirical findings detailing whether the risk bounds from the previous sections are also the risk bounds one can expect when dealing with real datasets. Indeed, for the related question of computing coresets, experimetal work by (7]) seems to indicate that the worst case bounds by [47] are not what one has to expect in practise for center based clustering. Generally, two properties can determine the risk decrease. First, the clusters may be well separated [4] 29]. Indeed, making assumptions to this end, there is also some theoretical evidence that rate of O /n) is possible 52 The other, somewhat related explanation is that if the ground truth consists of k < k clusters 13 the dependency on i will point more towards the smaller, true number of clusters. We run the experiments both for center based clustering, as well as subspace clustering. While the focus of the paper is arguably more on subspace clustering, the experiments are important in both cases. Although both problems are hard to optimize exactly, center based clustering is significantly more tractable and thus may lend better insight into practical learning rates. For example, we have an abundance of approximation algorithms for (ks 2) clustering [6] 61] whereas, even in the of (kt, 1, 2 clustering in two dimensions [49] is not possible to find any finite approximation in polynomial time.
In the main body, we focus on (k: 1, clustering, as there already exists a phase transition in terms of the computational complexity between the normal k-median and k-means problems and the (k: 1, 1) and (k: 1, 2) clustering objectives, while j still admits more positive results than other subspace clustering problems Agarwal et al. 3. Feldman et al. [1 42).
Datasets We use four publicly available real-world datasets: Mushroom 70
Skin-Nonskin 12
MNIST [51] and Covtype [15]. Below, we show the results the Covtype dataset, and the remaining
8

---

F1
0.14
K:20
e-10
R-30
0,00175
6-30
6-20
0.00
0.001.0
0.08
0.00125
0.001.0
0.006
000075
0424
000000
000022
0050
0000000
500
2000
1300
2000
2500
2000
23003
4003
1090
1500
2000
2350
3003
3000
jrl. cmd
0 0000000
D00014
0 000022
1-50
500040
Docen
0 0,00055
D00009
0.00004
00005
00000
0.000C0
1000
1500
1500
2002
1550
Figure 1: Excess risk for line clustering on Covtyp. Shaded areas show max-min intervals.
experiments deferred the supplementary material. Each dataset normalized by the diameter, ensuring that all points lie in By
Table 1: Datasets used for the experiments
Dataset
Points
Dim
Labels
Mushrooms 3,124
112
2
MNIST
60,000
784
10
Skin Nonskin
245,057
2
Covtype
581,012
54
7
Problem parameters and algorithms For both center based clustering as well as subspace clus- tering, we focus on the powers z E 21,2, 4). 2 is arguably the most popular and also the most tractable variant. z is the objective with the least susceptibility consider the cases = 3, due to it minimizing asymmetry and z 4 as tractable alternative the coverage objective - oc. The excess risk is evaluated for & E {10, 20, 30, 50} for both center based and subspace clustering. Expectation maximization (EM) type algorithms are used for both center-based and subspace clustering, though this is severe computational challenge fo (1,j.2) clustering, if z * 2, see (24] 36). Given a solution S we first assign every point to its closest center and subsequently recompute the center. For more details on initialization and concrete implementations, we refer to the supplementary material.
outliers. Finally, we
Experimental setup and results To estimate the optimal cost OPT for the two objective functions, run the corresponding appropriate algorithms mentioned above ten times the entire dataset P and use the minimal objective value as an estimate for OPT. We obtain a sample S; of size n by sampling uniformly random and estimate the optimal cost for that sample, OPT, We repeat this 5
times. The empirical excess risk is calculated as E, // Σ P.OPP. OPT. The excess risk for based clustering is evaluated on exponential-sized subset sizes n E [26 .?,.,, 212).

---

We fit line of the form c. K where c, 91. 92 are the optimizeable parameters. Let be the excess risk in run i. Let and n, the values of and run and let the total number of times the excess risk was evaluated for each combination of algorithm and dataset. We use gradient descent on the following loss to optimize the parameters LSE Σi= (3)
The results in Figure I show that the excess risk for subspace clustering decreases quicker for higher values of 2, and we see a similar pattern for center-based clustering. The supplementary material contains more details on the empirical evaluations of center-based clustering. The best-fit lines shown Tables and the supplementary material indicate that the empirical excess risk values decrease slightly quicker than predicated by theory. The expected values are 91 = 92 = 0.5 and we observe Q1 92 around 0.44, 0.52 respectively. For this indicates slightly favorable dependency in practice. For 92, we consider the difference to the theoretical bound of 0.5 negligible. The choice of does not seem to have significant impact on either finding. For subspace clustering, the dependency on k is a bit more pronounced and increases slightly towards the theoretical guarantees. Contrary to hopes that margin or stability conditions might occur on practical datasets, the results indicate that the theoretical guarantees of the learning rate near-optimal even in practice. Moreover, the rates were not particularly affected by either the choice of a or by the dimension, j when analyzing subspace clustering.
7 Conclusion and open problems
In this paper, we presented several new generalization bounds for clustering objectives such as k-median and subspace clustering. When the centers are points constant dimensional subspaces, our upper bounds are optimal up to logarithmic terms. For projective clustering, we give a lower bound showing that the results obtained by (3) are nearly optimal. key novel technique was using an ensemble of dimension reduction methods with very strong guarantees.
An immediate open question is to which degree ensembles of dimension reductions improve learning rates over a single dimension reduction. Is it possible to find natural problems where there is separation between the embeddability and the learnablity of class of problems, or given the ensemble, is it always possible to find a single dimension reduction with the guarantees of the ensemble? Another open question is motivated by the recent treatment of clustering through the lens of computational social choice [19] Using current techniques from coresets [17] and learning theory
[5]. it seems difficult to improve over the learning rate of (v**m) for the fair clustering problem specifically. It it possible to match the bounds for unconstrained clustering?
Disclosure of Funding Acknowledgements
Maria Sofia Bucarelli was partially supported by projects FAIR (PE0000013) and SERICS (PE00000014) under the MUR National Recovery and Resilience Plan funded by the European Union NextGenerationEU. Supported also by the ERC Advanced Grant 788893 AMDROMA, EC H2020RIA project "SoBigData+4" (87 1042). PNRR MUR project 1R0000013-SoBigDate
Chris Schwiegelshohn was supported by the Independent Research Fund Denmark (DFF) under a Sapere Aude Research Leader grant No 1051-00106B.
10

---

References
[1] E. F. Abaya and G. L.. Wise. Convergence of vector quantizers with applications to optimal quantization. SIAM Journal Applied Mathematics, (4(1:1133-189 1984. doi: 10.1137/ 0144013. URL https:://ooll http:::/ddo..or///// 10. 1137/0144013
[2] P. K. Agarwal, S. Har-Peled, and K. R. Varadarajan. Approximating extent measures of points. ACM, 51(4):606-635, 2004.
[3] P. K. Agarwal, C. M. Procopiuc, and K. R. Varadarajan. Approximation algorithms for a k-line center. Algorithmica, 42(3-4):221-330, 2005. doi: 10.1007750043--05511666 URL
https://doi. org/10.
[4] H. Angelidakis. K. Makarychev, and Y. Makarychev. Algorithms for stable and perturbation- resilient problems. In H. Hatami, P. McKenzie, and V. King, editors, Proceedings of the 49th Anmual ACM SIGACT Symposium on Theory of Computing, Canada, June 19-23, 2017. pages 438-451. ACM, 2017. doi: 10.1145/305399.335553 URL
2017, Montreal, QC,
https:// org/ 1145/ 001455/3553399 33555999955999999558777 3055487
[5] A. Antos, L. Gyorfi, and A. Gyorgy. Individual convergence rates in empirical vector quantizer design. IEEE Transactions on Information Theory, 51(11):40134402 2005. doi: 10.1109 1009/TTT 066.85
[6] D. Arthur and S. Vassilvitskii. k-means++: the advantages of careful seeding. In Proceedings of the Eighteenth Annual ACM-SIAM Symposium Discrete Algorithms, SODA 2007, New Orleans, Louisiana, USA, January 7-9, 2007, pages 1027-1035, 2007. URL http:httt..aaae org/ trgg/itation..o cfm?id= 1283494
[7] R. Bach and M. I. Jordan. Predictive low-rank decomposition for kernel methods. In Proceedings of the 22nd international conference Machine learning, ICML '05, page 33-40, New York, NY, USA, 2005. Association for Computing Machinery, ISBN 595931805 doi: 10.1 1023111.11111222333
URL htttss:/ddol. org/oogg///oo 11e...11111111111 1102356
[8] Bartlett, T. Linder, and Lugosi. The minimax distortion redundancy in empirical quantizer design. IEEE Transactions on Information Theory, (4(5):1802-1813 1998. doi: 10.1 109/18. 8. 705560.
[9] L.. Bartlett and S. Mendelson. Rademacher and gaussian complexities: Risk bounds and structural results. J. Mach. Learn. Res., 3:463 2002. URL
v3/bartlett02a. html
[10] P. L. Bartlett, T. Linder, and G. Lugosi. The minimax distortion redundancy in empirical quantizer design. JEEE Trans. Inf. Theory, 44(5):1802-1813, 1998. doi: 10. 109/18. 70556.. URL httpht orgooo////// 10. 1109/11911118 705560
[11] L. Becchetti, M. Bury, V. Adden-Addad, Grandoni, and Schwiegelshohn. Oblivious dimension reduction for k-means: beyond subspaces and the
lemma. In Proceedings of the 51 Annual ACM SIGACT Symposium on Theory of Computing, STOC 2019, Phoenix, AZ, USA, June 23-26, 2019, pages 1039-1050, 2019. doi: 10. 10.1145/3113276.3313311 URL https::///oll: org/ 10. 11111111111/// 3316318
[12] R. Bhatt and A. Dhall. Skin Segmentation. UCI Machine Learning Repository, 2012.
[13] C. Bhattacharyya, R. Kannan, and A. Kumar. How many clusters? an algorithmic answer. In J. Naor and N. Buchbinder, editors, Proceedings of the 2022 ACM-SIAM Symposium on Discrete Algorithmss, SODA 2022, Virtual Conference / Alexandria, VA, USA, January
9 12, 2022, pages 2607-2640. SIAM, 2022. doi: 0t..1137/197811111977000 https://doi. org/10..r/. 1ww.:111.97111199777110 102
URL
[14] G. Biau, L. Devroye, and G. Lugosi. On the performance of clustering in hilbert spaces. IEEE Transactions on Information Theory, 54(2):781 1-790, 2008. doi: 109/TTTT.200..9135511
[15] J. Blackard. Covertype. UCI Machine Learning Repository, 1998.

---

[16] C. Boutsidis. A. Zouzias, and P. Drineas. Random projections for SkS-means clustering. In Advances in Neural Information Processing Systems 23: 24th Anmual Conference on Neural Information Processing Systems 2010. Proceedings of meeting held 6-9 December 2010, Vancouver, British Columbia, Canada. pages 198-306 2010.
[17] V. Braverman, V. Cohen-Addad, S. H. Jiang, R. Krauthgamer, C. Schwicgelshohn, M. B. Toftrup, and X. Wu. The power of uniform sampling for coresets. In 63rd IEEE Annual Symposium on Foundations of Computer Science, FOCS 2022, Denver CO, USA, October 31 November 3, 2022, pages 462-473, 473. IEEE, 2022. doi: 10. 22110/9FOC54455..2022222 https://do1. org /0g///..// 1109 1119/F0005495////11 2022. 00051
URL
[18] D. Calandriello and L. Rosasco. Statistical and computational trade-offs in kernel k- means. In S. Bengio, H. Wallach, H. Larochelle, K. Grauman, N. Cesa-Bianchi, and Garnett, editors, Advances Neural Information Processing Systems, volume 31. Cur- ran Associates, Inc., 2018. URL URL httttp:://prooeeedngge www.eeeiiinnnn...iis.se.oe 1w00ee4430723111110oaaaaaaa
R.
Paper. .df
[19] Chierichetti, R. Kumar, S. Lattanzi, and S. Vassilvitskii. Fair clustering through fairlets. In I. Guyon, U. von Luxburg, S. Bengio, H. M. Wallach, R. Fergus, S. V. N. Vishwanathan, and R. Garnett, editors, Advances in Neural Information Processing Systems 30: Annual Conference on Neural Information Processing Systems 2017, December 4-9, 2017, Long Beach, CA, USA, pages 5029-5033 2017.
[20] R. Chitta, R. Jin, T. C. Havens, and A. K. Jain. Approximate kernel k-means: Solution to large scale kernel clustering. In Proceedings of the 17th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, KDD 111. page 895-903, New York, NY, USA, 2011. Association for Computing Machinery. ISBN 978 148800001133 137. doi: 10.1145/2020408 2020055
URL htt.::ttt////tll org/ 10. 10111114/0000
1145/2020000 2205552222408...0 2020558
[21] R. Chitta, R. Jin, and A. K. Jain. Efficient kernel clustering using random fourier features. In Proceedings of the 2012 IEEE 12th International Conference on Data Mining, ICDM '12, page 161-170, USA, 2012. IEEE Computer Society. ISBN 9780769549057. doi: 10. 10.1109/IC
2012.61. URLhttpps //w.i. org/10. 1109 ICDMM 2012. 61
[22] P. Chou. The distortion of vector quantizers trained on n vectors decreases to the optimum as (1/n). In Proceedings of 1994 IEEE International Symposium Information Theory, pages 457-, 1994. doi: 10. 109//SST. 1994.39507..
[23] K. L. Clarkson and D. P. Woodruff. Numerical linear algebra in the streaming model. In Proceedings of the 41st Annual ACM Symposium Theory of Computing (STOC), pages 205-214, 2009.
[24] K. L. Clarkson and D. P. Woodruff. Input sparsity and hardness for robust subspace approxi- mation. In JEEE 56th Annual Symposium Foundations of Computer Science. FOCS 2015, Berkeley, CA, USA, 17-20 October, 2015, pages 310-329, 2015. doi: 10.1109/FOCS. URL httt://d/ doi. org 10. 1109/FOCS. 2015.
[25] K. L. Clarkson, E. Hazan, and D. Woodruff. Sublinear optimization for machine learning. J. ACM, 59(5):23:1-23:49 2012. doi: 10. 10.114/33776666622766333 URL http/t//t////o org/10 1 1145/2371656 237716111666622118888 2371658
[26] S. Clémençcon. On u-processes and clustering performance. In J. Shawe-Taylor, R. Zemel, Bartlett, F. Pereira, and K. Weinberger, editors, Advances in Neural Information Processing Systems, volume 24. Curran Associates, Inc., 201 1. URL httpttts:///oceeddddde ieuruu neurips Paper .aneer.pd.. pddf
[27] M. B. Cohen and R. Peng. Lp row sampling by lewis weights. R. Rubinfeld, editors, Proceedings of the Forly-Seventh Annual ACM on Symposium on Theory of Computing, STOC 2015, Portland, OR, USA, June 14-17, 2015, pages 183-192. ACM, 2015. doi: (0.114527463992746666 http: //tp::///ooiiiie org 1ttp///0..111127440 2746567
A. Servedio and
12

---

[28] M. B. Cohen, S. Elder, C. Musco, C. Musco, and M. Persu. Dimensionality reduction for k-means clustering and low rank approximation. In Proceedings of the Forty-Seventh Annual ACM Symposium on Theory of Computing, STOC 2015, Portland, OR, USA, June 14-17, 2015, pages 163-172, 2015.
[29] V. Cohen-Addad and C. Schwiegelshohn. On the local structure of stable clustering instances. In 58th IEEE Annual Symposium Foundations of Computer Science, FOCS 2017, Berkeley, CA, USA, October 15-17, 2017, pages 49-60, 2017. doi: 10.11099/0S URL
https://doi: http::////ooo.//////// 1109 1111/F0CS90000 /FCS 2017
[30] V. Cohen-Addad, D. Saulpic, and C. Schwiegelshohn. new coreset framework for clustering.
In S. Khuller and V. V. Williams, editors, STOC '21: 53rd Annual ACM SIGACT Symposium on Theory of Computing, Virtual Event, Italy, June 21-25, 2021. ACM, 2021. URL https
//doi. org 10. 1 1145/3406325
3406325.... 3451022
[31] V. Coden-Addad, Saulpic, and C. Schwiegelshohn. Improved coresets and sublinear algo- rithms for power means in euclidean spaces. In A. Beygelzimer, Y. Dauphin, P. Liang, and J. W. Vaughan, editors, Advances in Neural Information Processing Systems 35: Annual Conference on Neural Information Processing Systems 2021, NeurlPS 2021, December 7-10, 2021, Virtual Conference, 2021.
[32] V. Cohen-Addad, K. G. Larsen, D. Saulpic, and C. Schwiegelshohn. Towards optimal lower bounds for k-median and k-means coresets. In S. Leonardi and A. Gupta, editors, STOC 22: 54th Annual ACM SIGACT Symposium on Theory of Computing, Rome, Italy, June 20 24, 2022, pages 1038-1051 ACM, 2022. doi: 10. 00.1145/35199353559998 URL https //doi.org/ 10. /144/3511955 3519946
[33] V. Cohen-Addad, K. G. Larsen, D. Saulpic, C. Schwiegelshohn, and O. A. Sheikh-Omar. Improved coresets for euclidean k-means. In NeurIPS, 2022.
URL http::/ [20Caab6cBaaaaaaddd22eeeeddddddd Atwe:e44---bstttttt---aaaaa Conference html
nips cc lappp_pppeeeeeeee www.ffilalepee//////e pappr//022/haaeeeepppppppppaa
[34] V. Cohen-Addad, D. Saulpic, and C. Schwiegelshohn. Deterministic clustering in high dimen- sional spaces: Sketches and approximation. In 64th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2023 (to appear), 2023.
[35] A. Deshpande and K. R. Varadarajan. Sampling- Sampling-based dimension reduction for subspace approximation. In D. S. Johnson and U. Feige, editors, Proceedings of the 39th Annual ACM Symposium on Theory of Computing, San Diego. California, USA, June 1 11-13, 2007, pages 641-650. ACM, 2007. doi: 10.1145/1250790, 200.1/55599900.088844.8 250884. URL htttt:///ddoi org/oo.///// 10. 1145/ 1250790 1250884
[36] A. Deshpande, M. Tulsiani, and N. K. Vishnoi. Algorithms and hardness for subspace ap- proximation. In D. Randall, editor, Proceedings of the Twenty-Second Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2011, San Francisco, California, USA, Jan- uary 23-25, 2011, pages 482-496. SIAM, 2011. doi:
URL
https://dot 2rg/10.10 1137/1 www.99811119798...8888
[37] I. S. Dhillon, Y. Guan, and B. Kulis. Kernel k-means: Spectral clustering and normalized cuts. In Proceedings of the Tenth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, KDD '04, page 551-556. New York, NY. USA, 2004. Association for Computing Machinery. ISBN 1581138881, doi: 10.1145/1014052.10144 1014118, URL https
7/doi org/orgg//11 /000 1145/1014052 1014118
[38] H. Ding. A sub-linear time framework for geometric optimization with outliers in high dimen- sions. In F. Grandoni, G. Herman, and P. Sanders, editors, 28th Annual European Symposium on Algorithms, ESA 2020, September 7-9, 2020, Pisa, Italy /irrtull Conference), volume 173 of L.Ples, pages 38:1 138:21.. Schloss Dagstuhl Lentruiz-eenuuu für Informatik, 2020. doi: 10.4230//IPIcs.ESAA. 2020.38. URLpst //t.i///....o// orgo /00 4230/LIPICS...... ESA 2020.0020.22 38
[39] C. Fefferman, S. Mitter, and H. Narayanan. Testing the manifold hypothesis. Journal of the American Mathematical Society, -944)99331 2016.
13

---

[40] D. Feldman and M. Langberg. A unified framework for approximating and clustering data. In Proceedings of the 43rd ACM Symposium on Theory of Computing, STOC 2011, San Jose, CA. USA, 6-8 June 2011 I, pages 569-578, 2011.
[41] D. Feldman, A. Fiat, and M. Sharir. Coresets forweighted facilities and their applications. In 47th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2006), 21-24 October 2006, Berkeley, California, USA, Proceedings, pages 315-3330000 1-244.4 IEEE Computer Society, 2006. doi: 10. 100//F/CS.000...2 URL https///:///do org/ 10. 1109/FOCS. 2006 22
[42] D. Feldman, A. Fiat, M. Sharir, and D. Segev. Bi-criteria linear-time approximations for generalized <-mman/mediaanceenter In J. Erickson, editor, Proceedings of the 23rd ACM Symposium on Computational Geometry, Gyeongju, South Korea, June 6-8, 2007, pages 19-26 ACM, 2007. doi: 0A414445122709..2447777 URL /RLhtts::///ol org/ 10. 1145/ 1145/1247066 1247069 1247073
[43] D. Feldman, M. Monemizadeh, C. Sohler, and D. P. Woodruff. Coresets and sketches for high dimensional subspace approximation problems, In M. Charikar, editor, Proceedings of the Twenty- Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2010, Austin, Texas, USA, January 17-19, 2010, pages 630 649. SIAM, 2010. doi: 00.113771.97811117777735553 URL httph::t///ott org/ 10. 97117/71.97711197777777 53.
[44] D. Feldman, M. Schmidt, and C. Sohler. Turning big data into tiny data: Constant-size coresets for k-means, pea, and projective clustering. SIAM J. Comput. 49(3);601-665 1657, 2020. doi: 10.1137/18M1209844 URL battpss://oi.... 10. 1137/ 1117711111111853
[45] D. J. Foster and A. Rakhlin. foo vector contraction for rademacher complexity. CoRR, abs/191 1.06468, 2019. URL
06468
[46] L. Huang and N. K. Vishnoi. Coresets for clustering in euclidean spaces: importance sampling is nearly optimal. In K. Makarychev, Y. Makarychev, M. Tulsiani, G. Kamath, and J. Chuzhoy, editors, Proccedings of the 52nd Anmual ACM SIGACT Symposium on Theory of Computing. STOC 2020, Chicago, IL, USA, June 22-26, 2020, pages 1416-1429, ACM, 2020. doi: 10.1145/ 3357713.3384296. URL httph: //ts:////oi.. org/ 1ttp:/11..111/333577/
http:////.bbooor...1011/4/////// 338444 3384296
[47] L. Huang. J. Li, and X. Wu. Towards optimal coreset construction for (k, z)-clestering: Breaking the quadratic dependency on k. CoRR, abs/2211.11922 2022. doi: 10.48500/aXx..221111922
http:htttt//dttt org/ 10. 400.0/8550//0/ ar 2211. 11923
[48] N. Klein and N. E. Young. On the number of iterations for dantzig optimization and packing-covering approximation algorithms. SIAM J. Comput, 44(4): 1144))111441111) 1172, 2015. doi: 10.1137/12087222X. URL httph:h//////// org/ 1137/120872221
[49] V. A. Kumar, S. Arya, and H. Ramesh. Hardness of set cover with intersection 1. In U. Montanari, J. D. P. Rolim, and E. Welzl, editors, Automata, Languages and Programming. 27th International Colloquium, ICALP 2000, Geneva, Switzerland, July 9-15, 2000, Proceedings, volume 1853 of Lecture Notes in Computer Science, pages 624 635. Springer, 2000. doi: 10.1007/3-540-44 45000--------- 53. URL https::/doiii org/ 10. 1007/3 540 45022- X__3
[50] Lauer. Risk bounds for learning multiple components with permutation-invee invariant losses. In S. Chiappa and R. Calandra, editors, The 23rd International Conference Artificial Intelligence and Statistics, AISTATS 2020, 26-28 August 2020, Online [Palermo, Sicily, Italy), volume 108 of Proceedings of Machine Learning Research, pages 1178 1187. PMLR, 2020. URL
htttp:/pprocediing www.mmlr.r.rerr. www.:ppessss/////e http//vvvv1/aaaar2.... html
[51] Y. Lecun, L. Bottou, Y. Bengio, and P. Haffner. Gradient-based learning applied to document recognition. Proceedings of the IEEE, (6((1))2278-233) 1998. doi: 10.1 10.1199/,.726791.
[52] C. Levrard. Nonasymptotic bounds for vector quantization in hilbert spaces. The Annals of Statisties, 43(2), apr 2015. doi: 10. a0. 1293. URL. https: //doi. org/10 10. 1214% 2F14 aos1293
14

---

[53] S. Li and Y. Liu. Sharper generalization bounds for clustering. In M. Meila and T. Zhang, editors. Proceedings of the 38th International Conference on Machine Learning. ICML 2021, 18-24 July 2021, Virtual Event, volume 139 of Proceedings of Machine Learning Research, pages 6392-6402. 6402. PMLR, 2021. URL htt.hhttp/pprcceednnge mmr. www.ppressssv/eee h1tp///19/l1/kaa. html,
[54] T. Linder. On the training distortion of vector quantizers. IEEE Transactions on Information Theory, 46(4):1617-1622) 2000. doi: 111109988880005.
[55] T. Linder, G. Lugosi, and K. Zeger. Rates of convergence in the source coding theorem, in empirical quantizer design, and in universal lossy source coding. IEEE Transactions on Information Theory, 40(6):1728- 1740, 1994. doi: 10.1109/18.34044
[56] Liu, X. Huang, Y. Chen, and A. K. Suykens. Random features for kernel approximation: A survey on algorithms, theory, and beyond, 2020. URL 11154
[57] Y. Liu. Refined learning bounds for kernel and approximate SkS-means. In M. Ran- zato, A. Beygelzimer, Y. N. Dauphin, P. Liang, and W. Vaughan, editors, Ad- vances in Neural Information Processing Systems 34; Annual Conference on Neural Information Processing Systems 2021, NeurIPS 2021, December 6-14, 2021, virtual. pages 6142-6154, 2021. https: p/tpceed/////oooeinggg/ http://rrroodnng...rroroooooo www.ipp.cc.pppprr///.....c /atperr/021/hahh/
34B66690000&88655eccc6666 Abstract.
[58] Y. Liu, S. Liao, S. Jiang, L. Ding, H. Lin, and W. Wang. Fast cross-validation for kernel-based algorithms. IEEE Transactions on Puttern Analysis and Machine Intelligence, 1P:1-1, 01 2019. doi: 10.109/TPAML220128822777
[59] S. P. Lloyd. Least squares quantization in PCM. IEEE Trans. Inf. Theory, 28(2): 1982. doi: 10. 1982.1056489) URL petps://doi.ooo 10.g//0..50 1109/TIT. 1056489
[60] K. Makarychev, Y. Makarychev, and I. P. Razenshteyn. Performance of oohhson-lindenseee transform for k-means and k-medians clustering. In Proceedings of the 5 Annual ACM
SIGACT Symposium on Theory of Computing, STOC 2019, Phoenix, AZ, USA, June 23-26. 2019, pages 1027-1038, 2019.
doi: 10.1145/3311326.3333 1145/3313276 033111117773333633
URL https://doi http:///ooooog////////////////
[61] R. R. Mettu and C. G. Plaxton. Optimal time bounds for approximate clustering. Mach. Learn., 56 56(1-3):35 60, 2004. doi: 10. //doi. 100 1023/022B/BBB MACH. 00000331144.8832.....
URL https
[62] S. Narayanan and J. Nelson. Optimal terminal dimensionality reduction in euclidean space. In M. Charikar and E. Cohen, editors, Proceedings of the 5 Annual ACM SIGACT Symposium on Theory of Computing, STOC 2019, Phoenix, AZ, USA, June 23-26, 20/9, pages ACM, 2019. doi: 10.1145/3313276.3333100 3316307
WRLL/ttps:://dtt /ttp:/oo...rr/11111114////1111
[63] R. Ostrovsky, Y. Rabani, L. J. Schulman, and C. Swamy. The effectiveness of lloyd-type methods for the k-means problem. J. ACM, 29(6):28:1122 1-22:22, 2012. doi: 10.1145/2395116.229951 11t.00.11112229911111 URL httpttttt///ooorrggggeee 1tt.:/......000011111////9/11110 2395117
[64] D. Pollard. Strong Consistency of K-Means Clustering. The Annals of Statisticss, 9(1): 140.
1981. doi: 1/2114/00/111734553333 URL https://doi org/10. 2214/20s/1177345333
[65] D. Pollard. A Central Limit Theorem for k-Means Clustering. The Annals of Probability, 10 (4):919 926, 1982. doi: 10. 10.1214/aaa 1/121//////111779937777 URL httt////t///oi.. http://ooo..or/1..11111111/1 1r.//0..11 1176993713
[66] D. Pollard. Quantization and the method of k-means. IEEE Trans. Inf. Theory, 28(2):199- 204, 1982. doi: 1981 URL http:///oo.orrgg..111010100 1982
1056481
[67] A. Rudi and I.. Rosasco. Generalization properties of learning with random features, 2016.
URL https: : //trxaaxivvv////////a htg/abb//102..44777
15

---

[68] A. Rudra and M. Wootters. Every list-decodable code for high noise has abundant near- optimal rate puncturings. In D. B. Shmoys, editor, Symposium on Theory of Computing. STOC 2014, New York, NY, USA, May 31 June 03, 2014, pages 764-773. ACM, 2014. doi: 10.1 (0.1145//591799.259919
URLhtttp
1145/ 2591977
[69] T. Sarlós. Improved approximation algorithms for large matrices via random projections. In Proceedings of the 47th Annual IEEE Symposium on Foundations of Computer Science (FOCS), pages 143-152, 2006.
[70] J. Schlimmer. Mushroom. UCI Machine Learning Repository, 1987.
[71] C. Schwicgelshohn and O. Sheikh-Omar. An empirical evaluation of k-means coresets. In S. Chechik, G. Navarro, E. Rotenberg, and G. Herman, editors, 30th Annual European Symposium on Algorithms, ESA 2022, September 5-9, 2022, Berlin/Potsdam, Germany, volume 244 of LIPlcs, pages 84:1 -8::17. Schloss Dagstuhl Leibniz Zentrrum für Informatik, 2022. doi: 0..420/LIPIcs.EEA.22222 84. URL httpss://oi.. www..rr//............ 4w30//22II0ss.... ESA 2022. 84
[72] J. Shawe-Taylos C. K. I. Williams, N. Cristianini, and J. S. Kandola. On the eigenspectrum of the gram matrix and the generalization error kernel-pca. IEEE Trans. Inf. Theory, 51(7); 2510 2522,,222222 2005. doi: 10. 10.1109/TI..20058855000 2005 850052
URL https:///tp.i.... org/ 10. 1109/TIT
[73] N. D. Shyamalkumar and K. R. Varadarajan. Efficient subspace approximation algorithms. In N. Bansal, K. Pruhs, and C. Stein, editors, Proceedings of the Eighteenth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2007, New Orleans, Louisiana, USA, January 7-9, 2007, pages 532-540. SIAM, 2007. 1283383 1283440
URL http: acm. org/ citation..... cfm7id=
[74] C. Sohler and D. P. Woodruff. Strong coresets for k-median and subspace approximation: Goodbye dimension. In 59th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2018, Paris, France, October 7-9, 2018, pages 802 813, 2018. doi: 10. 10.1109/F0CS.2018. 00081. URL httpp::s///oi..orr wttp///......////////// 1109/F0CS..... 0008.00081
[75] R. Vershynin. Introduction to the non-asymptotic analysis of random matrices. In Y. C. Eldar and G. Kutyniok, editors, Compressed Sensing, pages 210-268. Cambridge University Press, 2012. doi:
URL https://doi. org//0.
cbb9780511794308.000
[76] R. Vidal. Subspace clustering. IEEE Signal Process. Mag., 28(2):52-68, 2011. doi: 10.1109/
MSP.2010.939739, URL https://////d pttttps://do..org//1/ /00 1109/MSP. 2010. 00100999739
[77] R. Wang and D. P. Woodruff. Tight bounds for I, oblivious subspace embeddings. In T. M. Chan, editor, Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2019, San Diego California, USA, January 6-9, 2019, pages 1825-1843. SIAM, 2019. doi: 10. 10.1137/1.97816111 197778111977548.110 URL httph:ttts///o/t org/ 10 1137/1 9781111999771111
110
[78] S. Wang. A. Gittens, and M. W. Mahoney. Scalable kernel k-means clustering with nystrom approximation: Relative-error bounds. Journal of Machine Learning Research, 20(12):1 1-49, 2019. http::
org/ www.oo///....eeeoooooooo pwpprs/ v20/ 57- .html
[79] D. P. Woodruff and T. Yasuda. Sharper bounds for l, sensitivity sampling. In A. Krause, E. Brunskill, K. Cho, B. Engelhardt, S. Sabato, and Scarlett, editors, International Conference on Machine Learning, ICML 2023, 23-29 July 2023, Honolulu, Hawaii, USA, volume 202 of Proceedings of Machine Learning Research, pages 37238-37272. PMLR, 2023. URL mlr wttpss//2222wwodrufffo
html
[80] R. Yin, Liu, Lu, W. Wang, and D. Meng. Divide-and-conquer learning with nyström: Optimal rate and algorithm. Proceedings of the AAAI Conference on Artificial Intelligence, 34 (04):6696-6703, Apr. 2020. doi: 110.///.................... index. hwtp:/ppp//////////
v34i04.614777 htttsstts::/ //ojs.aaaai....................a aaai. .org/
AAAI/ http://ttilll./oooooo view/vi4.l.
16

---

[81] X. Zhang and S. Liao. Incremental randomized sketching for online kernel learning. In K. Chaudhuri and Salakhutdinov, editors, Proceedings of the 36th International Conference on Machine Learning, volume 97 of Proceedings of Machine Learning Reseurch, pages 7394 7403. PMLR, 09-15 Jun 2019. URL httts://proceeddnge mlr wtaalr.prs////eeeeeeee v97 v97/zhang19h
html
17

---

Supplementary Materials
A Proof of Lemma 4.2
In this section, we include the proof of Lemma an2 and some preliminary facts that will be useful for the proof.
Let r be Rademacher vector, ie. every entry r; is sampled independently uniformly from f-1, } Further, say that is Gaussian vector if every entry 9i is standard Gaussian with mean 0 and variance 1. We have the following useful properties of Gaussians.
Fact A.1 (Appendix B.1 by (68)) Let 01.... In
Gaussians with means μ4 and variances of.
If of S o2 for all i, then [[max Iad]] S 20 / log
If the Gaussians are independent, then Eim1 0g9i is Gaussian distributed with mean Σ 0:44 and variance Σ a/
If the gi independent standard Gaussians with mean 0 and variance 1, then E is Chi-squared distributed with mean [[[VY] E O(yn).
Another result we need is the following
Lemma A.2 (Lemma 5.2 of (71). [W 11122.)) & (1 2/e)².
We now ready prove the Lemma 4.2
The proof of Lemma is similar arguments used prove Dudley's 's theorem. We also write here the statement of the Lemma for the sake of completeness
Lemma (Lemma 4.2
Let D be distribution over B and let P be set of points sampled from D. Suppose that for a set of n rn-dimensional vectors V, we have absolute constants C, > such that
log WV(V, [)) E O(= -2 log" (n (n.nn .C).
(7)
Then
(Vclog1
|Clog n
Gn(V) E0
Proof. For ease of notation, we use solutions S induced by points, but the proof carries over without any modifications other than changing the notation to collections of subspaces U.
Consider an arbitrary cost vector S. We write S as telescoping sum
S
141, h.s
h=0
where o 0 and S a vector from
from.V(V NVV, 11-loo, 2-1) approximating SsS Observe that
11 - 1. < a+ - us + ri S 2.22 2-
(8)
18

---

due to the triangle inequality. Thus we have
n Gv(V)
Epg
sup(v )r 9
-Bpg
sup
Σ
(uhtis )
S 1=0
E P.g
sup(v S
h=0
Ep Pg
sup ght1.5 Sh.sE
(uh+1. Sr.
1=0
MV 3. (1+1))))) (XV.
log
E.
sup bt Sh [V (1+1)))) NNVV
(o4+1, - (o4t18-o/h1s4
h=0
+ +EP.s P.
sup A S..s [V 2 (XV
(oht1, - -
hm log
log
Bp
sup h+1.s A. LV(V (1
(Mi+1. - UA.STT
(9)
h=0
+Ep.
Su
(10)
We bound the terms
differently, starting with the latter.
For every
(o log n. ST S -1 - won n.5 1|2 [[]gg]12],
due to the Cauchy Schwarz inequality. Further,
||0 - Bug 1, vn. 11 olog n.S 1100 S Vn. log V 1
which, combined with the third item in Fact A. yields
( VTl O(1.
Ep
sup - ploon. EO
(II)
S
We now consider the term Due to the second item of Fact A.1 (1u+1s h.S is Gaussian distributed with mean () and variance
7
- S 2n22-21 24
Thus, we have, using the first item in Fact A.I
log
Er
sup A+13 0h.8 AA -0
1o - ST g
h=0
log 72
<
32n 24 log [V(V.I1-1lx.. 2-(411) N(V. 2-
h=0
(12)
19

---

Now using equation
we obtain that,
32n log
x XVV, 2- E O( log? n)
2-²)|
So we have that
log 72
32n 2 2h log
(1(+)) x 2-h)| O(v n log? n)
(13)
Adding the bounds 13 and for Terms
10 and
9 respectively yields the claim.
Finally, we will frequently use the following triangle inequality extended powers.
Lemma A.3 (Triangle Inequality for Powers (Lemma A.I of (60)). Let b, c be arbitrary set of points in a metric space with distance function d and let z be positive integer. Then for any & > 0
1 1+
d(a,b) S (1+5)= d(a, +
d(b,c)²
2z 2-1
[d(a,)) byt - d(a,c))) S d(a c)*
d(b,c)²
B Omitted Proofs for Center-Based Clustering
Lemma B.1. Let P C. Bg be a set of points. Let V be the set of all cost vectors of P foror (k, 2)- clustering. Then there exists an E-clustering net of size
[IV, S exp(O(1) 2 k d log(ze
Proof. We start by proving the bound for k Suppose we are given net ((B, |1. 6). for
8 to be determined later. Consider a candidate solution {s} with cost vector vfs) E V. Let s' be the point in E A(B I1. 6) of such that ||s s'll S 6, if s' is not unique any one will be sufficient. Let s be the cost vector S', The number of distinct solutions S' are [W 11-112. 8) exp(O(1) d log 1) due to Lemma A.2
What is left to show is that all solutions constructed in this way satisfy the guarantee of N/V (1-1,o0 8), for an appropriately chosen 8. We have for any p E P and any non non-negative integer 2 due to Lemma A.3
2z +
a
||p- s|l - -11p- --1p-111 81F <
a ||p
-
s||² +
|ss
s'11²
a
2-1
S a 1pp a|1 8 + (32)²
8
We set z and = a 2 T(222 e²_ Then the term above is upper bounded by
at most 1p >|| < 2. Now since |||p =||= - 1p s S for all B also implies |minses ||p =11² - minves |pp - & S e, we have proven our desired approximation.
To conclude, observe that by our choice of 8, the overall net N has size at most exp(O(1) z.d- log(2e-1)).
To extend this proof to k-centers, observe that any solution consisting of k centers can be obtained by selecting k points from Bg, rather than one. This raises the net size of the single cluster case by power of k.
We now show that Lemma B. combined with terminal embeddings yields the desired net. Lemma (Equation 4 in Lemma 5.2p. Let D be distribution over Bá and let P set of points sampled from D and let V be defined as in Theorem 2 Then
(V,,, (l) s exp(O(1)2² k.E lo (log(z) log(e (o)(
20

---

Proof. Let f RR - R be terminal embedding, that is f is such that m E 00 2 PI and for all E Pand E IRd
lp 1 a11* = ())) f())ll;
as given by 62 Therefore, for any candidate solution S, we also have
cost(p, S) (1 2f) f(S)).
In other words, the set of cost vectors in the image of f is the desired - for the true set of cost vectors. Hence E-nct for the cost vectors induced by solutions in the image of is also One)-net for the set of cost vectors.
thus may apply Lemma B.1 for all cost vectors induced by solutions in the image of f. After rescaling by constant factors, the overall net size is therefore exp(O(1)=² k log n (log(z) + log(=-1)))
C Omitted Proofs for Subspace Clustering
In this section, we provide full proofs for Section 5 relative subspace clustering. We start with a few basic lemmas that will be useful in the calculations later.
We further require the following bounds that will prove useful in the calculations later. Lemma C.1. Let 0, b be numbers in [0, 2] and lel e > O. Suppose a² = 12 + b. Then
|a bl E.
Moreover, for any non-negative integer 2, we have
la - bO < 2- (3z)*
Proof. For the first part of the lemma, we observe
la2 b21 = la bl (a (a+ b) s
which implies
la bl S..
For the second part, Lemma
A.3 implies
22
+
x-1
32 + +-1
|a bi1 S e max(a, b)a +
1a -10 se 27
eea s 2(
This lemma now immediately implies the following corollary by rescaling 8.
Corollary C.2. Let a, b be numbers in [0, 2] and let > O. Suppose a² 122 + 1:327= max(e e2). Then for any non non-negative integer z, we have
la b²1 S.
We now show that for any candidate subspace U find subspace representing it that is spanned by only few vectors in P.
Lemma (Lemma
5.5
Let C Bd. For any orthogonal matrix E Rixd there exists M C P. such that
with M = Olj E
vp E P. ( - Haleel s ||(I HM)pl
(14)
Proof. Initially, M 0. We add points to M in rounds and denote by Mj the set after rounds.
Furthermore, let TT, be the projection matrix onto the subspace spanned by M, at round t. If there is a p E in round such that
- (T- Hplp > el[(T - IIppp
(15)
'The dependency is easily derived via straightforward application of Lemma A.3
21

---

then we let M4+1 = M, U {p}. Our goal is to show that after T E O(j=-} many rounds, we have | (I- 11r)pl S [|(I 1Ir)p|I. We show this by proving inductively
I 11 2 22
For the base case t = 0. this is trivially true. Thus suppose we add point in iteration t + 1. Reformulating Equation we have (I-NWel > E. By the Pythagorean theorem, we therefore 111-116)21
have
- | 11 = IT,1 II(I p1l 2 . 2 26. (1.
Now since 1I, is projection and since U has orthonormal columns j | 11 2 10T If T e we obtain || 2 This implies that U is contained in the space spanned by Mr. Conversely, must also be orthogonal to the kernel of My that (
0. Therefore after
at most = 3 rounds, we have |I0 IIr)pI S II(I IIT)pII-
Lemma (Lemma 5.4p Let P C B1 be set of points and let be a positive integer. Then there exists an (e.j)-projectivv net of size
WI < exp(O(1) d- log(]=
Proof. Let N be an e/j-net of the Euclidean unit ball, i.c. A |l,)),,//) due to Lemma A.2 Let = & N be the set of jususess of of N. We claim that for every S, there exists an S" A such that
||ST pllz = ||S pll2 te.
Note that this implies the claim as W E ((1+ ") = exp(O(1) d j. -oloooe--)) 1)).
Define STT to be the vector in N closest to the ith row of ST, i.c I|ST S 1l2 S e/j. We have
||ST* S112 S >x !|S S S e. Therefore
|| p|l2 I1(s* -s 1p ST
ple
< 11(ST - -s'" )pll + ||5 pll2
< 1| pll2 11S S ||2|p|12
I | pll2 +
The bound ||ST pll2 2 1|S pll2- - e proven analogously.
We conclude with the proof of Equation 5 in Lemma 5.2
Lemma Equation in Lemma 5.2). Let D be distribution over Ba and let P a set n points sampled D and let V,,, be defined as in Theorem 5.1 Then
[V(V s I1-lox, S exp(O(L)(32)) k. -- + log(je-1)) Iog
Proof. Let a, 8 >> 0 be sufficiently small parameters depending on that will determined later. We first describe a construction for nets for a single subspace of rank at most j. before composing subspaces.
We start by describing the composition of the nets. For every subset M C P. with |M E O(ja=)), we let M denote an orthogonal projection matrix of the span of M. Note that this implies rank(IlM)
N(Baank(i ||-1|,,, (),,)) be (8, projective net of the point set UpEN {IIMP} of size at most exp(O(L) rank([lM)) log(j3 given by Lemma 5.4 Finally, let N := (IIM).
O(ja -2. Further, let N (IIar)
We consider an arbitrary orthogonal matrix U E Rixd, Denote by My the subset of points and by Ih the projection matrix given by Lemma 5.5 using a as the precision variable. We claim that for every U, there exists an U' E N such that for all E P
( [1 - DoTlle + II(T IT -T - |[(T - -T-UUT)N UUT) E EO(a + 3).
22

---

In other words, by enumerating over all (B.j) projjectve nets, we obtain an Ola + -'subspecee clustering net for (1. cluustrnn,,,,, The desired error of then follows by choosing a and | accordingly. For U, we construct U" as follows. Let D Vll, i.c DD Hy. Further, let V UTD, D, notice that V has at most rows that have at most unit norm. Hence, there exists U" E N such that
1 - | s
that is a (...j))projecttve net.
We then obtain
1 10 11rpl2++ 11y
| 2 3
|1( 11r))12
= mupl2 | ||(7 - IT
2
= [I
(Eq 6
= [I
- - 2p" 11 UU -1-1)))
(Lem 5.5)
= [I UPT 1p 2a 11(1 - (17))p1 +
Setting a² = 3= (4(32]= 2 we then have due to Corollary C.2
|upll |I0 Hopll + |1( Hy 1 11( UU pll UUT)P!
Se.
(16)
To extend this from single j-dimensional subspace to a solution 14 given by the intersection of j j-dimensional subspaces, we define cost vectors S obtained from / _ N as follows. For each U E U let U" be constructed as above and lt' be the union of the thus constructed U". Then, with slight abuse notation, letting Hgg correspond the subspace used obtain U'. define
M' = min U'eu
[[[ - TTg )ll? + || - ||T
Let U be the subspace to which p is assigned 21 and let U be the center in Ut used to approximate U and let U = argmingreeer ete |||(/ - IT ) || ||0TT6=/1311** and let U E U be the
center approximated by U*! Then applying Equation 16 we have
[|(I UUT )pl
[I(1 U** pl
[[[(I Iu upl + ||T | Tuxpl 11210/2 +
||([T - )p1) + ||
p | +E
Thus, the cost vectors obtained from N are (k, clcusstriin net, i.c.
S
min ES
[s', [6] [ min ll II
$||² S..
sES
What remains is bound the size of the clustering net. Here first observe that size of the clustering is equal |W| |. For [.V), we have -ooo-21oa--1 I n Olja - loga-)) many choices of
[P|
(II). turn, the size of each N (II) is bounded by (3/j) -0(ia-7) due to Lemma 5.4 Thus the
overall size of V is
exp (A: j. 0(a loga (log Tolga-"(ogg jlog (og))
= exp(O(1)(32) *+2 k.j. j. e n + joggjj loge
as desired,
23

---

C.1 Proofs of Theorem 5.6 (Section 5.1
The proof of the theorem is a straightforward application of Theorem 4.1 with the following Lemma
Lemma C.3. Let D be a distribution over B2, let set of points sampled from D, and let V be defined as in Theorem 5.6 Then for any > 0
(v
kj
Rad (V3.) E
1og
Proof. We use the following result due to Foster and Rakhlin
45
Theorem C.4 (&oo contraction inequality (Theorem by 45
R and let L for all X, X' E RR For any >> O, there exists a constant C >> such that if léb (()((()))VV]]]((+)))) - B then
Let F
c +
x
6: R
R be L-Lipschitz with respect to the foe norm, i.e. (1x(X) (
Bn
Rad (0 o FFF CC C. LVK max Rad (FI) 3/27/
max; R, (Fl:))
We use this theorem follows. Our functions associated with candidate solutions U4 that is +()) = mingeu [I UU pl13 In other words, f maps point p to the k-dimensional vector, where (1()) = |I(T U,U )rll and selects the minimum value among all || U. pll.
Thus, we require three more steps. First, we have to bound the Lipschitz constant of the minimum operator. Second, we have to give bound on 8. Third and last, we have to give bound on the Rademacher complexity
1. Rad (V) E,, sup 1U0-U0")ple
(17)
U PEP
The Lipschitz constant of the minimum operator with respect to the loo norm can be readily shown to be 1 as for any two vectors v, y with min; l/1 y
min min yi d x; yj xj Ui S [z, My S 1 vlloo.
Since an orthogonal matrices and E B we have [|(I - UU )p13 < and thus 3 is bounded by 1.
Thus, we only require bound on Equation 17 For this, we use result by [50] Since the result embedded in the proof of another result, we restate it here for the convenience of the reader.
Lemma C.5 (Compare the proof Theorem 3 of (50). Let P be set of n points in B and let U be the set of all orthogonal matrices of rank at most j. For every E U, define fu (p) = || 11 and let F be the set of all functions fo (p(p) Then.
1 E, sup (1(I-UT)) E UEi
[
Rad, (F) = n1
PEP
Proof. We have
Rad,, sup
Σ
[1(1 UU
)P E, Σ
|pll 3r + E, sup
1f pEr
U PEP
PEP
24

---

We observe that the term E, EpEP |pl TT is 0. Thus, we focus on the second term. We have
E, sup
Σ
I0T pll
Up
sup E, sup
Σ
p prU p. E, sup trace(p' "UU p) rpp
U
U
E, sup
trace(UU" pp-) (U"
U
pEP
UU Σ (rp (To-)o7) pp"))
E, sup trace
PEP
S E, sup |
Σ
pD. pp"
PEP
We have |||||= S vj. we focus
EpepTo "pp""
Here, we have
( TD TD. PPP
pp mp" pEP
Σ
= trace
Σrp rp pD" PEP
IPEP
ΣΣ, PEP
Tp TT trace (pp" (pp""q"")
Σ Σ PEP PEP
Tp Tg. (p"a)²
This implies
n (F) = E, sup
Σ
[ I E, sup |
Σ
rp pp"
U PEP
PEP
Vr E,
Pp Fi g)
PEP PEP
(Jensen's inequality) < Vj.
E Σ
TT (pT
PEP
Vi
(NT p)
Σ Vnj.
Vnj.
PEP
PEP
Solving the above for Rad, (F)) concludes the proof.
can now conclude the proof.
Combining the bounds on and 3 with Lemma C.5 and Theorem
C.4
we have
Rad, Rad,(V O VT V
377 (n)
as desired.
C.2 Lower Bound
Finally, we also show that the bound given in Theorem 5.6 is optimal, up to polylog factors.
V kt
Theorem (5.7). There exists a distribution D supported on By such that E(V,2) Ω
Proof. We first describe the hard instance distribution D. We assume that we are given d = 2kj dimensions. Let e; be the standard unit vector along dimension with i {1.... d). p, E [0, 1 be a parameters, where is sufficiently small. We set the densities for point as follows.
p
if e,, i E (1....,k k.
Pig
p P
if e, E (kj + 1.....d) .d. otherwise
(18)
0
25

---

We choose such that integral over densities is i.e. kj.p+t kj. (p (p) = 1. It is straightforward to verify that for sufficiently small. p E ( We denote the points {e..... eky by G for "good" and the points {ckj+1,.... ed} by B for "bad".
We now characterize the properties of the optimal solution as well suboptimal solutions.
Lemma C.6. Let D be the distribution described above in Equation 18 Then for any optimal solution U = {UI,... Uk}, we have E; E Ur i E {I,..., kj} and some and OPT = kj 1-j-p-(1-3)
Proof. We transform the instance into d x diagonal matrix D where Dú, = /Pie.. So D is x d diagonal matrix with diagonal entries equal to /p for the first j.j elements and yp- E for elements from j + 1 to d. Now consider any partition of the points into clusters C. with the corresponding subspace U2 for (L E (1...., k} ). The optimal solution for U, is simply the right singular vector of the submatrix of D corresponding to points in C,, which by the construction of D is the j points with the largest weight. This means that each cluster can remove at most Σx=1 1
from the cost, so & clusters remove at most Σ 2i=1 j from the cost. This imples that the cost of the clustering is lower bounded by Σ D Σ D2 = Ei=kj+1 De, Conversely, the solution has exactly this cost, which implies that must be optimal.
Using Lemma C.6 we now have to, given n independent samples from D. Control the probability that the sample P will (falsely) put a higher weight some of the points in B than the points in G. Let Bez denote the set of misclassified points in and let Porr denote the optimum computed on the sample P. We have
EDcost(D, Port)] = kj p (1 10-63 e) + e Baar
and hence expected excess risk bound of
E[cost(D, POrT)] OPT p- g E[Ber].
By linearity of expectation, we have Belll = kj Ple E Bexl. Thus, Ejcost(D, Poer)] OPT ((1)s. Pleaj+1 E Ber] Define Gtow to the set of points from G that are have an empirical density of at most p. Let Eaj+i denote the empirical density of eRj+1. We now claim that
TPeek E Bez] 2 Pleijti > p PAece-e-- Ck--111 E Bex)
Plexs+1 E BE > p] PlEKYti > pl 2 1/2 Plenjti > p]
The first inequality follows because we are considering a subset of the possible events, the second inequality follows because the number of points with an empirical estimated density greater than is negatively correlated with the empirical density Ekj+1 of the point Ekj. Specifically, conditioned on
Ekj+1 > p. the mean and median density of any point e; E G is at most 1 4-p(n-p-n) = p- p-(1-p) p. Thus, the (marginal) mean and median density of any other point is below and therefore the probability that 6kj+1 will be in Ber is at least 1/2.
Thus, what remains to be shown is bound on PP(ek > p). Here, we use the tightness of the Chernoff bound (see Lemma 4 of (48).
Lemma C.7 (Tightness of the Chernoff Bound). Let X be the average of n independent, 0/1 random variables. For any E E (0, 1/2] and μ E (0, 1/2), assuming pm 2 3 if each random variable is I with probability at least μt, then
P > (1+ +)pp > exp(-9e²jun) jmm)
Thus, sampling n elements, we have
E ) - (1 - E) .).
P [eks > pl
P
ckj >
1 + 1 1-8)
exp
-9
E)2
(1 - c)mm
E (2(1) exp
(Tk kjj
26

---

If we require E[cost(D, Port)] OPT = E for sufficiently small absolute constant we also require P Pleks pl c' and hence V ki I d" for sufficiently small absolute constants d' and d". Letting E - 0 then shows that the excess risk can asymptotically decrease no faster than
D Details for the Experiments (Section 6
D.1 Description datasets
Mushroom comprises of 1 112 categorical features of the appearance of mushrooms with class labels corresponding to poisonous or edible. MNIST contains 28x28 pixel images of handwritten digits. Skin Nonskin are RGB values given as 3 numerical features used to predict if pixel is skin not. Lastly, Covtype consists of a mix of categorical and numerical features used to predict seven different cover types of forests. In the main body, we focus Covtype because of its large number of points.
D.2 Description of algorithms
Center based clustering For each experiment, we use an expectation maximization (EM) type algorithm. Given solution S, we first assign every point to its closest center and subsequently, we recompute the center. For the case is more commonly known Llyod's method [59]. For the cases, obtained via gradient descent. The initial centers are chosen via D sampling, i.c. sampling centers proportionate the zth power of the distance between a point and its closest center (for 2 this is the k-means++ algorithm by (6).
2, we do this analytically and this case the EM algorithm
3, 3,344) 4). the new center is
We wrote all of the code using Python and utilized the Pytorch library for implementations using gradient descent. Specifically, we employed the AdamW optimizer to find the closest center with learning rate set to 0.01. All experiments were conducted on a machine equipped with single NVIDIA RTX 2080 GPU.
Subspace Clustering For subspace clustering, we consider E (1,2,5) ) to demonstrate the effects of the subspace dimension on convergence rate, taking computational expenses into consideration. Since there are known tractable algorithms for these problems with guarantees, we initialize solution l = .U, UR} } by sampling orthogonal matrices of rank j. where the subspace for each matrix is determined via the volume sampling technique (55 Subsequently, we run the EM algorithm. As before. the expectation step consists of finding the closest subspace for every point. For 2, the maximization step consists of finding the j principal component vectors of the data matrix induced by each cluster. For the other values of z, it is NP-hard even approximate the maximization gradient descent find local optimum. Due the fact that _iin_nonskin
step (24), only has 3 features, we only evaluate the excess risk for E {1, Due to a large computational dependency dimension, do not evaluate subspaces the MNIST dataset.
D.3 Experimental results
In this section, we provide plots of the excess risk and the found parameters of the best-fit lines for each of the datasets.
Table 2: Best fit lines on Covtype and Mushroom (left to right)
c
@1
(2
c
Q
42
3 10-
0.44
0.54
1
-100-
0.48
0.51
40-
0.42
0.52
8
8-10-2
0.48
0.51
3
6.10-
0.44
0.51
4-10-
0.49
0.50
4
10-0
0.44
0.51
-
0.49
0.50
27

---

0319
3711
0000
2800
4000
3030
309
2510
2006
2050
2009
2500
400
1309
180
2000
2994
3009
1.000
1840
C2000
Figure 2: Excess risk for center-based clustering on the Covertype dataset. The shaded areas indicate the maximal and minimal deviation for the respective sample sizes.
304
322
202
341
0222
023
0907
Figure 3: Excess risk for center- clustering on the Mushroom dataset. The shaded areas indicate the maximal and minimal deviation for the respective sample sizes.
Table 3: Best fit lines Skin_ NonSkin and MNIST (left right)
Q2
Q1
Q2
2 10
0.49
0.50
1 10-1
0.49
0.51
2
3. 10-3
0.47
0.52
5 10-2
0.50
0.50
8 10-
0.46
0.53
3. 10-2
0.50
0.50
2- 10-4
0.46
0.53
8 10
0.50
0.50
28

---

2-1
2-2
0210
1800
1800
3003
8090
00001
27309
209C
2016
2009
1500
100
2096
1009
$..33
038022
5000
00303
0250
Figure 4: Excess risk for center-based clustering on the Skin_Noniia Nonskin dataset. The shaded areas indicate the maximal and minimal deviation for the respective sample sizes.
2-1
222
802
381
223
190
1300
7012
1900
L.13
0424
0223
2.44
341
Figure 5: Excess risk for center-based clustering on the MNIST dataset. The shaded areas indicate the maximal and minimal deviation for the respective sample sizes.
29

---

1+4.
1-20
0.22
030
C413
x2
0.00
300
Figure 6: Excess risk for subspace clustering on the Mushroom dataset. The shaded areas indicate min/max values
Table 4: Best fit line for subspace clustering Covtype and Mushroom (left right)
c
Q1
c
Q1
1
0.1
0.45
0.54
1
1
10-1
0.48
0.51
1
2. 10
0.48
0.51
1
2
1.10-
0.48
0.51
1
10-4
0.46
0.53
1.10
0.49
0.49
1
1-
0.46
0.52
2
7.10-2
0.48
0.51
2
80
0.48
0.51
2
2
6.10-2
0.50
0.49
2
2-10-3
0.47
0.51
2
6.10
0.49
0.48
2
4-10-5
0.46
0.53
3
4-10-2
0.49
0.50
2
4
2-10-6
0.46
0.52
3
2
3.10
0.49
0.50
5
3-
0.48
0.51
3
3.10
0.49
0.49
5
5-10-5
0.46
0.53
4
2.10-2
0.49
0.50
5
4.10-7
0.47
0.52
4
2
2
2.10-
0.49
0.50
5
3.10-9
0.47
0.51
4
1. 10
0.48
0.50
30

---

[22 701
006.99
006020
Dotra 94
0.008
500075
006225
1900
2039
4001
1900
190
2400
122,507
033025
033000
033000
633006
120
13:9
190
3051
740
400
1960
2905
100
12.50
3.000
3.000
Jei,
12.40
1.3001
$39002
0.8
0,0000
10000
0.-
2000
Figure 7: Excess risk for subspace clustering on the Skin Nonskin dataset. The shaded areas indicate min/max values
31

---

Table 5: Best fit line for subspace clustering on Skin-Nonskin
j
Z
q1
Q2
1
1
10-4
0.48
0.50
2
3-10-1
3
0.45
0.53
1
2-103
0.46
0.53
2
2-10-1
0.46
0.53
1
4-10-
0.46
0.53
2
2-
0.46
0.53
4
1
90
0.46
0.53
2
30-6
0.46
0.53
32


Reviews:
[{"review_id": "DFufsmPloy", "reviewer": "Reviewer_hJ3D", "summary": "This paper studies generalization bounds for clustering problems, including ceter-based clustering and subspace clustering. For center-based clustering, they recover the optimal bound (up to log term) of $\\widetilde{O}(\\sqrt{k/n})$; the technique can be extended to k-median also. For subspace clustering, the derive the first bound $\\widetilde{O}(\\sqrt{kj^2/n})$ for the generalized $(k, j, z)$-clustering objectives, which had been established only for the scenario $z = 2$; for the special case  $z=2$, they further refine the bound to $\\widetilde{O}(\\sqrt{kj/n})$ that meets the current upper-bound in the literature, and prove that this is tight. Experiments are given. ", "questions": "N.A. ", "limitations": "Limitations are addressed. There is no negative societal impact of the work. ", "rating": 7, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The paper advances the knowledge on generalization bound for general subspace clustering, which is the main merit of this paper. The authors also prove the tightness for the case $z=2$. \n\nGiven the intricate relevance between the clustering problem with coreset construction, dimension reduction and so on, the paper did a good job on discussing the relevant work and laying out their proof sketch, while pointing out the challenges for generalizing the results (from  $z=2$ as in the paper's reference [34]) to the case $(k, j, z)$. It is then clear that the chaining technique, which has resulted in tight bounds for coreset clustering and especially $(k, j, 2)$ clustering, is not compatible with existing (generic) dimension reduction techniques. From there, the authors design an ad-hoc dimension reduction technique for subspace clustering to overcome the obstacle. Several insights and techniques in the paper are thus new and of independent interests, while such arguments seem restrictively applicable to only clustering case.  \n", "weaknesses": "While the paper is good in terms of technicality and novelty, it can be made more interesting if the authors can discuss better on use cases and importance of $z > 2$. In fact, the case $z=2$, which would correspond to the $\\ell_2$  loss seems much more prevalent and important in practice. The current few-line discussion in the paper is a bit succinct and also does not point to any reference. \n\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the comments.\n\nThe loss functions for different values of $z$ are often considered in theoretical papers (for instance [26,35]). The most important variant for large values of $z$ is undoubtedly $z\\rightarrow \\infty$, as it generalizes problems such as the minimum enclosing ball and $k$-center. Nevertheless, for the learning setting, large values of $z$ render the problem infeasible.\n\nAs a more feasible alternative with provable guarantees, one can interpolate between and $\\ell_2$ loss and $\\ell_{\\infty}$ by considering higher higher values of $z$, which has been done, for example, in [28]. Moreover, as observed by [*] (who we forgot to add to the references but should be included), learning bounds for $k$-means in $\\ell_1$ space can be obtained by studying $(k,4)$ clustering in $\\ell_2^2$ space. \n\nWe will add these references and discussion in the potential final version.\n\n[26] V. Cohen-Addad, D. Saulpic, and C. Schwiegelshohn. A new coreset framework for clustering. STOC 2021\n\n[28] V. Cohen-Addad, D. Saulpic, and C. Schwiegelshohn. Improved coresets and sublinear algorithms for power means in euclidean spaces. Advances in Neural Information Processing Systems, 34, 2021.\n\n[35] D. Feldman and M. Langberg. A unified framework for approximating and clustering data. STOC 2011\n\n[*] Lingxiao Huang, Nisheeth K. Vishnoi: Coresets for clustering in Euclidean spaces: importance sampling is nearly optimal. STOC 2020"}, {"review_id": "KaGtc4un4K", "reviewer": "Reviewer_zjTi", "summary": "The authors study two clustering problems from the perspective of generalization:\n-standard center-based clustering objectives such as k-means, k-median and more generally the different norms associated with the objective\n-projective subspace clustering: where the goal is to find a k subspaces such that if you project the points there, you minimise a natural distance objective.\n\nThe main question addressed for both of these problems is:\nIf we are given a sample set of n data points drawn independently from a fixed (unknown) distribution, and we perform clustering on those n points, how fast will the solution on the sample converge to the optimal clustering on the fixed (unknown) distribution?\n\n", "questions": "N/A", "limitations": "N/A", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "+presentation and literature review is done in a careful manner \n+results for both clustering objectives are novel and interesting\n+generalization bounds almost tight", "weaknesses": "-A lot of the tools needed by the authors seem to have been used in prior works too. Having said that, there are some proposed new techniques for dimension reduction which, though tailored to the problem at hand, seems interesting. ", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": ""}, {"review_id": "BOJ4fDvTuJ", "reviewer": "Reviewer_ZgJL", "summary": "This paper presents several generalization bounds for clustering objectives such as \nk-median and subspace clustering. When the centers are points or constant dimensional subspaces, the upper bounds are optimal up to logarithmic terms. For projective clustering, this work gives a lower bound showing that the results obtained by [34] are nearly optimal. A key technique was using an ensemble of dimension reduction methods with guarantees.", "questions": "See “Weaknesses”.", "limitations": "N/A", "rating": 5, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "This paper has the following contributions: \nFor center-based objectives, this work shows a convergence rate, which matches the known optimal bounds for k-means, and extends it to other important objectives such as k-median. For subspace clustering with j-dimensional subspaces, this work also shows a convergence rate. For the specific case of projective clustering, which generalizes k-means, a converge rate is provided.", "weaknesses": "1.Insufficient research on related work. \nThis work is not the first random projection clustering work, such as papers [1,2]. These papers are not cited in this paper. The superiority of this work cannot be verified. Please compare them from the theoretical analysis, experimental results, algorithm complexity, etc.\n\n[1]Yin R, Liu Y, Wang W, et al. Randomized Sketches for Clustering: Fast and Optimal Kernel $ k $-Means[J]. Advances in Neural Information Processing Systems, 2022, 35: 6424-6436.\n\n[2]Yin R, Liu Y, Wang W, et al. Scalable Kernel $ k $-Means with Randomized Sketching: From Theory to Algorithm[J]. IEEE Transactions on Knowledge and Data Engineering, 2022.\n\n2.The experiments is not enough. There are many related works in this field. If this paper can be compared with related work through experiments and the performance of the work can be analyzed in detail, it would be better.\n\n3.The presentation of references is not standardized, such as:\n\n[20] P. Chou. The distortion of vector quantizers trained on n vectors decreases to the optimum as Op(1/n). In Proceedings of 1994 IEEE International Symposium on Information Theory, pages 457–, 1994. doi: 10.1109/ISIT.1994.395072.\n\n[28] V. Cohen-Addad, D. Saulpic, and C. Schwiegelshohn. Improved coresets and sublinear algorithms for power means in euclidean spaces. Advances in Neural Information Processing Systems, 34, 2021.\n\n[50] Y. Liu, S. Liao, S. Jiang, L. Ding, H. Lin, and W. Wang. Fast cross-validation for kernel-based algorithms. IEEE Transactions on Pattern Analysis and Machine Intelligence, PP:1–1, 01 2019. doi: 10.1109/TPAMI.2019.2892371.\n\n4.The organization and presentation of this paper can be further improved. \n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We will add the desired aforementioned references. We can also standardize the references.\n\nHowever, we seriously question the validity of the criticism that we did not compare \"theoretical analysis, experimental results, algorithm complexity, etc\". In words of the reviewer, \"This work is not the first random projection clustering work\" and the reviewer seems to imply that the two proposed references are the first to do so.\n1. The proposed references focus on kernel k-means. k-means is not the primary subject of this study, having been solved optimally in previous work and our techniques go beyond what is possible for k-means, and indeed what is being done in those two papers. Our considered objective functions and settings are different. \n2. The reviewer seems to think that random projections are a core part of our work. This is false. Nowhere do we use random projections for $(k,j,z)$ clustering in any way and we specifically made a point to discuss shortcomings of all existing dimension reduction methods. \n3. Random projections for clustering have been used as early as 2010 by [BZD], and subsequently studied in [CEMMP,MMR,BBCGS], all of which have appeared before the two papers mentioned by the reviewer and, it must be said, both failed to cite any of these earlier works. With the exception of [BZD], which we admittedly forgot and will rectify, these papers *are* in fact cited by us.\n\nThus we strongly believe that the criticism that we did not compare \"theoretical analysis, experimental results, algorithm complexity, etc\" to the references suggested by the reviewer or that we did not do due diligence with the related work has no basis whatsoever. \n\nAs for the organization, we would appreciate if the reviewer could provide details. \n\n[BZD] Christos Boutsidis, Anastasios Zouzias, Petros Drineas: Random Projections for $k$-means Clustering. NIPS 2010\n\n[CEMMP] Michael B. Cohen, Sam Elder, Cameron Musco, Christopher Musco, Madalina Persu: Dimensionality Reduction for k-Means Clustering and Low Rank Approximation. STOC 2015\n\n[MMR] Konstantin Makarychev, Yury Makarychev, Ilya P. Razenshteyn: Performance of Johnson-Lindenstrauss transform for k-means and k-medians clustering. STOC 2019\n\n[BBCGS] Luca Becchetti, Marc Bury, Vincent Cohen-Addad, Fabrizio Grandoni, Chris Schwiegelshohn: Oblivious dimension reduction for k-means: beyond subspaces and the Johnson-Lindenstrauss lemma. STOC 2019"}, {"review_id": "NSrm5qPoi3", "reviewer": "Reviewer_iH2U", "summary": "This paper investigates generalization bounds for center based and subspace clustering, providing upper bounds on excess risk for $(k,z)$ and $(k,j,z)$ clustering and lower bound for $(k,j,z)$ clustering for special case of $z=2$. \n\nThe bounds for $(k,j,z)$ clustering are novel and lower bounds helps establish optimality of previously known bounds.", "questions": "Q1: Could this approach also help obtain improvements for when additional structural assumptions are imposed on $\\mathcal{D}$?\n\nQ2: What changes in bound for Lemma 4.4 when points do not lie in low-dimensional space?", "limitations": "Please refer weakness and questions. Work is theoretical in nature, negative societal impact is not apparent.", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "The paper is well written and proof sketch is easy to follow. \n\nThis work provides improvements over existing work in extending $(k,z)$ clustering bounds. Getting chaining type analysis to work in this setting is non-trivial.\n\nThe techniques used for proving upper bounds for subspace clustering are novel and using multiple dimensionality reductions for analysis is indeed interesting.\n\nThe lower bound construction is clean. Overall, I like the results in this paper.\n\nI have not verified all the proofs in the appendix but the proof sketch and flow seems right to me.", "weaknesses": "The bounds are interesting in certain parameter regimes, specifically when $j$ and $z$ are constants. Limitations in current approach to extend beyond this is not discussed.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We acknowledge the reviewer's comments.\n\nRegarding the limitations in $j$ and $z$, for $z\\rightarrow\\infty$, no generalization bounds are possible, at least in this problem setup. The main issue is that problems with $z\\rightarrow\\infty$ are too sensitive to outliers and even regions with an extremely low density are important. An exponential depedency on $z$ is likely necessary, as for $z'\\in \\Omega(\\log n)$, where $n$ is the sample size, the cost of a $(k,j,z')$ clustering and a $(k,j,\\infty)$ clustering is very close.\nFor large values of $j$, there are no limitations in our analysis, barring perhaps a quadratic dependecy for $z\\neq 2$. The only reason why we mentioned that $j$ is a constant because this is typically assumed in practice [7]. The main limitations are only in terms of finding a tractable algorithm that solves the problem. For example, for $(k,1,z)$ clustering, the problem is inapproximable even in the Euclidean plane [1]. Exponential time algorithms that solve these problems exist [2,3], but are mainly of theoretical interest. \n\nQ1: It may be possible.  For $k$-means, previous work has achieved a learning rate of $O(1/n)$ under certain assumptions, see [4,5]. It may be possible to weaken these assumptions and/or extend these ideas to k-median. It is, for example, a very interesting open problem to show that assuming ORSS-stability [6], a learning rate of $O(k/n)$ is possible. Doing so will likely require a different approach than what we are currently doing.\nFor $(k,j,z)$ clustering, we are not aware of any prior results. It is likely that some assumptions exist such that this possible.\n\nQ2: This lemma itself does not change. But using our ensemble of dimension reductions, we obtain the bounds for Lemma 4.5, which are independent of $d$. We only use lemma 4.4. once we know that we can map the points to some low-dimensional space. If the dependency on $d$ can be eliminated entirely, one would bypass the necessity for dimension reduction and directly achieve an optimal learning rate for $(k,j,z)$ clustering.\n\n[1] V. S. Anil Kumar, Sunil Arya, H. Ramesh: Hardness of Set Cover with Intersection 1. ICALP 2000\n\n[2] Kenneth L. Clarkson, David P. Woodruff: Input Sparsity and Hardness for Robust Subspace Approximation.FOCS 2015\n\n[3] Dan Feldman, Michael Langberg: A unified framework for approximating and clustering data. STOC 2011\n\n[4] C. Levrard. Nonasymptotic bounds for vector quantization in hilbert spaces. The Annals of Statistics 2015\n\n[5] Shaojie Li, Yong Liu: Sharper Generalization Bounds for Clustering. ICML 2021\n\n[6] Rafail Ostrovsky, Yuval Rabani, Leonard J. Schulman, Chaitanya Swamy: The effectiveness of lloyd-type methods for the k-means problem. J. ACM 59(6): 28:1-28:22 (2012)\n\n[7] René Vidal: Subspace Clustering. IEEE Signal Process. Mag. 28(2): 52-68 (2011)\n\n"}, {"review_id": "493C01Owcu", "reviewer": "Reviewer_26Fm", "summary": "The authors study the generalization bounds for two clustering problems: center-based clustering and subspace (projective) clustering. The authors argue that the problems reduce to bounding  the Gaussian complexity of the set of cost functions over all possible solutions. To achieve this, they apply the union bound on the telescoping sum over a nested sequence of solutions sets that are increasingly more accurate. To find a set of solutions at a specific level of accuracy, the authors use the \\emph{terminal embedding} for the center-based clustering, and they propose a new dimensionality reduction method for the projective clustering. ", "questions": "- As the authors mentioned in D.2, the projective clustering is serverly limited in computational aspect. Has there been any attempt to solve this issue? The authors probably should mention this limitation somewhere in the paper as well.", "limitations": "The authors have mentioned several open problems related to this work, but I think the most important problem is whether the projective clustering rate of $\\tilde{O}(\\sqrt{kj^2/n})$ is optimal for $z\\not= 2$.", "rating": 7, "confidence": 3, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "- The authors provide the first provable bound for projective clustering. For a specific case with the squared cost, they show that the previous bound by Fefferman, Mitter, and Narayanan (2016) is optimal.\n- I find the chaining technique to be quite interesting, and it could be applied to other learning problems.\n- The authors did a decent job of giving a high level idea of their proofs\n- The experimental result on real datasets agree with the theoretical results.\n", "weaknesses": "My only concerns are regarding the applications and experiments. Since this is mainly theoretical paper, these should not be major concerns.\n\n- The problem of projective clustering should be better motivated in the introduction. What are some real applications of projective clustering? What are the common choices of $j$?\n- The experiment are performed with $j\\in \\{1,2,5\\}$, with only $j=1$ presented in the main paper. In my opinion, there should be a bit of discussion on how the experimental results conform (or deviate) from theory as $j$ increases.\n\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the comments.\n\nRegarding the questions and weaknesses:\n\nTo the best of our knowledge, the most commonly used choice of $j$ are small constants. For example [1] never use $j$ larger than 4. The reason why we focussed on $j=1$ in the main body is that there already exists a phase transition in terms of the computational complexity between the normal $k$-median and $k$-means problems and using lines as centers, while still admitting more positive results than other subspace clustering problems [2,3,4]. In addition, the problem is often considered in computational geometry as it can be interpreted as finding the ($k$) closest cylinders. But we are open to putting more attention on other values of $j$.\n\nIn terms of tractability: the $(k,1,z)$ problem is inapproximable up to any factor, even in 2 dimensions, for any choice of $z$ [5]. Similarly, the $(1,j,z)$ problem is APX hard [6,7] unless $z=2$ in which case the problem is variously known as PCA or low rank approximation. To run an EM-like algorithm for $(k,j,z)$ clustering, as we did in the experiments, we require a very accurate (read $(1+\\epsilon)$ approximation). The currently best known algorithms for $z=1$ and $n$ points run in time $O(\\exp((j\\cdot\\epsilon^{-1})^{O(z)})$ [6,8]. Unfortunately, running these algorithms even for small values of $j$ is still very impractical. Thus we relied on heuristic EM-like methods which is also what [1] suggests.\n\n[1] René Vidal: Subspace Clustering. IEEE Signal Process. Mag. 28(2): 52-68 (2011)\n\n[2] Dan Feldman, Amos Fiat, Micha Sharir: Coresets forWeighted Facilities and Their Applications. FOCS 2006\n\n[3] Dan Feldman, Amos Fiat, Micha Sharir, Danny Segev: Bi-criteria linear-time approximations for generalized k-mean/median/center. SCG 2007\n\n[4] Pankaj K. Agarwal, Cecilia Magdalena Procopiuc, Kasturi R. Varadarajan: Approximation Algorithms for a k-Line Center. Algorithmica 42(3-4): 221-230 (2005)\n\n[5] V. S. Anil Kumar, Sunil Arya, H. Ramesh: Hardness of Set Cover with Intersection 1. ICALP 2000\n\n[6] Kenneth L. Clarkson, David P. Woodruff: Input Sparsity and Hardness for Robust Subspace Approximation. FOCS 2015\n\n[7] Amit Deshpande, Madhur Tulsiani, Nisheeth K. Vishnoi: Algorithms and Hardness for Subspace Approximation. SODA 2011\n\n[8] Dan Feldman, Michael Langberg: A unified framework for approximating and clustering data. STOC 2011\n"}]

Author rebuttal:

Meta-review: This paper provides the first upper and lower generalization bounds for subspace clustering. The reviewers had a variety of small comments and are overall in favor, I am glad to recommend acceptance.

Minor comment: "converge rate" in the abstract should be "convergence rate".
Decision: Accept (poster)