On Margin-Based Cluster Recovery with Oracle Queries
Year: 2022

Abstract:
We study an active cluster recovery problem where, given a set of n points and an oracle answering queries like “are these two points in the same cluster?”, the task is to recover exactly all clusters using as few queries as possible. We begin by introducing a simple but general notion of margin between clusters that captures, as special cases, the margins used in previous works, the classic SVM margin, and standard notions of stability for center-based clusterings. Under our margin assumptions we design algorithms that, in a variety of settings, recover all clusters exactly using only O(log n) queries. For Rm, we give an algorithm that recovers arbitrary convex clusters, in polynomial time, and with a number of queries that is lower than the best existing algorithm by ⇥(mm) factors. For general pseudometric spaces, where clusters might not be convex or might not have any notion of shape, we give an algorithm that achieves the O(log n) query bound, and is provably nearoptimal as a function of the packing number of the space. Finally, for clusterings realized by binary concept classes, we give a combinatorial characterization of recoverability with O(log n) queries, and we show that, for many concept classes in Rm, this characterization is equivalent to our margin condition. Our results show a deep connection between cluster margins and active cluster recoverability.

heading: 1 Introduction
text: This work investigates the problem of exact cluster recovery using oracle queries, in the well-known framework introduced by Ashtiani et al. [2016]. We are given a set X of n points from some domain X (e.g., from the Euclidean m-dimensional space Rm) and an oracle answering to samecluster queries of the form “are these two points in the same cluster?” or label queries of the form “which cluster does this point belong to?”. The oracle answers are consistent with some clustering C = (C1, . . . , Ck) of X unknown to the algorithm, where k is a fixed constant. The goal is to design an algorithm that recovers C by using as few queries as possible. Clearly, if there are no restrictions on C, then any algorithm needs n queries in the worst case. Thus, our goal is to understand when C can be recovered efficiently; ideally, in polynomial time, and by making O(log n) queries. A natural attempt is to consider clusterings with well-separated clusters, since this is what is often considered a “good clustering”. The existing work goes precisely in this direction, starting with the following result of Ashtiani et al. [2016] for the case X ✓ Rm. If every cluster Ci is separated from X \ Ci by a ball centered in the center of mass of Ci, and that ball does not intersect other clusters even if expanded by a factor of 1 + , then with high probability
35th Conference on Neural Information Processing Systems (NeurIPS 2021).
poly(k,m, 1/ ) log n queries are sufficient to recover C in polynomial time. This is called “spherical margin” condition, and is called the margin.
Unfortunately, the spherical margin condition is not very realistic, since it imposes a very precise shape upon the clusters. In a generalization attempt, Bressan et al. [2020] showed that one can actually recover clusters with ellipsoidal separators with arbitrary centers, by increasing the number of queries to poly(k,m, 1/ ) (m/ )m log n. This result is achieved via boosted one-sided error learning, which works as follows. Suppose that, by making f(k,m, ) queries, we could identify correctly (with zero mistakes) a constant fraction of the points in some cluster Ci. Then, we could label those points as i, remove them from the dataset, and repeat. It is not hard to show that, after O(k log n) rounds, we will have correctly labeled all the input points with high probability. The difficult task is, of course, to learn a constant fraction of some cluster Ci with one-sided error (one-sided error means that any point of X predicted to be in Ci must be in Ci). The key insight in [Bressan et al., 2020] is that, if the clusters have margin with respect to their ellipsoidal separators, then roughly (m/ )m queries are sufficient. This leads to the following question: how much can this approach be extended?
In this work we provide several answers, revealing an interesting connection between margin-based cluster recovery and one-sided error learning. Our main contributions are as follows.
1. We introduce a new notion of margin in Rm, that we call “convex hull margin” (Definition 2). This is a strict generalization of the margins of Bressan et al. [2020], Ashtiani et al. [2016] and of the usual SVM margin, and allows the clusters to have any shape whatsoever as long as they are convex. Under the convex hull margin, we develop a novel technique for learning with one-sided error that we call convex hull expansion trick. It essentially amounts to sampling many points from a single cluster and “inflate” their convex hull by a factor of (1 + ). This technique yields a polynomial-time exact cluster recovery algorithm that uses poly(k,m, 1/ ) (1 + 1/ )m log n queries (Theorem 1). The (1 + 1/ )m dependence on and m is significantly better than that of Bressan et al. [2020], and closer to their lower bound of order (1 + 1/ )m/2.
2. We introduce a notion of cluster margin for general pseudometric spaces called one-versus-all margin (Definition 3). This notion of margin is strictly more general than convex hull margin, and captures, as special cases, standard notions of stability for clustering problems such as k-means or k-centers. We show that, if a clustering has one-versus-all margin, then it can be recovered with M( ) poly(k) log n queries via a pure learning-theoretic approach (Theorem 3), where M( ) is a quantity related to the packing numbers of the pseudometric space. We show that the dependence on M( ) is essentially optimal, thus characterizing the recoverability of clusterings in this setting.
3. Finally, we show a connection between margin-based learning and exact active cluster recoverability, when clusters are realized by some concept class H (that is, when for each cluster Ci there is a concept hi 2 H such that X \ hi = Ci). We show that if a certain combinatorial parameter, the coslicing dimension cosl(H), is bounded, then one can learn clusterings with cosl(H) poly(k) log n label queries; otherwise, ⌦(n) queries are needed in the worst case (Theorem 4). Moreover we show that, for all concept classes in Rm that are closed under affine transformations and well-behaved in a natural sense, finite coslicing dimension and positive one-versus-all margin are equivalent (Theorem 5).
Note that actively learning a clustering is equivalent, up to a relabeling of the classes, to actively learning a multiclass classifier in the transductive realizable case. Hence our results apply to that case, too. In particular, our O(log n) query bounds imply eO(log 1/") query bounds for pool-based active learning [McCallum and Nigam, 1998] of multiclass classifiers, where " is the generalization error. To see this, draw a set X of ⇥ " 1(K log 1/" + log 1/ ) unlabeled samples from the underlying distribution, where K is the relevant measure of capacity (e.g., the Natarajan dimension), run our algorithms over X , and compute a hypothesis consistent with the recovered labeling C. These kinds of reductions are standard in active learning, see for instance [Kane et al., 2017].
On the other hand, our results do not apply to actively learning subsets h ✓ X (that is, to active learning in the standard sense) if our margin conditions are only enjoyed by the set of positives X+ = X \ h. To see this, let X ⇢ R2 and suppose X+ contains a single point. Then X+ satisfies our conditions with unbounded margin w.r.t. the Euclidean distance, but any algorithm needs ⌦(n) label queries to recover it. This does not happen with clustering because, in that case, every class enjoys the margin property, and in particular both the “positives” and the “negatives” for k = 2.
Table 1 compares the bounds resulting from the different notions of margins known.
where dW (a, b) =
p
ha b,W (a b)i; note that for ⌧ 1 this can be thought of as dW (y, ci) > (1 + )dW (x, ci).
Related work. Same-cluster queries were introduced formally in [Ashtiani et al., 2016] together with the active cluster recovery problem. Those queries are natural to implement in crowd-sourcing systems, and for this reason they have been extensively studied both in theory [Ailon et al., 2018a,b, Gamlath et al., 2018, Huleihel et al., 2019, Mazumdar and Pal, 2017, Mazumdar and Saha, 2017b,a, Saha and Subramanian, 2019, Vitale et al., 2019] and in practice [Firmani et al., 2018, Gruenheid et al., 2015, Verroios and Garcia-Molina, 2015, Verroios et al., 2017].
Various notions of margin are central in both active learning and cluster recovery [Xu et al., 2004, Balcan et al., 2007, Balcan and Long, 2013, Kane et al., 2017, Bressan et al., 2021]. Our coslicing dimension is similar to the slicing dimension of Kivinen [1995] and the star number of Hanneke and Yang [2015]. Our lower bounds, like many others, are inspired from a construction by Dasgupta [2004]. Our arguments based on packing numbers are similar to those based on the inference dimension of Kane et al. [2017] or the lossless sample compression of Hopkins et al. [2021], as we cannot infer the label of a point only when it is far from already-labeled points. A query bound similar to the one given by our convex hull expansion trick, but worse by a factor roughly 2m, can be inferred by adapting arguments of Hopkins et al. [2020b]. Combinatorial characterizations of multiclass learning have been proposed in the passive case by Ben-David et al. [1995], Rubinstein et al. [2009], Daniely and Shalev-Shwartz [2014]. Other learning settings related to one-sided and active learning are RPU learning [Rivest and Sloan, 1988] and perfect selective classification [El-Yaniv and Wiener, 2012] — see [Hopkins et al., 2020a] for a discussion.

heading: 2 Preliminaries and notation
text: All missing proofs can be found in the supplementary material. The input is a pair (X,O), where X is a set of n points from some domain X , and O is a label oracle that, when queried on any x 2 X , returns the cluster id C(x) of x. The oracle O is consistent with a latent clustering C = (C1, . . . , Ck) of X , i.e., a k-tuple of pairwise disjoint sets whose union is X .1 We allow clusters to be empty. Our goal is to recover C by making as few queries as possible to O. Queries can be made adaptively, that is, the j-th point to be queried can be chosen as a function of the answers to the first j 1 queries. We express the number of queries as a function of k, n, and other parameters to be introduced later. This setting is essentially equivalent to the semi-supervised active clustering (SSAC) framework of Ashtiani et al. [2016], where the oracle answers same-cluster queries SCQ(x, y) that, for any two points x, y 2 X , return TRUE iff C(x) = C(y). We use label queries instead of SCQ queries for simplicity; any SCQ query can be emulated with two label queries. Conversely, the label of any point can be learned with k SCQ queries, up to a relabeling of the clusters, so our bounds hold for an SCQ oracle as well if multiplied by k. For conciseness, we state query bounds in the form f(k,m, n, ),
1In line with previous works, we assume k is fixed and known.
for instance O k2 (1 + 1/ )m log n . These bounds should be thought of as min n, f(k,m, n, ) , since obviously we never need to query the same point twice.
We often assume a metric or pseudometric d over X (a pseudometric allows two distinct points to have distance 0). For x 2 X and r 0, the closed ball of radius r centered at x is B(x, r) = {y 2 X : d(x, y)  r}. For any X ⇢ X , we denote by d(X) = supx,x02X d(x, x0) the diameter of X measured by d, and we define d(;) = 0. For any two sets U, S ⇢ X , we denote by d(U, S) = infx2U,y2S d(U, S) their distance according to d, and we define d(U, ;) = 1. For any X ⇢ Rm, we write conv(X) for the convex hull of X . The unit sphere in Rm is Sm 1 = {x 2 Rm : kxk2 = 1}. We recall some learning-theoretic facts. Let H be an arbitrary collection of subsets of X (i.e., a concept class). The intersection class of H is I(H) = S i2N{h1 \ . . .\ hi : h1, . . . , hi 2 H}. Given any S ⇢ X and any S0 ✓ S realized by some h? 2 H, the smallest concept in I(H) consistent with S0 is defined as h = T {h 2 H : h \ S = S0}. Note that h ✓ h?. Finally, we recall the definition of learning with one-sided error: Definition 1 (Kivinen [1995], Definition 4.4). An algorithm A learns H with one-sided error " and confidence with r examples if, for any target concept h? 2 H and any probability measure P over X , by drawing r independent labeled examples from P , the algorithm outputs a concept h ✓ h? such that P(h? \ h)  " with probability at least 1 .

heading: 3 Margin-based exact recovery of clusters in Rm
text: In this section we consider the case X = Rm. We show that the ellipsoidal margin of Bressan et al. [2020] can be significantly generalized, while retaining the O(log n) query complexity, by introducing what we call the convex hull margin. In a nutshell the convex hull margin says that, given any cluster C, any point not in C is separated by the convex hull of C by a distance at least times the diameter of C. Instead of using the Euclidean metric, however, we allow distances to be measured by any pseudometric over Rm, which we do not need to know, and which may even differ from cluster to cluster. The only requirement is that the pseudometric be homogeneous and invariant under translation (i.e., induced by a seminorm). Definition 2 (Convex hull margin). Let D be the family of all pseudometrics induced by the seminorms over Rm, and let X ⇢ Rm be a finite set. A clustering C = (C1, . . . , Ck) of X has convex hull margin if for every i 2 [k] there exists di 2 D such that:
di X \ Ci, conv(Ci) > di(Ci) (1)
This definition has a few interesting properties. First, it strictly generalizes the ellipsoidal margin of Bressan et al. [2020] and the spherical margin of Ashtiani et al. [2016]. To see this, let D be the class of all pseudometrics over Rm that can be written as dW (x, y) = hx y,W (x y)i for some positive semidefinite matrix W 2 Rm⇥m (for the spherical margin, take W = rI where I is the identity matrix). Second, it strictly generalizes (the multiplicative version of) the classic SVM margin. Indeed, under the Euclidean metric, if X has diameter R = (X) and every cluster C can be separated from X \ C by a linear separator whose boundary has distance ⇢ from X , then C has convex hull margin at least ⇢R ; and there are cases with arbitrarily small (multiplicative) SVM margin but arbitrarily large convex hull margin, see Section 4. Finally, pseudometrics are versatile and can express, for instance, the Euclidean distance between points after a projection on a subspace. This models scenarios where each cluster only “cares” about a certain subset of the features.
Under the convex hull margin, we give a polynomial-time algorithm, named CHEATREC (for Convex Hull ExpAnsion Trick Recovery) that recovers C using O(log n) queries. Theorem 1. Let (X,O) be an instance whose latent clustering C has convex hull margin > 0. Then CHEATREC(X,O, ) outputs C, runs in time poly(k, n,m), and with high probability makes a number of label queries to O bounded by O k2m5 (1 + 1/ )m log(1 + 1/ ) log n .
To put this result in perspective, consider the algorithm of Bressan et al. [2020]. Under an ellipsoidal margin of EL, that algorithm achieves a query bound of roughly m
EL
m log n. One can check
that an ellipsoidal margin of EL implies EL3 for all EL  1 2. Hence, in this range, our dependence on is better by ⇥(m)m factors. 2Their definition uses squared distances, so the relationship with our margin is 1 + p 1 + EL.
Both CHEATREC and the algorithm of [Bressan et al., 2020] are based on boosting learners with one-sided error. What makes CHEATREC different is, thus, how it learns with one-sided error. To explain this, let us recall how algorithm of Bressan et al. [2020] works. The algorithm starts by drawing a uniform random sample of ⇥(m2) points SC from some cluster C. (As there are at most k clusters, to draw s points u.a.r. from some cluster we can just draw ks points u.a.r. from X , query their labels, and take the subset of the majority label). Then, it computes an outer approximation of conv(SC) by fitting a minimum-volume ellipsoid E(SC) to SC . Since the VC dimension of m-dimensional ellipsoids is O(m2), by standard PAC bounds E(SC) contains half of C with good probability. The problem is that E(SC) approximates conv(SC) very roughly, and thus it may intersect a large portion of X \C. Indeed, the algorithm makes roughly (m/ EL)m additional queries to filter out all points in E(SC) \ (X \ C). This gives us the following idea: instead of spending that many queries on “cleaning” E(SC), we spend them to build a much larger sample SC , so that we can approximate conv(SC) using a class of convex bodies of VC dimension much higher than ⇥(m2) — for instance, a polytope on (1 + 1/ )m vertices. That body should enclose conv(SC) quite tightly; perhaps so tightly to contain no point outside C. This intuition leads to our technique, called convex hull expansion trick, which essentially amounts to drawing a large sample from some cluster C and inflate its convex hull by a factor 1 + . This technique yields bounds that, compared to [Bressan et al., 2020], are strictly better and hold under more general assumptions. In the rest of the section, we describe this trick and sketch the proof of Theorem 1. For the complete proof, see the supplementary material.

heading: 3.1 CHEATREC and the convex hull expansion trick
text: The starting point of CHEATREC is the following idea. Let C be any cluster of C, and let SC be any subset of C. Let K = conv(SC), choose any z 2 K, and let Q = (1+ )K be the scaling of K with respect to z. Finally, let d 2 D be the pseudometric under which C has convex hull margin . Since d is homogeneous and invariant under translation (recall that every d 2 D is induced by a seminorm), any y 2 X such that d(y,K)  d(K) must belong to C as well. Therefore, X \Q ✓ C. That is, Q contains only points of C.
Clearly, knowing that X \Q ✓ C is not enough; in order to make progress, we must guarantee that X \Q forms a good fraction of C (in principle X \Q could just coincide with SC , in which case we learn nothing). To this end, we draw a uniform random sample S from X of size |S| = ks, where s will be set later, and query all labels of S. For every cluster C we let SC = S \ C; as there are at most k clusters, at least one of them satisfies |SC | s. The convex hull expansion trick says that, if (1) s is roughly (1 + 1/ )m, and (2) z = µK , where µK is the center of mass of K, then Q contains a good fraction of C with good probability. This gives the desired query bounds for learning C with one-sided error; to implement the trick in polynomial time, however, we have to replace µK with an approximation, since computing it exactly is hard [Rademacher, 2007]. The convex hull expansion trick in fact states that the claim about Q holds even with such an approximation.
We give below a formal statement of the trick, and a sketch of its proof. The uniform probability measure U over K is defined by U(K 0) = vol(K
0) vol(K) for all measurable K 0 ✓ K. A probability measure P is "-uniform if |P(K 0) U(K 0)|  " for all measurable K 0 ✓ K.
Lemma 1 (Convex hull expansion trick). Fix > 0, and let s = ⇥ m5 1 + 1/ m log 1 + 1/ large enough. Let SC be a sample of s independent uniform random points from some cluster C, and let K = conv(SC). Let X1, . . . , XN be independent random points sampled "-uniformly from K, with " 2 ⇥(m 1) small enough and N 2 ⇥(m2) large enough, and let z = 1N PN i=1 Xi. Finally, let Q = (1 + )K where the center of the scaling is z. Then P |Q \ C| |C|/2 1/2.
Sketch of the proof. For simplicity we ignore factors poly(m) and log(1/ ). To begin, suppose Q was obtained by scaling K about its own center of mass, µK . By a probabilistic argument adapted from [Naszódi, 2018], there exists a polytope P on roughly (1 + 1/ )m vertices such that K ✓ P ✓ Q. Now, the class Pt,m of all polytopes on at most t vertices in Rm has VC-dimension roughly t, see [Kupavskii, 2020]. Let then t = (1 + 1/ )m. Since P 2 Pt,m, and since P is consistent with SC (that is, SC ✓ P ), by standard PAC bounds P(|P \X| |C|/2) 1/2 as long as |SC | = ⌦(t) = ⌦ (1 + 1/ )m . But P ✓ Q, so P(|Q \X| |C|/2) 1/2 as well.
Now suppose that, in place of µK , we use z = 1N PN
i=1 Xi where each Xi is an independent random points sampled "-uniformly from K. We consider K is in isotropic position. The radius of K is then at most m, so kXik2  m. By standard calculations this implies that, if N = ⇥(m2) and each Xi comes from a distribution that is ⇥(1/m)-uniform over K, with good probability z is at distance ⌘ = O(1) from µK . In particular, by increasing N by constant factors, we can make arbitrarily small the probability that ⌘  1/3. This is sufficient to adapt a result of Naszódi [2018], through an extension of Grunbaum’s inequality for convex bodies due to Bertsimas and Vempala [2004], and show that a polytope P such as the one described above still exists, even if we expand K about z.
We conclude with a note on implementing CHEATREC in polynomial time. First, we should sample the points Xi efficiently. To this end, we transform SC so that conv(SC) is in near-isotropic position. This amounts to computing John’s ellipsoid for SC , and applying the map that turns that ellipsoid into a ball, which takes polynomial time. Afterwards, we can draw every Xi via the “hit-and-run from a corner” algorithm of Lovász and Vempala [2006], in time poly(m, |SC |) log m" — this includes the time to solve a linear program to determine when the random walk of [Lovász and Vempala, 2006] hits the boundary of K. Once we have z = 1N PN i=1 Xi, the only remaining issue is to avoid computing K = conv(SC) and Q = (1 + )K explicitly as intersections of halfspaces, as this could take time |SC |⇥(m). Instead, we just rescale the sample SC about z, obtaining a representation of Q as a set of vertices. Then, computing X \ Q amounts to solving for every x 2 X a feasibility problem, which takes polynomial time.

heading: 4 The one-versus-all margin
text: In this section, we let X be a generic space equipped with a set of pseudometrics. Like in Section 3, we want to formulate a notion of margin between clusters. However, we cannot express the margin in terms of diameter of convex hulls (since X need not be a vector space and may have no notion of convexity at all). Thus, we introduce a notion called one-versus-all margin. We prove that clusterings with positive one-versus-all margin can be recovered with O(log n) oracle queries. However, we do not provide a running time analysis; the implementation of our algorithm depends on X and on the specific class of clusterings, and in general may take time superpolynomial in the size of the input. Let us introduce the one-versus-all margin. Definition 3 (One-versus-all margin). Fix k pseudometrics d1, . . . , dk over X . A clustering C = (C1, . . . , Ck) of a finite set X ⇢ X has one-versus-all margin with respect to d1, . . . , dk if for all i 2 [k] we have di(X \ Ci, Ci) > di(Ci).
Remark. Unlike the convex hull margin (Definition 2), here d1, . . . , dk are fixed in advance. The reason is that here X may not be a linear space, C1, . . . , Ck may not be convex, or d1, . . . , dk may not be induced by seminorms. Hence, we cannot apply techniques like the convex hull expansion trick, which work for every pseudometric including d1, . . . , dk. As a consequence, it is unclear how one can recover C efficiently without knowing d1, . . . , dk in advance. Before continuing, we shall prove that the one-versus-all margin can be arbitrarily large while the multiplicative SVM margin is arbitrarily small. This also proves an analogous claim for the convex hull margin in Section 3. Lemma 2. For any u 2 R2 let du(x, y) = |hu, x yi|. For any ⌘ > 0 there exists a clustering C = (C1, C2) on a set X ⇢ R2 that has arbitrarily large one-versus-all margin with respect to d(0,1), d(1,0), and yet du(C1, C2)  ⌘ du(X) for all u 2 R2.
Proof sketch. Consider Figure 1. The two points along the x axis belong to C1, and the two points along the y axis belong to C2. The pseudometric d1 = d(0,1) measures the distance along the y axis, and the pseudometric d2 = d(1,0) measures the distance along the x axis. Therefore d1(C1, C2) > 0 = d1(C1), and d2(C1, C2) > 0 = d2(C2). Hence, the one-versusall margin of C with respect to d1, d2 is unbounded. Yet, for any ⌘ > 0 and any u 2 R2 we can make du(C1, C2)  ⌘ du(X) by placing the endpoints of the clusters arbitrarily near the origin.

heading: 4.1 The one-versus-all-margin captures the stability of center-based clusterings
text: Fix any pseudometric d over X . A clustering C = (C1, . . . , Ck) of X is center-based if there exist k points c1, . . . , ck 2 X , called centers, such that for every i 2 [k] and every x 2 Ci we have d(x, cj) > d(x, ci) for all j 6= i. In other terms, every point is assigned to the nearest center. It is well known that many popular center-based clustering problems, such as k-means or k-centers, are NP-hard to solve in general. However, those problems become polynomial-time solvable (or approximable) if the solution C meets certain stability properties. We show that two of these properties, the ↵-center proximity of Awasthi et al. [2012] and the (1 + ")-perturbation resilience of Bilu and Linial [2012], imply positive one-versus-all margin. Let us recall these properties. We define a (1 + ")-perturbation of d as any function d0 (which need not be a pseudometric) such that d  d0  (1 + ")d. Definition 4. Let C be a center-based clustering.
• C satisfies the ↵-center proximity property with ↵ > 1 if, for all i 2 [k], for all x 2 Ci and all j 6= i we have d(x, cj) > ↵ d(x, ci).
• C is (1+ ")-perturbation resilient with " > 0 if it is induced by the same centers c1, . . . , ck under any (1 + ")-perturbation of d.
It is known that (1+")-perturbation resilience implies ↵-center proximity with ↵ = 1+", see [Awasthi et al., 2012]. Our result is:
Theorem 2. If C satisfies ↵-center proximity, then it has one-versus-all margin (↵ 1) 2
2(↵+1) . Hence,
if C satisfies (1 + ")-perturbation stability, then it has one-versus-all margin " 2
2("+2) .

heading: 4.2 Cluster recovery with one-versus-all margin
text: We conclude by showing how a clustering with one-versus-all margin > 0 can be recovered with O(log n) queries. Our algorithm, MREC, draws uniform random points from X and then selects the smallest hypothesis consistent with the points sampled from each cluster (see Section 2). We will show that the VC-dimension of the class from which that hypothesis is taken can be bounded in terms of 1 . This implies that, at every round, MREC learns a constant fraction of labels without mistakes.
We need some further notation. Let d be any pseudometric over X . For any X ⇢ X and any r > 0, let M(X, r, d) be the maximum cardinality of any A ✓ X such that d(x, y) > r for all distinct x, y 2 A. From now on we assume that M(X, r, d) is bounded3, and for any > 0, we define M( , d) = max{M B(x, r), r, d : x 2 X , r > 0}. Thus any ball B contains at most M( , d) points at pairwise distance greater than times the radius of B, and some B attains this bound. Finally, by vc-dim(H,X) we denote the VC-dimension of a generic concept class H over a set X . Lemma 3 (One-versus-all margin implies one-sided-error learnability). Let d be any pseudometric over X . For any finite X ⇢ X and any > 0, define the effective concept class over X:
H = {C ✓ X : d(X \ C,C) > d(C)} (2) Then H = I(H), and vc-dim(H,X)  M⇤( , d) where M⇤( , d) = max(2,M( , d)). Therefore, H can be learned with one-sided error " and confidence with O " 2(M⇤( , d) log 1/" + 1/ ) examples by choosing the smallest consistent hypothesis in H .
Sketch of the proof. To prove that H = I(H), one can take any two C1, C2 2 H and show that C1 \ C2 satisfies the margin condition, too. To prove that vc-dim(H,X)  M⇤( , d), we have two steps. First, let sl(H,X) be the slicing dimension of H . This is the size of the largest subset S ✓ X sliced by H , i.e., such that for every x 2 S there is C 2 H giving S \ x = S \ C, see [Kivinen, 1995]. As the same work shows, we have vc-dim(I(H), X)  sl(H,X); hence, to prove vc-dim(H,X)  M⇤( , d) it suffices to prove that sl(H,X)  M⇤( , d). To this end, we use a packing argument. Suppose that S ✓ X is sliced by H , choose any x 2 S, and let C 2 H such that S \ x = S \ C. By construction of H , we know that d(C, x) > d(C). Since S \ x ✓ C, this yields:
d S \ x, x
d(C, x) > d(C) d(S \ x) (3)
3If M(X, r, d) is not bounded, then our results can be extended in the natural way, that is, we can prove a lower bound of ⌦(n) queries for instances of n points.
It can be shown that this implies d(S \ x, x) > d(S) for all x 2 S, and, in turn, |S|  M⇤( , d). The claim on the learnability with one-sided error holds by choice of the smallest consistent hypothesis in H = I(H), combined with standard PAC bounds.
We present our main result. Let M( ) = maxd2{d1,...,dk}M( , d) with d1, . . . , dk as in Definition 3.
Theorem 3. Let (X,O) be any instance whose latent clustering C has one-versus-all margin > 0 with respect to d1, . . . , dk. Then MREC(X,O, , d1, . . . , dk) outputs C while making, with high probability, at most O(M⇤( )k log k log n) label queries to O, where M⇤( ) = max(2,M( )). Moreover, for any algorithm A and for any > 0, there are instances with one-versus-all margin on which A makes ⌦(M(2 )) label queries in expectation.
Sketch of the proof. For the lower bounds, we take a set X on M(2 ) points at pairwise distance larger than 2 times the radius of X , which is at least times the diameter of X , and we draw a random clustering C in the form (x,X \ x). One can see that C has one-versus-all margin , and simple arguments, coupled with Yao’s principle for Monte Carlo algorithms, show that any algorithm needs ⌦(M(2 )) queries in the worst case to return C. For the upper bounds, we show how to learn an expected constant fraction of X with one-sided error using ⇥(M⇤( )k log k) queries; the rest follows by our general boosting argument. To begin, for each i 2 [k] we consider the effective concept class:
Hi = {C ✓ X : di(C,X \ C) > di(C)} (4)
We then set " = 1/2k and = 1/2, and draw a labeled sample S of size ⇥(" 1(M⇤( ) log 1/" + log 1/ )) = ⇥(M⇤( )k log k). Finally, for each i 2 [k] we choose the smallest hypothesis bCi 2 Hi consistent with the subset Si ✓ S labeled as i, and we assign label i to all points in bCi. Clearly, bCi ✓ Ci, therefore we are learning with one-sided error. Moreover, by Lemma 3, with probability at least 1/2 we have | bCi| |Ci| "|X| = |Ci| |X|/2k. As | bCi| 0, this implies E| bCi| |Ci|/2 |X|/4k. By summing over all i, this shows that we are labelling correctly at least |X|/4 points in expectation.
Remark. By Theorem 3, in Rm MREC yields a O(log n) query bound even when the clusters are not convex. Note however that this does not mean that MREC subsumes CHEATREC, for two reasons. First, as noted above, here d1, . . . , dk are known in advance, whereas MREC does not need to know them. Second, MREC works by computing the smallest hypothesis bCi consistent with Si (see the proof of Theorem 3), which in general may take superpolynomial time. Indeed, CHEATREC runs in polynomial time by not computing bCi at all.

heading: 5 One-versus-all clusterings
text: In this section we consider the case where the clusters of C are realized by some concept class H over X . This is the clustering equivalent of the one-versus-all multiclass classifiers (see, e.g., [ShalevShwartz and Ben-David, 2014]). We show that C is actively recoverable if and only if H has finite coslicing dimension, a combinatorial quantity similar to the star number of Hanneke and Yang [2015] and the slicing dimension of Kivinen [1995]. We also show that, for a wide family of concept classes in Rm, a finite coslicing dimension is equivalent to a positive one-versus-all margin. Let X be any domain, X ⇢ X any finite set, and C = (C1, . . . , Ck) a clustering of X . Let H be any concept class over X . We say that C is realized by H if for all i 2 [k] there is some hi 2 H such that Ci = X \ hi. For example, the ellipsoidal clusters of Bressan et al. [2020] can be formulated by letting X = Rm and letting H to be the family of all ellipsoids in Rm, and the convex clusters of Section 3 can be formulated by letting X = Rm and letting H to be the family of all polytopes in Rm. Clearly, we expect the number of queries needed to recover C to depend on H. This leads us to the question: what can we say about the recoverability of C in terms of H?

heading: 5.1 The coslicing dimension
text: We show that the number of queries needed to actively recover C depends on a combinatorial quantity that we call coslicing dimension of H. Definition 5. We say that H coslices X ✓ X if for all x 2 X there exist two concepts h+x , h x 2 H such that X \ h+x = {x} and X \ h x = X \ {x}. The coslicing dimension of H is:
cosl(H) = sup{|X| : X is cosliced by H}
If H coslices arbitrarily large sets then we let cosl(H) = 1.
For instance, let X = Rm. If H is the class of linear separators, then cosl(H) = 1 (take X to be the set of vertices of an n-vertex polytope and use the hyperplane separator theorem). If instead H is the class of axis-aligned boxes, it can be shown that cosl(H) = 2m. Our main result is: Theorem 4. If cosl(H) < 1 then there is an algorithm that, given any n-point instance whose latent clustering C is realized by H, recovers C with O(cosl(H) k log k log n) label queries with high probability. Moreover, for any algorithm A there are instances on cosl(H) points whose latent clustering C is realized by H where A makes ⌦(cosl(H)) label queries in expectation to return C. As a consequence, if cosl(H) = 1 then in the worst case any algorithm needs ⌦(n) label queries in expectation to recover an n-point clustering realized by H.
Sketch of the proof. We follow the same ideas of the proof of Theorem 3. For the lower bound, we take any X cosliced by H with |X| = cosl(H), and we draw a random clustering of X in the form (x,X \ x). For the upper bound, for each i 2 [k] we define the effective concept class:
Hi = {C : C = C 0i ^ (C 01, . . . , C 0k) 2 Pk(X)} (5)
where Pk(X) is the set of all clusterings of X realized by H. As observed in the proof of Lemma 3, we have the general relationship vc-dim(I(Hi), X)  sl(Hi, X) whenever sl(Hi, X) < 1. Therefore, if we show that sl(Hi, X)  cosl(H), by drawing a labeled sample of size ⇥(cosl(H) k log k) we can recover the labels of an expected constant fraction of X , as in the proof of Lemma 3. To prove that sl(Hi, X)  cosl(H), let U = {x1, . . . , x`} ✓ X be sliced by Hi. By construction of Hi, there are ` clusterings C1, . . . , C` realized by H and such that Cj = (xj , U \xj) for all j 2 [`]. This implies that U is cosliced by H. Hence, |U |  cosl(H) and so sl(Hi, X)  cosl(H).
Remark. In the case of convex clusters in Rm, we would let H be the class of all convex polytopes, obtaining cosl(H) = 1 and thus Theorem 4 would not provide any useful bound. This is true even if C has convex hull margin > 0, although by Theorem 1 we know that C can be recovered with O(log n) queries. The same holds for the one-versus-all margin. This is because we defined the coslicing dimension as a function of H, through which we cannot capture margin properties — indeed, the margin depends on the instance (X,O) rather than on H. We note however that one could fix this by redefining the coslicing dimension in the form cosl(H, I), where I is a class of instances, and adapt Theorem 4 correspondingly. Then, under the assumption that all the instances (X,O) 2 I have margin > 0, one could bound cosl(H, I) as a function of , recovering the same type of bounds of Theorem 1 and Theorem 3.

heading: 5.2 The one-versus-all margin, again!
text: We look again at the case X = Rm. Consider any concept class H. Theorem 4 and the remark above say that, if cosl(H, I) < 1 where I is the class of allowed instances, then the latent clustering of any instance can be recovered with O(log n) queries. Note that we are not using any notion of margin here — only the finiteness of cosl(H, I). Here we show that, for a wide family of concept classes in Rm, a finite coslicing dimension and a positive one-versus-all margin are actually equivalent. This equivalence is established by proving that the O(log n) query bound is attainable if and only if the instances have positive one-versus-all margin. In what follows, we assume that H satisfies: Definition 6. A concept class H in Rm is non-fractal if there is h 2 H such that both h and its complement contain a ball of positive radius.
This assumption avoids pathological cases; for instance, H containing only hypotheses that are affine transformations of Cantor’s set. Our result is: Theorem 5. Let H be a concept class in Rm that is non-fractal and closed under affine transformations. There is an algorithm that, given any instance whose latent clustering C has one-versus-all margin and is realized by H, returns C while making O(Mk log k log n) label queries with high probability, where M = max 2, (1 + 4/ )m . Moreover, for any algorithm A, there exist arbitrarily large n-point instances, whose latent clustering C has arbitrarily small one-versus-all margin and is realized by H, where A makes ⌦(n) label queries in expectation to recover C.
Sketch of the proof. The upper bounds follow by Theorem 3 and the packing number of Rm. For the lower bounds, we show that arbitrarily large packings of a sphere are cosliced by H. We use Figure 2 for reference. Let h 2 Rm be such that both h and its complement h contain a ball of positive radius. Then, for any ⇢ > 0 there exist a ball B = B(c, r) ✓ h with r > 0, and a point x 2 h such that d(B, x)  ⇢. Now take a sphere S of radius r0 ⌧ r with center on the segment xc. Let ⌘ = supy2S\B d(x, y), and let X be an ⌘-packing of S, that is, a subset of points of S such that d(x0, x00) > ⌘ for all distinct x0, x00 2 X . Note how this implies that every x0 2 X \ x necessarily lies in S \ B, and therefore, in S \ h. Moreover, by letting ⌘/r0 ! 0, we can take X arbitrarily large. Since H is closed under affine transformations, by rotating X it follows that for every x 2 X there is hx 2 H such that X \ hx = X \ x. By applying the same argument to h and by complementation we can show that X \ h0x = {x} for some h0x 2 H for all x 2 X as well. Hence H coslices arbitrarily large sets. To conclude, invoke Theorem 4.
Note that Theorem 5 applies to several basic concept classes H. For instance, when H is the class of all linear separators, the class of all ellipsoids, the class of all polytopes, and the class of all convex bodies (bounded or not, and possibly degenerate). It also includes more complex classes with non-convex concepts, for instance, the class of all finite or infinite disjoint unions of balls, polytopes, or convex bodies.

heading: 6 Future Work
text: An interesting direction for future work is to explore the power of different types of queries to avoid the exponential dependency on the dimensionality of the ambient space. Another open problem is to understand if our margin conditions are sufficient to obtain PTASes for k-means and other centerbased clustering problems. A third open problem is to close the gap in the exponential dependence on the dimension in the Euclidean case, which is (1+1/ )m in our upper bound and roughly (1+1/ )m/2 in the lower bound of Bressan et al. [2020].
Acknowledgments and Disclosure of Funding
The authors gratefully acknowledge partial support by the Google Focused Award “Algorithms and Learning for AI” (ALL4AI). Nicolò Cesa-Bianchi is also supported by the MIUR PRIN grant Algorithms, Games, and Digital Markets (ALGADIMAR) and by the EU Horizon 2020 ICT-48 research and innovation action under grant agreement 951847, project ELISE (European Learning and Intelligent Systems Excellence).

Review summaries:
This work examines a cluster recovery problem where the algorithm has access to an oracle that can return whether two points lie in the same cluster. It builds on a line of work [Ashtiani et al. ‘16] [Bressan et al. ‘20] that does so with only O(log n) queries but under a margin property (the dependence on the margin is hidden in the number of queries). [Ashtiani et al. ‘16] did so with a spherical margin property: there is a sphere around each cluster separating it from all other points, and this had to continue to hold as the sphere was expanded by a (1 + gamma) factor. [Bressan et al. ‘20] generalized this assumption to ellipsoidal margins, and this work further generalizes that to “convex hull” margins and even further to “one-versus-all” margins.

This work studies query efficient cluster recovery with label queries. In particular, given a k-clustering $(C_1,\ldots,C_k)$ of an $n$ point set $X$, the learner may ask, adaptively, for any $x \in X$, “which cluster contains x?” The goal is to recover the clustering on all n points using only $O_k(\log(n))$ queries. This is a very natural problem, variants of which have seen significant study both within the clustering (e.g. Ashtiani et al. 2016) and active learning literature (e.g. Kane et al. 2017).  The authors prove a number of interesting results to this effect. In the Euclidean setting, the authors introduce a novel complexity measure called the “Convex Hull Margin” that non-trivially generalizes previous sufficient conditions for query efficient cluster recovery such ball and ellipsoid-based margins and the SVM margin. They show that small convex hull margin implies computational and query efficient cluster recovery (with near optimal query complexity), even improving previous special cases such as the ellipsoid margin. The authors also study an extension to non-Euclidean spaces which are only assumed to have some fixed set of pseudometrics. In this case, they introduce a novel measure called “one-versus-all” margin. They prove this measure generalizes a number of known cluster recovery results such as center proximity and perturbation stability, and also gives a sufficient condition for query (but not computationally) efficient cluster recovery.  Finally, the authors also address an interesting variant of cluster recovery where the clusters must be realized by some fixed concept class H. In this scenario, the authors introduce coslicing dimension which captures a well-known lower bound of Dasgupta showing that efficient learning is impossible when every point can be cutoff from the rest. They then proceed to show that this is in fact the only barrier to efficient cluster recovery—proving that finite coslicing dimension is necessary and sufficient.

This paper considers the problem of finding convex clusters in space using a small number of cluster queries. It gives an algorithm for this problem, and also extends the algorithm to the one-vs-all margin. It further shows a connection to exact active cluster recoverability.