Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 7: Good paper, accept
review_content: 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.
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.

The 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.

I 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.

Minor comments:
I 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.

The abstract and introduction inexplicably seem to think that R^m and Euclidean space are the same thing. 

The 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.

Typos: k-uple should be k-tuple.
limitations_and_societal_impact: Yes.
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: 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.
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):
- [Ashtiani et al. ‘16]: O(k log n + k^2 / gamma^4 log k)
- [Bressan et al. ‘20]: O(k log n (k^2 m^2 log k + 2^m (m / gamma log (m / gamma))^m)
- This work: O(k^2 m^5 (1 + 1/gamma)^m log (1 + 1/gamma) log n)

Notably, 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.

For 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.

It’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.

Overall, 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.

Misc.:
- Line 243: Equation (2) does not appear to be centered properly.

-----
I've read the author's response, thank you!

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_title: null

final_score: rating: 7: Good paper, accept
review_content: 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).

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.
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.

My only real complaints are due to a few missing references.

First, 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. 

Second, 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!

Finally a few minor notes:

Usually 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.

I 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.
limitations_and_societal_impact: N/A
review_title: null

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)