Venue: ICLR 2020 Conference

Reviews:

final_score: rating: 6: Weak Accept
review_content: This paper studies the problem of learning both the distance metric and a linkage rule from clustering examples. Suppose we have L metrics d_1, …, d_L and L’ linkage rules for hierarchical agglomerative clustering, D_1, …, D_L’ where each rule is a 2-point-based merge function (i.e. computes the distance between some two points in the clusters, examples of such functions are single-linkage and complete-linkage). The paper considers the problem of finding the convex combination of the distance functions and linkage rules which best fits the data. The main result (Theorem 1) is an \tildeO((L’ + L)^2 L’ /eps^2) uniform convergence bound on the number of clustering instances which are required to learn up to expected loss \eps the best possible convex combination. The key technical part of the proof is showing that for any fixed clustering the loss function is piecewise-constant with a small number of simple pieces. The overall approach is based on Balcan et al.’17 who solve the case when the distance metric is known but the linkage rule is to be learned and Balcan et al. ‘19 who give techniques for the piecewise constant case. Some further results are given which are specific to learning a mix of two merge functions under a single distance metric and the best combination of two metrics when using the complete linkage merge function. Experimental results are given on MNIST, CIFAR-10 and some other fairly small datasets.

The paper makes a somewhat interesting contribution to the area, but I think can only be seen as a basic step in the general direction. Most of the interesting merge functions used for HAC don’t boil down to simple 2-point-merge rules (average-linkage, Ward’s method, etc.). The sample complexity of the problem is rather prohibitive. In particular, it is unclear to me why the experimental setup in the paper is consistent with the theoretical model -- when i.i.d. clusterings should be sampled from a distribution, why is it ok to just sample 5 random classes from MNIST a bunch of times? In this case the ground truth clustering is fixed and you sample some subset of classes from it each time. This seems like a much simpler setup compared to the general setting considered in the paper.  I would expect a real experimental setup to have all n points be fixed, then you have a distribution over different clusterings on the same set of points which you sample from each time.

review_title: Official Blind Review #1

final_score: rating: 6: Weak Accept
review_content: Summary:

This paper proposed a data-driven method of selecting a linkage-based clustering algorithm from a large space. The space of algorithms is parameterized by two sets of parameters which indicate the convex combinations of metrics and merge functions. They analyze the sample complexity for small generalization error. An efficient algorithm for searching an empirically optimal algorithm is proposed.

Comments:

In general, I think this is a good quality paper. 
- Selecting a clustering algorithm from a large space by a data-driven method is an interesting and sound idea, which makes a lot of sense to me. 
- The theorem for generalization error is strong.

It can be further improved in the following aspects (mainly the experiments).
- The curves in Fig 3 all look smooth, so I wondered whether one can simply apply a grid search on [0.1,0.2,...,1.0], the obtained algorithm should also be very good. To demonstrate the advantage and necessity of the proposed search algorithm, I think it better to either conduct an experiment with a higher dimensional search space (instead of only searching \alpha) or demonstrate a case when there is a sharp turn near the optimal point, so that grid search won't work well.
- Although the authors have proved the generalization error, it is still better to empirically validate the theoretical result, by showing the training and testing errors along with varying sample sizes.

Overall I like the idea and the theoretical analysis in this paper, but the experimental results could be further improved. Therefore I vote for weak acceptance.


----- after reading the response --

I'd like to thank the authors for giving more explanations. Theoretically, I understand the advantages of the proposed algorithm, but still, it is more convincing if stronger experiments can be conducted.

My score does not change, but overall I advocate to accept this paper.

review_title: Official Blind Review #3

final_score: rating: 6: Weak Accept
review_content: In this paper, the authors propose an approach to learning combinations of (instance-wise) distance metrics and (cluster-wise) merge functions to optimally cluster instances from a  particular data distribution. In particular, given a set of clustering instances (each of which is a set of instances from the domain and their cluster assignment), a set of distance metrics, and a set of merge functions, the proposed approach aims to learn a convex combination of the distance metrics and merge functions to reconstruct the given clusterings.

The paper has two main contributions. First, a PAC learning type of guarantee is given on the quality of the learned clustering approach. Second, an efficient data structure for identifying the convex combinations is given. A small set of experiments suggests that, in practice, the learned combinations can outperform using single distance metrics and merge functions.

Comments

I am not an expert in this area; I had trouble following the details of the theoretical developments. However, I appreciated that intuition was given on both what the theorems and lemmas were showing as well as the main steps of the proofs.

Concerning Theorem 1, it is not exactly clear to me what the contribution is on top of [Balcan et al., 2019]. The text mentions that they already give sample complexity guarantees in what seems like the same setting (piecewise-structured cost function).

The authors point out that depth-first traversal is a good choice here due to its memory efficiency. However, in cases where the search space is a graph rather than a tree (i.e., there are multiple paths to some nodes), then DFS can exponentially increase the work compared to breadth-first or other search strategies (e.g., [Edelkamp and Schroedl, 2012]). While the name suggests that the “execution tree” is, indeed, a tree, is this guaranteed to be the case? or could multiple paths lead to the same partition?

For the experimental evaluation, it seems as though there is no “test” set of clustering instances. It would be helpful to also include performance of the learned combinations on some test clustering instances to give an idea of how generalizable to approach is to other instances within the data distribution. (Of course, the main contributions of this work are the theoretical developments, so just one or two examples would be sufficient.)

For motivation, it would be helpful to give some examples where the prerequisites of this work are actually met; that is, cases where sufficiently large number of labeled cluster instances are available, but the generative mechanism of the clusters is not.

For context, it could be helpful to briefly mention how, if at all, the current results apply to widely-used clustering algorithms such as k-means or Gaussian mixture models.

Typos, etc.

The references are somewhat inconsistently formatted. Also, some proper nouns in titles are not capitalized (e.g., “lloyd’s families”).

“leaves correspond to” -> “leaves corresponding to”

What does the “big-Oh tilde” notation in Theorem 1 mean?

review_title: Official Blind Review #2

Meta-review: All reviewers come to agreement that this is a solid paper worth publishing at ICLR; the authors are encouraged to incorporate additional comments suggested by reviewers.
Decision: Accept (Poster)