Learning to Link
Authors: Maria-Florina Balcan
Travis Dick
Manuel Lang
Venue:  (2020)
Keywords: Data-driven Algorithm Configuration
Metric Learning
Linkage Clustering
Learning Algorithms

Abstract: Clustering is an important part of many modern data analysis pipelines, including network analysis and data retrieval. There are many different clustering algorithms developed by various communities, and it is often not clear which algorithm will give the best performance on a specific clustering task. Similarly, we often have multiple ways to measure distances between data points, and the best clustering performance might require a non-trivial combination of those metrics. In this work, we study data-driven algorithm selection and metric learning for clustering problems, where the goal is to simultaneously learn the best algorithm and metric for a specific application. The family of clustering algorithms we consider is parameterized linkage based procedures that includes single and complete linkage. The family of distance functions we learn over are convex combinations of base distance functions. We design efficient learning algorithms which receive samples from an application-specific distribution over clustering instances and learn a near-optimal distance and clustering algorithm from these classes. We also carry out a comprehensive empirical evaluation of our techniques showing that they can lead to significantly improved clustering performance on real-world datasets.

LEARNING TO LINK
Maria-Florina Balcan Carnegie Mellon University ninamf cs. cmu. edu
Travis Dick
Manuel Lang
University of Pennsylvania tbd0 seas. upenn. edu
Karlsruhe Institute of Technology manuel. langestudent. kit. edu
ABSTRACT
Clustering is an important part of many modern data analysis pipelines, including network analysis and data retrieval. There are many different clustering algorithms developed by various communities, and it is often not clear which algorithm will give the best performance task. Similarly, we often have multiple ways to measure distances between data points, and the best clustering performance might require a non-trivial combination of those metrics. In this work, we study data-driven algorithm selection and metric learning for clustering problems, where the goal is to simultaneously learn the best algorithm and metric for specific application. The family of clustering algorithms we consider is parameterized linkage based procedures that includes single and complete linkage. The family of distance functions we learn over are convex combinations of base distance functions. We design efficient learning algorithms which receive samples from distribution over clustering instances and learn a near-optimal distance and clustering algorithm from these classes. We also carry out comprehensive empirical evaluation of our techniques showing that they can lead to significantly improved clustering performance on real-world datasets.
specific clustering
inplication-spccife
1 INTRODUCTION
Overview. Clustering is an important component of modern data analysis. For example, we might cluster emails as a pre-processing step for spam detection, or we might cluster individuals in social network in order to suggest new connections. There are a myriad of different clustering algorithms, and it is not always clear what algorithm will give the best performance on specific clustering task. Similarly, we often have multiple different ways to measure distances between data points, and it is not obvious which distance metric will lead to the best performance, In this work, we study data-driven algorithm selection and metric learning for clustering problems, where the goal is use data to simultaneously learn the best algorithm and metric for a specific application such as clustering emails or users of a social network. An application is modeled as a distribution over clustering tasks, we observe an i.i.d. sample of clustering instances drawn from that distribution, and our goal is to choose an approximately optimal algorithm from a parameterized family of algorithms (according some well-defined loss function). This corresponds settings where we repeatedly solve clustering instances (c.g., clustering the emails that arrive each day) and we want to use historic instances learn the best clustering algorithm and metrie.
The family of clustering algorithms we learn over consists of parameterized linkage based procedures and includes single and complete linkage, which are widely used in practice and optimal in many cases (Awasthi et al. 2014 Saeed et al. 2003: White et al., 2010 Awasthi et al. 2012; Balcan and Liang] 2016 Grosswendt and Roeglin 2015). The family of distance metrics we learn over consists of convex combinations of base distance functions. We design efficient learning algorithms that receive samples from an ipplication-spciffi distribution over clustering instances and simultaneously learn both a near-optimal distance metric and clustering algorithm from these classes. We contribute to recent line of work that provides learning -twooretigttttiiall guarantees for data-driven algorithm configuration (Gupta and Roughgarden] 2017 Balcan et al. 2017 2018a] 2019). These papers analyze the intrinsic complexity of parameterized algorithm families in order to provide sample complexity guarantees, that is, bounds on the number of sample instances needed in order to find an approximately optimal algorithm for a given application domain. Our results build on the work of Balcan al. (2017) , who studied the problem of learning the best clustering algorithm from class of linkage based procedures, but did not study learning the best metric. In addition to our sample complexity guarantees, we develop number of algorithmic tools that enable learning application specific clustering algorithms and metries for realistically large clustering instances. We use our efficient implementations to conduct comprehensive experiments on clustering domains derived from both real-world and synthetic datasets. These experiments demonstrate that learning

---

application-specife algorithms and metrics can lead to significant performance improvements over standard algorithms and metrics.
Our Results. We study linkage-based clustering algorithms that take as input a clustering instance S and output a hierarchical clustering of S represented as binary cluster tree. Each node in the tree represents a cluster in the data at one level of granularity, with the leaves corresponding to individual data points and the root node corresponding to the entire dataset. Each internal node represents cluster obtained by merging its two children. Linkage-basse clustering algorithms build a cluster tree from the leaves up, starting with each point belonging to its own cluster and repeatedly merging the "closest" pair of clusters until only one remains. The parameters of our algorithm family control both the metric used to measure pointwise distances, as well as how the linkage algorithm measures distances between clusters (in terms of the distances between their points).
This work has two major contributions. Our first contribution is to provide sample complexity guarantees for learning effective intiicattoo-spcciffe distance metrics for use with linkage- based clustering algorithms. The key challenge is that, if we fix clustering algorithm from the family we study and a single clustering instance S, the algorithm output is piecewise constant function of our metric family's ' parameters. This implies that, unlike many standard learning problems, the loss we want to minimize is very sensitive to the metric parameters and small perturbations to the optimal parameters can lead to high loss. Our main technical insight is that for any clustering instance S, we can partition the parameter space of our metric family into relatively small number of regions such that the ordering over pairs of points in given by the metric is constant on each region. The clustering output by all algorithms in the family we study only depends on the ordering over pairs of points induced by the metric, and therefore their output is also a piecewise constant function of the metric parameters with not too many pieces. We leverage this structure to bound the intrinsic complexity of the learning problem, leading uniform convergence guarantees. By combining our results with those Balcan et al. (017). we show how to simultaneously learn both an application-specific metric and linkage algorithm.
Our second main contribution is comprehensive empirical evaluation of our proposed methods, enabled by new algorithmic insights for efficiently learning application-specifie algorithms and metrics from sample clustering instances. For any fixed clustering instance, we show that we can use an execution free data structure efficiently construct a coarse partition of the joint parameter space so that on each region the output clustering is constant. Roughly speaking, the execution tree compactly describes all possible sequences of merges the linkage algorithm might make together with the parameter settings for the algorithm and metric that lead to that merge sequence. The learning procedure proposed by |Balcan et al. (017)) takes a more combinatorial approach, resulting in partitions of the parameter space that have many unnecessary regions and increased overall running time. |Balcan et al. (20T8a) and Balcan et al. (20T 8b) also use an execution tree approach for different algorithm families, however their specific approaches to enumerating the tree are not efficient enough to be used in our setting, We show that using a depth-first traversal of the execution tree leads to significantly reduced memory requirements, since in our setting the execution tree is shallow but very wide.
Using our efficient implementations, we evaluate our learning algorithms on several real world and synthetic clustering applications. We learn the best algorithm and metric for clustering applications derived from MNIST. CIFAR-10, Omniglot, Places2, and synthetic rings and disks distribution. Across these different tasks the optimal clustering algorithm and metric vary greatly. Moreover, in most cases we achieve significant improvements in clustering quality over standard clustering algorithms and metrics.
Related work. Gupta and Roughgarden (2077) introduced the theoretical framework for analyzing algorithm config- uration problems that we study in this work. They provide sample complexity guarantees for greedy algorithms for canonical subset selection problems including the knapsack problem, maximum weight independent set, and machine scheduling.
Some recent works provide sample complexity guarantees for learning application-specet clustering algorithms. Balcan et al. (0017) consider several parameterized families of linkage based clustering algorithms, one of which is a special case of the family studied in this paper. Their sample complexity results are also based on showing that for single clustering instance, we can find a partitioning of the algorithm parameter space into regions where the output clustering is constant. The families of linkage procedures they study have a single parameter, while our linkage algorithm and metric families have multiple Moreover, they suppose we given fixed metric for each clustering instance and do not study the problem of learning an application-speciff problem of learning the best initialization procedure and local search method to use in clustering algorithm inspired by Lloyd's method for k-means clustering. Their sample complexity results are again based on demonstrating that for any clustering instance, there exists a partitioning of the parameter space on which the algorithm's 's output is constant.
metric. [Blcan et al.) (2018b) study the related
2

---

The parameter space partitions in both of these related works are defined by linear separators. Due to the interactions between the distance metric and the linkage algorithm, our partitions are defined by quadratic functions.
The procedures proposed by prior work for finding an empirically optimal algorithm for a collection of problem instances roughly fall into two categories: combinatorial approaches and approaches based on an execution- data structure. Gupta and Roughgarden (0117) and [alcan et al. (2017) are two examples of the combinatorial approach. They show that the boundaries in the constant-output partition of the algorithm parameter space always occur at the solutions to finitely many equations that depend on the problem instance. To find an empirically optimal algorithm, they find all solutions to these problem-dependent equations to explicitly construct a partition of the parameter space. Unfortunately, only small subset of the solutions are actual boundaries in the partition. Consequently, their partitions contain many extra regions and suffer from long running times. The execution-tree based approaches find the coarsest possible partitioning of the parameter space such that the algorithm output is constant. [Balcan et al. (2018h) and Balcan ct al. (2018a) both use execution trees to find empirically optimal algorithm parameters for different algorithm families. However, the specific algorithms used to construct and enumerate the execution tree are different from those explored in this paper and are not suitable in our setting.
2 LEARNING CLUSTERING ALGORIHTS
The problem we study is as follows. Let X' be data domain. A clustering instance consists of a point set S = {f1,..., ] C X' and an (unknown) target clustering y (CI...., Ct). where the sets Cj..... Cs partition S' into & clusters. Linkage-basse based clustering algorithms output a hierarchical clustering of the input data, represented by a cluster tree. We measure the agreement of cluster tree T with the target clustering y = (Ci,.... , C*)) in terms of the Hamming distance between )' and the closest pruning of T into k clusters (i.e., h: disjoint subtrees that contain all the leaves of T). More formally, we define the loss {(T.)) minn,,....""',, min [i] Σ |C; \ Pa.l, where A \ B denotes set difference, the first minimum is over all prunings Pı..... ...... , Ps of the cluster tree T, and the second minimum is over all permutations of the is cluster indices. This formulation allows us to handle the case where each clustering task has a different number of clusters, and where the desired number might not be known in advance. Our analysis applies to any loss function E measuring the quality of the output cluster tree T, but we focus on the Hamming distance for simplicity. Given a distribution D over clustering instances (i.e.. point sets together with target clusterings), our goal is to find the algorithm A from a family A with the lowest expected loss for an instance sampled from D. As training data, we assume that we are given an i.i.d. sample of clustering instances annotated with their target clusterings drawn from the application distribution D.
We study linkage-basee based clustering algorithms. These algorithms construct a hierarchical clustering of a point set by starting with each point belonging to a cluster of its own and then they repeatedly merge the closest pair of clusters until only one remains. There are two distinct notions of distance at play in linkage-based algorithms: first, the notion of distance between pairs of points (e.g., Euclidean distance between feature vectors, edit distance between strings, or the Jaccard distance between sets). Second, these algorithms must define a distance function between clusters, which we refer to as merge function to avoid confusion. merge function 1) defines the distance between a pair of clusters A, B C X' in terms of the pairwise distances given by a metric d between their points. For example, single linkage uses the merge function Dmnnn ( (A, d; min diaa, b) and complete linkage uses the merge function Dmax (A, B; d) maxac B ((a.b).
Our parameterized family of unnage-based clustering algorithms allows us to vary both the metric used to measure distances between points, as well as the merge function used to measure distances between clusters. To vary the metric, we suppose we have access to L metrics di...., di defined on our data universe X. and our goal is to find the best convex combination of those metrics. That is, for any parameter vector 3 E A = { E [0, 11/ Σ. B, = 1}. we define a metric de( x') = Σ, 3, d2(x, x²). This definition is suitable across a wide range of applications, since it allows to learn the best combination of given set of metries for the application at hand. Similarly, for varying the merge function, we suppose we have L' merge functions D,..... Drr. For any parameter a E AL', define the merge function (A, B;d) Σ; or (A, B;d). For each pair of parameters B E f. and a A obtain different clustering algorithm (i.e., one that repeatedly merges the pair of clusters minimizing Da (:s dæ)). Pseudocode for this method is given in Algorithm [ In the pseudocode, clusters are represented by binary trees with leaves corresponding to the points belonging to that cluster. For any clustering instance S C X, we let (S)) denote the cluster tree output by Algorithm| when run with parameter vectors a and B
3

---

Algorithm Linkage Clustering
Input: Metrics di....,, du, merge functions Di...., Dr' points Ti,,... fi,...,,dy In X, parameters a and (.
1. Let = [Ieaf( [xa)( be the initial set of nodes (one leaf per point).
2. While M M>>1
(a) Let B be the clusters in N minimizing (A(A, B; d.)).
(b) Remove clusters A and B from N and add Node(A, B) to
3. Return the cluster tree (the only element of N).
First, we provide sample complexity results that hold for any collection of metrics di,...,d dr and any collection of merge functions Di,..., Dr, Dr, that belong the following family:
Definition 1. A merge function D is 2-point-based if for any pair of clusters A, B C X' and any metric d. there exists pair of points (a, b) E A x B such that D(A, B; d) = d(a, 6). Moreover, the pair of points defining the merge distance the ordering of pairwise distances. More formally, if d and d' are two metrics s.t. for all a, a' e A
must depend only and b, b' E B, we have d(a. b) S d(a', b*) if and only if d' (a. b) I d' (a',, b'), then D(A, B; d) = d(a, b) implies that D(A, B²d") d' ().
For example. both single and complete linkage are 2-point-basee merge functions, since they output the distance between the closest or farthest pair of points, respectively.
Theorem 1.
Fix any metrics d1....,dı .d. 2-point- -ased merge Di..... Dr', and distribution D over clustering instances with at most n points. For any parameters E >> O and 8 > 0. let (11.3)).....
be an i.idd.
Ô (L'+1)² clustering instances with target clusterings drawn from D. Then with probability at least 1 ó over the draw of the sample, we have
sample of = o (L' + L) log (L log (t)
N
sup (o (r.
el ((An,
- E (SS)D [(A(AA SE.
N
The key step in the proof of Theorem is to show that for any clustering instance with target clustering V. the function (ar, B3 + (("),,(S),,) 3) is piecewise constant with not too many pieces and where each piece is simple. Intuitively, this guarantees that for any collection of clustering instances, we cannot see too much variation in the loss of the algorithm on those instances as we vary over the parameter space. In Appendix [A] we use this fact to bound the empirical Rademacher complexity of the learning problem and obtain the uniform convergence guarantee in Theorem] [ In the remainder of this section, we prove the key structural property.
We let (ax, AL x AL denote a pair of parameter vectors for Algorithm 1. viewed as a vector in RL/+L, Our parameter space partition will be induced by the sign-pattern of .M quadratic functions.
Definition 2 (Sign-pattern Partition). The sign-patter partition of TR? induced M functions fi..... JM : R -> R is defined as follows: Let F R² + {+1) at be the function F(C) (sign(fi( ... sign(fM(()) Two points Ç. C' E Iº' belong to the same region in the partition iff F(C) = F(C'). Each region is of the form Z = {c E IR" (CC) = b]. for some sign-pattern vector E (+1)
We show that for any fixed metrics di....,dz dp and clustering instance S (.1...., hn} X, we can find sign- pattern partitioning of A induced by linear functions such that, on each region, the ordering over pairs of points in S induced by the metric dæ is constant. An important consequence of this result is that for each region 2 in this partitioning of AL, the following holds: For any 2-point-basee merge function and any pair of clusters A, B C S, there exists pair of points (a, b) E A x B such that D(A, B; dg) dg b) for all B E Z. In other words, restricted to / parameters belonging to Z, the same pair of points (a, b) defines the D-merge distance for the clusters A and B.
Lemma 1. Fix any metrics di,...,df and a clustering instance S C X. There exists a set H of O(() linear functiins mapping RR to E with the following property: if two metric parameters B.3' E AL belong to the same region in the sign-pattern partition induced by H. then the ordering over pairs of points in S given by dæ and d' are the same, That is, for all points a, b, a', b E S we have da(a.b) b) I da(a', ()) iff dæ (a. b) d (8).
Proof sketch. For any pair of points a, b E S, the distance da b) is linear function of the parameter B. Therefore, for any four points a, b, a', b S, we have that d b) S da(a', b') iff ha. y (B) < O. where ha, 8/ is the linear
4

---

do' Let H = (ha.ba'.' a, b, b, b' E S} be the collection of all such linear functions arising from any subset of points. On each region of the sign-pattern partition induced by H. all comparisons of pairwise distances in S are fixed, implying that the ordering over pairs of points in S is fixed. ]
function given by (a. d
Building on Lemma] 1 we now prove the main structural property of Algorithm | We argue that for any clustering
instance S C X. there is a partition induced by quadratic functions of A x A.. C IR= over and /3 into regions such that on each region, the ordering over all pairs of clusters according to the merge distance (=::::: dg) is fixed. This implies that for all (a. (3) in one region of the partition, the output of Algorithm I when run on S is constant, since the algorithm output only depends on the ordering over pairs of clusters in S given by Dalt,:;
Lemma 2. Fix any metrics di....,dı, any E-point-based merge functions Di...., Du. and clustering instance S C X. There exists a set Q of ((S))*1)) quadratic functions defined on R so that if parameters (ac, (3) and (o', belong the same region of the sign-pattern partition induced by Q, then the ordering over pairs of clusters in S given by Dalis-; dg)) and Dr (.....d is the same. That is, for all clusters A, B, AL, B' C S, we have that DA(A, B3dg) < (A,(A,, B'; dd) ifs Der A, B; dæy S Dov(A', B'; ).y).
Proof sketch. Let H be the linear functions constructed in Lemma 1 and fix any region 2 in the sign-pattern partition induced by H. For any i E [4]], since the merge function D; is E-point-based and the ordering over pairs of points according to da((s-) .) in the region Z is fixed, for any clusters A, B, A', B' C S we can find points ag, bi, ag bj da(a; b.) and Di(A', B'; dg) dæ(a 8)) for all [3 E R. Therefore, expanding the
such that (A, B; dg)
definition of Da. we have that Da (A, B; dg) S Da (A', B': dg) iff A. (., 33 S 0, where 9A,B.A' .B' (a, (3) = Σ.E, (,,5 b,) - da B)). Observe that the coefficients of each quadratic function depend only on 4L'
points in S, so there are only ((())47) possible quadratics of this from collected across all regions 2 in the sign-patter partition induced by H and all subsets of 4 clusters. Together with H. this set of quadratic functions partitions the joint parameter space into regions where the ordering over all pairs of clusters is fixed.
A consequence of Lemma 2 is that for any clustering instance S with target clustering V the function (a, 3) H (SA is piecewise constant, where the constant partitioning is the sign-patten partition induced by ((S)
quadratic functions. The proof of Theorem T now follows from using this fact to bound the empirical Rademacher complexity of the learning problem.
The above analysis can be extended to handle several more general settings. First, we can accommodate many specific merge functions that are not included in the 2-point-basee family, at the cost of increasing the number of quadratic functions
Extensions.
Q needed in Lemma 2 For example, if one of the merge functions is average linkage, Davg( (A, B; d) = TAI- B LaEA,E d( b), then Q will be exponential in the dataset size n. Fortunately, our sample
complexity analysis depends only on log( 2). this still leads to non-trivial sample complexity guarantees (though the computational algorithm selection problem becomes harder). We can also extend the analysis to more intricate methods for combining the metrics and merge functions. For example, our analysis applies to polynomial combinations of metrics and merges at the cost of increasing the complexity of the functions defining the piecewise constant partition.
3 EFFICIENT ALGORITHM SELECTION
In this section we provide efficient algorithms for learning low-loss clustering algorithms and metries for application- specific distributions 'D defined over clustering instances. We begin by focusing on the special case where we have a single metric and our goal to learn the best combination of two merge functions (i.e., L. = and L/ = 2). This special case is already algorithmically interesting. Next, we show how to apply similar techniques to the case of learning the best combination of two metrics when using the complete linkage merge function (i.c., L = 2 and L' = 1). Finally, we discuss how to generalize our techniques to other cases.
Learning the Merge Function. We will use the following simplified notation for mixing two base merge functions Do B: d) and Di (A, B; d)) for each parameter a E [0, 1], let Da B; d) = (1 - Do (A, B; d) + a aD (A, B; d) denote the convex combination with weight (1 - a) on Do and weight a on Dj. We let Amerge (S: Do, D1) denote merge
the cluster tree produced by the algorithm with parameter a, and Amerge (Do. D2) = {A (: Do D1) a E [0, 1]} denote the parameterized algorithm family.
5

---

00 o
a [0.1]
o a e [0.1]
K]]
o l
E (1.
X]
(
Figure I: An example of the execution tree of Amerge (Dmin; Dmax) for clustering instance with 4 points. The nested rectangles show the clustering at each node.
Our goal is to design efficient procedures for finding the algorithm from Amerge (Do. D2) (and more general families)
that has the lowest average loss on sample of labeled clustering instances (1), (Sx, VN) where ) (c k. C((O) is the target clustering for instance S,. Recall that the loss function ((T, computes the Hamming
distance between the target clustering )/ and the closest pruning of the cluster tree T. Formally, our goal is to solve the following optimization problem: argmin NV Σ.= [(Ar (Sr; D1).
The key challenge is that, for fixed clustering instance S we can partition the parameter space [0, 1] into finitely many intervals such that for each interval I, the cluster tree output by the algorithm A (S; Do. D2) is the same for every parameter in a E I. It follows that the loss function is a piecewise constant function of the algorithm parameter. Therefore, the optimization problem is non-convex and the loss derivative is zero wherever it is defined, rendering gradient descent and similar algorithms ineffective.
We solve the optimization problem by explicitly computing the piecewise constant loss function for each instance S.. That is, for instance i we find a collection of discontinuity locations 0 (+)
C, = 1 and values (6) ...., UMM e I so that for each j E [Mr]]. running the algorithm on instance St with a parameter in (5- C3 has loss equal vj Given this representation of the loss function for each of the N instances, finding the parameter with minimal average loss can be done in O(M log (M)) time, where M E, M, is the total number of discontinuities from all N loss functions. The bulk of the computational cost is incurred by computing the piecewise constant loss functions, which we focus on for the rest of the section.
c
(s)
We exploit a more powerful structural property of the algorithm family to compute the piecewise constant losses: for clustering instance S and any length f, the sequence of first merges performed by the algorithm a piecewise constant function of the parameter (our sample complexity results only used that the final tree is piecewise constant). For length = O, the partition is a single region containing all parameters in [0, 1]. since every algorithm trivially starts with the empty sequence of merges. For each length > O, the piecewise constant partition for the first t merges is a refinement of the partition for - 1 merges. We can represent this sequence of partitions using a partition tree, where each node in the tree is labeled by interval, the nodes at depth describe the partition of [0. 1] after t merges, and edges represent subset relationships. This tree represents all possible execution paths for the algorithm family when run on the instance S as we vary the algorithm parameter. In particular, each path from the root node to leaf corresponds to one possible sequence of merges. We therefore call this tree the execution tree of the algorithm family when run on S. Figure [[] shows an example execution tree for the family Amergs (Dmin D Dmax). ). To find the piecewise constant loss function for clustering instance S, it is sufficient to enumerate the leaves of the execution tree and compute the corresponding losses. The following result, proved in Appendix B, shows that the execution tree for Amerye (Do, D1) is well defined.
Lemma 3. For any merge functions Do and D2 and any clustering instance S, the execution tree for Amerge (Do, D1) when run on S is well defined. That is, there exists a partition tree s.t. for any node v at depth i, the same sequence of first t merges is performed by Amerge for all a in node v's interval.
The fundamental operation required to perform a depth-fire first traversal of the execution tree is finding a node's ' children.
That is, given a node, its parameter interval [ato, ani) and the set of clusters at that node C1, Cm. find all possible merges that will be chosen by the algorithm for a E [Mt, Om)) We know that for each pair of merges (C,, C2) and (C%, C)), there is single critical parameter value where the algorithm switches from preferring to merge (C,, Cj) to (C,, C)). A direct algorithm that runs in Omm)) time for finding the children of node in the execution tree is to compute all Omm²) critical parameter values and test which pair of clusters will be merged on each interval between

---

D, dissance
0. distance
G
Cr.bs
G,6
G
92
01
Cg wins
G wins
6.99 wina dx
(a) First iteration
(b) Final output
Figure 2: Depiction of Algorithm 2 when given three clusters, C₁, C2 and C3. Each line shows the D, distance between one pair of clusters as a function of the parameter a. On the first iteration, aggoritm@@detemminn that clusters C2 and C3 are the closest for the parameter a = Oto. calculates the critical parameter values C12 and C13, and advances a to C13. Repeating the process partitions of [ctas ami) into merge-constant regions.
consecutive critical parameters. We provide a more efficient algorithm that runs in time O(m² where M S m² is the number of children of the node.
Fix any node in the execution tree. Given the node's parameter interval = [ow, Qn)) and the set of clusters Ci,..., C. resulting from that node's 's merge sequence, we a sweep-line algorithm to determine all possible next merges and the corresponding parameter intervals. First, we calculate the merge for a = a% by enumeration in (mm²) time, Suppose clusters C, and C are the optimal merge for a. We then determine the largest value a' for which C2 and Cj are still merged by solving the linear equation Da Cÿ) = Da(Ci, (CR, Ci) for all other pairs of clusters C2 and Ct keeping track of the minimal solution larger than a. Since there are only (mm) alternative pairs of clusters, this takes O (m²) time. Denote the minimal solution larger than by E I. We are guaranteed that A will merge clusters C, and Cj for all a' E [a, c). We repeat this procedure starting from a = c to determine the next merge and corresponding interval, and on, sweeping through the parameter space until
Otii- Algorithm 2 in Appendix B provides pseudocode for this approach and Figure 2 shows an example. Our next result bounds the running time of this procedure.
Lemma 4. Let Ci,..., Cm be collection of clusters, Do and D1 be any pair of merge functions, and [ato: Ois) be a subset of the parameter space. If there are M distinct cluster pairs Ci, Cj that minimize Do (Ci, C₁) for values of a [a and), then the running time of Algorithm 2 is O(Mm²K) K). where K is the cost of evaluating the merge functions Do and Dj.
With this, algorithm for computing the piecewise constant loss function for instance S performs a depth- first traversal of the leaves of the execution tree for Amerge (Do, D1). using Algorithm 2 to determine the children of each node. When we reach leaf in the depth-first traversal, we have both the corresponding parameter interval I C [0, 1]. as well as the cluster tree T such that An merge (S) = ''' for all a E I. We then evaluate the loss E(T, J) to get one piece of the piecewise constant loss function. Detailed pscudocode for this approach is given in Algorithm in Appendix
Theorem 2.
Let 5 = (x1,.... Fn. be a clustering instance and Do and D2 be any two merge functions. Suppose that the execution tree of Amerge (Do, D1) on S has E edges. Then the total running time of Algorithm 3 is O(En2 K), where K is the cost of evaluating Do and D once.
We can express the running time of Algorithm 3 in terms of the number of discontinuities of the function or + Amerge (S). There is one leaf of the execution tree for each constant interval of this function, and the path from the root of the execution tree to that leaf is of length enumerating the execution tree to obtain the piecewise constant loss function for a given instance S spends O K'
1. Therefore. the cost associated with that path is most O(Kn3) kn)) and
time for each constant interval of a + A (S). In contrast, the combinatorial approach of Balcan et al. 2017 requires that we run a-linkage once for every interval in their partition of [0, 1]. which always contains O(n²) intervals (i.e., it is refinement of the piecewise constant partition). Since each run of a-Linkage costs O(Kn² 2 log n)) time, this leads to a running time of O OKKn" l).. The key advantage of our approach stems from the fact that the number of discontinuities of the function a + Atherge (S) is often several orders of magnitude smaller than Onn)).
Learning the Metric. Next we present efficient algorithms for computing the piecewise constant loss function for single clustering instance when interpolating between two base metrics and using complete linkage. For a pair of fixed base metrics do and d, and any parameter value 3 E [o, 1], define dz(a, b) = (1 3) (a, b) + Bd, (a, b). Let Amerric (S; do. di) denote the output of running complete linkage with the metric ds, and Ametric (do, dj) denote the family of all such algorithms. We prove that for this algorithm family, the execution tree is well defined and provide an
7

---

efficient algorithm for finding the children of each node in the execution tree, allowing us to use depth-first traversal to find the piecewise constant loss function for any clustering instance S.
Lemma 5. For any metrics do and di and any clustering instance S. the execution tree for the family America (do, di when run on S is well defined. That is, there exists a partition tree s.t. for any node v at depth i, the same sequence of first 1 merges is performed by Aggenic for all in node v's interval.
Next, we provide an efficient procedure for determining the children of a node v in the execution tree of Americ (do, d Given the node's parameter interval / = [Sho, Bui) and the set of clusters Ct...., C. resulting from that node's 's sequence of merges, we again use a sweep-line procedure to find the possible next merges and the corresponding parameter intervals. First, we determine the pair of clusters that will be merged by Ageti for B = Bio by enumerating all pairs of clusters. Suppose the winning pair is C2 and Cj and let æ E C2 and x' E C3 be the farthest pair of points between the two clusters. Next, we find the largest value of 3" for which we will still merge the clusters C2 and Cj. To do this, we enumerate all other pairs of clusters Cg and C₁ and all pairs of points y E C2 and y' E C₁, and solve the linear equation d2. x²) ) = d (3. v/),, keeping track of the minimal solution larger than 3. Denote the minimal solution larger than I by c. We are guaranteed that for all 3' [8. c). the pair of clusters merged will be C₁ and Cj. Then we repeat the process with / = to find the next merge and corresponding interval, and so on, until 8 2 Bui Pseudocode for this procedure is given Algorithm D Appendix
B The following Lemma bounds the running time:
Lemma 6. Let Ci,..., Cm be a collection of clusters, do and di be any pair of metrics, and [Bt.: Bui) be a subset of the parameter space. If there are M distinct cluster pairs C2 Cj that complete linkage would merge when using the metric da for 3 E (m)), the running time of Algorithm is O(Mm)).
Our algorithm for computing the piecewise constant loss function for an instance S is almost identical for the case of the merge function: it performs a bepth-first traversal of the leaves of the execution tree for Ameuric (do, d1), using Algorithm to determine the children of each node. Detailed pseudocode for this approach is given in Algorithm in
Appendix B The following Theorem characterizes the overall running time of the algorithm.
Theorem 3. Let S = (II,...,
} be a clustering instance and de and dj be any two merge functions, Suppose that the execution tree of Americc (do, d on S has E edges. Then the total running time of Algorithm 5 is O(En)). ).
Extension to general algorithm families, In this section we introduced efficient algorithm selection procedures for two special cases where the algorithm family has single parameter. Working with a one-dimensional parameter space allowed us to compute partitions of the parameter space using efficient sweep-line procedures. The key additional challenge when working with higher-dimensional parameter spaces is that the partition of the parameter space given by each level of the execution tree becomes more complicated, defined by the sign-pattern partition induced by a collection of quadratic functions. Efficient execution-tree based algorithm selection procedures for our more general algorithm family will require an analog of the sweep-ling line algorithms described above that efficiently compute the children of a node in the execution tree, together with a minimal number of quadratic functions describing the partition.
It may also be promising to explore combinatorial-style algorithm selection procedures. As a consequence of Lemma for any collection of N clustering instances with at most n points, we can find ONNn" quadratic functions whose sign-pattern partition divides the parameter space into polynomially many regions where the algorithm output is constant every instance. It follows that we can find an empirically optimal parameter in polynomial time if we are able to identify a parameter from each region of the sign-pan aggn-pattern partition polynomial time. For example, when the parameter space is IR? for each vertex of each region in the sign-patten partition, there is pair of quadratic functions such that (v( = qz (v) = O. By solving this equation for all pairs of quadratic functions, we are able to find a parameter from each region. An interesting future direction is to develop efficient analogs for higher-dimension parameter spaces.
4 EXPERIMENTS
In this section we evaluate the performance of our learning procedures when finding algorithms for application-specffie clustering distributions. Our experiments demonstrate that the best algorithm for different applications varies greatly, have large gains in cluster quality using a mixture of base merge functions metrics.
and that in many cases
Experimental setup. In each experiment we define a distribution D over clustering tasks. For each clustering instance, the loss of the cluster tree output by a clustering algorithm is measured in terms of the loss ( J), which computes the Hamming distance between the target clustering and the closest pruning of the cluster tree. We draw N sample
8

---

clustering tasks from the given distribution and use the algorithms developed in Section to exactly compute the average empirical loss for every algorithm one algorithm family. The theoretical results from Section Jensure that these plots generalize to new samples from the same distribution, so our focus is on demonstrating empirical improvements in clustering loss obtained by learning the merge function or metric.
Clustering distributions. Most of our clustering distributions are generated from classification datasets by sampling a subset of the dataset and using the class labels as the target clustering. We briefly describe our instance distributions together with the metrics used for each below. Complete details for the distributions can be found in Appendix C
MNIST Subsets. The MNIST dataset (LeCun et al. 1998) contains images of hand-written digits from 0 to 9. We generate a random clustering instance from this data by choosing k 5 random digits and sampling 200 images from each digit, giving a total of n = 1000 images. We measure distance between any pairs of images using the Euclidean distance between their pixel intensities.
CIFAR-10 Subsets. We similarly generate clustering instances from the CIFAR-I0 dataset (Krizhevsky 2009). To generate an instance, select & = 5 classes random and then sample 50 images from each class, leading to total of n = 250 images. We measure distances between examples using the cosine distance between feature embedding extracted from a pre-trained Google inception network (Szegedy et al. 2015).
Omniglot Subsets. The Omniglot dataset (Lkee et al. 2015 contains written characters from 50 alphabets, with a total of 1623 different characters. To generate clustering instance from the omniglot data, we choose one of the alphabets at random, we sample & from (5..... . .00 uniformly at random, choose k random characters from the alphabet, and include all 20 examples of those characters in the clustering instance. We use two metrics for the omniglot data: first, cosine distances between neural network feature embeddings of the character images from a simplified version of AlexNet (Krizhevsky et al., 2012). Second, each character is also described by "stroke", which is sequence of coordinates (Z,, 3/1) f= describing the trajectory of the pen when writing the character. We hand-design a metric based the stroke data: the distance between pair of characters is the average distance from a point either stroke to its nearest neighbor on the other stroke. A formal definition is given in the appendix.
Places2 Subsets. The Places2 dataset consists of images of 365 different place categories, including "volcano", "gift shop". and "farm" (Zhou et al. 2017). To generate a clustering instance from the places data, we choose k randomly from (5,.... 10). choose k random place categories, and then select 20 random examples from each chosen category. We use two metries for this data distribution. First, we use cosine distances between feature embeddings generated by a VGG16 network (Simonyan and Zisserman 2013) pre- pre-trained on ImageNet (Deng et al., 2009). Second, we compute color histograms in HSV space for each image and use the cosine distance between the histograms.
Places2 Diverse Subsets. We also construct an instance distribution from a subset of the Places2 classes which have diverse color histograms. We expect the color histogram metric to perform better this distribution. To generate clustering instance, we pick k = 4 classes from aquarium, discotheque, highway, iceberg, kitchen, lawn, stage-indoor, underwater ocean deep, volcano, and water tower. We include 50 randomly sampled images from each chosen class, leading to a total of n = 200 points per instance.
Synthetic Rings and Disks. We consider two dimensional synthetic distribution where each clustering instance has 4 clusters, where two are ring-shaped and two are disk-shaped. To generate each instance we sample 100 points uniformly at random from each ring or disk. The two rings have radiuses 0.4 and 0.8, respectively. and are both centered at the origin. The two disks have radius 0.4 and are centered at (1.5, 0.4) and (1.5, -0.4), respectively. For this data, we measure distances between points in terms of the Euclidean distance between them.
Results. Learning the Merge Function. Figure Jshows the average loss when interpolating between single and complete linkage as well as between average and complete linkage for each of the clustering instance distributions described above. For each value of the parameter a E 0. 1]. report the average loss over N = 1000 i.i.d. instances drawn from the corresponding distribution. We see that the optimal parameters vary across different clustering instances. For example, when interpolating between single and complete linkage. the optimal parameters are a = 0.874 for MNIST, a = 0.98 for CIFAR-10, a 0.179 for Rings and Disks, and a = 0.931 for Omniglot. Moreover, using the parameter that optimal for one distribution on another would lead to significantly worse clustering performance. Next, we also see that for different distributions, it is possible to achieve non-trivial improvements over single, complete, and average linkage by interpolating between them. For example, on the Rings and Disks distribution we see an improvement of almost 0.2 error, meaning that an additional 20% of the data is correctly clustered.
9

---

0.8
0.30
0.8
Hamming CodE
0.7
Hammin Coet
6.7
Nomming CoST
0.25
0.7
Hamming
0.15
0.0
0.30
SC
0.05
0.5
3.00
0.25
0.50
0.75
1.00
0.00
0.25
0.50
0.75
1.00
0.00
0.25
0..50
0.75
1.00
0.00
0.25
0.50
0.75
1.00
(a) MNIST
(b) CIFAR-10
(c) Rings and Disks
(d) Omniglot
Figure 3: Empirical loss for interpolating between single and complete linkage ('SC' in the legend) well as between average and complete linkage ('AC' in the legend) over 1000 sampled clustering instances.
Learning the Metric. Next consider learning the best metric for the Omniglot, Places2, and Places2 Diverse instance distributions. Each of these datasets is equipped with one hand-designed metric and one metric based on neural-network embeddings. The parameter 3 0 corresponds the hand-designed metric, while Figure S shows the empirical loss for each parameter / averaged over N = 4000 samples for each distribution. On all three distributions the neural network embedding performs better than the hand-designed metric, but we can achieve non-trivial performance improvements by mixing the two metrics. On Omniglot, the optimal parameter is at B = 0.514 which improves the Hamming error by 0.091, meaning that we correctly cluster nearly 10% more of the data. For the Places2 distribution see an improvement of approximately 1% with the optimal parameter being 3 = 0.88, while for the Places2 Diverse distribution improvement is approximately 3.4% with optimal 3 being 0.87.
corresponds to the embedding.
0.50
0.65
0.50
0.55
Homming
0.45
0.30
0.25
0.30
0.75
1.00
0.25
0.75
1.00
0.50
3.00
(a) Omniglot
(b) Places2
(c) Places2 Diverse
Figure 4: Empirical loss interpolating between two distance metrics on Omniglot, Places2, and Places2 distributions. each plot, S 0 corresponds to the hand-crafted metric and 3 corresponds to the neural network embedding.
Number of Discontinuities. The efficiency of our algorithm selection procedures stems from the fact that their running time scales with the true number of discontinuities in each loss function, rather than a worst-case upper bound. Of all the experiments we ran, interpolating between single interpolating between single and complete linkage for MNIST had the most discontinuities per loss function with an average of 362.6 discontinuities per function. Given that these instances have = 1000 points, this leads to speedup of roughly n x./362.6 6 = 2.76 x 10 over the combinatorial algorithm that solves for all (n²)) critical points and runs the clustering algorithm once for each. Table Appendix shows the average number of discontinuities per loss function for all of the above experiments.
5 CONCLUSION
In this work study both the sample and algorithmic complexity of learning Linkage-basee clustering algorithms with low loss for specific application domains. We give strong bounds on the number of sample instances required from an application domain in order to find approximately optimal algorithm from rich family of algorithms that allows us to vary both the metric and merge function used by the algorithm. We complement our sample complexity results with efficient algorithms for finding empirically optimal algorithms for sample of instances. Finally, carry out experiments on both real-world and synthetic clustering domains demonstrating that our procedures can often find algorithms that significantly outperform standard linkage-bascd clustering algorithms. An important future direction for learning linkage based clustering algorithms is the design of efficient algorithm selection procedures for higher dimensional parameter spaces.
10

---

ACKNOWLEDGEMENTS
This work was supported in part by NSF grants CCF-1535967, I1S-1618714, IIS- 190-199,,,,, CCF-1910321, SES-1119453, an Amazon Research Award, a Bloomberg Research Grant, a Microsoft Research Faculty Fellowship, and by the generosity of Eric and Wendy Schmidt by recommendation of the Schmidt Futures program.
REFERENCES
Pranjal Awasthi, Avrim Blum, and Or Sheffet. Center-based clustering under perturbation stability. In Information Processing Letters, 2012.
Pranjal Awasthi, Maria-Florina Balcan, and Konstantin Voevodski. Local algorithms for interactive clustering. In JCML, 2014.
Maria-Florina Balcan and Yingyu Liang. Clustering under perturbation resilience. In SIAM Journal Computing, 2016.
Maria-Florina Balcan, Vaishnavh Nagarajan, Ellen Vitercik, and Colin White. Learning-theoretic foundations of algorithm configuration for combinatorial partitioning problems. Proceedings of the Conference Learning Theory (COLT), 2017.
Maria-Floriin Balcan, Travis Dick, Tuomas Sandholm, and Ellen Vitercik. Learning to branch. In ICML, 2018a.
Maria-Florina Balcan, Travis Dick, and Colin White. Data-driven clustering via parameterized lloyd's families. In NewrIPS, 2018b.
Maria-Florina Balcan, Dan DeBlasio, Travis Dick, Carl Kingsford, Tuomas Sandholm, and Ellen Vitercik. How much data is sufficient to learn high-performing algorithms? arXiv preprint arXiv: 1r0ivv190.002800 2019.
Peter L Bartlett and Shahar Mendelson. Rademacher and gaussian complexities: Risk bounds and structural results. Journal of Machine Learning Research, 3(Nov):443-482. 2002.
R. C. Buck. Partition of space. Amer. Math. Monthly, 50:541-544 1943. ISSN 0002-9890.
Deng, W. Dong, R. Socher, L..J. Li, K. Li, and Fei-Fei. ImageNet: A Large-Scale Hierarchical Image Database, CVPR, 2009.
Anna Grosswendt and Heiko Roeglin. Improved analysis of complete linkage clustering. In European Symposium of Algorithms, 2015.
Rishi Gupta and Tim Roughgarden. A PAC approach to application-specific algorithm selection. SIAM Journal on Computing, 46(3):992 1017, 2017.
Alex Krizhevsky. Learning multiple layers of features from tiny images. In Technical Report, 2009.
Alex Krizhevsky, Ilya Sutskever, and Geoffrey E. Hinton. Imagenet classification with deep convolutional neural networks. In NeurlPS, 2012.
Brenden M. Lake, Ruslan Salakhutdinov, and Joshua B. Tenenbaum. Human-level concept learning through probabilistic program induction. Science, 350(6266):1332 1338, 2015. doi: 10.1 wttp://iienc..aa30055.5
Y. LeCun, I. Bottou, Y. Bengio, and P. Haffner. Gradient-based learning applied document recognition. In Proceedings of the IEEE, 1998.
Pascal Massart. Some applications of concentration inequalities to statistics. 9(2):245-303, 2000.
Mehreen Saeed, Onaiza Maqbool, Haroon Atique Babri, Syed Zahoor Hassan, and S. Mansoor Sarwar. Software clustering techniques and the use of combined algorithm. In European Conference Software Maintenance and Reengineering, 2003.
S. Shalev-Shwartz and S. Ben-David. Understanding machine learning: From theory to algorithms. Cambridge University Press, 2014.
11

---

Karen Simonyan and Andrew Zisserman. Very deep convolutional networks for large-scale image recognition. ICLR, 2015.
Christian Szegedy, Wei Liu, Yangqing Jia, Pierre Sermanet, Scott Reed, Dragomir Anguelov, Dumitru Erhan, Vincent Vanhoucke, and Andrew Rabinovich. Going deeper with convolutions. In CVPR, 2015.
James R. White, Saket Navlakha, Niranjan Nagarajan, Mohammad- Reza Ghodsi, Carl Kingsford, and Mihai Pop. Align- ment and clustering of phylogenetic markers implications for microbial diversity studies. In BCM Bioinformatics, 2010.
Bolei Zhou, Agata Lapedriza, Aditya Khosla, Aude Oliva, and Antonio Torralba. Places: A 10 million image database for scene recognition. /EEE Transactions on Pattern Analysis and Machine Intelligence, 2017.
A APPENDIX FOR LEARNING CLUSTERING ALGORITTMM
We begin by providing complete proofs for the piecewise structural Lemmas from the main body.
Lemma 1. Fix any metrics di,...,dy di and a clustering instance S C X. There exists a set H. of O(S((t) linear functions mapping R to R with the following property: if two metric parameters B, E Ar, belong to the same region in the sign-pattern partition induced by H. then the ordering over pairs of points in S given by dæ and dæ are the same. That is, for all points a, b, d' E S we have dz(a, b) S da(a', b') iff da (a. b) S (a
Proof. Let S be any clustering instance and fix points a, b, a.' b E S. For any parameter B AL, by definition of dæ. we have that
1 B,d b) S Σ Bid(d''))) = Σ
dz(a, S dz(d',8)
=
Σ 2m
Define the linear function ha. 8/ (B)
di B')). Then we have that dø(a, b) S do(a', 8) if ha, (B) S. O and dø(a, b) > dø(a', "ald',,o if b. v (3) 0.
(. 3
Let H ( ba,b,'' a', 6' E S} be the collection of all such linear functions collected over all possible subsets of 4 points in S. Now suppose that 33 and S belong to the same region in the sign-pattemn partition induced by H. For any points a, b, a', D' E S. we are guaranteed that sigu(ha.b,r (ha.b,a', (3)) = sign(ha,b,a' (B'),, which by the above arguments imply that ( b) S da(a', b') iff de (a, b) S dg (a', U)), as required.
Lemma 2. Fix any metrics di,..., dr, any 2-point-basee merge functions Di...., Dr. and clustering instance S SC X. There exists a set Q of (( quadratic functions defined on BL'+L so that if parameters (a,, 3) and 33") belong the same region of the sign-pattern partition induced by Q, then the ordering over pairs of clusters in S given by (a(..1d and D& (..-;,; dgy) is the same. That is. for all clusters A, B, A, B' C. S, we have that D. (A d3) < Da A'A.B". B'; dg) iff D B: dg) < (A', B¹; d.z).
Proof. From Lemmal [ we know we can find set H of O((S linear functions defined on RRd that induce sign- pattern partition of the |9 parameter space A C. R2 into regions where the ordering over pairs of points according to the dg distance is constant.
Now let Z C Ar be any region of the sign-patter partition of A induced by H. From Lemma I we know that for all parameters 3 Z, the ordering over pairs of points in S according to d3 is fixed. For any 2-point-basse merge function, the pair of points used to measure the distance between a pair of clusters depends only on the ordering of pairs of points according distance. Therefore, since DI...., Dr are all 2-point-based, of clusters (A, B) and each merge function index i E [T'], there exists a pair of points (as, by) E A x B such that (A, B; dg)) = da (a,, bi) for all /3 e Z. In other words, all of the merge functions measure distances between A and B using fixed pair of points for all values of the metric parameter ,3 in the region Z. Similarly, let A', B C S be any other pair of clusters and (a/, 6/) E A' x B' be the pairs of points defining (A B3: dg) for each [L'. Then for
know that for any pair
12

---

all B E 2, we have that
(A B;da) S (a(AABBidd)
=
Σ
Σ
a Di B;dg)
im1
i=l
0:
(d, -
04
(yd
j=l
j=1
L
ag (d, b,) - s 0.
Now define the quadratic function
L' ΣΣ i=j==1
B = 0g
(1)
For all B E Z, we are guaranteed that (A B;da) S (A', B'; :33) if and only if QA,B,A' B (), < O. Notice that the coefficients of A', only depend on 4L' points in S, which implies that if we collect these quadratic functions over all quadruples of clusters A, B, A', B¹ C S, we will only obtain O(1S)4E)) different quadratic functions. These O((S) L functions induce sign-pattern partition of A Z for which the desired conclusion holds. Next, observe that the coefficients the quadratic functions defined above do not depend on the region 2 we started with. It follows that the same set of O((5)42)) quadratic functions partition any other region Z' in the sign-patters partition induced by H so that the claim holds on A Z'.
Now let Q contain the linear functions in H. (viewed as quadratic functions over R R.''+. by placing zero coefficient all quadratic terms and terms depending a), together with the ((IS) quadratic functions defined above. Then we have that ||] O[ + ) region of the
([S))t)). Now suppose that (a, and (a', belong to the same partition of Ar L C RL'+L induced by the quadratic functions Q. Since Q contains H. this implies that B and 3' belong to the same region Z in the sign-pattern partition induced by H. Moreover, since @ contains all the quadratic functions defined in (T) it follows that D& (A, B,dg)= S Da d') if and only if D& (A, B; d
D& (A', B'; dg.), ), as required.
Our proof of Theorem [ depends crucially the number of regions in the sign-pattern partition induced by collection of functions. Based on the work of Buck (1943), we know that when the functions fi....; fM are linear, then the number of regions is at most )3 substantial improvement over the naive bound of 2 We can also leverage this result to bound the number of regions by (3M)²² " tp when the functions are quadratic by viewing each quadratic function linear function
(p² + p) dimeenionall space. The following result summarizes these facts.
Lemma 7. Let T be the number of regions in the sign-pattem partition of Rp induced by fi,-... JM RP TR. The following statements hold.
1. If the functions are linear, ie., f((C) = w. Ç + for w. E ERP and r E R, then T S (3MY.
If the functions are quadratic, i.e, f((C) = < STQ:S= + w. S for Qi E RPX,, w, E Rp and r, E R, then
T & (3M)²+2
which shows that if H is collection of M hyperplanes in IR", then the number of connected components R² H is at most (.M)). To connect this to the pagn-pattenn partitioning induced by the collection of linear functions fi..... fMr. let H. be the set of M hyperplanes defined by {< E Rº fC(
Proof. The proof of the first statement follows from the work of Buck 1943)
0} for [M]. The connected components of IR" \ H correspond exactly to the sign-pattern partition of the functions fi...., J'ss, and by the result of Buck (1943). 3) it follows that the
number of regions the partition is at most (3M)². Equivalently, we know that [(F(C) < E T S (3M)², where
F(C)= = (sign(f((C)) sign,, (M))) is the sign-patters function. That is, F takes at most (3M y distinct values.
13

---

Next we use the first statement to prove the second statement. Let 4p R - R be the function that maps vector Ç to the vector containing all products of pairs of elements from Ç concatenated the beginning Ç:
( = (GiSI, (GiSIi...SSi ..... SaSi..... SaSa: S1.-..,Sa)) Sa).
Let (()) = - QTQ w < ++ be a quadratic function where Q E RRxx, RP, and E IR. Now let
(Q.1....., 9tds ..... 4dl :d...... Idd. Wi..... wa).
Then we have that (() v (c)) In other words, q is linear function of (C)) This guarantees that we find M linear functions ,y....,uu h, R +p + such that fz(S) - (x(((()) for all E [M]. Let BP*+P + {+1] be
the sign-pattern function for h1 h....., has Then we have
s (((()) | E Re*+ S (3M))²+p (F(C) | E R²H = (+(()) & [PP /
where the last inequality follows from the first statement for linear functions. It follows that the number of regions in the sign-pattern partition induced by M quadratic functions most (3M))'++.
With this, we are ready to prove Theorem 1
Theorem 1. Fix any metrics d1....,dy 2-point-basse based m Di...., Dr., and distribution D over clustering instances with most n points. For any parameters > 0 and 6 let (1),,))),....... (Sx (NN: be i.i.d.
sample of N = - ( (L' + L)) log (WSttyern log (1)) Ô ( clustering instances with target clusterings drawn from D. Then with probability at least 1 over the draw of the sample, we have
N
1
((Aa, Σ
- E [((Aa.(S)))))) Se.
sup (ax ()
N
(5.D)~
Proof of Theorem 7 Our goal is to provide a uniform convergence guarantee that ensures the sample loss of any pair of parameters (a. 33 is close to its expected cost on the underlying distribution. Towards that end, define the family of loss functions F = {fa.g: (S.3)) + (S)). algorithm parameters and maps each clustering instance S with target clustering ) to that algorithm's 's loss when run on ().)). We will bound the empirical Rademacher complexity of F to prove uniform convergence guarantees. Let S (1),, ..... D. The empirical Rademacher complexity of the class of functions F on the sample S is given by
(a. 3 A x Ar where the function fa.9 fixes
be a sample of clustering instances with target clusterings drawn from the distribution
N Σ
1 R(F S) = N
sup Ja.
where is vector of N independent Rademacher random variables.
From Lemma 2. know that
find collection of O(n quadratic functions for each clustering instance S so that the output of Algorithm when run on S; is constant on each region of the induced sign-pattern partition of the parameter space. Let Q be the collection of ONN 4L') quadratic functions collected across all N clustering instances S S1,..., SN- Whenever
parameter settings (ax, () and (a',8") belong to the same region in the sign-pattern partition induced by Q. we know that for all instance indices i, we have La a V1) = lo ar
V.). Applying the regions. This implies that we can find a collection of T parameter vectors (or,, BI),..., .,... ((T,, Br) (by taking one from each region in the partition) so that the following holds: for every (a. (3) E A Az. there exists j [T] such that for all clustering instances (S,, y1) in the sample S we have ba, = fa, ,, (S,, J.). With this, we can bound the empirical Rademacher complexity as follows:
second statement of Lemma 7 we know that this partition has most T (3) (1))) +()
N Σ
R(F S)
E
sup JA
Σ
E
sup ISJST
o.fa, (S (S..
N
Now, using the fact that the losses take values in [0, 1] and the supremum is over only T distinct elements, can apply Massart's Lemma (Massart 2000) to obtain R(F, S) O(ylog(T)/N)) Taking logs and simplifying our bound on T,
14

---

we have that log(T) 0(('+ (gg(N))),)))))))))))))))))) giving the following bound on the empirical Rademacher complexity of F:
R(F,S)= + 1)2 (
Next, from standard Rademacher complexity bounds (Bartlett and Mendelson 2002), we are guaranteed that with probability at least - 8 we have that
sup (A
1
Σ
N
(a,
E (8.3)/
(S. (a,
-0 R(F,S) + 1og(1/5)
N
N
i=1
(I) L) L)
log(1
+
N
N
(I' L) L log(Nn) log(1/6)
N
where the last equality follows from the fact that for any x, 2 0 we have vz + V S 2(x + y). Since the right hand side goes to zero N grows, remains to choose N sufficiently large that the right hand side is bounded by c.
Let A L' and B -L' + L) log(n) + log(1/5) so that the error bound is given by O (V A Alog(N)+B
N
We are guaranteed that V Alog(N)+B Se whenever N 2 2 (A log( N) + B). Using the fact that for a 2 and 2 0 N
have that x 2 4a (oo((a() + 2b implies that log (z) b (e.g., see Lemma A.2 in (Shalev-Shwartz Shwartz and Ben
David 2014)), follows that when N 4A log 24 + 28 O / log A + B)). we also have v A Blog(N)+B
Substituting and B and simplifying the expression completes the proof.
B APPENDIX FOR EFFICIENT ALGORITHM SELECTION
B.1 LEARNING THE MERGE FUNCTION
In this section we provide details for learning the best combination of two merge functions. We also give detailed pseudocode for sweepline algorithm for finding the children of node in the execution (see Algorithm and for the complete algorithm (see Algorithm 3
Algorit Find merges for Amerge Amar D1)
Input: Set of clusters Ci,..., Cm, merge functions Do. Dr, parameter interval [Otoy Ohi).
1. Let M = ( be the initially empty set of possible merges.
2. Let I 0 be the initially empty set of parameter intervals.
3. Let a =
4. While < Omi
(a) Let C;, Cj be the pair of clusters minimizing (1 a) Do(C,, C2) + Di
(b) For each k, e [m], let cu Ao/(A, A1), where A, (P, C2) (p Ci) for e (0,1).
(c) Let = min (cu caa > a) U (am)))
(d) Add merge (C2, Cÿ) to M and [a, c) I.
(c) Set a =
5. Return M and I.
For any merge functions Do and D and any clustering instance S, the execution tree for Amerge (Do, D1) when run on S is well defined. That is, there exists a partition tree s.t. for any node u at depth t, the same sequence of first merges is performed by Amerge for all a in node v's interval.
Lemma
15

---

Algorithm 3 Depth-first Enumeration of a-linkage Execution Tree
Input: Point set ,n. cluster distance functions d1 and d2.
1. Let r be the root node of the execution tree with r.. ((z1)..... (r,)) and r.I = [0.
2. Let be a stack of execution tree nodes, initially containing the root r.
3. Let T = 0 be the initially empty set of possible cluster trees.
4. Let Z = 0 be the initially empty set of intervals.
5. While the stack is not empty:
(a) Pop execution tree node off stack s.
(b) If e has a single cluster, add e.N to T and e.
(c) Otherwise, for each merge (C,, C2) and interval Te returned by Algorithm 2 run on e.V and e.T:
Let be new node with state given by e.N after merging C2 and Cj and c. le- ii. Push e onto the stack s.
6. Return T and I.
Proof. The proof is by induction on the depth t. The base case is for depth & = 0, in which case we can use a single node whose interval is [o, 1]. Since all algorithms in the family start with an empty-sequence of merges, this satisfies the execution tree property.
Now suppose that there is tree of depth with the execution tree property. If |S| - then we are finished, since the algorithms in Amerge (Do. D2) make exactly |S] 1 merges. Otherwise, consider any leaf node of the depth tree with parameter interval I,. It is sufficient to show that we can partition L, into subintervals such that for in each subinterval the next merge performed is constant. By the inductive hypothesis, we know that the first merges made by A are the same for all a E T,. After performing these merges, the algorithm will have arrived at some set of clusters C1 Cr...., C. with = |S] - f. For each pair of clusters C, and Cj, the distance (C,, C2) (1 a) Do C2) + a (C, C,) is a linear function of the parameter a. Therefore, for any clusters C; C₁ Ck. and C₁ the algorithm will prefer to merge C. and Cj over Cj and Cg for (possibly empty) sub-interval of L., corresponding where (C, C2) < Da (C, Ci). For any fixed pair of clusters C2 and Cj. taking the intersection of these intervals over all other pairs Cý and Cs guarantees that clusters C, and Cý will be merged exactly for parameter values in some subinterval of J,. For each merge with a non-empty parameter interval, we can introduce a child node of u labeled by that parameter interval. These children partition I, into intervals where the next merge is constant, required.
the values of E Lu
Lemma 4. Let Cı,..., Cm be collection of clusters, Do and Dj be any pair of merge functions, and (Oto: Ons) be a subset of the parameter space. If there are M distinct cluster pairs Ci Cj that minimize Da (Ci, C₁) for values of a [agns and) then the running time of Algorithm 2 is O(Mm² K), where K is the cost of evaluating the merge functions Do and Dj.
The loop in step 4 of Algorithm runs once for each possible merge, giving a total of M iterations. Each iteration finds the closest pair of clusters according to D., using (mm)) evaluations of the merge functions Dg and D Calculating the critical parameter value e involves solving O(m²) linear equations whose coefficients are determined by four evaluations of D and D,. It follows that the cost of each iteration is O(m² 2 K), where K is the cost of evaluating Do and D,, and the overall running time is O(Mm²K).
Proof.
meegeffunction functions. Suppose that Theorem 2. Let S (x1,..., In be a clustering instance and Do and D2 be any two merge the execution tree of Amerge (Do, Di) on S has E edges. Then the total running time of Algorithm 3 is O(En² K), where K is the cost of evaluating Dy and D2 once.
Proof. Fix any node in the execution tree with m clusters Ci,..., Cm and M outgoing edges (i.e., M possible merges from the state represented by v). We run Algorithm to determine the children of e, which by Lemma costs OMMn² K). since m n. Summing over all non-leaves of the execution tree, the total cost is O K). In addition to computing the children of a given node, we need to construct the children nodes, but this takes constant time per child.
16

---

B.2 LEARNING THE METRIC
In this section we provide details for learning the best combination of two metrics. We also give detailed pseudocode for our sweepline algorithm for finding the children of a node in the execution tree (see Algorithm 4 and for the complete algorithm (see Algorithm 5
For any metrics do and d1 and any clustering instance S, the execution tree for the family Ametric (do, d1) when run on S is well defined. That is, there exists a partition tree s.t. for any node v at depth i, the same sequence of first t merges is performed by Aggnic for all B in node v's 's interval.
Lemma 5.
Proof. The proof is by induction on the depth t. The base case is for depth t = 0, in which case we can use a single node whose interval is [o, 1]. Since all algorithms in the family start with ampty-sequence of merges, this satisfies the execution tree property.
Now suppose that there is tree of depth t with the execution tree property. If = |S| then we are finished, since the algorithms in Ameriic (dg, d1) make exactly S - merges. Otherwise, consider any leaf node e of the depth t tree with parameter interval J.. It is sufficient to show that can partition Ia into subintervals such that for / in each subinterval the next merge performed is constant. By the inductive hypothesis, we know that the first merges made by Ampettic are the same for all 3 E u. After performing these merges, the algorithm will have arrived at some set of clusters Ct.... Cm with m = |S| t. Recall that algorithms in the family Americ (dg, d1) run complete linkage using the metric dz. Complete linkage can be implemented in such a way that it only makes comparisons between pairwise point distances (i.e., is dz .²) larger or smaller than (v.y) y') ?)). To see this, for any pair of clusters, we can find the farthest pair of points between them using only distance comparisons. And, once we have the farthest pair of points between all pairs of clusters, we can find the pair of clusters to merge by again making only pairwise comparisons. It follows that if two parameters 3 and B' have the same outcome for all pairwise distance comparisons, then the next merge to be performed must be the same. We use this observation to partition the interval I, into subintervals where the next merge is constant. For any pair of points 2, x' E S, the distance da (z, x²) (1 - (B) du (2,, x²) + 3 d1 (z,, 2²) is linear function of the parameter 3. Therefore, for any points x, x', y. E S, there is at most one critical parameter value where the relative order of d (3r, .²) and a (y.y') changes. Between these O(1S)*) critical parameter values, the ordering on all pairwise merges is constant, and the next merge performed by the algorithm will also be constant. Therefore, there must exist a partitioning of Ly into most O(S))*) sub-intervals such that the next merge constant on each interval. We let the children of u correspond to the coarsest such partition.
Lemma Let CI...., Cm be a collection of clusters, do and dj be any pair of metrics, and [Sto: Pai) be a subset of the parameter space. If there are M distinct cluster pairs C₁ Cj that complete linkage would merge when using the metric da for 3 E 13t. Pu)) the running time of Algorithm is O(M²)).
Proof. The loop in step 4 of Algorithm 4 runs once for each possible merge, giving a total of M iterations. Each iteration finds the merge performed by complete linkage using the dg metric, which takes (n²²) time, and then solves On?²) linear equations to determine the largest value of f such that the same merge is performed. It follows that the cost of each iteration is O(n?), leading to overall running time of O(Mn²). Note, we assume that the pairwise distances d (z, x²) can be evaluated in constant time. This can always be achieved by precomputing two n X n distance matrices for the base metrics do and dj, respectively.
Theorem 3. Let S = (II,..., In) ) be a clustering instance and dg and d, be any two merge functions. Suppose that the execution tree of Ameriia (do, di) on S has E edges. Then the total running time of Algorithm 5 is OEEn).
Proof. Fix any node v in the execution tree with m clusters Ci,..., Cm and M outgoing edges (i.e., M possible merges from the state represented by v). We run Algorithm to determine the children of c, which by Lemma 6 costs OMn?). Summing over all non-leaves of the execution tree, the total cost is OEEn?).
C APPENDIX FOR EXPERIMENTS
Clustering distributions.
17

---

Algorithm 4 Find all merges for Ametric (do; d1)
Input: Set of clusters Ci...., Cm. metrics do, d1. parameter interval [s,s Pni).
1. Let M 0 be the initially empty possible merges.
2. Let I = 0 be the initially empty set of parameter intervals.
3. Let 3 = Bio.
4. While 3 < Sni:
(a) Let C, C2 be the pair of clusters minimizing maXaeA.bEB da b).
(b) Let E C₁ and x' Cj be the farthest points between C₁ and Cj.
(c) For all pairs of points y and y belonging to different clusters, let Cys' Ao/(Ao A1) where A,
dp(u. v') dp(x,x²) for p (0. 1).
(d) Let min(ffwy Cyy 3) (3m))
(e) Add merge (C;, Cj) to M and (3,c) I.
(f) Set B c.
5. Return M and I.
Algorithm Depth-firs first Enumeration of 8-linkage Execution Tree
Input: Point set F1, ... In. cluster distance functions d and d2.
1. Let be the root node of the execution tree with r.N = {(x1),.... (In)) and r./ [0,
2. Let be a stack of execution tree nodes, initially containing the root r.
3. Let T = 0 be the initially empty set of possible cluster trees.
4. Let I = @ be the initially empty set of intervals.
5. While the stack is not empty:
(a) Pop execution tree node off stack s.
(b) If e. has single cluster, add e.N to T and e.J I.
(c) Otherwise, for each merge (C,, Cj) and interval la returned by Algorithm 4 run on e-V' and e.I:
Let c be a new node with state given by e.N' after merging C, and Cj and c. Ic. ii Push e onto the stack 8.
6. Return and
18

---

MNIST Subsets. Our first distribution over clustering tasks corresponds to clustering subsets of the MNIST dataset LeCun et al. 1998), which contains 80,000 hand-written examples of the digits 0 through 9. We generate random clustering instance from the MNIST data as follows: first, we select & = 5 digits from {O...., 9} at random, then we randomly select 200 examples belonging to each of the selected digits, giving a total of n 1000 images. The target clustering for this instance is given by the ground-truth digit labels. We measure distances between any pair of digits in terms of the the Euclidean distance between their images represented as vectors of pixel intensities.
CIFAR-10 Subsets. We also consider a distribution over clustering tasks that corresponds to clustering subsets of the CIFAR-10 dataset (Krizhevsky 2009). This dataset contains 6000 images of each of the following classes: airplane, automobile, bird, cat, deer, dog, frog, horse, ship, and truck. Each example is a 32 x 32 color image with 3 color channels. We pre-process the data obtain neural-network feature representations for each example. We include 50 randomly rotated and cropped versions of each example and obtain feature representations from layer 'in4d' of a pre-trained Google inception network. This gives a -44-dimensional feature representation for each of the 3000000 examples (50 randomly rotated copies of the 6000 examples for each of the 10 classes). We generate clustering tasks from CIFAR-I0 as follows: first, select k- = 5 classes at random, then choose 50 examples belonging to each of the selected classes, giving total of n = 250 images. The target clustering for this instance is given by the ground-truth class labels. We measure distance between any pair of images as the distance between their feature embeddings.
Omniglot Subsets. Next, we consider a distribution over clustering tasks corresponding to clustering subsets of the Omniglot dataset (Lake al. 2015). The Omniglot dataset consists of written characters from 50 different alphabets with a total of 1623 different characters. The dataset includes 20 examples of each character, leading to a total of 32,460 examples. We generate a random clustering instance from the Omniglot data as follows: first, we choose one of the alphabets at random. Next, we choose k uniformly in (5,.... 10} and choose k random characters from that alphabet. The clustering instance includes 20k examples and the target clustering given by the ground-truth character labels.
We use two different distance metrics on the Omniglot dataset. First, we use the cosine distance between neural network feature embeddings. The neural network was trained to perform digit classification on MNIST. Second, each example has both an image of the written character, as well as the stroke trajectory (i.e., a time series of (z,,) y) coordinates of the tip of the pen when the character was written). We also use the following distance defined in terms of the strokes: Given two trajectories
(Iz, -xI,,() and s' = (2'', vi)T=,, we define the distance between them by d(s, = T+T (E d((Ie, ((), s') + ET=1 d(<'),
1_
(())),))).s)) s)).ss) where d( d((z,,)).. s') denotes the Euclidean distance
from the point (Ize Me.) to the closest point in s'. This is the average distance from any point from either trajectory to the nearest point on the other trajectory. This hand-designed metric provides complementary notion of distance to the neural network feature embeddings.
Places2 Subsets. The Places2 dataset consists of images of 365 different place categories, including "volcano", "gift shop", and "farm" (Zhou et al. 2017). To generate a clustering instance from the places data, we choose & randomly from (5.... 10), choose l random place categories, and then select 20 random examples from each chosen category. We restrict ourselves to the first 1000 images from each class.
We use two metrics for this data distribution. First, we use cosine distances between feature embeddings generated by a VGG16 network pre-trained on imagenet. In particular, we use the activations just before the fully connected layers, but after the max-pooling is performed, so that we have 512-dimensional feature vectors. Second, we compute color histograms in HSV space for each image and use the cosine distance between the histograms. In more detail, we partition the hue space into 8 bins, the saturation space into 2 bins, and the value space into 4 bins, resulting in 64-dimensional histogram counting how frequently each quantized color appears in the image. Two images are close under this metric if they contain similar colors.
Places2 Diverse Subsets. We also construct an instance distribution from subset of the Places2 classes which have diverse color histograms. We expect the color histogram metric to perform better on this distribution. To generate a clustering instance, we pick k: = 4 classes from aquarium, discotheque, highway, iceberg, kitchen, lawn, stage-indoor, underwater ocean deep, volcano, and water tower. We include 50 randomly sampled images from each chosen class, leading to a total of n = 200 points per instance.
Synthetic Rings and Disks. We consider a two dimensional synthetic distribution where each clustering instance has 4 clusters, where two are ring-shaped and two are disk-shaped. To generate each instance sample 100 points uniformly at random from each ring or disk. The two rings have radiuses 0.4 and 0.8, respectively, and are both centered at the
19

---

origin. The two disks have radius 0.4 and are centered at (1.5, 0.4) and (1.5, -..4). respectively. For this data, we measure distances between points in terms of the Euclidean distance between them.
Average Number of Discontinuities. Next we report the average number discontinuities the loss function for a clustering instance sampled from each of the distributions described above for each of the learning tasks consider. In all cases, the average number of discontinuities is many orders of magnitude smaller than the upper bounds. The metric learning problems tend to have though our only worst-case bound on the number of discontinuities when interpolating between average and complete linkage is exponential in n, the empirical number of discontinuities is always smaller than for interpolating between single and complete linkage. The results are shown in Table [
discontinuities than learning the best merge function. Surprisingly, even
Distribution
Task
max
Average # Discontinuities
Omniglot
SC
200
59.4
Omniglot
AC
200
33,9
Omniglot
metric
200
201.1
MNIST
SC
1000
362.6
MNIST
AC
1000
282.0
Rings and Disks
SC
400
29.0
Rings and Disks
AC
400
18.3
CIFAR-10
SC
250
103.2
CIFAR-10
AC
250
66.2
Places2
metric
200
241.0
Places2 Diverse
metric
200
269.6
Table 1: Table of average number of discontinuities for piecewise constant loss function sampled from each distribution and learning task. Task 'SC' corresponds to interpolating between single and complete linkage, 'AC' interpolating between average and complete linkage, and 'metric" is interpolating between two base metrics. The column labeled "max n is an upper bound on the size of each clustering instance.
20


Reviews:
[{"review_id": "rJlGe3uIqS", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": null, "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "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.\n\nThe 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.\n", "extra_scores": {"experience_assessment": "I have published in this field for several years.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper thoroughly.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}, {"review_id": "HkgY83ahtr", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": null, "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "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.\n\nThe 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.\n\nComments\n\nI 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.\n\nConcerning 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).\n\nThe 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?\n\nFor 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.)\n\nFor 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.\n\nFor 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.\n\nTypos, etc.\n\nThe references are somewhat inconsistently formatted. Also, some proper nouns in titles are not capitalized (e.g., “lloyd’s families”).\n\n“leaves correspond to” -> “leaves corresponding to”\n\nWhat does the “big-Oh tilde” notation in Theorem 1 mean?\n", "extra_scores": {"experience_assessment": "I do not know much about this area.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper.", "review_assessment:_checking_correctness_of_experiments": "I carefully checked the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}, {"review_id": "HkgPT3nJqH", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": null, "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "Summary:\n\nThis 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.\n\nComments:\n\nIn general, I think this is a good quality paper. \n- 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. \n- The theorem for generalization error is strong.\n\nIt can be further improved in the following aspects (mainly the experiments).\n- 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.\n- 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.\n\nOverall 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.\n\n\n----- after reading the response --\n\nI'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.\n\nMy score does not change, but overall I advocate to accept this paper.\n", "extra_scores": {"experience_assessment": "I have read many papers in this area.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}]

Author rebuttal:

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)