On Margin-Based Cluster Recovery with Oracle Queries
Authors: Marco Bressan
Nicolò Cesa-Bianchi
Silvio Lattanzi
Andrea Paudice
Venue: NeurIPS 2021 Poster (2021)
Keywords: theory of clustering
active learning
clustering in metric spaces
convex hulls
clustering stability
same-cluster queries

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 $\mathbb{R}^m$, we give an algorithm that recovers \emph{arbitrary} convex clusters, in polynomial time, and with a number of queries that is lower than the best existing algorithm by $\Theta(m^m)$ 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 near-optimal 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 $\mathbb{R}^m$, this characterization is equivalent to our margin condition. Our results show a deep connection between cluster margins and active cluster recoverability.


On Margin-Based Cluster Recovery with Oracle Queries
Marco Bressan
Nicolò Cesa-Bianchi
Dept. of CS, Univ. of Milan, Italy breso.b @ unimi.it
DSRC & Dept. of CS, Univ. of Milan, Italy scoolo.cesaabianchi @ unnim..it
Silvio Lattanzi
Andrea Paudice
Google silviol@ gomgle.com
Dept. of CS, Univ. of Milan, Italy & Istituto Italiano di Tecnologia, Italy
andrea.paudice @audice@@eae @ unimi.it
Abstract
We study an active cluster recovery problem where, given a set of n points and 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 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 (log n) queries. For RT", we give an algorithm that recovers arbitrary convex clusters, in polynomial time, and with number of queries that is lower than the best existing algorithm by ((m") factors. For general pseudometric spaces, where clusters might not be convex might not have any notion of shape, we give an algorithm that achieves the Ollog n) query bound, and is provably near- optimal as a function of the packing number of the space. Finally, for clusterings realized by binary concept classes, we give a combinatorial characterization recoverability with nl queries, and we show that, for many concept classes in IR" this characterization is equivalent to our margin condition. Our results show deep connection between cluster margins and active cluster recoverability.
Introduction
This work investigates the problem of exact cluster recovery using oracle queries, in the well-known framework introduced by Ashtiani et al. [016]. We are given a set X of n points from some domain X' (e.g., from the Euclidean m-ddimensional space "!" and an oracle answering to same- cluster 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 consistent with some clustering (CI...., Cx) of unknown to the algorithm, where is a fixed constant. The goal is to design an algorithm that recovers C by using few queries as possible.
Clearly, if there are no restrictions on C, then any algorithm needs queries the worst case. Thus, our goal is to understand when C can be recovered efficiently; ideally, in polynomial time, and by making Ollog r)) queries. A natural attempt to consider clusterings with well-separated clusters, since this is what is often considered "good clustering". The existing work goes precisely in this direction, starting with the following result of Ashtiani et al. (2016) for the case X C RT every cluster C; is separated from X C by ball centered in the center of mass of C, and that ball does not intersect other clusters even if expanded by a factor of + 7, then with high probability
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

poly(k, m. 1/-) log queries are sufficient to recover C. in polynomial time. This is called "spherical margin" condition, and y is called the margin.
Unfortunately, the spherical margin condition is not very realistic, since it imposes a very precise shape upon the clusters. In generalization attempt. [Bressan et al. [0200] showed that one can actually recover clusters with ellipsoidal separators with arbitrary centers, by increasing the number of queries to poly(k; m, 3/1) (1=/>)"" log n. This result is achieved via boosted one-sided error learning, which works as follows. Suppose that, by making [k, m, 7) queries, we could identify correctly (with zero mistakes) a constant fraction of the points in some cluster C.. Then, we could label those points as i, remove them from the dataset, and repeat. It is not hard to show that, after O 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 C2 with one-sided error (one-sided eπror means that any point of X predicted to be in C, must be in C.). The key insight in [Bressan et al. 2020 is that, the clusters have margin with respect to their ellipsoidal separators, then roughly (m//>) Th queries are sufficient. This leads to the following question: how much can this approach be extended?
attempt,Bressan
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 new notion of margin in R" 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 + 7)) This technique yields a polynomial-time exact cluster recovery algorithm that uses poly(k, m. 1/>) (1 1/5) log queries (Theorem T). The (1 + 1/-) dependence on fy and m is significantly better than that of Bressan et al. 20200. and closer to their lower bound of order (1 + 1/-)m//?
2. We introduce notion of cluster margin for general pseudometric spaces called one-versus-di 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--lll margin, then it can be recovered with (()) pkly(k) log n queries via pure learning -thoorethhc approach (Theorem B) where M()) is quantity related to the packing numbers of the pseudometric space. We show that the dependence on M1) is essentially optimal, thus characterizing the recoverability of clusterings in this setting. 3. Finally, we show connection between nargin-based learning and exact active cluster recov- erability, when clusters are realized by some concept class H (that is, when for each cluster C, there is concept h; E H such that X n h; C₁). We show that if certain combina- torial parameter, the coslicing dimension (H)) is bounded, then one can learn clusterings with cosl (H) poly(k) log label queries; otherwise, Q(n) queries are needed in the worst case (Theorem f. Moreover we show that, for all concept classes in Ih that are closed under affine transformations and well-behaved in 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 multiclass classifier in the transductive realizable case. Hence our results apply to that case, too. In particular, our Olog n) query bounds imply Ölog 1/e) query bounds for pool-based active learning [McCallum and Nigam 1998 of multiclass classifiers, where e is the generalization error. To see this, draw set X of O & T(= log 1/s + log 1/8)) 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 C X (that is, to active learning in the standard sense) if our margin conditions are only enjoyed by the set of positives X4 X O h. To see this, let X C IR2 and suppose X+ contains single point. Then X satisfies our conditions with unbounded margin w.r.t. the Euclidean distance, but any algorithm needs ((n) label queries 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 I compares the bounds resulting from the different notions of margins known.

---

margin
query bound
reference
spherical
o k logn n + 1:2 log 1
Ashtiani et al.
2016
k logn n (k'm² log k + max 2Tm 0 )(})
ellipsoidal
0
7 log m2
Bressan et al. 2020
k kmm (1+ :) log (1 + 7) logn)
convex hull
0
this work
one-versus-all
OM h2 log logk log
this work
Table I: Summary of existing margin notions and corresponding known query bounds for same-cluster
queries. The first three bounds assume X = R".. The fourth bound is for general pseudometric spaces and M (r) is roughly a packing number-see see Section 4 Note that m can often be replaced by the maximum rank (i.e., the rank of the subspace spanned by the points) of any cluster, see (Bressan et al. 2020]. The spherical margin assumes, for every cluster C₁ that Va C₁, y X Ci d'y, 14) > (1+7)d(z,, 14)), where μ4 = [ea Exec, I. The ellipsoidal margin assumes that for some PSD matrix W E IRm and some e4 E nem, Vo E C. y X \ Ci, dw (v: (4) > +T+ (I, C.), where dw (a. b) = V(a b, W(a b)); note that for y < this can be thought of as dw (y. ci) > + () (z, Gi).
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.
201 8a b
Gamlath al.) 2018 Huleihel et al. 2019, Mazumdar and Pal 2017 Mazumdar and Saha
2017b
Saha and Subramanian, 2019 Vitale et al., 2019] and in practice |Firmani et al. 2018 Gruenheid
ct 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 al. 2007| Balcan and Long 2013. Kane al. 2017 Bressan al. 202 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
22044]
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. [202]], ]. 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 2Tm, can be inferred
by adapting arguments of HHpkins 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 Shaley-Shwartz) [2014). Other learning settings related to one-sided and active learning are RPU learning [Rivest and Sloan|
1988) and perfect selective classification (EI-Yaniy and Wiener
2012
see [Hopkins et al. 2020a for discussion.
2
Preliminaries and notation
All missing proofs can be found in the supplementary material. The input is a pair (X, O), where X is set of points from some domain X. and O is label oracle that, when queried any I E X, returns the cluster id C(x) of æ. The oracle O is consistent with a latent clustering C = (Ct...., Cc) of X, i.e., k-tuple of pairwise disjoint sets whose union is X 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 function of the answers to the first
1 queries. We express the number of queries as a function of k, n,, and other parameters to be introduced later. This setting essentially equivalent to the semi-supervised active clustering (SSAC) framework of Ashtiani et al. (2066), where the oracle answers same-cluster queries SCQ(I, y) that, for any two points x, E 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 & SCQ queries, up relabeling of the clusters, our bounds hold for an sco oracle as well if multiplied by k. For conciseness, we state query bounds in the form fk, m, n, 7),
In line with previous works, assume i is fixed and known.
3

---

for instance Ok2 (1 + 1/-)a logn). These bounds should be thought of as min (n., fkk 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' and 2 0. the closed ball of radius centered at x: is r(x, = {y N' d(xx, y) S r. For any X C X, we denote by (x(X) = =' d(x, x²) the diameter of X measured by d, and we define (0) infset.gss d(U, .) their distance according d, and we define d(U, 0) = xo. For any X C R we write conv(X) for the convex hull of X. The unit sphere in I is 5 {z R ||ai|12 1/22=00 1}. We recall some Icarning-theooe theoretic facts. Let H be an arbitrary collection of subsets of X (i.e., a concept class). The intersection class of H is [(H) = UseN fhy nh. : ,1.....,h,
O. For any two sets U.S C X. we denote by d(U, =
h4 E H). Given any S C X and any S' C S realized by some ht* E H. the smallest concept in ((H) consistent with S' defined as h = =[ E H h ns = 5'). Note that ho k", Finally, we recall the definition of learning with siddd error:
Definition (Kivinen [1995]. Definition 4.4), An algorithm A learns H with one-sided error & and confidence ö with examples if. for any target concept h H and any probability measure P over X. by drawing independent labeled examples fromm P, the algorithm outputs a concept h C hh* suchh that P(h \ h) S with probubility least -6 5.
3 Margin- exact recovery of clusters in R.
In this section we consider the case X' = R". We show that the ellipsoidal margin of Bressan ett al. [020] 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 R" 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 seminorm).
Definition 2 (Convex hull margin). Let D be the family of all pseudometrics induced by the semi- norms over Rmm and let X C IhT be a finite set. A clustering C (CI...., CCk) of X has convex hull margin y for every E [k] there exists d; E D such that:
dx(X \. C2 conv(C.)) > (a,(C))
(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 pscudometrics over R" that can be written as dw [z, y) = (a y, W(x - y)) for some positive semidefinite matrix W E Rmmm (for the spherical margin, take W rT 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 p from X, then C' has convex hull margin least f;: and there are cases with arbitrarily small (multiplicative) SVM margin but arbitrarily large convex hull margin, see Section g Finally, pseudometrics are versatile and can express, for instance, the Euclidean distance between points after a projection on subspace. This models scenarios where each cluster only "cares" about certain subset of the features.
Under the convex hull margin, give a polynomial-time -time algorithm, named CHEATREC (for Convex Hull ExpAnsion Trick Recovery) that recovers C using Olog n) queries.
Theorem 1. Let (X, O) be an instance whose latent clustering C has convex hull margin "y >> O. Then CHEATREC X, 7) outputs C, runs in time poly (k:, n., m.), and with high probability makes a number of label queries to O bounded by Olkmm (1 + 1/7)* log(1 + log.n.
To put this result in perspective, consider the algorithm of Bressan et al. 2020 Under an ellipsoidal
margin of YEL. that algorithm achieves a query bound of roughly <pp
log n. One can check
that an ellipsoidal margin of TEL implies ? 2 vEE for all TEL S dependence on 7 is better by ((m)" factors.
Hence, in this range, our
Thhei definition uses squared distances, the relationship with our margin is 1 ++y 2 vI YEL.
4

---

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 (mm²) points Sc from some cluster C. (As there are at most clusters, to draw 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& minimum-volume ellipsoid E(Sc) to Sc. Since the VC dimension of m-dimensional ellipsoids is O(m²), by standard PAC bounds E(Sc) contains half of C' with good probability. The problem is that EScc) approximates conv(Se) very roughly, and thus it may intersect a large portion of X \ C. Indeed, the algorithm makes roughly (m//7n.)" ) additional queries to filter out all points in E(Sc) n (X) (C).
This gives us the following idea: instead of spending that many queries on "cleaning" F((Sc), we spend them to build a much larger sample Sc, so that we can approximate conv(Sc) using class of convex bodies of VC dimension much higher than O(m²) - for instance, polytope on (1 + 1/4)* m vertices. That body should enclose conv(Sc) quite tighty; 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 large sample from some cluster C' and inflate its convex hull by a factor + 7. This technique yields bounds that, compared to [Bressan et all, 2020]. are strictly better and hold under more general assumptions. In the rest of the section, we deseribe this trick and sketch the proof of Theorem For the complete proof, see the supplementary material.
3.1 CHEATREC and the convex hull expansion trick
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(Se) choose any x E K, and let Q = (1 + 7) be the scaling of K with respect z. Finally, let d E D be the pseudometric under which C has convex hull margin 7. Since d is homogeneous and invariant under translation (recall that every d E D is induced by a seminorm), any y X such that d(y, K) 5 70a(K) must belong to C' as well. Therefore, X inn S C. That is, Q contains only points of C.
Clearly, knowing that X nQQ C C is not enough; in order make progress, must guarantec that X I Q forms a good fraction of C (in principle X n Q could just coincide with Sc. in which case we learn nothing). To this end, we draw uniform random sample S from X of size |S| ks, where 8 will be set later, and query all labels of S. For every cluster C we let Sc = S n C: as there are at The convex hull expansion trick says that, if (1) s is roughly (1 + 1/>)m² and (2) 2 = μK, where 2x 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 uxx 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.
most i clusters, at least one of them satisfies |Scl
We give below formal statement of the trick, and a sketch of its proof. The uniform probability measure UI over is defined by U((K) = vol( for all measurable K' C K. A probability measure
vol(K)
P is E-uniform if IP(K') - U(K') S for all measurable K' C K.
Lemma 1 (Convex hull expansion trick). Fix > O, and let s = (1+111/)))" log (1 ++11/ 11/)) large enough. Let Sc be sample of independent uniform random points from some cluster C, and let K = conv(Sc). Let ".,..,,,, be independent random points sampled e-uniformly from K, with 01m small enough and N E O(m²) large enough, and let z + >N Xa. Finally,
let Q (1 + K where the center of the scaling is Then P((Qn)) > (C12)) 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 probabilistic argument adapted from Naszódi 2018), there exists a polytope P on roughly (1+ + 1/5)*T vertices such that K C Q. Now, the class Pt.m of all polytopes on at most vertices in RM has VC-dimension roughly t, see [Kupavskii] 2020). Let then t = (1 + 1/2)a. Since P E Pi.m. and since P is consistent with Sc (that 1s, Sc C P), by standard PAC bounds P([P n X| 2 (CI/2) 2 1/2 long as |Scl = Q(t = 2((1 + 1/-) But P C Q, so P([Q nx| 2 (CI/2) > 1/2 as well.
5

---

N Em= X, where each X; is an independent random points sampled e-uniformly from K. We consider K isotropic position. The radius of K is then at most m, so | S m. By standard calculations this implies that, if N = ((m²) and each X; comes from a distribution that is /m)--ufforrm over K, with good probability
Now suppose that, in place of Pk. we use 2=
at distance " Q(1) from ИК- In particular, by increasing N by constant factors, we can make arbitrarily
small the probability that 7j I 1/3. This is sufficient to adapt a result of Naszódi (2018), through an
extension of Grunbaum's s inequality for convex bodies due to Bertsimas and Vempala (2004), and show that a polytope such as the one described above still exists, even if we expand K about 2. E
We conclude with a note on implementing CHEATREC in polynomial time. First, we should sample the points X, efficiently. To this end, we transform Sc so that (onv(Sc) is in near-isotropic position. This amounts to computing John's 's ellipsoid for Sc, and applying the map that turns that ellipsoid into a ball, which takes polynomial time, Afterwards, we can draw every X, via the "hit-and-run from corner" algorithm of Lovász and Vempala (2006), in time poly(m, |Sc|)) log the time to solve a linear program to determine when the random walk of [[ovááz and Vempala 2006) hits the boundary of K. Once we have 2 N Σx= X,, the only remaining issue is to avoid computing K conv(Sc) and Q = (L + K explicitly intersections of halfspaces, as this could take time | Instead, we just rescale the sample Se about z, obtaining representation of Q as set of vertices. Then, computing X n Q amounts to solving for every x E X feasibility problem, which takes polynomial time.
this includes
4 The one-versus-all margin
In this section, we let X' be a generic space equipped with a set of pseudometrics. Like in Section 5 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 all). Thus, we introduce notion called one-versus-all margin. We prove that clusterings with positive one-versus-all margin can be recovered with (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-al margin). Fix ls pseudometrics di...., da over X. A clustering C = (CI,...,Cy of a finite set X X has one-versus-all margin y with respect to di....,d dg if for all i E [k] we have dX \ C., C.) > r @5, (C.).
Remark. Unlike the convex hull margin (Definition 2). here dj.... ......... de are fixed in advance. The reason is that here X' may not be a linear space, C1..... C₁ may not be convex, or d1.... dg may not be induced by seminorms. Hence, we cannot apply techniques like the convex hull expansion trick, which work every pseudometric including d1..... dg. As a consequence, it is unclear how one can recover C efficiently without knowing d1, .......,.. dç in advance.
Before continuing, we shall prove that the me-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 5
Lemma 2. For any E R let du(x. v) (u, - y) For any O there exists clustering
(C1, C2) on a set X C IR2 that has arbitrarily large one-versus all margin with respect to d(u,1), d(1,)) and yet di, (C1, C2) < 11 na (X) for all u E R..
Proof sketch. Consider Figure The two points along the x axis belong to C1 and the two points along the y axis belong to Cz. The pseudometric d1 d/o.1) measures the distance along the axis, and the pseu- dometric d2 = d(1,0 measures the distance along the x axis. Therefore (CI, C2) >
da, (C1). and (2(C1, C2) > 0 = &d, (C2). Hence, the one-versus- all margin of C with respect to d1, d2 is unbounded. Yet, for any 1) > 0 and any E IR² we can make (C, C2) < 77 6z, (X) by placing the endpoints of the clusters arbitrarily near the origin.
Figure 1: An instance with arbitrarily small SVM margin but unbounded one- versus-all margin.

---

4.1 The one-versus-all-man captures the stability of center-based clusterings
Fix any pseudometric over X. A clustering C = (Ci....,,Co C2)) of X center- renter-based if there exist k points cI....,cC, Ck E X. called centers, such that for every i E [k] and every I C2 we have d(z,c)) > d(z, ci) for all j # In other terms, every point is assigned to the nearest center. it well known that many popular center-based clustering problems, such as k-means or k-centers, are Na-hard to solve in general. However, those problems become polynomial-time solvable (or approximable) the solution C. meets certain stability properties. We show that two of these properties, the a-center proximity of Awastti et al. 2012] and the (1 + perturrbatio resilience of Bilu and Linial [2022] imply positive one-versus-al margin. Let us recall these properties. We define a (1 + =pprtturbbtiionn of d as any function d' (which need not be a pseudometric) such that S d' S (1+e)d.
Definition 4. Let C be center-based clustering.
C satisfies the a-center proximity property with a if. for all i E for all x E C, and all j * i we have d(z, e;) > a ad(x, ci).
is (1 + +) perturbation resilient with E 0 if is induced by the same centers C1,..., C2. under
any (1 + s) -perturbation of d.
is known that peeruurrraaaano resilience implies a-center proximity with a 1+s, see Awasthi et al. 2012]. Our result is:
Theorem 2. IfC satisfies o-center proximity, then it has one-versus-all margin 7 2 (a-1) 1)² Hence,
2a-1j
C satisfies (1 e)-perturbattio stability, then has one-versus-all margin 7. 2(e+2)
4.2 Cluster recovery with one-versus-all margin
We conclude by showing how clustering with one-versus-all margin 7 > 0 can be recovered with (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 L. This implies that, every round, MREC learns a constant fraction of labels without mistakes. 3.
We need some further notation. Let d be any pseudometric over X. For any X C X and any > 0. let M(X,r. r, d) be the maximum cardinality of any A C X such that d(x, y) > r for all distinct y,y E A. From now on we assume that M(X, r; d) is bounded and for any 7 O, define (17, d) = max(MM(B(z,))) yr, d) x E X,r > 0}. Thus any ball B contains most M(7, d) points at pairwise distance greater than y times the radius of B, and some B attains this bound. Finally, by ve-dim (, X) we denote the VC-dimension of generic concept class H over set X. Lemma 3 (One-versus-al all margin implies one-sided-erro learnability). Let d be any pseudometric over X. For any finite X X and any y > 0, define the effective concept class over X:
H = ==
d(X C)C) > (
Then = I(H), and ve-dim H, () S (y, d) where M d) = max(2, M(, d)). Therefore, H can be learned with one-sided error and confidence 5 with O(e 00e-2((M (7,d) d) log 1/e + 1/6) examples by choosing the smallest consistent hypothesis in H.
Sketch of the proof. To prove that H = I(H), one can take any two C₁, C2 H and show that
C n C2 satisfies the margin condition, too. To prove that ve-dim H, X) S MM d), we have TwO steps. First, let sI(H,X) be the slicing dimension of H. This is the size of the largest subset S C X sliced by H, i.e., such that for every x E S there is C E H giving S \ a = S n C, see (Kivinen, |995). As the same work shows, we have vo-dim([(H). X) < sl(H, hence, to prove ve-dim X) < MM d) it suffices to prove that sl(H, X) M (T, d). To this end, we use a packing argument. Suppose that S C X is sliced by H, choose any S. and let C E H such that S \ 5 D C. By construction of H, we know that d(C,,) x) > (0a(C). Since S \ x C C, this yields:
d( x, 2 d(C,,) > (C 2 7 (S(((())
(3)
'II T.,,X x,, d) is not bounded, then our results can be extended in the natural way, that is, we can prove a lower bound of (()) queries for instances of points.
7

---

It can be shown that this implies d(S' \ x2 > (S) for all z E S, and, in turn |S| < (y, d). The claim on the learnability with one-sided error holds by choice of the smallest consistent hypothesis in H- = TH), combined with standard PAC bounds.
We present our main result. Let (() = maxde d.) M d) with d di...., da as in Definition
Theorem 3. Let (X, O) be any instance whose latent clustering C has one-versus-all margin Y > 0 with respect to di....,de dx. Then MREC(X, O, 7, di...., probability, at most O(M (7) log k log n) label queries O where M* (1) max(2, M()).
......d, dk) outputs C while making, with high
Moreover, for any algorithm- A and any y > O, there are instances with ame-versus-al margin ?
on which A makes (2x)) label queries in expectation.
Sketch of the proof. For the lower bounds, we take a set X on M (27) points at pairwise distance larger than 27 times the radius of X. which is least times the diameter of X, and we draw random clustering C in the form (x, X \ æ). One can see that C has one-versus-all margin 7 and simple arguments, coupled with Yao's principle for Monte Carlo algorithms, show that any algorithm needs (2y)) 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 O (7)k log k) queries: the rest follows by our general boosting argument. To begin, for each i E [k] we consider the effective concept class:
= (C d(c,x () > > (C)}
(4)
We then set & = 1/2k and = 1/2, and draw a labeled sample S of size O(s- log 1/c + log 1/6)) (MM log k). Finally, for each i [k] we choose the smallest hypothesis C. E H; consistent with the subset S, C S labeled i, and we assign label i to all points in C. Clearly, C S C.. therefore we are learning with one-sided error. Moreover, by Lemma 3 with probability at least 1/2 we have |C,1 2 |C,| - = = |C&| - / As |C,| 2 0, this implies E C,| >
[C.I/2 - |/K4 By summing over all i, this shows that we are labelling correctly at least | points in expectation.
Remark. By Theorem in R 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 di,...,d d2 are known in advance, whereas MREC does not need to know them. Second, MREC works by computing the smallest hypothesis C; consistent with S: (see the proof of Theorem 3 which in general may take superpolynomial time. Indeed, CHEATREC runs in polynomial time by not computing C₁ at all.
5 One-versus-all clusterings
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 the one-versus-all multiclass classifiers (see, e.g., [Shalev] Shwartz and Bav-D 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 19955 We also show that, for a wide family of concept classes in IRm a finite coslicing dimension is equivalent to positive one-versus-all margin.
Let X' be any domain, X C X' any finite set, and C = (CI..... C1) clustering of X. Let 7 be any concept class over X. We say that is realized by H. for all E [k] there is some hT H such that C = X C h4. For example, the ellipsoidal clusters of Bressan et al. 2020 can be formulated by _g and the convex clusters of Section 3 can be formulated by letting X = R and letting H to be the family of all polytopes in Rmm Clearly, we expect the number of queries needed to recover to depend on H. This leads us to
letting X' = m and letting H to be the family of all ellipsoids
the question: what can we say about the recoverability of C in terms of H??
8

---

5.1 The coslicing dimension
We show that the number of queries needed to actively recover C depends on combinatorial quantity that we call coslicing dimension of H.
Definition 5. We say that H coslices X S X if for all x E X there exist two concepts h h2 E H such that X n h {x} and X n h = X (z). The coslicing dimension of H. is:
cosl(H) | X is cosliced by H} If H. coslices arbitrarily large sets then we ler cHsl(H) oc.
For instance, let X' = RR... If H. is the class of linear separators, then cosl(H) co (take X to be the set of vertices of an n-vertex polytope and use the hyperplane separator theorem). instead H is the class of axis-aligned boxes, it can be shown that cosl(H) = 2mn. Our main result is:
Theorem 4. If cosl(H) < oc then there is an algorithm that, given any n-point instance whose latent clustering C is realized by H. recovers C with (H)) k log k llo n) label queries with high probability. Moreover, for any algorithm A there are instances on cos((H) points whose latent clustering C realized by H. where A makes Q ()))))(H)) label queries expectation to return C. As a consequence, if cosl(H) oo then in the worst case any algorithm needs (m)) 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| = (H), and we draw a random clustering of X in the form (2c, X \ vt.
For the upper bound, for each i [k:] we define the effective concept class:
= (C C= A (C,...., ..) E Px()))
(5)
where P& is the set of all clusterings of X realized by H. As observed in the proof Lemma we (.,iim([(H,),.)))
Therefore, sl XX) whenever si X) < we show that sl H, X) S cos)(H). by drawing a labeled sample of size ( (H) l: log k) we can recover the labels of expected constant fraction of X, as in the proof of Lemma 3 To prove that sl H,, X) I cosl(H). let U = {#1,... Iz C X be sliced by H,. By construction of H,, there f clusterings C1, ....... Ce realized by H and such that C₁ = (zzj. U U( for all j E [e]. This implies
have the general relationship
that U is cosliced by H. Hence, |U| S (H))(H) and so sl H; X) I cos)
L
Remark. In the case of convex clusters in Im would let H be the class of all convex polytopes, obtaining (H)) = do and thus Theorem would not provide any useful bound. This is true even if C has convex hull margin y > although by Theorem ! we know that can be recovered with Olog n2) queries. The same holds for the one-versus-all margin. This is because we defined function of H. through which we cannot capture margin properties
the coslicing dimension 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 I), where I is class of instances, and adapt Theorem 4 correspondiigly. Then, under the assumption that all the instances (X, O) E I have margin y > 0. one could bound cosl(H, I) as function of y, recovering the same type of bounds of Theorem and Theorem R
5.2 The one-versus-all margin, again!
We look again the case X' _ Consider any concept class H. Theorem and the remark above say that, if cosl(H, Z)- < oc where I is the class of allowed instances, then the latent clustering of any instance can be recovered with Olog n) queries. Note that we are not using any notion of margin here only the finiteness of cosl(?l.
Here show that, for wide family of concept classes in RT finite coslicing dimension and positive one-versus-all margin are actually equivalent. This equivalence is established by proving that the Ollog 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 E H such that both 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 concept class in I."' that is non-fractal and closed under affine transforma- tions. There is an algorithm that, given any instance whose latent clustering C has one-versus-all margin 7 and is realized by H. returns C. while making O (MM k log k log n. label queries with high probability, where M max (2, (1 + 4/-)""). Moreover, for any algorithm A, there exist arbitrarily large n-point instances, whose latent clustering C has arbitrarily small on-versus-all margin and is realized by H. where A makes (n)) label queries in expectation recover C.
Sketch of the proof. The upper bounds follow by Theorem S and the packing number of IR"". For the lower bounds, show that arbitrarily large packings of a sphere are cosliced by H. We use Figure 2 for reference. Let h E I be such that both / and its complement h contain ball of positive radius. Then, for any p > there exist a ball = r) S h with r > O, and point E h such that d( S p. Now take a sphere S of radius r' < with center on the segment
X
Let yu S & d(x, y), and let X be an 7-packing of S, that is, subset of points of S such that d(x', x²) > 1, for all distinct x'xx" E X. Note how this implies that every x' E X \ necessarily lies in S n B, and therefore, in h. Moreover, by letting n/r' + O, we can take X arbitrarily large. Since H is closed under affine transformations, by rotating X follows that for every x E X there ht E H such that X n hr X æ. By applying the same argument to h and by complementation we can show that X n h2= = {z} for some 1/ E H for all x E as well. Hence H coslices arbitrarily large sets. To conclude, invoke Theorem 4
Figure The 17-accknng X is in B, and thus in h. except for x that lies in h. By taking B arbitrarily close to x; we can make v arbitrarily small and thus X arbitrarily large.
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.
6 Future Work
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 obtain PTASSs for k-means and other center- based 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+11/ 1/-""" in our upper bound and roughly (1 1/-/
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 Al" (AI.L4AT). Nicold Besa-Bianchi 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).
References
N. Ailon, A. Bhattacharya, and R. Jaiswal. Approximate correlation clustering using same-cluster queries. In Proc. of LATIN, pages 14-27, 2018a.
N. Ailon, A. Bhattacharya, Jaiswal, and A. Kumar. Approximate clustering with same-cluster queries. In Proc. of ITCS, volume 94, pages 40:1-40:21, 2018b.
10

---

H. Ashtiani. S. Kushagra, and S. Ben-David. Clustering with same-cluster queries. In Advances in Neural Information Processing Systems, volume 29, pages 3216-3224, 2016.
Awasthi, A. Blum, and O. Sheffet. Center-based clustering under perturbation stability. Information Processing Letters, 1 11((1):49-54 2012.
M.-F. Balcan and P. Long. Active and passive learning of linear separators under log-coneave distributions. In Proc. of COLT, pages 288-316, 2013.
M.-F. Balcan, A. Broder, and T. Zhang, Margin based active learning. In Proc. of COLT, pages 35-50, 2007.
A. Basu and T. Oertel. Centerpoints: link between optimization and convex geometry. SIAM Journal on Optimization, 27(2):866888, 2017.
S. Ben- Den-David, N. Cesa-Bianchi. D. Haussler, and P. Long. Characterizations of learnability for classes of {0.... n vallued functions. Journal of Computer and System Sciences, 50(1):74-86, 1995.
D. Bertsimas and S. Vempala. Solving convex programs by random walks. J. ACM, 51(4):540-556, July 2004.
Y. Bilu and N. Linial. Are stable instances easy? Comb. Probab. Comput., 21(5):643-661) Sept. 2012.
M. Bressan, N. Cesa- Cesa-Bianches Bianchi, S. Lattanzi, and A. Paudice. Exact recovery of mangled clusters with same-cluster queries. Advances in Neural Information Processing Systems, volume 33, pages 9324-9334, 2020.
M. Bressan, N. Cesa-Bianchi, S. Lattanzi, and A. Paudice. Exact recovery of clusters in finite metric spaces using oracle queries. In Proc. of COLT, volume 134, pages 775-803, 2021.
A. Daniely and S. Shalev-Shwartz. Optimal learners for multiclass problems. In Proc. of COLT, volume 35, pages 287-316, 2014.
Dasgupta. Analysis a greedy active learning strategy. In Proc. NIPS, page 337-344, 2004.
R. El- Yaniv and Y. Wiener. Active learning via perfect selective classification. Journal of Machine Learning Research, 13(2), 2012.
D. Firmani, Galhotra, B. Saha, and Srivastava. Robust entity resolution using a crowd oracle. IEEE Data Eng. Bull., 41(2):91-103, 2018.
B. Gamlath, S. Huang, and O. Svensson. Semi-supervised algorithms for approximately optimal and accurate clustering. In Proc. of ICALP, pages 57:1-57:14, 2018.
A. Giannopoulos. Notes on isotropic convex bodies, 2003. URL http://users. uoa. gr/
A. Gruenheid, B. Nushi, T. Kraska, W. Gatterbauer, and D. Kossmann. Fault-tolerant entity resolution with the crowd. arXiv preprint arXiv:1512.00537, 2015.
S. Hanneke and L. Yang. Minimax analysis of active learning. J. Mach. Learn. Res., 16(12): 3487-3602, 2015.
M. Hopkins, Kane, and Lovett. The power of comparisons for actively learning linear classifiers. In Advances in Neural Information Processing Systems, volume 33, pages 6342-6353, 2020a.
M. Hopkins, D. Kane, S. Lovett, and G. Mahajan. Noise-tolerant, reliable active classification with comparison queries. In Proc. of COLT, volume 125, pages 1957-2006, 2020b.
M. Hopkins, D. Kane, S. Lovett, and M. Moshkovitz. Bounded memory active learning through enriched queries. In Proc. of COLT, pages 2358 2288,22372200 2021.
W. Huleihel, A. Mazumdar, M. Médard, and Pal. Same-cluster querying for overlapping clusters. In Advances in Neural Information Processing Systems, volume 32, pages 10485-10495, 2019.

---

D. M. Kane, S. Lovett, S. Moran, and J. Zhang. Active classification with comparison queries. In Proc. of IEEE FOCS, pages 355-366, 2017.
L. Khachiyan. Rounding of polytopes in the real number model computation. Mathematics of Operations Research, 21(2):30--320, 1996.
J. Kivinen. Learning reliably and with one-sided error. Mathematical Systems Theory, 2822)141-112 1995.
A. Kupavskii. The VC-dimension of k-vertex d-polytopes. Combinatorica, 4001 2020.
L. Lovász and S. Vempala. Hit-and-rup from comer. SIAM Journal on Computing, 35(4):985-0055. 2006.
A. Mazumdar and S. Pal. Semisupervised Clustering, AND-Queries and Locally Encodable Source Coding. In Advances in Neural Information Processing Systems, volume 30, pages 6489-6499, 2017.
A. Mazumdar and B. Saha. Query complexity of clustering with side information. In Advances in Neural Information Processing Systems, volume 30, pages 1682-4699 2017a.
A. Mazumdar and B. Saha. Clustering with noisy queries. In Advances in Neural Information Processing Systems, volume 30, pages 5788-5799, 2017b.
A. McCallum and K. Nigam. Employing em and pool- based active learning for text classification. In Proc. of ICML, page 350-358, 1998.
M. Naszódi. Approximating a convex body by polytope using epsilon-net theorem. Discrete Computational Geometry, 61()):68--693, Mar. 2018.
L. A. Rademacher. Approximating the centroid is hard. In Proc. of ACM SoCG, page 302-305, 2007.
R. L. Rivest and R. Sloan. Leamiing complicated concepts reliably and usefully. In Proc. of COLT, pages 69-79, 1988.
B. I. Rubinstein, P. L. Bartlett, and J. H. Rubinstein. Shifting: One-inclusion mistake bounds and sample compression. Journal of Computer and System Sciences, 75(1):37-59, 2009.
B. Saha and Subramanian. Correlation Clustering with Same-Cluster Queries Bounded by Optimal Cost. In Proc. of ESA, pages 81:1-81:17, 2019.
S. Shalev-Shwartz and S. Ben-David Understanding Machine Learning: From Theory to Algorithms. Cambridge University Press, USA, 2014. ISBN 1107057132.
V. Verroios and H. Garcia-Molina. Entity resolution with crowd error. In Proc. of IEEE ICDE, pages 219-230, 2015.
V. Verroios, H. Garcia-Molina, and Papakonstantinou. Waldo: An adaptive human interface for crowd entity resolution. In Proc. of ACM SIGMOD, pages 1133-1148, 2017.
F. Vitale, A. Rajagopalan, and C. Gentile. Flattening hierarchical clustering through active learning. In Advances Neural Information Processing Systems, volume 32, pages 15263-15273, 2019.
L. Xu, J. Neufeld, Larson, and D. Schuurmans. Maximum margin clustering. Advances Neural Information Processing Systems, pages 1537-1544, 2004.
12

---

Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope? [Yes]
(b) Did you describe the limitations of your work? [Yes] The assumptions and conditions
under which our results hold are clearly specified in the paper.
(c) Did you discuss any potential negative societal impacts of your work? [N/A] This is
purely theoretical paper and does not imply any foreseeable societal consequence.
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you are including theoretical results...
(a) Did you state the full of assumptions all theoretical results? [Yes]
(b) Did you include complete proofs of all theoretical results? [Yes]
3. If you ran experiments...
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either the supplemental material or as URL)? [N/A]
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [N/A]
(c) Did you report error bars (e.g., with respect the random seed after running experi- ments multiple times)? [N/A]
(d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, or cloud provider)? [N/A]
4. If you are using existing assets (e.g., code, data, models) or curating/releasing new assets...
(a) your work uses existing assets, did you eite the creators? [N/A]
(b) Did you mention the license of the assets? [N/A]
(c) Did you include any new assets either in the supplemental material or as a URL? [N/A]
(d) Did you discuss whether and how consent obtained from people whose data you're you're using/curating? [N/A]
(c) Did you discuss whether the data you are using/curating contains personally identifiable information or offensive content? [N/A]
5. If you used crowdsourcing or conducted research with human subjects...
(a) Did you include the full text of instructions given participants and screenshots, if applicable? [N/A]
(b) Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, applicable? [N/A]
(c) Did you include the estimated hourly wage paid to participants and the total amount spent participant compensation? [N/A]
13


Reviews:
[{"review_id": "yjCh5d1bvEf", "reviewer": "Reviewer_BX75", "summary": "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.", "questions": "", "limitations": "", "rating": 7, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The first problem considered is where a label is defined by a convex body with a margin, such that if the convex body is expanded outwards by a small factor times its diameter, it does not intersect any new points. The algorithm to find a cluster samples points, draws a convex body around those of the same label, and then grows the body by a constant factor, about the center of mass of the points. The authors show with high probability the new body either contains a significant number of new points of the same label (or contains all points of the label). This is done by combining two separate combinatorical results, the first by Naszodi which bounds the number of vertices of the body, and the second a recent breakthrough of Kupavskii which gives the VC-dimension of this object. While the overview is quite straightforward, the details are not.\n\nThe authors then consider more general spaces, and define a one-vs-all margin similar to above, but without the requirements of Euclidean space, or even convexity. They show that it generalizes the clustering notions of center proximity and perturbation stability. They then demonstrate that such a margin implies learnability, and show how to plug it in to an analogue of the previous algorithm, to again learn clusters using a small number of label queries. This demonstrates that their framework can be applied to a range of setting.\n\nI found the results in this paper to be interesting and also deep while still being accessible. I would anticipate them being applied to other learning problems in related fields as well.\n\nMinor comments:\nI think the authors should expand on the comment in line 245 on fixing the pseudometrics in advance, and how this differs from what is done in line 141. I found this confusing.\n\nThe abstract and introduction inexplicably seem to think that R^m and Euclidean space are the same thing. \n\nThe opening assertion that queries identifying a point's cluster and queries determining whether a pair are in the same cluster are the equivalent, but this is only true if k is small and one a representative of each cluster at hand.\n\nTypos: k-uple should be k-tuple.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4 hours"}, "extra_text": {}}, {"review_id": "KGAtIR_Pfp0", "reviewer": "Reviewer_fefH", "summary": "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.", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Although all three of [Ashtiani et al. ‘16], [Bressan et al. ‘20], and this work manage to only use O(log n) queries, this way of writing the bound tunnel visions on the dependence on the number of points n and ignores the number of clusters k and the margin gamma. I went through the other papers, and the queries seem to have the following dependence on these other two parameters (omitting the dependence on the algorithm failure probability delta) (translating to the variable names used by this paper):\n- [Ashtiani et al. ‘16]: O(k log n + k^2 / gamma^4 log k)\n- [Bressan et al. ‘20]: O(k log n (k^2 m^2 log k + 2^m (m / gamma log (m / gamma))^m)\n- This work: O(k^2 m^5 (1 + 1/gamma)^m log (1 + 1/gamma) log n)\n\nNotably, with respect to the dimension m, this work has better dependence compared to [Bressan et al.’ 20] (which the authors point out in the paper) but worse dependence compared to [Ashtiani et al. ‘16]. In some sense then, this work is an improvement to the ellipsoid margin case, which seems much simpler to justify the impact of (compared to trying to come up with cases that fall under convex hull margins but not ellipsoid margins); [Bressan et al. ‘20] point out ellipsoids make sense over spheres when one expects the features to be on different scales.\n\nFor both of these last two results, I am concerned that the appearance of m in the exponent makes them not that useful. In the experimental section of [Bressan et al. ‘20], the problem dimension is chosen to be quite small: 2, 4, 6, or 8. This paper is missing an experimental section, and so the question of how the proposed algorithm practically compares to its two predecessors is left open.\n\nIt’s also worth considering exactly how much the generalized margin properties allow one to capture additional interesting cases. The paper proves that several other properties imply the one-versus-all margin, including the SVM margin, alpha-center proximity, and (1 + eps)-perturbation resilience.\n\nOverall, I think this result can be viewed as a nice theoretical contribution on past work. I wish the practical consequences were given a closer look, but I’d still lean towards acceptance to NeurIPS.\n\nMisc.:\n- Line 243: Equation (2) does not appear to be centered properly.\n\n-----\nI've read the author's response, thank you!\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "An optimistic view of where this line of research leads might be that future work improves the other factors in the query complexity / running time and it winds up being more applicable. I can see this work fitting into this hypothetical overall progression nicely due to the new margins and techniques it introduces.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3 hours"}, "extra_text": {}}, {"review_id": "IatEXIPn73F", "reviewer": "Reviewer_jtkL", "summary": "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).\n\nThe 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.\n\nFinally, 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.", "questions": "", "limitations": "", "rating": 7, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "This work makes significant progress on a natural, important problem in both clustering and active learning. The results are very clean, and likely of broad interest to the learning theory community. The techniques, while relatively simple, are an interesting mix of combinatorial, probabilistic, and inference based methods that could easily be of use in future work. On top of this the paper is well-written, and has careful analysis of their relation to margin parameters in prior work. The proofs I checked seemed sound, and no outlandish claims are made otherwise.\n\nMy only real complaints are due to a few missing references.\n\nFirst, the “Convex Hull Expansion Trick” is not novel. The same trick was introduced by Hopkins, Kane, Lovett, and Mahajan (COLT 2020) to bound the inference dimension of clusters (when considering halfspaces under TNC noise). However their analysis recovers a slightly worse query complexity bound, and may be of narrower scope than the general pseudometric variant considered in this work. The analysis is also quite different, as HKLM rely on LP duality. \n\nSecond, the coslicing dimension lower bound generalizes a result due to Dasgupta (in “Analysis of a greedy active learning strategy”). This should be mentioned. In fact I would say it is a strength of the result, the authors show that Dasgupta’s classic bound is essentially the only barrier to cluster recovery in this setting!\n\nFinally a few minor notes:\n\nUsually query complexity is included in computational complexity, so it doesn’t make much sense to say your algorithm uses exp(m) queries but runs in poly(m) time. Plus, the regime you consider is only really interesting for n >> 2^m (otherwise you can’t do inference), so poly(m) vs exp(m) runtime doesn’t really make a difference anyway.\n\nI think the terminology “outputs C deterministically\" is a bit non-standard (though not technically wrong) given that the algorithm is randomized. Usually this would be referred to as a “randomized zero-error” algorithm.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "N/A", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "8"}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper discusses a clustering setting in which clusters are recovered using queries of the form “are two points x, x’ in the same cluster”, in a general notion of margin which generalizes previously studied cases.  The paper is theoretical, with no experimental part.  Reviews are high quality, with consistent pro-accept bottom line.  Reviewers raised some concerns related to novelty of some notions defined in the paper, and also related to lack of experiments, but these do not seem to considerably impact the final opinion.


Decision: Accept (Poster)