Learning-Theoretic Foundations of Algorithm Configuration for
Combinatorial Partitioning Problems∗
Maria-Florina Balcan

Vaishnavh Nagarajan

Ellen Vitercik

Colin White

arXiv:1611.04535v3 [cs.DS] 17 May 2017

May 18, 2017

Abstract
Max-cut, clustering, and many other partitioning problems that are of significant importance to machine learning and other scientific fields are NP-hard, a reality that has motivated
researchers to develop a wealth of approximation algorithms and heuristics. Although the best
algorithm to use typically depends on the specific application domain, a worst-case analysis is
often used to compare algorithms. This may be misleading if worst-case instances occur infrequently, and thus there is a demand for optimization methods which return the algorithm
configuration best suited for the given application’s typical inputs. We address this problem
for clustering, max-cut, and other partitioning problems, such as integer quadratic programming, by designing computationally efficient and sample efficient learning algorithms which
receive samples from an application-specific distribution over problem instances and learn a
partitioning algorithm with high expected performance. Our algorithms learn over common
integer quadratic programming and clustering algorithm families: SDP rounding algorithms
and agglomerative clustering algorithms with dynamic programming. For our sample complexity analysis, we provide tight bounds on the pseudodimension of these algorithm classes, and
show that surprisingly, even for classes of algorithms parameterized by a single parameter, the
pseudo-dimension is superconstant. In this way, our work both contributes to the foundations
of algorithm configuration and pushes the boundaries of learning theory, since the algorithm
classes we analyze consist of multi-stage optimization procedures and are significantly more
complex than classes typically studied in learning theory.

∗

Authors’ addresses: {ninamf,vaishnavh,vitercik,crwhite}@cs.cmu.edu.

1

Introduction

NP-hard problems arise in a variety of diverse and oftentimes unrelated application domains. For
example, clustering is a widely-studied NP-hard problem in unsupervised machine learning, used to
group protein sequences by function, organize documents in databases by subject, and choose the
best locations for fire stations in a city. Although the underlying objective is the same, a “typical
problem instance” in one setting may be significantly different from that in another, causing approximation algorithms to have inconsistent performance across the different application domains.
We study how to characterize which algorithms are best for which contexts, a task often referred to in the AI literature as algorithm configuration. This line of work allows researchers
to compare algorithms according to an application-specific metric, such as expected performance
over their problem domain, rather than a worst-case analysis. If worst-case instances occur infrequently in the application domain, then a worst-case algorithm comparison could be uninformative
and misleading. We approach application-specific algorithm configuration via a learning-theoretic
framework wherein an application domain is modeled as a distribution over problem instances. We
then fix an infinite class of approximation algorithms for that problem and design computationally
efficient and sample efficient algorithms which learn the approximation algorithm with the best
performance over the distribution, and therefore an algorithm with high performance in the specific application domain. Gupta and Roughgarden [24] introduced this learning framework to the
theory community, but it has been the primary model for algorithm configuration and portfolio
selection in the artificial intelligence community for decades [33] and has led to breakthroughs in
diverse fields including combinatorial auctions [28], scientific computing [16], vehicle routing [12],
and SAT [42].
In this framework, we study two important, infinite algorithm classes. First, we analyze approximation algorithms based on semidefinite programming (SDP) relaxations and randomized
rounding procedures, which are used to approximate integer quadratic programs (IQPs). These
algorithms can be used to find a nearly optimal solution to a variety of combinatorial partitioning
problems, including the seminal max-cut and max 2-SAT problems. Second, we study agglomerative clustering algorithms followed by a dynamic programming step to extract a good clustering.
These techniques are widely used in machine learning and across many scientific disciplines for data
analysis. We begin with a concrete problem description.
Problem description. In this learning framework, we fix a computational problem, such as
max-cut or k-means clustering, and assume that there exists an unknown, application-specific
distribution D over a set of problem instances Π. We denote an upper bound on the size of the
problem instances in the support of D by n. For example, the support of D might be a set of
social networks over n individuals, and the researcher’s goal is to choose an algorithm with which
to perform a series of clustering analyses. Next, we fix a class of algorithms A. Given a cost
function cost : A × Π → [0, H], the learner’s goal is to find an algorithm h ∈ A that approximately
optimizes the expected cost with respect to the distribution D, as formalized below.
Definition 1 ([24]). A learning algorithm L (, δ)-learns the algorithm class A with respect to
the cost function cost if, for every distribution D over Π, with probability at least
1− δ i
over
h
m
the choice of a sample S ∼ D , L outputs an algorithm ĥ ∈ A such that Ex∼D cost ĥ, x −

minh∈A {Ex∼D [cost(h, x)]} < . We require that the number of samples be polynomial in n, 1 , and
1
δ , where n is an upper bound on the size of the problem instances in the support of D. Further, we
say that L is computationally efficient if its running time is also polynomial in n, 1 , and 1δ .
We derive our guarantees by analyzing the pseudo-dimension of the algorithm classes we study
1

(see Section 1.1, [31, 32, 2]). We then use the structure of the problem to provide efficient algorithms
for most of the classes we study.
SDP-based methods for integer quadratic programming. Many NP-hard problems, such as
max-cut, max-2SAT, and correlation clustering, can be represented as an integer quadratic program
(IQP) of the following form. The input is an n × n matrix A with nonnegative diagonal entries and
the
P output is a binary assignment to each variable in the set X = {x1 , . . . , xn } which maximizes
i,j∈[n] aij xi xj . In this formulation, xi ∈ {−1, 1} for all i ∈ [n]. (When the diagonal entries are
allowed to be negative, the ratio between the semidefinite relaxation and the integral optimum can
become arbitrarily large, so we restrict the domain to matrices with nonnegative diagonal entries.)
IQPs appear frequently in machine learning applications, such as MAP inference [25, 44, 20]
and image segmentation and correspondence problems in computer vision [15, 10]. Max-cut is
an important IQP problem, and its applications in machine learning include community detection
[7], variational methods for graphical models [34], and graph-based semi-supervised learning [39].
The seminal Goemans-Williamson max-cut algorithm is now a textbook example of semidefinite
programming [21, 41, 38]. Max-cut also arises in many other scientific domains, such as circuit
design [43] and computational biology [36].
The best approximation algorithms for IQPs relax the problem to anPSDP, where the input is
the same matrix A, but the output is a set of unit vectors maximizing i,j aij hui , uj i. The final
step is to transform, or “round,” the set of vectors into an assignment of the binary variables in X.
This assignment corresponds to a feasible solution to the original IQP. There are infinitely many
rounding techniques to choose from, many of which are randomized. These algorithms make up
the class of Random Projection, Randomized Rounding algorithms (RPR2 ), a general framework
introduced by [18]. RPR2 algorithms are known to perform well in theory and practice. When the
integer quadratic program is a formulation of the max-cut problem, the class of RPR2 algorithms
contain the groundbreaking Goemans-Williamson algorithm, which achieves a 0.878 approximation
ratio [21]. Assuming the unique games conjecture and P 6= N P , this approximation is optimal
to within any additive constant [27]. More generally, if A is any real-valued n × n matrix with
nonnegative diagonal entries, then there exists an RPR2 algorithm that achieves an approximation
ratio of Ω(1/ log n) [14], and in the worst case, this ratio is tight [1]. Finally, if A is positive
semi-definite, then there exists an RPR2 algorithm that achieves a 2/π approximation ratio [9].
We analyze several classes of RPR2 rounding function classes, including s-linear [18], outward
rotation [45], and ˜-discretized rounding functions [30]. For each class, we derive bounds on the
number of samples needed to learn an approximately optimal rounding function with respect to
an underlying distribution over problem instances using pseudo-dimension. We also provide a
computationally efficient and sample efficient learning algorithm for learning an approximately
optimal s-linear or outward rotation rounding function in expectation. We note that our results
also apply to any class of RPR2 algorithms where the first step is to find some set of vectors on the
unit sphere, not necessarily the SDP embedding, and then round those vectors to a binary solution.
This generalization has led to faster approximation algorithms with strong empirical performance
[26].
Clustering by agglomerative algorithms with dynamic programming. Given a set of n
datapoints and the pairwise distances between them, at a high level, the goal of clustering is to
partition the points into groups such that distances within each group are minimized and distances
between each group are maximized. A classic way to accomplish this task is to use an objective
function. Common clustering objective functions include k-means, k-median, and k-center, which
we define later on. We focus on a very general problem where the learner’s main goal is to minimize
an abstract cost function such as the cluster purity or the clustering objective function, which is
2

the case in many clustering applications such as clustering biological data [19, 29]. We study
infinite classes of two-step clustering algorithms consisting of a linkage-based step and a dynamic
programming step. First, the algorithm runs one of an infinite number of linkage-based routines
to construct a hierarchical tree of clusters. Next, the algorithm runs a dynamic programming
procedure to find the pruning of this tree that minimizes one of an infinite number of clustering
objectives. For example, if the clustering objective is the k-means objective, then the dynamic
programming step will return the optimal k-means pruning of the cluster tree.
For the linkage-based procedure, we consider several parameterized agglomerative procedures
which induce a spectrum of algorithms interpolating between the popular single-, average-, and
complete-linkage procedures, which are prevalent in practice [3, 35, 40] and known to perform
nearly optimally in many settings [4, 5, 6, 22]. For the dynamic programming step, we study an
infinite class of objectives which include the standard k-means, k-median, and k-center objectives,
common in applications such as information retrieval [11, 13]. We show how to learn the best
agglomerative algorithm and pruning objective function pair, thus extending our work to multiparameter algorithms. We provide tight pseudo-dimension bounds, ranging from Θ(log n) for simpler
algorithm classes to Θ(n) for more complex algorithm classes, so our learning algorithms are sample
efficient.
Key challenges. One of the key challenges in analyzing the pseudo-dimension of the algorithm
classes we study is that we must develop deep insights into how changes to an algorithm’s parameters
affect the solution the algorithm returns on an arbitrary input. For example, in our clustering
analysis, the cost function could be the k-means or k-median objective function, or even the distance
to some ground-truth clustering. As we range over algorithm parameters, we alter the merge step by
tuning an intricate measurement of the overall similarity of two point sets and we alter the pruning
step by adjusting the way in which the combinatorially complex cluster tree is pruned. The cost
of the returned clustering may vary unpredictably. Similarly, in integer quadratic programming, if
a variable flips from positive to negative, a large number of the summands in the IQP objective
will also flip signs. Nevertheless, we show that in both scenarios, we can take advantage of the
structure of the problems to develop our learning algorithms and bound the pseudo-dimension.
In this way, our algorithm analyses require more care than standard complexity derivations
commonly found in machine learning contexts. Typically, for well-understood function classes used
in machine learning, such as linear separators or other smooth curves in Euclidean spaces, there is
a simple mapping from the parameters of a specific hypothesis to its prediction on a given example
and a close connection between the distance in the parameter space between two parameter vectors
and the distance in function space between their associated hypotheses. Roughly speaking, it is
necessary to understand this connection in order to determine how many significantly different
hypotheses there are over the full range of parameters. Due to the inherent complexity of the
classes we consider, connecting the parameter space to the space of approximation algorithms and
their associated costs requires a much more delicate analysis. Indeed, the key technical part of
our work involves understanding this connection from a learning-theoretic perspective. In fact, the
structure we discover in our pseudo-dimension analyses allows us to develop many computationally
efficient meta-algorithms for algorithm configuration due to the related concept of shattering. A
constrained pseudo-dimension of O(log n) often implies a small search space of 2O(log n) = O(n) in
which the meta-algorithm will uncover a nearly optimal configuration.
We bolster the theory of algorithm configuration by studying algorithms for problems that are
ubiquitous in machine learning and optimization: integer quadratic programming and clustering.
In this paper, we develop techniques for analyzing randomized algorithms, whereas the algorithms
analyzed in the previous work were deterministic. We also provide the first pseudo-dimension
3

lower bounds in this line of work, which require an involved analysis of each algorithm family’s
performance on carefully constructed instances. Our lower bounds are somewhat counterintuitive,
since for several of the classes we study, they are of the order Ω(log n), even if the corresponding
classes of algorithms are defined by a single real-valued parameter.

1.1

Preliminaries and definitions

In this section, we provide the definition of pseudo-dimension in the context of algorithm classes.
Consider a class of algorithms A and a class of problem instances X . Let the cost function cost(h, x)
denote the abstract cost of running an algorithm h ∈ A on a problem instance x ∈ X . Similarly,
define the function class HA = {cost(h, ·) : X → R|h ∈ A}. Then, recall that a finite subset of
problem instances S = {x1 , x2 , . . . xm } is shattered by the function class H, if there exist real-valued
witnesses r1 , . . . , rm such that for all subsets T ⊆ S, there exists a function cost (hT , ·) ∈ H, or in
other words, an algorithm hT ∈ A such that cost (hT , xi ) ≤ ri if and only if i ∈ T . Then, we can
define the pseudo-dimension of the algorithm class A to be the pseudo-dimension P dim(H) of H
i.e., the cardinality of the largest subset of X shattered by H.
By bounding P dim(H), clearly we can derive sample complexity guarantees in the context
of algorithm classes [17]: for every distribution D over X , every  > 0, and every δ ∈ (0, 1],
2

m ≥ c H
P dim(H) + log 1δ for a suitable constant c (independent of all other parameters),
then with probability at least 1 − δ over m samples x1 , . . . , xm ∼ D,
m

1 X
cost(h, xi ) − Ex∼D [cost(h, x)] < 
m
i=1

for every algorithm h ∈ A. Therefore, if a learning algorithm receives as input a sufficiently large
set of samples and returns the algorithm which performs best on that sample, we can be guaranteed
that this algorithm is close to optimal with respect to the underlying distribution.

2

SDP-based methods for integer quadratic programming

In this section, we study several IQP approximation algorithms. These classes consist of SDP
rounding algorithms and are a generalization of the seminal Goemans-Williamson (GW) max-cut
algorithm [21]. We prove that it is possible to learn the optimal algorithm from a fixed class over
a specific application domain, and for many of the classes we study, this learning procedure is
computationally efficient and sample efficient.
P
We focus on integer quadratic programs of the form
i,j∈[n] aij xi xj , where the input is a
matrix A with nonnegative diagonal entries and the output is an assignment of the binary variables
X = {x1 , . . . , xn } maximizing this sum. Specifically, each variable in X is set to either −1 or 1. This
problem is also known as MaxQP [14]. Most algorithms with the best approximation guarantees
use an SDP relaxation. The SDP relaxation has the form
X
maximize
aij hui , uj i
subject to ui ∈ S n−1 .
(1)
i,j∈[n]

Given the set of vectors {u1 , . . . , un }, we must decide how they represent an assignment of the
binary variables in X. In the GW algorithm, the vectors are projected onto a random vector Z
drawn from an n-dimensional Gaussian. Next, if the directed distance of the resulting projection
is greater than 0, then the corresponding binary variable is set to 1, and otherwise it is set to −1.
4

In some cases, the GW algorithm can be improved upon by probabilistically assigning each
binary variable to 1 or −1. In the final rounding step, any rounding function r : R → [−1, 1] can
be used to specify that a variable xi is set to 1 with probability 12 + 21 · r (hZ, ui i) and −1 with
probability 21 − 12 · r (hZ, ui i). See Algorithm 1 for the pseudocode. This is known as a Random
Algorithm 1 SDP rounding algorithm with rounding function r
Input: Matrix A ∈ Rn×n .
1: Solve the SDP (1) for the optimal embedding U = (u1 , . . . , un ).
2: Choose a random vector Z ∈ Rn according to the n-dimensional Gaussian distribution.
3: Define the fractional assignment h : X → [−1, 1] such that h(xi ) = r (hZ, ui i).
Output: h.
Projection, Randomized Rounding (RPR2 ) algorithm, so named by the seminal work of [18]. The
randomized assignment h produced by an RPR2 algorithm is called a fractional assignment. Based
on the output h, we can derive a proper assignment of the variables x1 , . . . , xn where xi is set to 1
with probability 21 + 21 h(xi ) and −1 with probability 21 − 12 h(xi ).
In this section, we analyze the class of s-linear round functions. For the max-cut problem, [18]
proved that when the maximium cut in the graph is not very large, a worst-case approximation
ratio above the GW ratio is possible using an s-linear rounding function. For example, they proved
that if the optimal cut contains at most a 0.6 fraction of the edges, then the ratio is at least 0.9128.
The optimal choice of s depends on the graph, but we give an efficient algorithm to learn a nearly
optimal value for s in expectation over a distribution of problem instances. In Appendix B, we
consider other rounding functions, including ˜-discretized rounding functions [30], outward rotation
algorithms [45], and “sigmoid-like” rounding functions, which include the classes of s-linear and
outward rotation functions.
An s-linear rounding function φs : R → [−1, 1] is parameterized by s > 0, as follows:



−1 if y < −s
φs (y) = y/s if − s ≤ y ≤ s


1
if y > s.

Figure 1: A graph of the 2-linear function φ2 .

Our goal is to devise an algorithm Lslin that (, δ)-learns the best s-linear rounding function
with respect to a distribution D over MaxQP problem instances. Specifically, let slin∗s (A) be the
expected value of the solution returned by RPR2 using the rounding function φs when evaluated
on the MaxQP problem instance defined by the matrix A. We instantiate the cost function cost
to be cost(A, s) = −slin∗s (A). Here, we take the negative of slin∗s (A) since our goal is to find the
s parameter that will maximize this value in expectation, and minimizing cost(A, s) now amounts
to maximizing slin∗s (A). We require that Lslin returns a value ŝ such that with probability at least
1 − δ, if s∗ maximizes E [slin∗s (A)], then E [slin∗s∗ (A)] − E [slin∗ŝ (A)] < .
A∼D

A∼D

A∼D

One might expect that the first step would be to bound the pseudo-dimension of the class
Hslin∗ = {slin∗s : A → [−H, H] | s > 0} (Pdim(Hslin∗ )), where A is the set of all real-valued n × n
matrices with nonnegative diagonal entries and H is an upper bound on the range of slin∗s when
restricted to the support of the distribution over problem instances. We pursue an alternative route
5

that provides a simpler sample complexity and algorithmic analysis. We instead bound the pseudodimension of the class Hslin = {slins : A × Rn → [−H, H] | s > 0}, where slins (A, Z) is the value
of the fractional assignment produced by projecting the SDP embedding of A onto Z and rounding
the directed distances
function φs . ExplicPof the projections (multiplied by ||Z||) using the rounding
∗
itly, slins (A, Z) = i,j aij φs (hui , Zi) · φs (hui , Zi) . Notice that slins (A) = EZ∼Z [slins (A, Z)],
where Z denotes the standard n-dimensional Gaussian distribution. We prove tight bounds on the
pseudo-dimension of Hslin and derive generalization guarantees for the algorithm class we ultimately
care about: Hslin∗ , as follows. All omitted proofs can be found in Appendix A.
Theorem 2. Suppose that Lslin is an algorithm that takes
as input m samples (A(i) , Z(i) ) ∼
1 Pm
D × Z and returns the parameter ŝ which maximizes m i=1 slins (A(i) , Z(i) ). Further, supposePthat m is sufficiently large to ensure that with probability at least 1 − δ, for all s > 0,
m
1

(i)
(i)
|m
i=1 slins (A , Z ) − E(A,Z) [slins (A, Z)] | ≤ 2 . Then Lslin (, δ)-learns the class of s-linear
rounding functions with respect to the cost function −slin∗s .
Now, we will show that Pdim(Hslin ) = Θ(log n) and then we will present Algorithm 2, a
computationally efficient and sample efficient algorithm. We will often fix a tuple (A, Z) and
consider slins (A, Z) as a function of s, which we denote as slinA,Z (s). We begin with a helpful
lemma.
Lemma 1. The function slinA,Z : R>0 → R is made up of n + 1 piecewise components of the
form sa2 + sb + c for some a, b, c ∈ R. Moreover, if the border between two components falls at some
s ∈ R>0 , then it must be that s = |hui , Zi| for some ui in the optimal SDP embedding of A.
n−1 be the optimal embedding of A. Then we may write
Proof. First, let
PX = {u1 , . . . , un } ⊂ S
slinA,Z (s) = i,j aij φs (hui , Zi) · φs (hui , Zi) . For any ui ∈ X, the specific form of φs (hZ, ui i)
depends solely on whether hZ, ui i < −s, −s ≤ hZ, ui i ≤ s, or s < hZ, ui i. Of course, if hZ, ui i ≥ 0
or hZ, ui i < 0, we can disregard the possibility that hZ, ui i < −s or hZ, ui i > s, respectively. Then
so long as |hZ, ui i| > s, we have that φs (hZ, ui i) = ±1, where the sign depends on the sign of hZ, ui i.
Further, when s grows to the point where s > |hZ, uj i|, we have that φs (hZ, ui i) = hZ, uj i/s.
Therefore, if we order the set of real values {|hZ, u1 i| , . . . , |hZ, un i|}, then so long as s falls between
two consecutive elements of this ordering, the form of slinA,Z (s) is fixed. In particular, each
summand is either a constant, a constant multiplied by 1s , or a constant multiplied by s12 , perhaps
accompanied by an additive constant term. This means that we may partition the positive real line
into n + 1 intervals where the form of slin(A,Z) (s) is a fixed quadratic function, as claimed.

Lemma 1 allows us to prove the following bound on Pdim(Hslin ).
Lemma 2. Pdim(Hslin ) = Θ(log n).
Lemma 2 follows from Lemmas 3 and 4, where we prove Pdim(Hslin ) = O(log n) and Pdim(Hslin ) =
Ω(log n).
Lemma 3. Pdim(Hslin ) = O(log n).
Proof. We prove this upper bound by showing that if a set S of size m is shatterable, then
m = O(log n). This means that the largest shatterable set must be of size O(log n),so the pseudodimension of Hslin is O(log n). We arrive at this bound by fixing a tuple A(i) , Z(i) ∈ S and analyzing slinA,Z (s). In particular, we make use of Lemma 1, from which we know that slin(A,Z) (s)
is composed of n + 1 piecewise
quadratic components. Therefore, if ri is the witness corresponding

to the element A(i) , Z(i) , we can partition the positive real line into at most 3(n + 1) intervals
6

At most 3(n + 1) intervals
for sample (A(1) , Z (1) ) and witness r1

s>0

At most 3(n + 1) intervals
for sample (A(2) , Z (2) ) and witness r2

s>0

..
At most 3(n + 1) intervals
for sample (A(|S|) , Z (|S|) ) and witness r|S|

s>0

Merging the intervals of all samples and witnesses
At most (3n + 2)m + 1 intervals
for samples S and their respective witnesses

s>0


Figure 2: Partitioning s > 0 into intervals given a set S of m tuples A(i) , Z(i) and witnesses ri
such that within each interval for each i, slin(A(i) ,Z (i) ) (s) is always greater than ri or lesser than
ri .
where slinA,Z (s) is always either less than its witness ri or greater than ri as s varies over one
fixed interval. The constant 3 term comes from the fact that for a single, continuous quadratic
component of slin(A,Z) (s), the function may equal ri at most twice, so there are at most three
subintervals where the function is less than or greater than ri .
Now, S consists of m tuples A(i) , Z(i) , each of which corresponds to its own partition of the
positive real line. If we merge these partitions (as shown in Figure 2), simple algebra shows that
we are left with at most (3n + 2)m + 1 intervals such that for all i ∈ [m], slinA(i) ,Z(i) (s) is always
either less than its witness ri or greater than ri as s varies over one fixed interval. In other words,
in one interval, the binary labeling of S, defined by whether each sample is less than or greater
than its witness, is fixed. This means that if S is shatterable, the 2m values of s which induce all
2m binary labelings of S must come from distinct intervals. Therefore 2m ≤ (3n + 2)m + 1, so
m = O(log n).
Lemma 4. Pdim(Hslin ) = Ω(log n).
Proof sketch. In order
to prove that the pseudo dimension of Hslin is at least c log n for some c, we

present a set S = (G(1) , Z(1) ), . . . , (G(m) , Z(m) ) of m = c log n graphs and projection vectors that
can be shattered by Hslin . In other words, there exist m witnesses r1 , . . . , rm and 2m = nc values
of s, H = {s1 , . . . , snc }, such that for all T ⊆ [m], there exists sT ∈ H such that if j ∈ T , then
slinST (G(j) , Z(j) ) > rj and if j 6∈ T , then slinST (G(j) , Z(j) ) ≤ rj .
To build S, we use the same graph G for all G(j) and we vary Z(j) . We set G to be the graph
composed of bn/4c disjoint copies of K4 . Via a careful choice of the vectors Z(j) and witnesses rj ,
we pick out 2m critical values of s, which we call C, such that slinG,Z(1) (s) switches from above
to below its witness for every other element of the critical values in C. Meanwhile, slinG,Z(2) (s)
switches from above to below its witness half as often as slinG,Z(1) (s). Similarly, slinG,Z(3) (s)
switches from above to below its witness half as often as slinG,Z(2) (s), and so on. Therefore, we
achieve every binary labeling of S using the functions {slins | s ∈ C}, so S is shattered.
Our lower bound is particularly strong because it holds for a family of positive semidefinite
matrices, rather than a more general family of real-valued matrices. We now prove that our
learning algorithm, Algorithm 2 is correct, computationally efficient, and sample efficient.
To prove that Algorithm 2 (, δ)-learns the class of s-linear rounding functions, we first prove
that Algorithm 2 ideed outputs the empirically optimal value of ŝ.
7

Algorithm 2 An algorithm for finding an empirical value maximizing s-linear rounding function
Input: Sample S = {(A(1) , Z(1) ), . . . , (A(m) , Z(m) )}
(i)
(i)
1: For all i, solve for the SDP embedding U (i) of A(i) , where U (i) = (u1 , . . . , un ).

2: Let T = s1 , . . . , s|T | be the set of all values s > 0 such that there exists a pair of indices
(i)

j ∈ [n], i ∈ [m] with |hZ(i) , uj i| = s.
1 Pm
3: For i ∈ [|T | − 1], let ŝi be the value in [si , si+1 ] which maximizes m
i=1 slinA(i) ,Z(i) (s).
1 Pm
4: Let ŝ be the value in {ŝ1 , . . . , ŝ|T |−1 } that maximizes m
i=1 slinA(i) ,Z(i) (s).
Output: ŝ


1 Pm
(i)
(i) over the
Lemma 5. Algorithm 2 produces the value ŝ which maximizes m
i=1 slins A , Z
input sample S. Algorithm 2 has running time polynomial in m and n.
1 Pm
Proof. First, define hS,Z (s) = m
i=1 slinA(i) ,Z(i) (s), which we claim that Algorithm 2 maximizes.
In Lemma 1, we proved that each function slinA(i) ,Z(i) (s) is made up of at most n + 1 piecewise
components of the form sa2 + sb + c for some a, b, c ∈ R. Therefore, hS,Z (s) is made up of at most
mn + 1 piecewise components of the form sa2 + sb + c as well. Moreover, by Lemma 1, if the border
(i)

(i)

between two components falls at some s ∈ R>0 , then it must be that hZ(i) , xj i = s for some xj

in the optimal max-cut SDP embedding of A(i) . These are the thresholds which are computed in
Step 2 of Algorithm 2. Therefore, as we increase s starting at 0, s will be a fixed quadratic function
between the thresholds, so it is simple to find the optimal value of sP
between any pair of consecutive

1
(i)
(i) (Step 4),
thresholds (Step 3), and then the value maximizing hS,Z (s) = m m
i=1 slins A , Z
which is the global optimum.
We are now ready to prove our main result.
 

2
drawn from (D × Z)m , AlgoTheorem 3. Given a sample of size m = O H
log (n) + log 1δ
rithm 2 (, δ)-learns the class of s-linear rounding functions with respect to the cost function −slin∗s
and it is computationally efficient.



Proof. Let S = A(1) , Z(1) , . . . , A(m) , Z(m)
be a sample of size m. In Lemma 5, we prove

1 Pm
(i)
(i) in
that Algorithm 2 on input S returns the value ŝ which maximizes m
i=1 slins A , Z
polynomial
time. Then from our pseudodimension bound in Lemma 3 we have that with m =
 

H 2
O
log n + log 1δ
samples, with probability at least 1 − δ, for all s > 0,



1 X

slins A(i) , Z(i) −
E
[slins (A, Z)] < .
m
2
(A,Z)∼D×Z
m

i=1

Then, from Lemma 12, E [slins∗ (A)] − E [slinŝ (A)] < . Thus, Algorithm 2 (, δ)-learns the
A∼D

best s-linear function with respect to D.

3

A∼D

Agglomerative algorithms with dynamic programming

We begin with an overview of agglomerative algorithms with dynamic programming, which include
many widely-studied clustering algorithms, and then we define several parameterized classes of such
algorithms. As in the previous section, we prove it is possible to learn the optimal algorithm from
8

a fixed class for a specific application, and for many of the classes we analyze, this procedure is
computationally efficient and sample efficient. We focus on agglomerative algorithms with dynamic
programming for clustering problems. A clustering instance V = (V, d) consists of a set V of n
points and a distance metric d : V ×V → R≥0 specifying all pairwise distances between these points.
The overall goal of clustering is to partition the points into groups such that distances within each
group are minimized and distances between each group are maximized. Clustering is typically
performed using an objective function Φ, such as k-means, k-median, k-center, or the distance to
the ground truth clustering (a scenario we discuss in more detail in Section 3.2). Formally, an
objective function Φ takes as input a set of points c = {c1 , . . . , ck } ⊆ V which we call centers,
as well as a partition C = {C1 , . . . , CP
V which we call a clustering. We define the rich class
k } of P
of clustering objectives Φ(p) (C, c) = ki=1 ( q∈Ci d(q, ci )p )1/p for p ∈ [1, ∞) ∪ {∞}. The k-means,
k-median, and k-center objective functions are Φ(2) , Φ(1) , and Φ(∞) , respectively.1
Next, we define agglomerative clustering algorithms with dynamic programming, which are
prevalent in practice [3, 35, 40] and enjoy strong theoretical guarantees in a variety of settings
[4, 5, 6, 22]. Examples of these algorithms include the popular single-, complete-, and averagelinkage algorithms with dynamic programming. An agglomerative clustering algorithm with dynamic programming is defined by two functions: a merge function and a pruning function. A merge
function ξ(A, B) → R≥0 defines a distance between two sets of points A, B ⊆ V . The algorithm
builds a cluster tree T by starting with n singleton leaf nodes, and iteratively merging the two sets
with minimum distance until there is a single node remaining, consisting of the set V . The children
of any node T in this tree correspond to the two sets of points that were merged to form T during
the sequence of P
merges. Common choices for the merge function ξ include mina∈A,b∈B d(a, b) (single
1
linkage), |A|·|B|
a∈A,b∈B d(a, b) (average linkage) and maxa∈A,b∈B d(a, b) (complete linkage).
A pruning function Ψ takes as input a k 0 -pruning of any subtree of T and returns a score R≥0
for that pruning. A k 0 -pruning for a subtree T is a partition of the points contained in T ’s root
into k 0 clusters such that each cluster is an internal node of T . Pruning functions may be similar to
objective functions, though the input is a subtree. The k-means, -median, and -center objectives
are standard pruning functions. The algorithm returns the k-pruning of the tree T that is optimal
according to Ψ, which can be found in polynomial time using dynamic programming. Algorithm 3
details how the merge function and pruning function work together to form an agglomerative
clustering algorithm with dynamic programming. In the dynamic programming step, to find the
1-pruning of any node T , we only need to find the best center c ∈ T . When k 0 > 1, we recursively
find the best k 0 -pruning of T by considering different combinations of the best i0 -pruning of the left
child TL and the best k 0 − i0 -pruning of the right child TR for i0 ∈ {1, . . . , k − 1} and choosing the
best combination.
Pictorially, Figure 3 depicts an array of available choices when designing an agglomerative
clustering algorithm with dynamic programming. Each path in the chart corresponds to an alternative choice of a merging function ξ and pruning function Ψ. The algorithm designer’s goal is to
determine the path that is optimal for her specific application domain.
In Section 3.1, we analyze several classes of algorithms where the merge function comes from an
infinite family of functions while the pruning function is an arbitrary, fixed function. In Section 3.2,
we expand our analysis to include algorithms defined over an infinite family of pruning functions
in conjunction with any family of merge functions. Our results hold even when there is a fixed
preprocessing step that precedes the agglomerative merge step (as long as it is independent of ξ
1

There have been several papers that provide theoretical guarantees for clustering under this family of objective functions for other values of p. For instance, see Gupta and Tangwongsan’s work [23] which provides a O(p)
approximation algorithm when p < log n and Bateni et al.’s work [8] which studies distributed clustering algorithms.

9

Algorithm 3 Agglomerative algorithm with dynamic programming
Input: Clustering instance V = (V, d), merge function ξ, pruning function Ψ.
1: Agglomerative merge step to build a cluster tree T according to ξ:
• Start with n singleton sets {v} for each v ∈ V .
• Iteratively merge the two sets A and B which minimize ξ(A, B) until a single set remains.
• Let T denote the cluster tree corresponding to the sequence of merges.
2: Dynamic programming to find the k-pruning of T minimizing Ψ :
0
• For each node
 T , find the best k -pruning of the subtree rooted at T in T , denoted by
CT,k0 , cT,k0 according to following dynamic programming recursion:
(

minc∈T Ψ ({T }, c)
if k 0 = 1,

Ψ CT,k0 , cT,k0 =
mini0 ∈[k0 −1] Ψ CTL ,i0 ∪ CTR ,k0 −i0 , cTL ,i0 ∪ cTR ,k0 −i0
otherwise.
where TL and TR denote the left and right children of T , respectively.
Output: The best k-pruning of the root node Troot of T .

Figure 3: A schematic for a class of agglomerative clustering algorithms with dynamic programming.

10

and Ψ), therefore our analysis carries over to algorithms such as in [6].

3.1

Linkage-based merge functions

We now define three infinite families of merge functions and provide sample complexity bounds
for these families with any fixed but arbitrary pruning function. The families A1 and A3 consist
of merge functions ξ(A, B) that depend on the minimum and maximum of all pairwise distances
between A and B. The second family, denoted by A2 , is a richer class which depends on all pairwise
distances. All classes are parameterized by a single value α.
(
)
1/α
A1 =
min (d(u, v))α + max (d(u, v))α
α ∈ R ∪ {∞, −∞} ,
u∈A,v∈B

u∈A,v∈B



1/α




X
 1
A2 = 
(d(u, v))α 
α ∈ R ∪ {∞, −∞} ,


 |A||B| u∈A,v∈B



A3 = α min d(u, v) + (1 − α) max d(u, v) α ∈ [0, 1] .
u∈A,v∈B

u∈A,v∈B

For i ∈ {1, 2, 3}, we define Ai (α) as the merge function in Ai defined by α. A1 and A3 define
spectra of merge functions ranging from single-linkage (A1 (−∞) and A3 (1)) to complete-linkage
(A1 (∞) and A3 (0)). A2 defines a richer spectrum which includes average-linkage in addition to
single- and complete-linkage. Given a pruning function Ψ, we denote (Ai (α), Ψ) as the algorithm
which builds a cluster tree using Ai (α), and then prunes the tree according to Ψ. To reduce
notation, when Ψ is clear from context, we often refer to the algorithm (Ai (α), Ψ) as Ai (α) and
the set of algorithms {(Ai (α), Ψ) | α ∈ R ∪ {−∞, ∞}} as Ai . For example, when the cost function
is Φ(p) , then we always set Ψ to minimize the Φ(p) objective, so the pruning function is clear from
context.
Recall that for a given class of merge functions and a cost function (a generic clustering objective
Φ), our goal is to learn a near-optimal value of α in expectation over an unknown distribution of
clustering instances. One might wonder if there is some α that is optimal across all instances, which
would preclude the need for a learning algorithm. In Theorem 4, we prove that this is not the case;
for each p ∈ [1, ∞) ∪ {∞} and i ∈ {1, 2, 3}, given any α, there exists a distribution over clustering
instances for which Ai (α) is the best algorithm in Ai with respect to Φ(p) . Crucially, this means
that even if the algorithm designer sets p to be 1, 2, or ∞ as is typical in practice, the optimal
choice of the tunable parameter α could be any real value. The optimal value of α depends on the
underlying, unknown distribution, and must be learned, no matter the value of p.
To formally describe this result, we set up notation similar to Section 2. Let V denote the
set of all clustering instances over at most n points. With a slight abuse of notation, we will use
Φ(Ai (α),Ψ) (V) to denote the abstract cost of the clustering produced by (Ai (α), Ψ) on the instance
V.
Theorem 4. For i ∈ {1, 2, 3} and a permissible
value iof α for Ahi , there exists
h
i a distribution D
(p)
(p)
over clustering instances V such that EV∼D ΦAi (α) (V) < EV∼D ΦAi (α0 ) (V) for all permissible
values of α0 6= α for Ai .

For all omitted proofs in this section, see Appendix C. Now for an arbitrary objective function
Φ and arbitrary pruning function Ψ, we analyze the complexity of the classes

HA1 ×{Ψ},Φ = Φ(A1 (α),Ψ) : V → R≥0 α ∈ R ∪ {∞, −∞} ,
11


HA2 ×{Ψ},Φ = Φ(A2 (α),Ψ) : V → R≥0 α ∈ R ∪ {∞, −∞} , and

HA3 ×{Ψ},Φ = Φ(A3 (α),Ψ) : V → R≥0 α ∈ [0, 1] .

We drop the subscript Φ from HAi ×{Ψ},Φ when the objective function is clear from context. Furthermore, in our analysis we will often fix a tuple V = (V, d) and use the notation ΦAi ,V (α) to
analyze how ΦAi (α) (V) changes as a function of α. We start with A1 and A3 .




Theorem 5. For all objective functions Φ(p) , Pdim HA1 ,Φ(p) = Θ(log n) and Pdim HA3 ,Φ(p) =

2 and all pruning functions Ψ, Pdim H
Θ(log n). For all other objective
functions
Φ
=
A
×{Ψ},Φ
1

O(log n) and Pdim HA3 ×{Ψ},Φ = O(log n).
This theorem follows from Lemma 7 and Lemma 8. We begin with the following structural
lemma, which will help us prove Lemma 7.
Lemma 6. ΦA1 ,V : R ∪ {−∞, ∞} → R>0 is made up of O(n8 ) piecewise constant components.
Proof sketch. Note that for α 6= α0 , the clustering returned by A1 (α) and the associated cost are
both identical to that of A1 (α0 ) if both the algorithms construct the same merge tree. As we range
α across R and observe the run of the algorithm for each α, at what values of α do we expect A1 (α)
to produce different merge trees? To answer this, suppose that at some point in the run of algorithm
A1 (α), there are two pairs of subsets of V , (A, B) and (X, Y ), that could potentially merge. There
exist eight points p, p0 ∈ A, q, q 0 ∈ B, x, x0 ∈ X, and y, y 0 ∈ Y such that the decision of which pair
to merge depends on the sign of ((d(p, q))α + d(p0 , q 0 )α )1/α − ((d(x, y))α + d(x0 , y 0 )α )1/α . Using a
consequence of Rolle’s Theorem, which we provide in Appendix C, we show that the sign of the
above expression as a function of α flips at most four times across R. Since each merge decision
is defined by eight points, iterating over all (A, B) and (X, Y ) it follows that we can identify all
O(n8 ) unique 8-tuples of points which correspond to a value of α at which some decision flips. This
means we can divide R ∪ {−∞, ∞} into O(n8 ) intervals over each of which the merge tree, and
therefore the output of ΦA1 ,V (α), is fixed.
In Appendix C, we show a corresponding statement for A3 (Lemma 18). These lemmas allow
us to upper bound the pseudo-dimension of HA1 , Φ and HA1 , Φ by O(log n) in a manner similar to
Lemma 3, where we prove a pseudo-dimension upper bound on the class of s-linear SDP rounding
algorithms. Thus we obtain the following lemma.
Lemma 7. For any Φ, Pdim(HA1 , Φ) = O(log n) and Pdim(HA3 , Φ) = O(log n).
Next, we give lower bounds for the pseudo-dimension of the two classes.




Lemma 8. For any objective function Φ(p) , Pdim HA1 ,Φ(p) = Ω(log n) and Pdim HA3 ,Φ(p) =
Ω(log n).
Proof sketch. We give
a general proof outline that applies to both classes. Let b ∈ {1, 3}. We
 (1)
construct a set S = V , . . . , V (m) of m = log n − 3 clustering instances that can be shattered by
Ab . There are 2m = n/8 possible labelings for this set, so we need to show there are n/8 choices
of α such that each of these labelings is achievable by some Ab (α) for some α. The crux of the
proof lies in showing that given a sequence α0 < α1 < · · · < αn0 < αn0 +1 (where n0 = Ω(n)), it is
2

Recall that although k-means, k-median, and k-center are the most popular choices, the algorithm designer
can use other objective functions such as the distance to the ground truth clustering (which we discuss further in
Section 3.2).

12

Algorithm 4 An algorithm for finding an empirical cost minimizing algorithm in A1 or A3

Input: Sample S = V (1) , . . . , V (m) , b ∈ {1, 3}

1: Let T = ∅. For each sample V (i) = V (i) , d(i) ∈ S, and for each ordered set of 8 points
{v1 , . . . , v8 } ⊆ V (i) , solve for α (if a solution exists) in the following equation and add the
solutions to T : d(v1 , v2 )α + d(v3 , v4 )α = d(v5 , v6 )α + d(v7 , v8 )α .
If b = 1 :
d(v1 , v2 )α + d(v3 , v4 )α = d(v5 , v6 )α + d(v7 , v8 )α .
If b = 3 : αd(v1 , v2 ) + (1 − α)d(v3 , v4 ) = αd(v5 , v6 ) + (1 − α)d(v7 , v8 ).
Order the elements of set T ∪ {−∞, +∞} as α1 < . . . < α|T | . For each 0 ≤ i ≤ |T |, pick an
arbitrary α in the interval (αi , αi+1 ) and run Ab (α) on P
all clustering instances in S to compute
P
V∈S ΦAb (α) (V). Let α̂ be the value which minimizes
V∈S ΦAb (α) (V).
Output: α̂
2:

possible to design an instance V = (V, d) over n points and choose a witness r such that ΦAb (α) (V)
alternates n0 /2 times above and below r as α traverses the sequence of intervals (αi , αi+1 ).
Here is a high level description of our construction. There will be two “main” points, a and a0
in V . The rest of the points are defined in groups of 6: (xi , yi , zi , x0i , yi0 , zi0 ), for 1 ≤ i ≤ (n − 2)/6.
We will define the distances between all points such that initially for all Ab (α), xi merges to yi
to form the set Ai , and x0i merges to yi0 to form the set A0i . As for (zi , zi0 ), depending on whether
α < αi or not, Ab (α) merges the points zi and zi0 with the sets Ai and A0i respectively or vice versa.
This means that there are (n − 2)/6 values of α such that Ab (α) has a unique behavior in S
the merge
step. Finally,Sfor all α, sets Ai merge to {a}, and sets A0i merge to {a0 }. Let A = {a} ∪ i Ai and
A0 = {a0 } ∪ i A0i . There will be (n − 2)/6 intervals (αi , αi+1 ) for which Ab (α) returns a unique
partition {A, A0 }. By carefully setting the distances, we cause the cost Φ({A, A0 }) to oscillate above
and below a specified value r along these intervals.
The upper bound on the pseudo-dimension implies a computationally efficient and sample
effi

cient learning algorithm for Ai for i ∈ {1, 3}. See Algorithm 4. First, we know that m = Õ (H/)2
samples are sufficient to (, δ)-learn the optimal algorithm in Ai . Next, as a consequence of Lemmas 6 and 18, the range of feasible values of α can be partitioned into O(mn8 ) intervals, such that
the output of Ai (α) is fixed over the entire set of samples on a given interval. Moreover, these
intervals are easy to compute. Therefore, a learning algorithm can iterate over the set of intervals,
and for each interval I, choose an arbitrary α ∈ I and compute the average cost of Ai (α) evaluated
on the samples. The algorithm then outputs the α that minimizes the average cost.
Theorem 6. Let Φ be a clustering objective and let Ψ be a pruning function
computable in poly

H 2
1
log n + log δ , and a value i ∈ {1, 3},
nomial time. Given an input sample of size m = O

Algorithm 4 (, δ)-learns the class Ai × {Ψ} with respect to the cost function Φ and it is computationally efficient.
Proof.
Algorithm 4 finds the empirically best α by solving for the O(mn8 ) discontinuities of
P
V∈S ΦAb (α) (V) and evaluating the function over the corresponding intervals, which are guaranteed to be constant by Lemmas 6 and 18. Therefore, we can pick any arbitrary α within each
interval to evaluate the empirical cost over all samples, and find the empirically best α. This can be
done in polynomial time because there are polynomially many intervals, and the runtime of Ai (α)
on a given instance is polynomial time.
13

Then it follows from Theorem 5 that m samples are sufficient for Algorithm 4 to (, δ)-learn the
optimal algorithm in Ai for i ∈ {1, 3}.
Now we turn to A2 . We obtain the following bounds on the pseudo-dimension.
Theorem 7. For objective functions Φ(p) , Pdim(HA2 ,Φ(p) ) = Θ(n). For all other objective functions

Φ and all pruning functions Ψ, Pdim HA2 ×{Ψ},Φ = O(n).
This theorem follows from Lemmas 9 and 10.


Lemma 9. For all objective functions Φ and all pruning functions Ψ, Pdim HA2 ×{Ψ},Φ = O(n).

Proof. Recall the proof of Lemma 7. We are interested in studying how the merge trees constructed
by A2 (α) changes over m instances as we increase α over R. To do this, as in the proof of Lemma 7,
we fix an instance and consider two pairs of sets A, B and X, Y that could be potentially merged.
Now, P
the decision to merge one pair
is determined by the sign of the expression
P before the other
1
1
α −
α . First note that this expression has O(n2 )
(d(p,
q))
(d(x,
y))
p∈A,q∈B
x∈X,y∈Y
|A||B|
|X||Y |
terms, and by a consequence of Rolle’s
which we prove in Appendix C, it has O(n2 ) roots.
 Theorem

Therefore, as we iterate over the O (3n )2 possible pairs (A, B) and (X, Y ), we can determine

O 32n unique expressions each with
O(n2 ) values of α at which the corresponding decision flips.

Thus we can divide R into O n2 32n intervals over each of which the output of ΦA3 ,V (α) is fixed.

In fact, suppose S = V (1) , . .. , V (m) is a shatterable set of size m with witnesses r1 , . . . , rm . We
can divide R into O mn2 32n intervals over each of which ΦA2 ,V (i) (α) is fixed for all i ∈ [m] and

therefore the corresponding labeling of S according to whether or not ΦA2 (α) V (i) ≤ ri is fixed as
well for all i ∈ [m]. This means that HA2 can achieve only O mn2 32n labelings, which is at least
2m for a shatterable set S, so m = O(n).


Lemma 10. For all objective functions Φ(p) , Pdim HA2 ,Φ(p) = Ω(n).

Proof sketch. The crux of the proof is to show that there exists a clustering instance V over n
points, a witness r, and a set of α’s 1 = α0 < α1 < · · · < α2N < α2N +1 = 3, where N = b(n − 8)/4c,
such that ΦA2 ,V (α) oscillates above and below r along the sequence of intervals (αi , αi+1 ). We
finish the proof in a manner similar to Lemma 8 by constructing instances with fewer oscillations.
To construct V, first we define two pairs of points which merge together regardless of the value
of α. Call these merged pairs A and B. Next, we define a sequence of points pi and qi for 1 ≤ i ≤ N
with distances set such that merges involving points in this sequence occur one after the other. In
particular, each pi merges with one of A or B while qi merges with the other. Therefore, there
are potentially 2N distinct merge trees which can be created. Using induction to precisely set the
distances, we show there are 2N distinct values of α, each corresponding to a unique merge tree,
thus enabling A2 to achieve all possible merge tree behaviors. Finally, we carefully add more points
to the instance to control the oscillation of the cost function over these intervals as desired.
In Appendix C.1, we prove more results about A2 assuming a natural restriction on the instance
space V. In particular, we show the pseudo-dimension can be drastically reduced if the number of
unique distances in each problem instance is not too large. In Appendix C.2, we analyze classes
of algorithms that interpolate between A1 and A2 . A summary of results for all of our algorithm
classes can be found in Table 2.

14

3.2

Dynamic programming pruning functions

In the previous section, we analyzed several classes of linkage-based merge functions assuming a
fixed pruning function in the dynamic programming step of the standard linkage-based clustering
algorithm, i.e. Step 2 of Algorithm 3. In this section, we analyze an infinite class of dynamic programming pruning functions and derive comprehensive sample complexity guarantees for learning
the best merge function and pruning function in conjunction.
By allowing an application-specific choice of a pruning function, we significantly generalize
the standard linkage-based clustering algorithm framework. Recall that in the algorithm selection
model, we instantiated the cost function to be a generic clustering objective Φ. In the standard
clustering algorithm framework, where Φ is defined to be any general Φ(p) (which include objectives
like k-means), the best choice of the pruning function for the algorithm selector is Φ(p) itself as it
would return the optimal pruning of the cluster tree for that instantiation of cost. However, when
the goal of the algorithm selector is, for example, to provide solutions that are close to a ground
truth clustering for each problem instance, the best choice for the pruning function is not obvious.
In this case, we assume that the learning algorithm’s training data consists of clustering instances
that have been labeled by an expert according to the ground truth clustering. For example, this
ground truth clustering might be a partition of a set of images based on their subject, or a partition
of a set of proteins by function. On a fresh input data, we no longer have access to the expert or
the ground truth, so we cannot hope to prune a cluster tree based on distance to the ground truth.3
Instead, the algorithm selector must empirically evaluate how well pruning according to alternative objective functions, such as k-means or k-median, approximate the ground truth clustering
on the labeled training data. In this way, we instantiate cost to be the distance of a clustering
from the ground truth clustering. We guarantee that the empirically best pruning function from
a class of computable objectives is near-optimal in expectation over new problem instances drawn
from the same distribution as the training data. Crucially, we are able to make this guarantee even
though it is not possible to compute the cost of the algorithm’s output on these fresh instances
because the ground truth clustering is unknown.
Along these lines, we can also handle the case where the training data consists of clustering
instances, each of which has been clustered according to an objective function that is NP-hard
to compute. In this scenario, our learning algorithm returns a pruning objective function that is
efficiently computable and which best approximates the NP-hard objective on the training data,
and therefore will best approximate the NP-hard objective on future data. Hence, in this section,
we analyze a richer class of algorithms defined by a class of merge functions and a class of pruning
functions. The learner now has to learn the best combination of merge and pruning functions from
this class.
To define this more general class of agglomerative clustering algorithms, let A denote a generic
class of linkage-based merge functions (such as any of the classes Ai defined in Sections 3.1 and C)
parameterized by α. We also
define a rich class of center-based clustering objectives for the dynamic
 (p)
programming step: F = Ψ | p > 0 where Ψ(p) takes as input a partition C = {C1 , C2 , . . . , Ck0 }
of n0 points and a set of centers c = {c1 , c2 , . . . , ck0 } such that ci ∈ Ci . The function Ψ(p) is defined
3
If Φ is the distance to ground truth clustering, then Φ cannot be directly measured when the clustering algorithm
is used on new data. However, we assume that the learning algorithm has access to training data which consists of
clustering instances labeled by the ground truth clustering. The learning algorithm uses this data to optimize the
parameters defining the clustering algorithm family. With high probability, on a new input drawn from the same
distribution as the training data, the clustering algorithm will return a clustering that is close to the unknown ground
truth clustering.

15

Figure 4: Cluster tree corresponding to Table 1.

1
2
3

Clusters
Centers
Clusters
Centers
Clusters
Centers

A

B

C

D

E

A, B

D, E

A, B, C

A, B, C, D, E

{A}
{A}

{B}
{B}

{C}
{C}

{D}
{D}

{E}
{E}

{A, B}
{A}
{A}, {B}
{A}, {B}

{D, E}
{E}
{D}, {E}
{D}, {E}

{A, B, C}
{C}
{A, B}, {C}
{A, C}
{A}, {B}, {C}
{A, B, C}

{A, B, C, D, E}
{C}
{A, B, C}, {D, E}
{C, E}
{A, B}, {C}, {D, E}
{A, C, E}

Table 1: Example dynamic programming table corresponding to the cluster tree in Figure 4 for
k = 3.
such that
(p)

Ψ

(C, c) =

sX X
p

(d(q, ci ))p .

(2)

Ci ∈C q∈Ci

Note that the definition of Ψ(p) is identical to Φ(p) , but we use this different notation so as not to
confuse the dynamic programming function with the clustering objective function. Let A(α) denote
(p)
the α-linkage merge function from A and F(p) denote the pruning function
 Ψ . Earlier, for an
abstract objective Φ, we bounded the pseudodimension of HA×{Ψ},Φ = Φ(A(α),Ψ) : V → R≥0 ,
where Φ(A(α),Ψ) (V) denoted the cost of the clustering produced by building the cluster tree on V
using the merge function A(α) and then pruning the tree using a fixed pruning function Ψ. Now, we
are interested in doubly-parameterized algorithms of the form (A(α), F(p)) which uses the merge
function A(α) to build a cluster tree and then use the pruning function F(p) to prune it. To
analyze the resulting class of algorithms,
which we will denote by A × F, we have to bound the

pseudodimension of HA×F ,Φ = Φ(A(α),F (p)) : V → R≥0 p > 0 .
Recall that in order to show that pseudodimension of HA×{Ψ},Φ is upper bounded by dHA , we
proved that,
given

 a sample of m clustering instances over n nodes, we can split the real line into at
dHA
most O m2
intervals such that as α ranges over a single interval, the m cluster trees returned
by the α-linkage merge function are fixed. To extend this analysis to HA×F ,Φ , we first prove a
similar fact in Lemma 11. Namely, given a single cluster tree, we can split the real line into a fixed
number of intervals such that as p ranges over a single interval, the pruning returned by using the
function Ψ(p) is fixed. We then show in Theorem 8 how to combine this analysis of the rich class
of dynamic programming algorithms with our previous analysis of the possible merge functions to
obtain a comprehensive analysis of agglomerative algorithms with dynamic programming.
We visualize the dynamic programming step of Algorithm 3 with pruning function Ψ(p) using
a table such as Table 1, which corresponds to the cluster tree in Figure 4. Each row of the
table corresponds to a sub-clustering value k 0 ≤ k, and each column corresponds to a node of the
corresponding cluster tree. In the column corresponding to node T and the row corresponding to
the value k 0 , we fill in the cell with the partition of
T into k 0 clusters that corresponds to the best

k 0 -pruning of the subtree rooted at T , CT,k0 , cT,k0 as defined in Step 2 of Algorithm 3.
16

Figure
5: Partition of the positive real line based on whether or not
P
p
q∈T (d(q, v2 )) as p ranges R>0 .

P

p
q∈T (d(q, v1 ))

≤

Lemma 11. Given a cluster tree T for a clustering instance V = (V, d) of n points, the positive
real line can be partitioned into a set I of O(n2(k+1) k 2k ) intervals such that for any I ∈ I, the
cluster tree pruning according to Ψ(p) is identical for all p ∈ I.
Proof. To prove this claim, we will examine the dynamic programming (DP) table corresponding
to the given cluster tree and the pruning function Ψ(p) as p ranges over the positive real line. As
the theorem implies, we will show that we can split the positive real line into a set of intervals so
that on a fixed interval I, as p ranges over I, the DP table under Ψ(p) corresponding to the cluster
tree is invariant. No matter which p ∈ I we choose, the DP table under Ψ(p) will be identical, and
therefore the resulting clustering will be identical. After all, the output clustering is the bottomright-most cell of the DP table since that corresponds to the best k-pruning of the node containing
all points (see Table 1 for an example). We will prove that the total number of intervals is bounded
by O(n2(k+1) k 2k ).
We will prove this lemma using induction on the row number k 0 of the DP table. Our induc0
tive
will be the following. The positive real line can be partitioned into a set I (k ) of

 hypothesis
Q 0
0
0
0
O n2 kj=1 n2 j intervals such that for any I (k ) ∈ I (k ) , as p ranges over I (k ) , the first k 0 rows of
the DP table corresponding to Ψ(p) are
Notice
that this means that the positive real line

 invariant.

Qk
2
2
2
= O n2(k+1) k 2k intervals such that for any
can be partitioned into a set I of O n
j=1 n j
I ∈ I, as p ranges over I, the DP table corresponding to Ψ(p) is invariant. Therefore, the resulting
output clustering is invariant as well.

Base case (k 0 = 1). Let p be a positive real number. Consider the first row of the DP table
corresponding to Ψ(p) . Recall that each column in the DP table corresponds to a node T in the
clustering tree where T ⊆ V . In the first row of the DP table and the column corresponding to node
T , we fill in the cell with the single node T and the point c ∈ T which minimizes Ψ(p) ({T }, {c}) =
P
p
q∈T (d(q, c)) . The only thing that might change as we vary p is the center minimizing this
objective.
Let v1 and v2 be two points in T . The point v1 is a better candidate for the center of T
than v2 if and only if Ψ(p) ({T }, {v1 }) ≤PΨ(p) ({T }, {v2 }) which
means that Ψ(p) ({T }, {v1 }) −
P
(p)
p
p
Ψ
0, or in other words,
q∈T (d(q, v1 )) −
q∈T (d(q, v2 )) ≤ 0. The equation
P ({T }, {v2 })p ≤ P
p
q∈T (d(q, v1 )) −
q∈T (d(q, v2 )) has at most 2|T | zeros, so there are at most 2|T | + 1 intervals
I1 , . . . , It which partition the positive real line such that for any Ii , as p ranges over Ii , whether or
not Ψ(p) ({T }, {v1 }) ≤ Ψ(p) ({T }, {v2 }) is fixed. For example, see Figure 5. Every pair of points in T
similarly partitions the positive real line into 2|T | + 1 intervals. If we merge all |T |2 /2 partitions —
2
one partition for each pair of points in T — then we are left with at most |T2| · 2|T | + 1 = |T |3 + 1
intervals I1 , . . . , Iw partitioning the positive real line such that for any Ii , as p ranges over Ii , the
point v ∈ T which minimizes Ψ(p) ({T }, {v}) is fixed.
17

Since T is arbitrary, we can thus partition the real line for each node T 0 in the cluster tree.
Again, this partition defines the center of the cluster T 0 as p ranges
Pover the3 positive real4 line. If we
merge the partition for every node T ∈ T , then we are left with
T ∈T |T | + 1 = O(n ) intervals
I1 , . . . , I` such that as p ranges over any one interval Ii , the centers of all nodes in the cluster tree
are fixed. In other words, for each T , the point vi ∈ T which minimizes Ψ(p) ({T }, {vi }) is fixed.
Of course, this means that the first row of the DP table is fixed as well. Therefore, the inductive
hypothesis holds for the base case.
Inductive step. Consider the k 0 th row of the DP table. We knowfrom the inductive
hypothesis
Qk0 −1 2 2 
0 −1)
(k
2
that the positive real line can be partitioned into a set I
of O n
intervals such
j=1 n j
0

0

0

that for any I (k −1) ∈ I (k −1) , as p ranges over I (k −1) , the first k 0 − 1 rows of the DP table
corresponding to Ψ(p) are invariant.
0
0
Fix some interval I (k −1) ∈ I (k −1) . Let T be a node in the cluster tree T and let TL and
TR be the left and right children of T in T respectively. Notice that the pruning which belongs in the cell in the ith row and the column corresponding to T does not depend on the other
cells in the ith row, but only on the cells in rows 1 through i − 1. In particular, the pruning
which belongs in this cell depends on the
inequalities defining which i0 ∈ {1, . . . , k 0 − 1} minimizes

Ψ(p) CTL ,i0 ∪ CTR ,k0 −i0 , cTL ,i0 ∪ cTR ,k0 −i0 . We will now examine this objective function and show
that the minimizing i0 , and therefore the optimal pruning, only changes a small number of times
0
as p ranges over I (k −1) .
For an arbitrary i0 ∈ {1, . . . , k 0 − 1}, since i0 and k 0 − i0 are both strictly less than k 0 , the best
0
i -pruning of TL (CTR ,i0 , cTR ,i0 ) is exactly the entry in the i0 th row of the DP table and the column
corresponding to TL . Similarly, the best k 0 − i0 -pruning of TR , (CTR ,k0 −i0 , cTR ,k0 −i0 ) is exactly the
entry in the k 0 − i0 th row of the DP table and the column corresponding to TR . Crucially, these
0
entries do not change as we vary p ∈ I (k −1) , thanks to the inductive hypothesis.
0
Therefore, for any i0 , i00 ∈ {1, . . . , k 0 − 1}, we know that for all p ∈ I (k −1) , the k 0 -pruning of
T corresponding to the combination of the best i0 -pruning of TL and the best k 0 − i0 pruning of
TR is fixed and can be denoted as (C 0 , c0 ). Similarly, the k 0 -pruning of T corresponding to the
combination of the best i00 -pruning of TL and the best k 0 − i00 pruning of TR is fixed and can
0
be denoted as (C 00 , c00 ). Then, for any p ∈ I (k −1) , (C 0 , c0 ) is a better pruning than (C 00 , c00 ) if
and only if Ψ(p) (C 0 , c0 ) ≤ Ψ(p) (C00 , c00 ). In order to analyze this inequality,
let us consider
p the
p
p
p
equivalent inequality Ψ(p) (C 0 , c0 ) ≤ Ψ(p) (C 00 , c00 ) i.e., Ψ(p) (C 0 , c0 ) − Ψ(p) (C 00 , c00 ) ≤ 0.
Now, to expand this expression let C 0 = {C10 , C20 , . . . , Ck0 0 } and c0 = {c01 , c02 . . . , c0k0 } and similarly
C 00 = {C100 , C200 , . . . , Ck0 0 } and c00 = {c001 , c002 . . . , c00k0 }. Then, this inequality can then be written as,
0

k X
X

i=1 q∈Ci0

The equation
0

Pk0 P
i=1

q∈Ci0

p
d(q, c0i )

(d(q, c0i ))p −

0

−

k X
X

i=1 q∈Ci00

Pk 0 P
i=1

q∈Ci00

d(q, c00i )

p

≤ 0.

(d(q, c00i ))p has has at most 2n zeros as p
0

ranges over I (k −1) . Therefore, there are at most 2n + 1 subintervals partitioning I (k −1) such that
as p ranges over one subinterval, the smaller of Ψ(p) (C 0 , c0 ) and Ψ(p) (C 00 , c00 ) is fixed. In other
words, as p ranges over one subinterval, either the combination of the best i0 -pruning of T ’s left
child and the best (k 0 − i0 )-pruning of T ’s right child is better than the combination of the best
i00 -pruning of T ’s left child with the best (k − i00 )-pruning of T ’s right child, or vice versa. For
all pairs i0 , i00 ∈ {1, . . . , k 0 − 1}, we can similarly partition I into at most 2n + 1 subintervals
0
defining the better of the two prunings. If we merge all (k 0 − 1)2 /2 partitions of I (k −1) , we have
0
2
0
(k −1)
· 2n + 1 = (k 0 − 1)2 n + 1 total subintervals of I (k −1) such that as p ranges over a single
2
18

subinterval,
argmini0 ∈{1,...,k0 −1} Ψ(p) CTL ,i0 ∪ CTR ,k0 −i0 , cTL ,i0 ∪ cTR ,k0 −i0



is fixed. Since these equations determine the entry in the ith row of the DP table and the column
corresponding to the node T , we have that this entry is also fixed as p ranges over a single subinterval
0
in I (k −1) .
0
The above partition of I (k −1) corresponds to only a single cell in the k 0 th row of the DP table.
Considering the k 0 th row of the DP table as a whole, we must fill in at most 2n entries, since there
are at most 2n columns of the DP table. For each column, there is a corresponding partition of
0
I (k −1) such that as p ranges over a single subinterval in the partition, the entry in the k 0 th row
0
and that column is fixed. If we merge all such partitions, we are left with a partition of I (k −1)
consisting of at most 2n2 (i − 1)2 + 1 intervals such that as p ranges over a single interval, the entry
0
in every column of the k 0 th row is fixed. As these intervals are subsets of I (k −1) , by assumption,
the first k 0 − 1 rows of the DP table are also fixed. Therefore, the first k 0 rows are fixed.
0
0
0
To recap, we fixed an interval I (k −1) such that as p ranges overI (k −1) , the first
 k − 1 rows of
Q
0 −1
k
the DP table are fixed. By the inductive hypothesis, there are O n2 j=1 n2 j 2 such intervals.
0

Then, we showed that I (k −1) can be partitioned into 2n2 (k 0 − 1)2 + 1 intervals such that for any
(k0 )
(k0 )
0
one subinterval
 IQ 0 , as p ranges over I , the first k rows of the DP table are fixed. Therefore,
k
there are O n2 j=1 n2 j 2 total intervals such that as p ranges over a single interval, the first k 0
rows of the DP table are fixed.
Aggregating this analysis over all k rows of the DP table, we have that there are
!
k


Y
2
= O n2(k+1) k 2k
O n2
n2 k 0
k=1

intervals such that the entire DP table is fixed so long as p ranges over a single interval.
We are now ready to prove our main theorem in this section.


Theorem 8. Given m clustering instances, suppose there are O m · 2O(dHA ) intervals that partition the domain of α such that as α ranges over a single interval, the m cluster trees returned
by the α-linkage merge function from A are fixed. Then, for all sets of m samples S ∼ Dm ,
P dim (HA×F ,Φ ) = O (dHA + k log n).
Proof. Let S be a set of clustering instances. Fix a single interval of α (as shown along the horizontal
axis in Figure 6) where the set of cluster trees returned by the α-linkage merge function from A
is fixed across all samples. We know from Lemma 11 that we can split the real line into a fixed
number of intervals such that as p ranges over a single interval (as shown along the vertical axis
in Figure 6), the dynamic programming (DP) table is fixed for all the samples, and therefore the
resulting set of clusterings
is fixed. In particular, for a fixed α interval, each of the m samples has

its own O n2(k+1) k 2k intervals of p, and when we merge them, we are left with O mn2(k+1) k 2k
intervals such that as p ranges over a single interval, each DP table for each sample
is fixed,
and


therefore the resulting clustering for each sample is fixed. Since there are O m2dHA such α



intervals, each inducing O mn2(k+1) k 2k such p intervals in total, we have O 2dHA m2 n2(k+1) k 2k
cells in R2 such that if (α, p) is in one fixed cell, the resulting
clustering across
all samples is


dHA 2 2(k+1) 2k
m
fixed. If HA×F shatters S, then it must be that 2 = O 2
m n
k , which means that

 
m = O log 2dHA n2(k+1) k 2k
= O (dHA + k log n).
19





O mn2(k+1) k 2k intervals of p
for a fixed α interval

p>0

Fixed set of pruned
cluster trees on samples S
in each cell

α
Fixed set of cluster trees
on samples S
for all α in this interval.
O(m · 2O(dHA ) ) intervals of α

Figure 6: Illustration of the partition of the parameter space as described in the proof of Theorem 9.


Theorem 9. Given a sample of size m = O (H/)2 (dHA + log n + log(1/δ)) and a clustering
objective Φ, it is possible to (, δ)-learn the class of algorithms A×F with respect to the cost function
Φ. Moreover, this procedure is efficient if the following conditions hold:
1. k is constant, which ensures that the partition of p values is polynomial in n.
2. 2dHA is polynomial in n, which ensures that the partition of α values is polynomial in n.
3. It is possible to efficiently compute the partition of α into intervals so that on a single interval
I, for all α ∈ I, the m cluster trees returned by α-linkage performed on S are fixed.
Proof. A technique for finding the empirically best algorithm from A × F follows naturally from
Lemma 11; we partition the range of feasible values of α as described in Section 3.1, and for each
resulting interval of α, we find the fixed set of cluster trees on the samples. We then partition
the values of p as discussed in the proof for Lemma 11. For each interval of p, we use Ψ(p) to
prune the trees and determine the fixed empirical cost corresponding to that interval of p and
α. This is illustrated in Figure 6. Iterating over all partitions of the parameter space, we can
find parameters with the best empirical cost. In Theorem 8, we use Lemma 11 to show that
Pdim(HA×F ,Φ ) = O (dHA + k log n) and thus arrive at our sample complexity bound when k is
constant.

4

Discussion and open questions

In this work, we show how to learn near-optimal algorithms over several infinite, rich classes of
SDP rounding algorithms and agglomerative clustering algorithms with dynamic programming.
We provide computationally efficient and sample efficient learning algorithms for many of these
problems and we push the boundaries of learning theory by developing techniques to compute the
pseudo-dimension of intricate, multi-stage classes of IQP approximation algorithms and clustering
algorithms. We derive tight pseudo-dimension bounds for the classes we study, which lead to strong

20

sample complexity guarantees. We hope that our techniques will lead to theoretical guarantees in
other areas where empirical methods for algorithm configuration have been developed.
There are many open avenues for future research in this area. In this work, we focused on
algorithm families containing only computationally efficient algorithms. However, oftentimes in
empirical AI research, the algorithm families in question contain procedures that are too slow to
run to completion on many training instances. In this situation, we would not be able to determine
the exact empirical cost of an algorithm on the training set. Could we still make strong, provable
guarantees for application-specific algorithm configuration in this scenario? This work also leaves
open the potential for data-dependent bounds over well-behaved distributions, such as those over
clustering instances satisfying some form of stability, be it approximation stability, perturbation
resilience, or so on.
Acknowledgments. This work was supported in part by grants NSF-CCF 1535967, NSF CCF1422910, NSF IIS-1618714, a Sloan Fellowship, a Microsoft Research Fellowship, a NSF Graduate
Research Fellowship, a Microsoft Research Women’s Fellowship, and a National Defense Science
and Engineering Graduate (NDSEG) fellowship.
We thank Sanjoy Dasgupta, Anupam Gupta, and Ryan O’Donnell for useful discussions.

References
[1] Noga Alon, Konstantin Makarychev, Yury Makarychev, and Assaf Naor. Quadratic forms on
graphs. Inventiones mathematicae, 163(3):499–522, 2006.
[2] Martin Anthony and Peter L Bartlett. Neural network learning: Theoretical foundations.
Cambridge University Press, 2009.
[3] Pranjal Awasthi, Maria-Florina Balcan, and Konstantin Voevodski. Local algorithms for interactive clustering. In Proceedings of the International Conference on Machine Learning (ICML),
pages 550–558, 2014.
[4] Pranjal Awasthi, Avrim Blum, and Or Sheffet. Center-based clustering under perturbation
stability. Information Processing Letters, 112(1):49–54, 2012.
[5] Maria-Florina Balcan, Nika Haghtalab, and Colin White. k-center clustering under perturbation resilience. In Proceedings of the Annual International Colloquium on Automata, Languages, and Programming (ICALP), 2016.
[6] Maria-Florina Balcan and Yingyu Liang. Clustering under perturbation resilience. SIAM
Journal on Computing, 45(1):102–155, 2016.
[7] Afonso S. Bandeira, Nicolas Boumal, and Vladislav Voroninski. On the low-rank approach for
semidefinite programs arising in synchronization and community detection. In Proceedings of
the Conference on Learning Theory (COLT), pages 361–382, 2016.
[8] MohammadHossein Bateni, Aditya Bhaskara, Silvio Lattanzi, and Vahab Mirrokni. Distributed balanced clustering via mapping coresets. In Proceedings of the Annual Conference
on Neural Information Processing Systems (NIPS), pages 2591–2599, 2014.
[9] Ahron Ben-Tal and Arkadi Nemirovski. Lectures on modern convex optimization: analysis,
algorithms, and engineering applications, volume 2. Siam, 2001.

21

[10] William Brendel and Sinisa Todorovic. Segmentation as maximum-weight independent set.
In Proceedings of the Annual Conference on Neural Information Processing Systems (NIPS),
pages 307–315, 2010.
[11] Fazli Can. Incremental clustering for dynamic information processing. ACM Transactions on
Information Systems (TOIS), 11(2):143–164, 1993.
[12] Yves Caseau, François Laburthe, and Glenn Silverstein. A meta-heuristic factory for vehicle routing problems. In International Conference on Principles and Practice of Constraint
Programming (CP), pages 144–158. Springer, 1999.
[13] Moses Charikar, Chandra Chekuri, Tomás Feder, and Rajeev Motwani. Incremental clustering
and dynamic information retrieval. In Proceedings of the Annual Symposium on Theory of
Computing (STOC), pages 626–635, 1997.
[14] Moses Charikar and Anthony Wirth.
Maximizing quadratic programs: extending
Grothendieck’s inequality. In Proceedings of the Annual Symposium on Foundations of Computer Science (FOCS), pages 54–60, 2004.
[15] Timothee Cour, Praveen Srinivasan, and Jianbo Shi. Balanced graph matching. In Proceedings
of the Annual Conference on Neural Information Processing Systems (NIPS), pages 313–320,
2006.
[16] Jim Demmel, Jack Dongarra, Victor Eijkhout, Erika Fuentes, Antoine Petitet, Rich Vuduc,
R Clint Whaley, and Katherine Yelick. Self-adapting linear algebra algorithms and software.
Proceedings of the IEEE, 93(2):293–312, 2005.
[17] R.M Dudley. The sizes of compact subsets of Hilbert space and continuity of Gaussian processes. Journal of Functional Analysis, 1(3):290 – 330, 1967.
[18] Uriel Feige and Michael Langberg. The RPR2 rounding technique for semidefinite programs.
Journal of Algorithms, 60(1):1–23, 2006.
[19] Darya Filippova, Aashish Gadani, and Carl Kingsford. Coral: an integrated suite of visualizations for comparing clusterings. BMC bioinformatics, 13(1):276, 2012.
[20] Roy Frostig, Sida Wang, Percy S Liang, and Christopher D Manning. Simple MAP inference
via low-rank relaxations. In Proceedings of the Annual Conference on Neural Information
Processing Systems (NIPS), pages 3077–3085, 2014.
[21] Michel X Goemans and David P Williamson. Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming. Journal of the ACM
(JACM), 42(6):1115–1145, 1995.
[22] Anna Grosswendt and Heiko Roeglin. Improved analysis of complete linkage clustering. In
European Symposium of Algorithms, volume 23, pages 656–667. Springer, 2015.
[23] Anupam Gupta and Kanat Tangwongsan. Simpler analyses of local search algorithms for
facility location. arXiv preprint arXiv:0809.2554, 2008.
[24] Rishi Gupta and Tim Roughgarden. A PAC approach to application-specific algorithm selection. In Proceedings of the 2016 ACM Conference on Innovations in Theoretical Computer
Science (ITCS), pages 123–134, 2016.
22

[25] Qixing Huang, Yuxin Chen, and Leonidas Guibas. Scalable semidefinite relaxation for maximum a posterior estimation. In Proceedings of the International Conference on Machine
Learning (ICML), pages 64–72, 2014.
[26] Fredrik D Johansson, Ankani Chattoraj, Chiranjib Bhattacharyya, and Devdatt Dubhashi.
Weighted theta functions and embeddings with applications to max-cut, clustering and summarization. In Proceedings of the Annual Conference on Neural Information Processing Systems
(NIPS), pages 1018–1026, 2015.
[27] Subhash Khot, Guy Kindler, Elchanan Mossel, and Ryan O’Donnell. Optimal inapproximability results for MAX-CUT and other 2-variable CSPs? SIAM Journal on Computing, 37(1):319–
357, 2007.
[28] Kevin Leyton-Brown, Eugene Nudelman, and Yoav Shoham. Empirical hardness models:
Methodology and a case study on combinatorial auctions. Journal of the ACM (JACM),
56(4):22, 2009.
[29] Marina Meilă. Comparing clusterings: an information based distance. Journal of multivariate
analysis, 98(5):873–895, 2007.
[30] Ryan O’Donnell and Yi Wu. An optimal SDP algorithm for max-cut, and equally optimal
long code tests. In Proceedings of the Annual Symposium on Theory of Computing (STOC),
pages 335–344, 2008.
[31] David Pollard. Convergence of stochastic processes. Springer-Verlag, 1984.
[32] David Pollard. Empirical processes. Institute of Mathematical Statistics, 1990.
[33] John R Rice. The algorithm selection problem. Advances in computers, 15:65–118, 1976.
[34] Andrej Risteski and Yuanzhi Li. Approximate maximum entropy principles via GoemansWilliamson with applications to provable variational methods. In Proceedings of the Annual
Conference on Neural Information Processing Systems (NIPS), pages 4628–4636, 2016.
[35] Mehreen Saeed, Onaiza Maqbool, Haroon Atique Babri, Syed Zahoor Hassan, and S Mansoor
Sarwar. Software clustering techniques and the use of combined algorithm. In Proceedings of
the European Conference on Software Maintenance and Reengineering, pages 301–306. IEEE,
2003.
[36] Sagi Snir and Satish Rao. Using max cut to enhance rooted trees consistency. IEEE/ACM
Transactions on Computational Biology and Bioinformatics (TCBB), 3(4):323–333, 2006.
[37] Timo Tossavainen. On the zeros of finite sums of exponential functions. Australian Mathematical Society Gazette, 33(1):47–50, 2006.
[38] Vijay V Vazirani. Approximation algorithms. Springer Science & Business Media, 2013.
[39] Jun Wang, Tony Jebara, and Shih-Fu Chang. Semi-supervised learning using greedy max-cut.
Journal of Machine Learning Research, 14(Mar):771–800, 2013.
[40] James R White, Saket Navlakha, Niranjan Nagarajan, Mohammad-Reza Ghodsi, Carl Kingsford, and Mihai Pop. Alignment and clustering of phylogenetic markers-implications for microbial diversity studies. BMC bioinformatics, 11(1):152, 2010.
23

[41] David P Williamson and David B Shmoys. The design of approximation algorithms. Cambridge
University press, 2011.
[42] Lin Xu, Frank Hutter, Holger H. Hoos, and Kevin Leyton-Brown. SATzilla: portfolio-based
algorithm selection for SAT. Journal of Artificial Intelligence Research, 32:565–606, June 2008.
[43] Chihiro Yoshimura, Masanao Yamaoka, Masato Hayashi, Takuya Okuyama, Hidetaka Aoki,
Ken-ichi Kawarabayashi, and Hiroyuki Mizuno. Uncertain behaviours of integrated circuits
improve computational performance. Scientific reports, 5, 2015.
[44] Mingjun Zhong, Nigel Goddard, and Charles Sutton. Signal aggregate constraints in additive
factorial HMMs, with application to energy disaggregation. In Proceedings of the Annual
Conference on Neural Information Processing Systems (NIPS), pages 3590–3598, 2014.
[45] Uri Zwick. Outward rotations: a tool for rounding solutions of semidefinite programming
relaxations, with applications to max cut and other problems. In Proceedings of the Annual
Symposium on Theory of Computing (STOC), pages 679–687, 1999.

A

Proofs from Section 2

Theorem 2. Suppose that Lslin is an algorithm that takes
as input m samples (A(i) , Z(i) ) ∼
1 Pm
D × Z and returns the parameter ŝ which maximizes m i=1 slins (A(i) , Z(i) ). Further, supposePthat m is sufficiently large to ensure that with probability at least 1 − δ, for all s > 0,
m
1

(i)
(i)
|m
i=1 slins (A , Z ) − E(A,Z) [slins (A, Z)] | ≤ 2 . Then Lslin (, δ)-learns the class of s-linear
rounding functions with respect to the cost function −slin∗s .
Proof. Theorem 2 follows directly from Lemma 12.
Lemma 12. Suppose that m is sufficiently large to ensure that with probability at least 1 − δ over
a draw of m samples A(i) , Z(i) ∼ D × Z, for all s-linear functions φs ,


1 X

E
[slins (A, Z)] < .
slins A(i) , Z(i) −
m
2
(A,Z)∼D×Z
m

i=1


1 Pm
(i)
(i) and s∗ maximizes
Then with probability at least 1 − δ, if ŝ maximizes m
i=1 slins A , Z
E [slins (A)], then E [slins∗ (A)] − E [slinŝ (A)] < .
A∼D

A∼D

A∼D

Proof. Notice that since D × Z is a product distribution, we have that


E
[slins (A, Z)] = E
E [slins (A, Z)] = E [slins (A)] ,
A∼D Z∼Z

(A,Z)∼D×Z

A∼D

so we know that with probability at least 1 − δ, for all s-linear functions φs ,


1 X

slins A(i) , Z(i) − E [slins (A)] < .
A∼D
m
2
m

i=1

By assumption, we know that with probability at least 1 − δ,


1 X

slinŝ A(i) , Z(i) − E [slinŝ (A)] <
A∼D
m
2
m

i=1

24

and



1 X

slins∗ A(i) , Z(i) − E [slins∗ (A)] < ,
A∼D
m
2
m

i=1

which means that E [slins∗ (A)] − E [slinŝ (A)] < .
A∼D

A∼D

Lemma 4. Pdim(Hslin ) = Ω(log n).
Proof. In order to prove
that the

 pseudo dimension
 of Hslin is at least c log n for some c, we must
present a set S = G(1) , Z(1) , . . . , G(m) , Z(m)
of m = c log n graphs and projection vectors
that can be shattered by Hslin . In other words, there exist m witnesses r1 , . . . , rm and 2m = nc s
values H = {s1 , . .. , snc } such that for all T ⊆ [m], there exists
 sT ∈ H such that if j ∈ T , then
(j)
(j)
(j)
(j)
slinST G , Z
> rj and if j 6∈ T , then slinST G , Z
≤ rj .
To build S, we will use the same graph G for all G(j) and we will vary Z(j) . We set G to be the
graph composed of bn/4c disjoint copies of K4 . If n = 4, then a simple calculation confirms that
an optimal max-cut SDP embedding of G is
  
 
 

−1/3
−1/3
−1/3
1


√
√


√
  
 − 2/3  − 2/3 
0
2/3
2
, p
, p
 .
 ,
0  0   2/3  − 2/3





0
0
0
0

Therefore, for n > 4, an optimal embedding is the set of n vectors SDP (G) such that for all
i ∈ {0, . . . , bn/4c − 1},
r
r
√
√
√
2
2
2
2
1
2 2
1
1
e4i+1 , − e4i+1 +
e4i+2 , − e4i+1 −
e4i+2 +
e4i+3 , − e4i+1 −
e4i+2 −
e4i+3
3
3
3
3
3
3
3
3

are elements SDP (G).
We now define the set of m vectors Z(j) . First, we set Z(1) to be the vector

Z(1) = 70 , 5 · 70 , 5 · 70 , 70 , 71 , 5 · 71 , 5 · 71 , 71 , 72 , 5 · 72 , 5 · 72 , 72 , 73 , 5 · 73 , 5 · 73 , 73 , . . . .

In other words, it is the concatenation the vector 7i (1, 5, 5, 1) for all i > 0. Next, Z(2) is defined as

Z(2) = 70 , 5 · 70 , 5 · 70 , 70 , 0, 0, 0, 0, 72 , 5 · 72 , 5 · 72 , 72 , 0, 0, 0, 0, . . . ,
so Z(2) is the same as Z(1) for all even powers of 7, and otherwise its entries are 0. In a similar
vein,

Z(3) = 70 , 5 · 70 , 5 · 70 , 70 , 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 74 , 5 · 74 , 5 · 74 , 74 , . . . .
j−1

To pin down this pattern, we set Z(j) to be the same as Z(1) for all entries of the form 7i2 (1, 5, 5, 1)
for i ≥ 0, and otherwise its entries are 0.
We set the following positive, increasing constants which will appear throughout the remaining
analysis:
a=
(1, 0, 0, 0) · (1, 5, 5, 1) = 1
√
p
p
√
b=
(−1/3, − 2/3, 2/3, 0) · (1, 5, 5, 1) = 5 √2/3 − 5 32+1
√
c=
(−1/3, 2 2/3, 0, 0) · (1, 5, 5, 1) = 10 32−1
√
p
p
√
d = (−1/3, − 2/3, 2/3, 0) · (1, 5, 5, 1) = 5 2/3 + 5 32+1 .
25

Figure 7: Depiction of slinG,Z(j) (s) as s increases from 0. A black dot means that slinG,Z(j) (s) ≥ rj
and a white dot means that slinG,Z(j) (s) < rj . Here, ai = 7i−1 c and bi = 7i−1 d.
We also set c̃ = b + c + bc − d − bd − cd and we claim that the witnesses


b
1
1
−1
r1 = −
2 3n c2
1
c̃
rj = −
j>1
j−1
2 3n72 −2 d2
are sufficient to prove that this set is shatterable, and we will spend the remainder of the proof
showing that this is true.
Now, the domain of slinG,Z(j) (s) can be split into intervals on which it has a simple, fixed form.
h j−1

j−1
These intervals begin at 1 and have the form 7i2 , 7(i+1)2
, for i ≥ 0. It is straightforward
h j−1

j−1
matter of calculations to check that for s ∈ 7i2 , 7(i+1)2
,
1
slinG,Z(j) (s) =
  h P2
i

j−1
i−1 2k2j−1
72i2
1
1

7
+
c̃
−
1

2
k=0

3n  s h
s

i



 1 12 c̃ Pi−1 72k2j−1 + 72i2j−1 b − 1
k=0
3n  s h
i

−
Pi−1 2k2j−1
1
1
2i2j−1 (b + c + bc) − y

7
+
7
c̃

2
k=0
 3n  s h

i


 1 12 c̃ Pi 72k2j−1
k=0
3n s
2i2j−1

h j−1

j−1
if s ∈ 7i2 , 7i2 b
h j−1

j−1
if s ∈ 7i2 b, 7i2 c
h j−1

j−1
if s ∈ 7i2 c, 7i2 d
h j−1

j−1
if s ∈ 7i2 d, 7(i+1)2
,

(1+b+c)
where y = 7
. (We note here that the power of 7 pattern was chosen so that these
s
intervals are well defined, since 7i d < 7i+1 .)
We call the following increasing
sequence of numbers points of interest, which we use to prove

that this set is shattered: 70 c, 70 d, 71 c, 71 d, 72 c, 72 d, . . . , 7i c, 7i d, . . .
We make two claims about these points of interest:
1. slinG,Z(1) (s) is above its witness whenever s = 7i c and it is below its witness whenever
s = 7i d for i ≥ 0.
2. Let j > 1 and consider slinG,Z(j) (s). There are 2j points of interest per interval
h j−1

j−1
7i2 , 7(i+1)2
.

On the first half of these points of interest, slinG,Z(j) (s) is greater than its witness and on
the second half, slinG,Z(j) (s) is less than its witness.
These claims are illustrated by the dots in Figure 7. Together, these claims imply that S can be
shattered because for any vector b ∈ {0, 1}m , there exists a point of interest s such that slins (S)
induces the binary labeling b on S.
26

The first claim is true because
slinG,Z(1)

" i−1
#
!
X
1
c̃
72k + 72i b − 1
72i c2
k=0




1
72i − 1
1
1
2i
c̃ · 2
= −
+7 b −1 ,
2 3n 72i c2
7 −1

 1
1
7i c = −
2 3n

which is an increasing function of i, so it is minimized when i = 0, where


 1
b
1
0
slinG,Z(1) 7 c = −
− 1 = r1
2 3n c2

so slinG,Z(1) 7i c is always at least its witness. Further,
slinG,Z(1)

 1
1
7i d = −
2 3n
1
1
−
2 3n

=

" i
#!
X
1
c̃
72k
72i d2
k=0
"
#!
1
72(i+1) − 1
c̃ ·
),
72i d2
48

which is again an increasing function in i, with a limit of
1
49c̃
−
< r1 .
2 144nd2


Therefore, slinG,Z(1) 7i d is always less than its witness, and we may conclude that the first claim
is always true.
For the second claim, notice that
j−1

7i2

j−1

c < 7i2

j−1 +1

j−1 +1

c < 7i2

j−1 +2

d < 7i2

j−1

j−1

j−1

c · · · < 7i2 +2 c = 7(i+1)2 c,
h j−1

j−1
so there are 2j points of interest per interval 7i2 c, 7(i+1)2 c , as claimed. The first two points
j−1

d < 7i2

j−1

of interest, 7i2 c and 7i2 d, fall in an interval where slinG,Z(j) is decreasing in s. Therefore, it
j−1
is minimized when s = 7i2 d, where
" i
#!
 j−1  1
X
1
1
j−1
slinG,Z(j) 7i2 d = −
c̃
72k2
2 3n 72i2j−1 d2
k=0
"
#!
j
1
1
7(i+1)2 − 1
1
.
= −
c̃ ·
2 3n 72i2j−1 d2
72j − 1

 j−1 
Simple calculations show that slinG,Z(j) 7i2 d is an increasing function in i, so it is minimized

when i = 0, where slinG,Z(j) (d) =

1
2

−

c̃
3nd2

> rj , as desired.
h j−1

j−1
The remaining points of interest fall in the interval 7i2 d, 7(i+1)2
, so slinG,Z(j) (s) has
 h P
i
j−1
1
1
c̃ ik=0 72k2
. This segment of the function has a negative derivative, so
the form 12 − 3n
s2
it is decreasing.
j−1
j−1
If j = 2, then the points of interest weh already considered,
7i2 c and 7i2 d, make up half

j−1
j−1
of the 2j points of interest in the interval 7i2 c, 7(i+1)2 c . Therefore, we only need to show
27

j−1 +1

that when s equals 7i2

j−1 +1

c and 7i2

d, then slinG,Z(j) (s) is less than its witness. As we saw,
 j−1

slinG,Z(j) is decreasing on this segment, so it is enough to show that slinG,Z(j) 7i2 +1 c is less
than its witness. To this end,
" i
#!
 j−1
 1
X
1
1
i2
+1
2k2j−1
slinG,Z(j) 7
c = −
c̃
7
2 3n 72i2j−1 +2 c2
k=0
"
#!
j
1
1
7(i+1)2 − 1
1
c̃ ·
.
= −
2 3n 72i2j−1 +2 c2
72j − 1
This is an increasing function of i with a limit of
Therefore, when s equals 7

i2j−1 +1

b and 7

i2j−1 +1

1
2

−

1
3n



1
72 c2

h

j

72
j
72 −1

c̃ ·

i

< rj when j = 2.

c, then slinG,Z(j) (s) is less than its witness.
h j−1

j−1
Finally, if j > 2, since slinG,Z(j) (s) is decreasing on the interval 7i2 c, 7(i+1)2
, we must
 j−1 j−2


th
only check that at the 2j−1 − 1
point of interest 7i2 +2 −1 d , slinG,Z(j) (s) is greater than
 j−1 j−2 
th
its witness and at the 2j−1 + 1
point of interest 7i2 +2 c , slinG,Z(j) (s) is less than its
witness. To this end,
" i
#!
 j−1 j−2
 1
X
1
1
i2
+2
−1
2k2j−1
d = −
slinG,Z(j) 7
c̃
7
2 3n 7i2j +2j−1 −2 d2
k=0
"
#!
j
1
1
7(i+1)2 − 1
1
c̃ ·
.
= −
2 3n 7i2j +2j−1 −2 d2
72j − 1
This function is increasing in i, so it is minimized when i = 0, where
"
#!
j
 j−2
 1
1
1
72 − 1
2
−1
d = −
slinG,Z(j) 7
c̃ · 2j
2 3n 72j−1 −2 d2
7 −1


1
c̃
1
= −
= rj .
j−1 −2 2
2
2 3n 7
d
 j−1 j−2

Therefore, slinG,Z(j) 7i2 +2 −1 d ≥ rj for all i.
Next,


i2j−1 +2j−2

slinG,Z(j) 7

 1
1
c = −
2 3n
1
1
= −
2 3n

1
7i2j +2j−1 c2
1
7i2j +2j−1 c2

which is an increasing function in i, with a limit of
j−1

1
c̃72

−
2 3nc2 72j − 1
28

"
"

c̃

i
X

2k2j−1

7

k=0

j

#!

7(i+1)2 − 1
c̃ ·
72j − 1

#!

.

as i tends toward infinity. Therefore,
j−1
 j−1 j−2  1
c̃72
 < rj
slinG,Z(j) 7i2 +2
≤ −
2 3nc2 72j − 1

for all i, so the second claim holds.

B

More algorithm classes for MaxQP

B.1

˜-discretized functions for max-cut

The class of ˜-discretized rounding functions are a finite yet rich class of functions for the RPR2
paradigm. They were introduced by O’Donnell and Wu as a tool for characterizing the SDP gap
curve for the max-cut problem, which we define shortly in order to describe O’Donnell and Wu’s
guarantees for RPR2 using ˜-discretized rounding functions. However, we first define the max-cut
SDP value of a graph G to be




 X
1 1
wij
Sdp(G) = max
,
− g(vi ) · g(vj )

g:V →Bn 
2 2
(vi ,vj )∈E

where n = |V | and Bn denotes {x ∈ Rn | ||x|| ≤ 1}.
Now, suppose that a graph G has an SDP value Sdp(G) ≥ c. The SDP gap curve GapSDP (c) is a
function that measures the smallest optimal max-cut value among all graphs such that Sdp(G) ≥ c.
In other words, given that Sdp(G) ≥ c, we are guaranteed that the optimal max-cut value of G is
at least GapSDP (c). Formally,
Definition 10. For 12 ≤ s ≤ c ≤ 1, we call the pair (c, s) an SDP gap if there exists a graph G
with Sdp(G) ≥ c and Opt(G) ≤ s. We define the SDP gap curve by
GapSDP (c) = inf{s | (c, s) is an SDP gap}.

O’Donnell and Wu prove that if G is a graph such that Sdp(G) ≥ c, if one runs RPR2 iteratively
with all ˜-discretized rounding functions, then with high probability, at least one will result in a
cut with value GapSDP (c) − ˜. We now formally state the definition of an ˜-discretized rounding
function as well as O’Donnell and Wu’s algorithm guarantees.
Definition 11. Given ˜ > 0, let I˜ denote the partition of R \ {0} into intervals,

I˜ = ±(−∞, −B], ±(−B, −B + ˜2 ], ±(−B + ˜2 , −B + 2˜
2 ], . . . , ±(−2˜
2 , −˜
2 ], ±(−˜
2 , ˜2 ) ,

p
where B = B(˜
) is the smallest integer multiple of ˜2 exceeding 2 ln(1/˜
). We say that a function
r : R → [−1, 1] is ˜-discretized if the following hold:
1. r is identically −1 on (−∞, −B], 0 at 0, and identically 1 on [B, ∞).
2. r’s values on the finite intervals in I˜ are from the set ˜Z ∩ (−1, 1).
2

Note that there are 2O(1/˜ ) ˜-discretized functions.
Theorem 12 (Corollary 5.4 in [30]). There is an algorithm which, given any graph G with Sdp(G) ≥
2
c and any ˜ > 0, runs in time poly(|V |)2O(1/˜ ) and with high probability outputs a proper cut in G
with value at least GapSDP (c) − ˜.
29

Namely, the algorithm alluded to in Theorem 12 takes as input a graph, runs RPR2 using all
˜-discretized rounding functions, and returns the cut with the maximum value. We define cut˜(G)
to be the value of the resulting cut.
It is well-known that the pseudo-dimension of a finite function class F has pseudo-dimension
log |F|. This immediately implies the following theorem.

Theorem 13. Given an input sample of size m = O 12 ˜12 + log 1δ there exists an algorithm that
(, δ)-learns the class of ˜-discretized rounding functions with respect to the cost function −cut˜.

B.2

Outward rotations

Next we study a class of “outward rotation” based algorithms proposed by Zwick [45]. For the maxcut problem, outward rotations are proven to work better than the random hyperplane technique
of Goemans and Williamson [21] on graphs with “light” max-cuts where the max-cut does not
constitute a large proportion of the edges. As stated earlier, though Feige and Langberg later
showed that there exists a class of rounding functions for which RPR2 becomes equivalent to
outward rotations [18], we will analyze this class as it was originally presented by Zwick [45].
The class of outward rotation algorithms is characterized by an angle γ ∈ [0, π/2] varying
which results in a range of algorithms between the random hyperplane technique of Goemans and
Williamson and the naive approach of outputting a random binary assignment [21]. Unlike RPR2 ,
the output here is a binary assignment. An outward rotation algorithm in essence extends the
optimal SDP embedding in Rn to R2n . The way this is done can be understood as follows. The
original embedding is first carried over to the first n co-ordinates of a 2n-dimensional space while the
remaining co-oordinates are set to zero. Suppose un+1 , un+2 , . . . , u2n are the orthonormal vectors
along each of the last n co-ordinates. Each embedding ui is rotated “out” of the original space,
towards un+i by an angle of γ. After performing these outward rotations, the new embedding is
projected onto a random hyperplane in R2n . The binary assignment is then defined deterministically
based on the sign of the projections like in the GW algorithm [21]. Intuitively, the parameter γ
determines how far the SDP embedding is used to determine the final projection of vi as against
an arbitrary value drawn from the normal distribution, which is contributed by ui . We formally
define the class below.
Algorithm 5 SDP rounding algorithm using γ-outward rotation
Input: Matrix A ∈ Rn×n
1: Solve the SDP (1) for the optimal embedding U = (u1 , . . . , un ) of A.
2: Define a new embedding u0i in R2n such that the first n co-ordinates correspond to ui cos γ and
the following n co-ordinates are set to 0 except the (n + i)th co-ordinate which is set to sin γ.
3: Choose a random vector Z ∈ R2n according to the 2n-dimensional Gaussian distribution.
4: For each decision variable xi , assign xi = sgn (hu0i , Zi) .
Output: x1 , . . . , xn .
We will now set up notations similar to Section 2. Let owrγ (A, Z) be the value of the binary
assignment produced by projecting the SDP embedding of A onto Z after rotating it outwardly by
γ. That is,
owrγ (A, Z) =

X
i,j



aij sgn hu0i , Zi sgn hu0j , Zi .

We will use owrγ (A) to denote the expected value of owrγ (A, Z) when Z is sampled from Z,
the 2n-dimensional normal distribution. It can be easily seen that a fact very similar to Lemma
30


12 in Appendix A will apply here. Therefore, we will again use samples of the form A(i) , Z(i) for
the pseudo-dimension
analysis.

Let Howr = owrγ : A × R2n → [0, 1] | γ ∈ [0, π/2] . We first prove in Section B.2.1 that the
pseudo-dimension of Howr is O(log n). Next, in Section B.2.2 we present an efficient learning
algorithm.
B.2.1

The pseudo-dimension of the class of outward rotation based algorithms

We show an upper bound on the pseudo-dimension of the class of outward rotation based algorithms.
In the following discussion, we will use the notation owrA,Z (γ) in order to examine how the value
changes as a function of γ for a fixed (A, Z).
Theorem 14. Pdim(Howr ) = O(log n).



Proof. Suppose S = A(1) , Z(1) , . . . , A(m) , Z(m) is shatterable. This means that there exist
m thresholds {r1 , . . . , rm } ⊂ R such that for each T ⊆ [m], there exists a parameter γT such that
owrA(i) ,Z(i) (γT ) > ri if and only if i ∈ T .

We claim that for each sample A(i) , Z(i) , owrA(i) ,Z(i) (γ) is a piecewise constant function in
γ with at most n values of γ at which it is discontinuous. If this were to be true, it means that
there exists n values a1 , a2 , . . . an such that for γ within a given interval in [0, a1 ], (a1 , a2 ], . . . [an , 1]
owrA(i) ,Z(i) (γ) is identical and so is the label given by the witness ri . Therefore, there are at most
mn values of γ which define mn + 1 intervals such that the labels given by the witnesses for the set
of m samples is identical within each interval i.e., only at most mn + 1 distinct labelings of S are
achievable for any choice of the witnesses. However, since S is shatterable, we need 2m < mn + 1.
Thus, s = O(log n)
Now, we only need prove our claim about owrA,Z (γ) given A and γ = Z. Observe that as
γ increases, owrA,Z (γ) will change only when sgn (hu0i , Zi) changes for some vi . Now, note that
hu0i , Zi = hui , Z[1,...,n] i cos γ + zn+i sin γ where Z[1,...,n] is the projection of Z over the first n coordindates. Clearly, hu0i , Zi is a monotone function in γ ∈ [0, π/2] and attains zero at


hui , Z[1,...,n] i
−1
γ = tan
−
.
zn+i
This implies that for each i ∈ [n], sgn (hu0i , Zi) changes at most once within [0, π/2]. Therefore,
owrA,Z (γ) is a piecewise constant function with at most n discontinuities.
B.2.2

A learning algorithm

We now present Algorithm 6 that efficiently learns the best value of γ for outward rotation with
respect to samples drawn from D × Z.
1 Pm
Lemma 13. Algorithm 6 produces the value γ̂ which maximizes m
i=1 owrA(i) ,Z(i) (γ) given the
 (1) (1) 

(m)
(m)
sample S = A , Z
,..., A ,Z
. Algorithm 6 has running time polynomial in m and
n.
Proof. Recall from the proof of Theorem 14 that T defines intervals over [0, π/2] within each of
which the behavior of any γ is constant across all samples in S. Therefore, we only need to examine
the performance of a single value of γ within each interval to exhaustively evaluate all possibilities,
and single out the best one.
Also observe that since there are only O(mn) values in T (in Step 2) and since computing the
binary assignment on a set of m instances for a particular value of γ takes polynomial time in m
and n, Step 3 should also take only polynomial time in m and n.
31

Algorithm 6 An algorithm for finding the empirical value maximizing γ



Input: Sample S = A(1) , Z(1) , . . . , A(m) , Z(m)
 (1)
1: Solve for U , . . . , U (m) the optimal SDP embeddings for A(1) , . . . , A(m) , where U (i) =


(i)
(i)
u1 , . . . , un .

2: Let T = γ1 , . . . , γ|T | be the set of all values γ ∈ [0, π/2] such that there exists a pair of indices


(j)
hu(j) ,Z[1,...,n] i
−1
= γ.
i ∈ [n], j ∈ [m] with tan
−
(j)
zn+i
 1 Pm

(i)
(i) .
3: Let γ̂ = argmax
i=1 owrγ A , Z
m
γ∈T ∪{π/2}

Output: γ̂

Together with Theorem 2 and Theorem 14, Lemma 13 implies the following theorem.

Theorem 15. Given an input sample of size m = O 12 log n log 1 + log 1δ drawn from (D×Z)m ,
Algorithm 6 (, δ)-learns the class of outward rotation algorithm with respect to the cost function
−owrγ .

B.3

A general analysis of RPR2 algorithms

In Sections 2 and B.2, we investigated two specific classes of RPR2 algorithms. We will now
present an analysis that can be applied to a wide range of classes of RPR2 algorithms including
that of s-linear functions and outward rotations. In particular, we show that for most classes of
“sigmoid-like” rounding functions, the pseudo-dimension of RPR2 is Θ(log n).
As a first step towards this goal, we define what it means for a class of rounding functions to be
“sigmoid-like” (Section B.3.1). Next, in order to both generalize and simplify the sample complexity
analysis, we provide an alternative randomized procedure to RPR2 , which we call Randomized
Projection Randomized Thresholding (RPRT), which produces a binary assignment rather than a
fractional assignment (Section B.3.2). We prove that RPRT is equivalent to RPR2 by showing
that in expectation, the assignment produced by RPRT has the same value as the assignment
produced by RPR2 on an arbitrary problem instance. We work in the RPRT framework to bound
the sample complexity required to (, δ)-learn the best rounding function in a fixed class for either
RPR2 or RPRT. We prove this by showing that the pseudo-dimension of RPRT with a sigmoid-like
rounding function is Θ(log n) (Section B.3.3). Finally, in Section B.3.4, we present an algorithm
which (, δ)-learns the best rounding function in a fixed class.
B.3.1

A generic class of sigmoid-like rounding functions

We say that a class of functions F is “sigmoid-like” if the functions in the class are parameterized
by a single constant s ∈ R+ and there exists a baseline function f1 ∈ F such that for every function
fs ∈ F, fs (x) := f1 (sx). Clearly, such a representation is rich enough to encompass classes of most
common sigmoid-like functions including s-linear functions or any piece-wise linear function. In
order for a class of sigmoid-like functions to qualify as SDP rounding functions, we additionally
require that each function is non-decreasing and has a limit of −1 as x approaches −∞, and has a
limit of 1 as x approaches ∞. In particular,
Definition 16. A class of real-valued functions F = {fs | s ∈ R+ } consists of sigmoid-like rounding
functions if there exists a baseline function f1 (x) : R → [−1, 1] such that
1. f1 (x) is non-decreasing,
32

2. lim f1 (x) = 1 and lim f1 (x) = −1,
x→∞

x→−∞

and for any function fs ∈ F, we can write fs (x) = f1 (sx).
Before we define RPRT, we make the following observation about sigmoid-like functions, as
it will be useful for our algorithm design and sample complexity analysis. In particular, observe
that for each s, Fs (x) := fs (x)+1
is a cumulative density function associated with some probability
2
distribution. This is because Fs is non-decreasing and its limits are 0 and 1 as x tends to −∞ and
+∞, respectively. We denote the probability density function associated with Fs by ps .
B.3.2

Randomized Projection Randomized Thresholding

RPRT differs from RPR2 primarily in that it produces a binary assignment rather than a fractional
assignment. In essence, RPRT simply samples a binary assignment from the distribution over
binary assignments that RPR2 effectively outputs. Like RPR2 , RPRT first projects the embedding
of an IQP instance A onto a random vector Z. However, RPRT then draws a random threshold for
each variable and assigns the variable to either 1 or −1 depending on whether the directed distance
of the projection (multiplied by ||Z||) is less than or greater than its threshold. The distribution
from which these thresholds are picked are designed to mimic RPR2 in expectation.
Algorithm 7 RPRT-based SDP rounding algorithm with rounding function fs ∈ F

Input: Matrix A ∈ Rn×n .
1: Solve the SDP (1) for the optimal embedding U = (u1 , . . . , un ) of A.
2: Choose a random vector Z ∈ Rn according to the n-dimensional Gaussian distribution.
n
3: Draw Q = (q1 , q2 , . . . , qn ) ∼ (p1 ) where p1 is the probability density function corresponding
to f1 (x).
4: For each decision variable xi , output the assignment xi = sgn (qi − shui , Zi).
Output: x1 , . . . , xn .
Now we show that the expected value of the binary assignment produced by RPRT is equal to
that of RPR2 for a given rounding function fs . We define rprts (A, Z, Q) to be the deterministic
value of the binary assignment produced by RPRT using the rounding function fs , given the values
of both Z and Q. Similarly, we define rprts (A, Z) to be the expected value of the binary assignment
produced by RPRT given the value of Z. In other words, rprts (A, Z) = EQ∼(p1 )n [rprts (A, Z, Q)] .
Finally, we define rprts (A) to be the expected value of the binary assignment produced by RPRT
and by rpr2s (A) the value of the binary assignment produced by RPR2 . In other words,
rprts (A) = EQ∼(p1 )n ,Z∼Z [rprts (A, Z, Q)] and rpr2s (A) = EZ∼Z [rpr2s (A, Z)]
Theorem 17. Given a MaxQP problem with input matrix A and a rounding function fs , the
expected value of the binary assignment produced by RPRT equals the value of the fractional assignment produced by RPR2 , i.e. rprts (A) = rpr2s (A) .
Proof. Let xi and x0i denote the binary and fractional assignments produced by RPR2 and RPRT
for a given Z and Q respectively. We claim that for all i, EQ∼(p1 )n [x0i ] = xi . If we can prove
this, then it implies that rprts (G, Z) = rpr2s (G, Z). To prove this, we will make use of the fact
that given Z, and hence given the projection hui , Zi, x0i and x0j are independent random variables.
Therefore, the expectation of x0i x0j over all random draws of Q can be written as the product of

33

their individual expected values.
rprts (A, Z) =
=

E

Q∼(p1 )n

X



X

aij x0i x0j 
i,j

aij EQ∼(p1 )n [x0i ]EQ∼(p1 )n [x0j ]

i,j

=

X

aij xi xj = rpr2s (A, Z).

i,j

Once we have rprts (A, Z) = rpr2s (A, Z), it is clear that rprts (A) = rpr2s (A) as Z is sampled
from the same distribution in both the algorithms.
Now we only need to show that for a given Z, EQ∼(p1 )n [x0i ] = xi i.e., for a given Z, for any
variable, the expected binary assignment of the randomized thresholding step is equal to the fractional assignment of RPR2 for that variable. Let us examine the expected binary assignment of
RPRT for a particular variable xi . The probability that xi is assigned +1 is P rqi ∼p1 [qi < shui , Zi].
Since f1 is the cumulative density function of p1 , this is equal to f1 (shui , Zi). However, due to the
way we defined fs , this value is in fact equal to fs (hui , Zi). We complete the proof by noting that
fs (hui , Zi) is precisely the fractional assignment of RPR2 for the choice of the rounding function
fs .
Now, taking advantage of this equivalence between RPR2 and RPRT for a given class of sigmoidlike functions, we will show that any learning algorithm that (, δ)-learns the best rounding functions
with respect to RPRT also (, δ)-learns the best rounding functions with respect to RPR2 . Recall
from Section 2 that in the analysis for pseudo-dimension, we incorporated Z in the sample set
S. In the same vein, we will now also incorporate Q
sample set. In other words, we will
 in(1)our (1)
provide to our learning algorithm the set of samples, A , Z , Q(1) , . . . , A(m) , Z(m) , Q(m) ∼
(D × Z × (p1 )n )m . In order to prove that this indeed works, we now state Theorem 18 and Lemma
14 which parallel Theorem 2 and Lemma 12 respectively.
Theorem 18. Suppose F = {fs |s > 0} is a class of sigmoid-like rounding functions. Let Hrprt =
{rprts : A × Rn × Rn → [0, 1]|s > 0} and let dHrprt be the pseudo-dimension of Hrprt . Suppose

that Lrprt is an algorithm that takes as input m samples A(i) , Z(i) , Q(i) ∼ D × Z × (p1 )n , where
m = O 12 (dHrprt log 1 + log 1δ ) , and returns the parameter ŝ that maximizes


1 X
rprts A(i) , Z(i) , Q(i) .
m
m

i=1

Then Lrprt (, δ)-learns the class of rounding functions F with respect to the cost function −rpr2s
and is computationally efficient.
The proof for Theorem 18 follows from the following Lemma that is similar to Lemma 12.
Lemma 14. Suppose that m is sufficiently
large to ensure that with probability at least 1 − δ over

(i)
(i)
(i)
a draw of m samples A , Z , Q
∼ D × Z × (p1 )n , for all functions fs ∈ F,



1 X

rprts A(i) , Z(i) , Q(i) −
E
[rprts (A, Z, Q)] < .
m
2
(A,Z,Q(i) )∼D×Z×(p1 )n
i=1
 1 Pm

(i)
(i)
(i) , and s∗ maxThen with
least 1 − δ, if ŝ maximizes m
i=1 rprts A , Z , Q
 probability at 
imizes
E [rpr2s (A)] , then E [rpr2s∗ (A)] − E [rpr2ŝ (A)] < .
m

A∼D

A∼D

A∼D

34

Proof of Lemma 14. Since D × Z × (p1 )n is a product distribution, we have that
E

(A,Z,Q)∼D×Z×(p1 )n

[rprts (A, Z, Q)] = E [rprts (A)] .
A∼D

But from Theorem 17 we know that rprts (A) = rpr2s (A), which implies that
E [rprts (A)] = E [rpr2s (A)] .

A∼D

A∼D

Hence, we can restate the assumption in the theorem statement as follows. With probability at
least 1 − δ, for all functions fs ,


1 X

rprts A(i) , Z(i) , Q(i) − E [rpr2s (A)] < .
A∼D
m
2
m

i=1

Since this true for ŝ and s∗ , we can say that with probability 1 − δ,


1 X

rprtŝ A(i) , Z(i) , Q(i) − E [rpr2ŝ (A)] <
A∼D
m
2
m

i=1

and




1 X
rprts∗ A(i) , Z(i) , Q(i) − E [rpr2s∗ (A)] < .
A∼D
m
2
m

i=1

Now, by definition of ŝ we have that,





1 X
1 X
rprtŝ A(i) , Z(i) , Q(i) ≤
rprts∗ A(i) , Z(i) , Q(i) .
m
m
m

m

i=1

i=1

Combining the previous three inequalities, we get that E [rpr2s∗ (A)] − E [rpr2ŝ (A)] < .
A∼D

B.3.3

A∼D

The pseudo-dimension of a general class of RPRT algorithms

The main result of this section is a tight bound on the pseudo-dimension of any general class of
RPRT algorithms.
Theorem 19. Let Hrprt = {rprts : A × Rn × Rn → [0, 1] | s > 0}. Pdim(Hrprt ) = Θ(log n).
This follows from Lemma 15 and Lemma 16 where we provide matching upper and lower bounds
on Pdim(Hrprt ).
Lemma 15. Pdim(Hrprt ) = O(log n).



Proof. Suppose S = A(1) , Z(1) , Q(1) , . . . , A(m) , Z(m) , Q(m) is shatterable. Then there exist
m thresholds {r1 , . . . , rm } ⊂ R such that for all T ⊆ [m], there exists a parameters sT such that
vals0 T A(i) , Z(i) > ri if and only if i ∈ T .

We first claim that for a given sample A(i) , Z(i) , Q(i) the domain of s i.e., (0, ∞) can be parti(i)

(i)

(i)

(i)

tioned into at most n + 1 intervals (0, a1 ], (a1 , a2 ], . . . (an , ∞) such that the binary assignment
produced by RPRT on the sample is identical across all parameter settings of s within a given
interval. Once this is proved, we can then consider a partition of the domain of s into at most
m
S
(i)
(i)
mn + 1 intervals based on the points
{a1 , . . . , an }. Now, we know that for any value of s within
i=1

35

a given interval of these mn + 1 intervals, the labeling induced by the witnesses on S is the same.
Therefore, there are at most mn + 1 possible labelings that can be produced by any choice of the
witnesses over any set of m samples. However, since we picked a shatterable instance, it must be
that 2m ≤ mn + 1 i.e., m = O(log n).
Now to complete
the proof, we need to examine the behavior of RPRT on a single sample

A(i) , Z(i) , Q(i) for different configurations of s. Observe that as we increase s from 0 to ∞
keeping all else constant, we expect RPRT to produce a different binary assignment only when the
assigned value changes for some vertex vi . However, this happens only when qi = shg(vi ), Zi i.e.,
when s = qi /hg(vi ), Zi. Since there are only n vertices, and at most one value of s at which the
algorithm changes behavior, we expect the algorithm to change its behavior at most n times as s
increases. This proves our claim.
We now prove a lower bound on the pseudo-dimension of Hrprt .
Lemma 16. Pdim(Hrprt ) = Ω(log n).
Proof. In order to prove that the pseudo-dimension
ofHrprt is at least c log n for some constant c,
 (1) (1) (i)
we must devise a set of samples S = G , Z , Q
, . . . , G(m) , Z(m) , Q(i) of size m = c log n
that can be shattered by Hrprt . This means that we should be able to find m witnesses r1 , . . . , rm
and 2m = nc s values H = {s1 , . . ., snc } such that for all T ⊆ [m], there exists sT ∈ H such that if
i ∈ T , then rprtsT G(i) , Z(i) , Q(i) > ri and if i 6∈ T , then rprtsT G(i) , Z(i) , Q(i) ≤ ri .
In our solution, we will use the same S as designed in the proof for Lemma 4. That is, all G(i) are
identical and each consists of n/4 disjoint K4 graphs over vertices Vk = {v4k+1 , v4k+2 , v4k+3 , v4k+4 }
for k = 0, 1, . . . bn/4c − 4. We will later pick Z(i) and Q(i) such that as the value of s increases,
we change the cuts on V1 , V2 , . . . in that order and the change in the cuts is alternatingly better
and worse. By appropriately choosing different values of Z(i) , we can carefully place the intervals
in which these oscillations occur across all samples so as to be able to shatter a sample of size
Ω(log n).
In order to define Z(i) and Q(i) , we make use of the following increasing sequence defined
i−1
recursively: c1 = 8 and ci = c2i−1 . Note that we can also write ci = 82
but we will use the
1
(i)
notation ci for the sake of convenience. Let aik = ck . We will now define Z in terms of aik as
i
follows. For even k, we define


 1
3
(i)
(i)
(i)
(i)
· aik , aik , · aik , aik
Z4k+1 , Z4k+2 , Z4k+3 , Z4k+4 =
2
2
and for odd k we define,


(i)
(i)
(i)
(i)
Z4k+1 , Z4k+2 , Z4k+3 , Z4k+4 = (aik , −aik , −aik , aik )

The rationale behind choosing the above value for Z(i) will become evident as we proceed with
the proof. First, by a simple calculation we can confirm that the directed distance of the projections
of the vertices on Z(i) lie in certain intervals as stated below.
For even k,


1

j = 4k + 1,
 2 aik , 2aik


 1 a , 2a 
j = 4k + 2,
ik
ik

hg (i) (vj ), Z(i) i ∈  12

j = 4k + 3,

2 aik , 2aik


−2a , − 1 a  j = 4k + 4.
ik
2 ik
36

For odd k,


1

aik , 2aik

2


−2a , − 1 a 
ik
(i)
(i)
2 ik 
hg (vj ), Z i ∈ 
 −2aik , − 12 aik



 1 a , 2a 
ik
2 ik

j
j
j
j

= 4k + 1,
= 4k + 2,
= 4k + 3,
= 4k + 4.

As for the choice of Q(i) , we pick the same value for all i. In particular, we choose Q(i) as
follows. For even k,


(i)
(i)
(i)
(i)
Q4k+1 , Q4k+2 , Q4k+3 , Q4k+4 = (−1, +1, +1, −1) ,
and for odd k,




(i)
(i)
(i)
(i)
Q4k+1 , Q4k+2 , Q4k+3 , Q4k+4 = (−1, −1, −1, +1) ,

Again, our choiceof Q(i) will make sense as we proceed with the proof. We now analyze
how

(i)
(i)
(i)
(i)
(i)
(i)
rprts G , Z , Q
varies as a function of s. We will show that rprts G , Z , Q
oscillates
above and below a threshold ri , bn/4c/2 times and these oscillations are spaced in such a manner
that we can pick 2m values of s that can shatter S.

First, let us examine the values of s at which we expect the behavior of rprts G(i) , Z(i) , Q(i)
to change. We know that this can only consist of values of s equal to 1/hg (i) (vj ), Z(i) i for some j.
Based on this fact,
 we observe that for the vertices in Vk the values of s at which the cut changes
lie in 12 cki , 2 · cki . Thus, note that the intervals of s in which the cut changes for V1 , V2 , . . . are
spaced far apart in increasing order because 2cki < 12 ck+1
given ci > 4.
i
Our analysis will henceforth focus on the values of s outside these intervals. We now claim
that there exists values bmax and bmin such that the value of the cut is only one of these values
 in
k , 2 · ck and
between
the
above
intervals.
In
particular,
the
value
is
equal
to
b
between
0.5c
max
i
i
h
i
0.5ck+1
, 2 · ck+1
for odd k and is equal to bmin for even k. By simple calculation, it can be verified
i
i
that the cut (S, S c ) assigned to Vk varies as follows. For even k,
(
{v4k+1 , v4k+4 }
s < 0.5cki ,
S=
{v4k+1 , v4k+2 , v4k+3 } s > 2 · cki ,
and for odd k,
(
{v4k+1 , v4k+2 , v4k+3 }
S=
{v4k+1 , v4k+4 }

s < 0.5cki ,
s > 2 · cki .

Now, when the cut is defined by S = {v4k+1 , v4k+4 } is 2/3. On the other hand when S =
{v4k+1 , v4k+2 , v4k+3 },
value of the cut is 1/2. Thus we can make a crucial observation here: as s
 1the
k
crosses the interval 2 ci , 2 · cki for even k, the net value of the cut over the whole graph decreases,
and for odd k it increases.

More precisely, we claim that rprts G(i) , Z(i) , Q(i) as a function of s outside these intervals
takes one of two values bmin and bmax . To state these values explicitly, let us define a set of variables
bk such that for even k, bk = 2/3 and for odd k, bk = 1/2. Observe that when s < 1/2, the value
1 Pbn/4c−1
bk as every odd graph contributes a value of 1/2 and every even graph
of the cut is bn/4c
k=0
contributes a value of 2/3 to the total cut. We will denote this value by bmax . Now when s ∈ (2, 12 ci ),
37

the value then decreases to

1
bn/4c

P

bn/4c−1
bk
k=0


− 2/3 + 1/2 which we will call bmin . We can extend

this observation as follows to any interval Ii,k = (2 · cki , 21 ck+1
)
i
(


bmin s ∈ Ii,k for even k ≤ bn/4c − 1,
(i)
(i)
(i)
rprts G , Z , Q
=
bmax s ∈ Ii,k for odd k ≤ bn/4c − 1,

Now we only need to choose ri to be (bmin + bmax )/2. To complete the proof, we need to show
that the oscillations with respect to these witnesses for all the samples are spaced in a manner that
we can pick 2m different s covering all possible oscillations for m = Ω(log n).
This becomes clear from two observations. First, Ii,2k ∪ Ii,2k+1 ⊂ Ii+1,k because ci = 2c2i−1 .
Secondly, values of s injIi,2k and kIi,2k+1 induce different labelings on the ith sample.
bn/4c

samples. It turns out that c2m /2 ≤ c1
. That is, Im,0 ∪ Im,1
Now consider m = log(bn/4c)
3
contains I1,0 ∪ . . . I1,bn/4c−1 . We then claim that the intervals I1,k each induce a different labeling
on S with respect to the witnesses. To see why this is true, observe that since Ii,k ⊂ Ii+1,bk/2c , the
labeling induced by s ∈ I1,k is defined by which terms of the sequence k1 = k, ki+1 = bki /2c are
odd. This however is in fact the binary equivalent of k. Since the binary equivalent for a given
k is unique, the labeling induced by I1,k is unique. Thus, we have Ω(log n) samples that can be
shattered.

B.3.4

A learning algorithm

We now present a learning algorithm(Algorithm 8) which (, δ)-learns the best rounding function
with respect to D from a class of sigmoid-like rounding functions.
Algorithm 8 An algorithm for finding an empirical value maximizing rounding function fs
n

o

(m)
Input: Sample S = A(1) , Z(1) , Q(1) , . . . , A(m) , Z(m),Q

1: Solve for X (1) , . . . , X (m) the optimal SDP embeddings of A(1) , . . . , A(m) , where X (i) =


(i)
(i)
x1 , . . . , xn .

2: Let T = s1 , . . . , s|T | be the set of all values s > 0 such that there exists a pair of indices
(j)

(j)

i ∈ [n], j ∈ [m] with hZ(j) , xi i = sqi .

 1 Pm
(i)
(i)
(i) .
3: Let ŝ = argmax
i=1 rprts A , Z , Q
m

Output: ŝ

s∈T ∪{s|T | +1}

In particular, we prove the following guarantee regarding Algorithm 8’s performance.

1 Pm
Lemma 17. Algorithm 2 produces the value ŝ which maximizes m
rpr2s A(i) , Z(i) , Q(i)
i=1



given the sample S = A(1) , Z(1) , Q(1) , . . . , A(m) , Z(m) , Q(m) . Algorithm 8 has running time
polynomial in m and n.
Proof. The correctness of the algorithm is evident from the proof for Lemma 15. The algorithm
identifies the n values of s at which the behavior of RPRT changes and proceeds to exhaustively
evaluate all the possible binary assignments which are only polynomially many. Therefore the
algorithm successfully finds the best value of s in polynomial time.

38


Corollary 1. Given an input sample of size m = O 12 log n log 1 + log 1δ drawn from (D × Z ×
(p1 )n )m , Algorithm 8 (, δ)-learns the class of rounding functions F with respect to the cost function
−rpr2s and is computationally efficient.

C

Proofs from Section 3

Theorem 4. For i ∈ {1, 2, 3} and a permissible
value iof α for Ahi , there exists
h
i a distribution D
(p)
(p)
over clustering instances V such that EV∼D ΦAi (α) (V) < EV∼D ΦAi (α0 ) (V) for all permissible

values of α0 6= α for Ai .

Proof. We give a general proof for all three classes A1 , A2 , and A3 . We will point out a few places
in the proof where the details for b = 1, 2, 3 are different, but the general structure of the argument
is the same. For each value of b, we construct a single clustering instance V = (V, d) that has the
desired property; the distribution D is merely the single clustering instance with probability 1.
Consider some permissible value of α, denoted α∗ . Set k = 4 and n = 210. The clustering
instance consists of two well-separated ‘gadgets’ of two clusters each. The class Ab results in
different 2-clusterings of the first gadget depending on whether α ≤ α∗ or not. Similarly, Ab results
in different 2-clusterings of the second gadget depending on whether α ≥ α∗ or not. By ensuring
that for the first gadget α ≤ α∗ results in the lowest cost 2-clustering, and for the second gadget
α ≥ α∗ results in the lowest cost 2-clustering, we ensure that α = α∗ is the optimal parameter
overall.
The first gadget is as follows. We define five points a1 , b1 , c1 , x1 and y1 . For the sake of
convenience, we will group the remaining points into four sets A1 , B1 , X1 , and Y1 each containing 25
points. We set the distances as follows: d(a1 , b1 ) = d(x1 , y1 ) = 1, d(a1 , c1 ) = 1.1, and d(b1 , c1 ) = 1.2.
For a ∈ A1 ∪ B1 , d(c1 , a) = 1.51 and d(a1 , a) = d(b1 , a) = 1.6. For x ∈ X1 ∪ Y1 , d(x1 , x) = d(y1 , x) =
1.6. For a ∈ A1 , b ∈ B1 , x ∈ X1 , and y ∈ Y1 , d(a, b) = d(x, y) = 1.6. We also define special points
x∗1 ∈ X1 and y1∗ ∈ Y1 , which have the same distances as the rest of the points in X1 and Y1
respectively, except that d(x1 , x∗1 ) = 1.51 and d(y1 , y1∗ ) = 1.51. If two points p and q belong to the
same set (A1 , B1 , X1 , or Y1 ), then d(p, q) = 1.5.
The distances d(x1 , c1 ) and d(y1 , c1 ) are defined in terms of b and α∗ , but they will always be
between 1.1 and 1.2. For b = 1, we set d(x1 , c1 ) = d(y1 , c1 ) = 1.2 − .1 · α∗ . For b = 2 and b = 3,
1
∗
∗
d(x1 , c1 ) = d(y1 , c1 ) = ((1.1α + 1.2α )/2) α∗ .
So far, all of the distances we have defined are in [1, 2], therefore they trivially satisfy the triangle
inequality. We set all of the rest of the distances to be the maximum distances allowed under the
triangle inequality. Therefore, the triangle inequality holds over the entire metric.
Now, let us analyze the merges caused by Ab (α) for various values of α. Regardless of the values
of α and b, since the distances between the first five points are the smallest, merges will occur over
these initially. In particular, regardless of α and b, a1 is merged with b1 , and x1 with y1 . Next, by
a simple calculation, if α ≤ α∗ , then c1 merges with a1 ∪ b1 . If α > α∗ , then c1 merges with x1 ∪ y1 .
Denote the set containing a1 and b1 by A01 , and denote the set containing x1 and y1 by X10 (one of
these sets will also contain c1 ). Between A01 and X10 , the minimum distance is ≥ 1.1 + 1.1 ≥ 2.2.
All other subsequent merges (except for the very last merge) will involve all distances smaller than
2.2, so we never need to consider A01 merging to X10 .
The next smallest distances are all 1.5, so all points in A1 will merge together, and similarly
for B1 , X1 , and Y1 . At this point, the algorithm has created six sets: A01 , X10 , A1 , B1 , X1 , and Y1 .
We claim that if α ≤ α∗ , A01 will merge to A1 and B1 , and X10 will merge to X1 and Y1 . This is
because the maximum distance between sets in each of these merges is 1.6, whereas the minimum
39

distance between {A01 , A1 , B1 } and {X10 , X1 , Y1 } is ≥ 2.2. Therefore, for all three values of b, the
claim holds true.
Next we claim that the 2-clustering cost of gadget 1 will be lowest for clusters A01 ∪ A1 ∪ B1 }
and X10 ∪ X1 ∪ Y1 and when c1 ∈ A01 , i.e., when α ≤ α∗ . Clearly, since the distances within
A01 ∪ A1 ∪ B1 and X10 ∪ X1 ∪ Y1 are much less than the distances across these sets, the best 2clustering is A01 ∪ A1 ∪ B1 and X10 ∪ X1 ∪ Y1 (with all points at distance ≤ 1.6 to their center).
We proved this will be a pruning of the tree when α ≤ α∗ . Therefore, we must argue the cost
of this 2-clustering is lowest when c1 ∈ A01 . The idea is that c1 can act as a very good center for
A01 ∪ A1 ∪ B1 . But if c1 ∈ X10 , then the best center for A01 ∪ A1 ∪ B1 will be an arbitrary point
in A1 ∪ B1 . The cost in the first case is 1.51p · 50 + 1.1p + 1.2p . The cost in the second case is
1.5p · 24 + 1.6p · 27.
For X10 ∪ X1 ∪ Y1 , the center does not change depending on α (x∗1 and y1∗ tie for the best center),
so the only difference in the cost is whether or not to include c1 . If α ≤ α∗ , then the cost is
1.5p · 24 + 1.51p + 1.6p · 26, otherwise the cost is 1.5p · 24 + 1.51p + 1.6p · 26 + (1.6 + 1.2 − 0.1α∗ )p .
Putting it all together, if α ≤ α∗ , the cost is 1.51p · 50 + 1.1p + 1.2p + 1.5p · 24 + 1.51p + 1.6p · 26.
Otherwise the cost is 1.5p · 48 + 1.51p + 1.6p · 53 + (1.6 + 1.2 − 0.1α∗ )p . Subtracting off like terms,
we conclude that the first case is always smaller because 1.51p · 49 + 1.1p + 1.2p < 1.5p · 24 + 1.6p ·
26 + (1.6 + 1.2 − 0.1α∗ )p for all p ≥ 1.
Next, we will construct the second gadget arbitrarily far away from the first gadget. The second
gadget is very similar to the first. There are points a2 , b2 , c2 , x2 , y2 , x∗2 , y2∗ and sets to A2 , B2 , X2 ,
Y2 . d(a2 , b2 ) = d(x2 , y2 ) = 1, d(x2 , c2 ) = 1.1, d(y2 , c2 ) = 1.2, and for b = 1, d(a2 , c2 ) = d(b2 , c2 ) =
1
∗
∗
1.2 − .1 · α∗ . For b = 2 or b = 3, d(a2 , c2 ) = d(b2 , c2 ) = ((1.1α + 1.2α )/2) α∗ . The rest of the
distances are the same as in gadget 1. Then c2 joins {a2 , b2 } if α ≥ α∗ , not α ≤ α∗ . The rest of the
argument is identical. So the conclusion we reach, is that the cost for the second gadget is much
lower if α ≥ α∗ .
Therefore, the final cost of the 4-clustering is minimized when α = α∗ , and the proof is complete.
Now we will show a structural lemma for A3 , which is similar to Lemma 6. Then we will provide
the full details for the proof of Lemma 6.
Lemma 18. ΦA3 ,V : [0, 1] → R>0 is made up of O(n8 ) piecewise constant components.
Proof. First note that for α 6= α0 , the clustering returned by A1 (α) and the associated cost are both
identical to that of A1 (α0 ) if both the algorithms construct the same merge tree. Now, as we increase
α from 0 to 1 and observe the run of the algorithm for each α, at what values of α do we expect
A1 (α) to produce different merge trees? To answer this, suppose that at some point in the run
of algorithm A1 (α), there are two pairs of subsets of V , (A, B) and (X, Y ), that could potentially
merge. There exist eight points p, p0 ∈ A, q, q 0 ∈ B, x, x0 ∈ X, and y, y 0 ∈ Y such that the decision
of which pair to merge depends on whether αd(p, q) + (1 − α)d(p0 , q 0 ) or αd(x, y) + (1 − α)d(x0 , y 0 )
is larger. Clearly, there is at most one value of α for which these expressions are equal, unless
the difference of the expressions is zero for all α. Assuming that ties are broken arbitrarily but
consistently, this implies that there is at most one α ∈ [0, 1] such that the choice of whether to
merge (A, B) before (X, Y ) is identical for all α < α0 , and similarly identical for α ≥ α0 . Since each
merge decision is defined by eight points, iterating over all pairs (A, B) and (X, Y ) it follows that
we can identify all O(n8 ) unique 8-tuples of points which correspond to a value of α at which some
decision flips. This means we can divide [0, 1] into O(n8 ) intervals over each of which the merge
tree, and therefore the output of ΦA1 ,V (α), is fixed.

40

Now we will provide the details of Lemma 6. In the argument for the structure of HA3 ,Φ ,
we relied on the linearity of A3 ’s merge equation to prove that for any eight points, there is
exactly one value of α such that αd(p, q) + (1 − α)d(p0 , q 0 ) = αd(x, y) + (1 − α)d(x0 , y 0 ). Now
we will use a consequence of Rolle’s Theorem (Theorem 20) to bound the values of α such that
((d(p, q))α + d(p0 , q 0 )α )1/α = ((d(x, y))α + d(x0 , y 0 )α )1/α .
P
x
Theorem 20 (ex. [37]). Let f be a polynomial-exponential sum of the form f (x) = N
i=1 ai bi ,
where bi > 0, ai ∈ R, and at least one ai is non-zero. The number of roots of f is upper bounded
by N .
Lemma 6. ΦA1 ,V : R ∪ {−∞, ∞} → R>0 is made up of O(n8 ) piecewise constant components.
Proof. As was the case for HA3 , the clustering returned by A1 (α) and the associated cost are
identical to that of A1 (α0 ) as long as both algorithms construct the same merge trees. Our objective
is to understand the behavior of A1 (α) over m instances. In particular, as α varies over R we
want to count the number of times the algorithm outputs a different merge tree on one of these
instances. For some instance V we will consider two pairs of sets A, B and X, Y that can be
potentially merged. The decision to merge one pair before the other is determined by the sign of
dα (p, q) + dα (p0 , q 0 ) − dα (x, y) + dα (x0 , y 0 ). This expression, as before, is determined by a set of 8
points p, p0 ∈ A, q, q 0 ∈ B, x, x0 ∈ X and y, y 0 ∈ Y chosen independent of α.
Now, from Theorem 20, we have that the sign of the above expression as a function of α flips 4
times across R. Since the expression is defined by exactly 8 points, iterating over all pairs (A, B)
and (X, Y ) we can list only O(n8 ) such unique expressions, each of which correspond to O(1) values
of α at which the corresponding decision flips. Thus, we can divide R into O(n8 ) intervals over
each of which the output of ΦA1 ,V (α) is fixed.
Now we give the full details for Lemmas 7 and 8.
Lemma 7. For any Φ, Pdim(HA1 , Φ) = O(log n) and Pdim(HA3 , Φ) = O(log n).

Proof. Suppose S = V (1) , . . . , V (m) is a set of clustering instances that can be shattered by
HA1 using the witnesses r1 , . . . , rm . We must show that m = O(log n). For each value of α ∈
R ∪ {−∞, ∞},
V (i) , based on whether or not
 the algorithm A1 (α) induces a binary labeling on each
(i)
(i)
ΦA1 (α) V
≤ ri . From Lemma 6, we know that every sample V partitions R ∪ {∞, −∞} into
8
O(n ) intervals in this way. Merging all m partitions, we can divide R ∪ {∞, −∞} into O(mn8 )
intervals over each of which ΦA3 ,V (i) (α), and therefore the labeling induced by the witnesses, is
fixed for all i ∈ [m] (similar to Figure 7). This means that HA1 can achieve only O(mn8 ) binary
labelings, which is at least 2m since S is shatterable, so m = O(log n).
The details for HA3 , Φ are identical, by using Lemma 18.




Lemma 8. For any objective function Φ(p) , Pdim HA1 ,Φ(p) = Ω(log n) and Pdim HA3 ,Φ(p) =
Ω(log n).
We first prove this lemma for the center-based objective cost denoted by Φ(p) for p ∈ [1, ∞) ∪
{∞}. We later note how this can be extended cluster purity based cost. We first prove the following
useful statement which helps us construct general examples with desirable properties. In particular,
the following lemma guarantees that given a sequence of values of α of size O(n), it is possible to
construct an instance V such that the cost of the output of A1 (α) on V as a function of α, that
(p)
is ΦA1 ,V (α), oscillates above and below some threshold as α moves along the sequence of intervals
(αi , αi+1 ). Given this powerful guarantee, we can then pick appropriate sequences of α and generate
41

y1 0
1
x1 0

1.41

1

xi 0

1.41

z1

yi 0

1.4 − 0.1αi
2

z1 0

zi 0
zi

1.4
1.3

yi

y1
1

1
xi

x1

Figure 8: The clustering instance used in Lemma 19
a sample set of Ω(log n) instances that correspond to cost functions that oscillate in a manner that
helps us pick Ω(n) values of s that shatters the samples.
Lemma 19. Given n ∈ N, b ∈ {1, 3}, and given a sequence of n0 ≤ bn/7c α’s such that 0 = α0 <
α1 < · · · < αn0 < αn0 +1 = .7, there exists a real valued witness r > 0 and a clustering instance
(p)
V = (V, d), |V | = n, such that for 0 ≤ i ≤ n0 /2 − 1, ΦAb (α) (V) < r for α ∈ (α2i , α2i+1 ), and
(p)

ΦAb (α) (V) > r for α ∈ (α2i+1 , α2i+2 ), for k = 2.

Proof. First, we focus on A3 , and we discuss A1 at the end of the proof. First of all, in order for
d to be a metric, we set all distances in [1, 2] so that the triangle inequality is trivially satisfied.
In particular, the following are the distances of the pairs of points within each group for 1 ≤ i ≤
(n − 2)/6.
d(xi , yi ) = d(x0i , yi0 ) = 1,
d(xi , zi ) = 1.3, d(yi , zi ) = 1.4,
d(x0i , zi ) = d(yi0 , zi ) = 1.4 − .1 · αi ,

d(xi , x0i ) = d(yi , yi0 ) = 2.
We set the distances to zi0 as follows (see Figure 8).

d(xi , zi0 ) = d(yi , zi0 ) = d(x0i , zi0 ) = d(yi0 , zi0 ) = 1.41,
d(zi , zi0 ) = 2.
Then the first merges will be xi to yi and x0i to yi0 , no matter what α is set to be (when each
point is a singleton set, each pair of points with the minimum distance in the metric will merge).
Next, zi will either merge to Ai or A0i based on the following equation:
α · 1.3 + (1 − α) · 1.4 ≶ α · (1.4 − .1 · αi ) + (1 − α)(1.4 − .1 · αi )
42

1.4 − .1 · α ≶ 1.4 − .1 · αi

=⇒
=⇒

αi ≶ α

If α < αi , then zi merges to A0i , otherwise it will merge to Ai . Notice that the merge expression
for Ai to A0i could be as small as α · 1.3 + (1 − α) · 2 = 2 − .7 · α, but we do not want this
merge to occur. If we ensure all subsequent merges have maximum distance less than 1.5, then
Ai will not merge to A0i (until A and A0 merge in the very final step) as long as α < .7, because
α · 1.5 + (1 − α) · 1.5 = 1.5 < 2 − .7 · .7.
These distances ensure zi0 merges after zi regardless of the value of α, since zi is closer than zi0
to xi , x0i , yi , and yi0 . Furthermore, zi0 will merge to the opposite set of zi , since we set d(zi , zi0 ) = 2.
The merge expression for zi0 to merge to the opposite set is α · 1.41 + (1 − α) · 1.41, while the merge
expression to the same set is ≥ α · 1.41 + (1 − α) · 2.
Now we set the distances to a and a0 as follows.
d(a, xi ) = d(a, yi ) = d(a0 , x0i ) = d(a0 , yi0 ) = 1.42,
d(a, x0i ) = d(a, yi0 ) = d(a0 , xi ) = d(a0 , yi0 ) = 2.
We also set all distances between Ai and A0j to be 2, for all i and j, and all distances between Ai
and Aj to be 1.5, for all i 6= j. We will set the distances from a and a0 to zi and zi0 later, but they
will all fall between 1.45 and 1.5. By construction, every set Ai will merge to the current superset
containing {a}, because the merge expression is α · 1.42 + (1 − α)1.5, and any other possible merge
will have value ≥ α · 1.3 + (1 − α) · 2, which is larger for α < .7. Similarly, all A0i sets will merge to
{a0 }.
Therefore, the final two sets in the linkage tree are A and A0 . Given 1 ≤ i ≤ (n − 2)/6, by con0 , . . . z0
0
0
struction, for α ∈ (αi , αi+1 ), {z1 , . . . , zi , zi+1
(n−2)/6 } ⊆ A and {z1 , . . . , zi , zi+1 , . . . z(n−2)/6 } ⊆
A0 .
Finally, we set the distances between a, a0 , zi , and zi0 to ensure the cost function oscillates.
∀1 ≤ j ≤ (n − 2)/12,

∀i,

d(a, zi0 ) = d(a0 , zi ) = 1.46

0
d(a, z2j−1 ) = d(a0 , z2j
) = 1.47,

0
and d(a, z2j ) = d(a0 , z2j+1
) = (2 · 1.46p − 1.47p )1/p .

Now we calculate
cost of (A, A0 ) for α’s in different ranges. Regardless of α, all
Pthe 2-clustering
partitions will pay i (d(a, xi )p + d(a, yi )p + d(a0 , x0i )p + d(a0 , yi0 )p ) = (n − 2)/6 · (4 · 1.42p ),but the
distances for zi and zi0 differ. For α ∈ (α0 , α1 ), all of the z’s pay 1.46p , so the cost is (n − 2)/6 · (4 ·
1.42p + 2 · 1.46p ). Denote this value by rlow .
When α ∈ (α1 , α2 ), the only values that change are z1 and z10 , which adds d(a, z1 ) + d(a0 , z10 ) −
d(a, z10 ) − d(a0 , z1 ) = 2 · (1.47p − 1.46p ) > 0 to the cost (the inequality is always true for p ∈ [1, ∞]).
Denote rlow + 2 · (1.47p − 1.46p ) by rhigh . When α ∈ (α2 , α3 ), the values of z2 and z20 change, and
the cost changes by d(a, z2 ) + d(a0 , z20 ) − d(a, z20 ) − d(a0 , z2 ) = 2 · ((2 · 1.46p − 1.47p ) − 1.46p ) =
−2 · (1.47p − 1.46p ), decreasing it back to rlow . P
In general, the cost for α ∈ (αi , αi+1 ) is rlow + 1≤j≤i (−1)i+1 · 2(1.47p − 1.46p ) = rlow + (1.47p −
1.46p ) + (−1)i+1 · (1.47p − 1.46p ). If α ∈ (α2j , α2j+1 ), then the cost is rlow , and if α ∈ (α2j+1 , α2j+2 ),
the cost is rhigh . We set r = (rlow + rhigh )/2, and conclude that the cost function oscillates above
and below r as specified in the lemma statement.
The pruning step will clearly pick (A, A0 ) as the optimal clustering, since the only centers with
more than 3 points at distance < 1.5 are a and a0 , and (A, A0 ) are the clusters in which the most
points can have a and a0 as centers. This argument proved the case where n0 = (n − 2)/6. If
43

n0 < (n − 2)/6, then we set d(a, zi ) = d(a0 , zi0 ) = 1.46 for all i > n0 , which ensures the cost function
oscillates exactly n0 times. This completes the proof.
It is straightforward to modify this proof to work for A1 . The only major change is to set
1

d(x0i , zi ) = d(yi0 , zi ) = ((1.3αi + 1.4αi )/2) αi .

Now we can prove Lemma 8.
Proof of Lemma 8. Given b ∈ {1, 2}, we prove the claim for HAb ,Φ(p) by constructing a set of
samples S = {V (1) , . . . , V (m) } where m = log n − 3 that can be shattered by HAb ,Φ(p) . That is,
we should be able to choose 2m = n/8 different values of α such that there exists some witnesses
(p)
r1 , . . . , rm with respect to which ΦAb (α) (·) induces all possible labelings on S.
Choose a sequence of 2m distinct α’s arbitrarily in the range (0, .7). We will index the terms of
this sequence using the notation αx for all x ∈ {0, 1}m , such that αx < αy iff x1 x2 . . . xm < y1 y2 ym .
Then the α’s satisfy
0 < α[0

... 0 0]

< α[0

... 0 1]

< α[0

... 1 0]

< · · · < α[1

... 1 1]

< .7.

Given x, denote by n(x) the vector corresponding to x1 x2 . . . xs + 1, therefore, αn(x) is the smallest
α greater than αx .
Now, the crucial step is that we will use Lemma 19 to define our examples V (1) , . . . V (m) and
witnesses r1 , . . . rm so that when α ∈ (αx , αn(x) ) the labeling induced by the witnesses on S corre(p)

sponds to the vector x. This means that for α ∈ (αx , αn(x) ) the cost function ΦAb (α) (V (i) ) must be
greater than ri if the ith term in x is 1, and less than ri otherwise. Since there are only 2m = n8
x’s, it implies that for any sample V (i) there at most n/8 values of α at which we want its cost to
flip above/below ri . We can we can accomplish this using Lemma 19 by choosing αx ’s for which
V (i) is supposed to switch labels. In this manner, we pick each V (i) and ri thus creating a sample
of size Ω(log n) that is shattered by HAb ,Φ(p) .
Note C.1. Lemma 8 assumes that the pruning step fixes a partition, and then the optimal centers
can be chosen for each cluster in the partition, but points may not switch clusters even if they are
closer to the center in another cluster. This is desirable, for instance, in applications which much
have a balanced partition.
If it is desired that the pruning step only outputs the optimal centers, and then the clusters are
determined by the Voronoi partition of the centers, we modify the proof as follows. We introduce
2n0 more points into the clustering instance: c1 , . . . , cn0 , and c01 , . . . , c0n0 . Each ci will merge to
cluster A, and each c0i will merge to cluster A0 . We set the distances so that ci and c0i will be the
best centers for A and A0 when α ∈ (αi , αi+1 ). The distances are also set up so that the cost of
the Voronoi tiling induced by c2i and c02i is rlow , and the cost for c2i+1 and c02i+1 is rhigh . This is
sufficient for the argument to go through.
Furthermore, the lower bound holds even ifSthe cost function is theSsymmetric distance to the
0
0 } be the ground
ground truth clustering. For this proof, let A ∪ i {z2i , z2i+1
} and A0 ∪ i {z2i+1 , z2i
truth clustering. Then in each interval as α increases, the cost function switches between having
(n − 2)/3 errors and having (n − 2)/3 − 2 errors.
Now we restate and prove Lemma 10.



Lemma 10. For all objective functions Φ(p) , Pdim HA2 ,Φ(p) = Ω(n).
44

To prove this, we start with a helper lemma.
Lemma 20. Given n, and setting N = b(n−8)/2c, then there exists a clustering instance V = (V, d)
of size |V | = n and a set of 2N + 2 α’s for which α-linkage creates a unique merge tree.
Proof. Here is the outline of our construction. At the start, two specific pairs of points will always
merge first: pa merges with qa , and pb merges with qb . The sets {pa , qa } and {pb , qb } will stay
separated until the last few merge operations. Throughout the analysis, at any point in the merging
procedure, we denote the current superset containing {pa , qa } by A, and we similarly denote the
superset of {pb , qb } by B. The next points to merge will come in pairs, (pi , qi ) for 1 ≤ i ≤ N . We
construct the distances so that pi and qi will always merge before pj and qj , for i < j. Furthermore,
for all i, {pi } will first merge to A or B, and then {qi } will merge to the opposite set as pi . Let
these two merges be called ‘round i’, for 1 ≤ i ≤ N . Finally, there will be a set CA of size N + 2
which merges together and then merges to A, and similarly a set CB which merges to B.
Thus, in our construction, the only freedom is whether pi merges to A or to B, for all i. This
is 2N combinations total. The crux of the proof is to show there exists an α for each of these
behaviors.
We attack the problem as follows. In round 1, the following equation specifies whether p1 merges
to A or B:
1
1
(d(pa , p1 )α + d(qa , p1 )α ) ≶ (d(pb , p1 )α + d(qb , p1 )α )
2
2
If the LHS is smaller, then p1 merges to A, otherwise B. By carefully setting the distances, we
will ensure there exists a value α0 which is the only solution to the equation in the range (1, 3).
Then p1 merges to A for all α ∈ (1, α0 ), and B for all α ∈ (α0 , 3). For now, assume it is easy to
force q1 to merge to the opposite set.
In round 2, there are two equations:
1
(d(pa , p2 )α + d(qa , p2 )α + d(p1 , p2 )α ) ≶
3
1
(d(pa , p2 )α + d(qa , p2 )α + d(q1 , p2 )α ) ≶
3

1
(d(pb , p2 )α + d(qb , p2 )α + d(q1 , p2 )α ),
3
1
(d(pb , p2 )α + d(qb , p2 )α + d(p1 , p2 )α ).
3

The first equation specifies where p2 merges in the case when p1 ∈ A, and the second equation is
the case when p1 ∈ B. So we must ensure there exists a specific α[−1] ∈ (1, α0 ) which solves equation
1, and α[1] ∈ (α0 , 3) which solves equation 2, and these are the only solutions in the corresponding
intervals.
In general, round i has 2i−1 equations corresponding to the 2i−1 possible states for the partially
constructed tree. For each state, there is a specific α interval which will cause the algorithm to
reach that state. We must ensure that the equation has exactly one solution in that interval. If we
achieve this simultaneously for every equation, then the next round will have 2 · 2i−1 states. See
Figure 9 for a schematic of the clustering instance.
For 1 ≤ i ≤ N , given x ∈ {−1, 1}i−1 , let Ex denote the equation in round i which determines
where pi merges, in the case where for all 1 ≤ j < i, pj merged to A if xj = −1, or B if xj = 1
(and let E 0 denote the single equation for round 1). Let αx ∈ (1, 3) denote the solution to Ex = 0.
Then we need to show the α’s are well-defined and follow a specific ordering, shown in Figure
10. This ordering is completely specified
by two conditions: (1) α[x −1] < α[x] < α[x 1] and (2)
S
α[x −1 y] < α[x 1 z] for all x, y, z ∈ i<N {−1, 1}i and |y| = |z|.
Now we show how to set up the distances to achieve all of these properties. To enhance
readability, we start with an example for n = 10, and then move to the general construction.

45

qb

pb
1

≈ 1.151

≈ 1.151
p1 2

pi

q1

qi

pN
qN
1.2

All distances here ≈ 1.5

1.1

1
qa

pa

Figure 9: The clustering instance used in Lemma 10

α0
p1

q1

α[−1]
p2

q2

α[−1 −1]
α[−1 −1]

α[1]
p2
α[−1 1]

α[−1]

α[−1 1]

q2

α[1 −1]
α0

α[1 −1]

α[1 1]
α[1]

α[1 1]

Figure 10: A schematic for the α intervals. Each edge denotes whether to merge pi to A or qi to A.

46

We give the construction round by round. All distances are in [1, 2] which ensures the triangle
inequality is always satisfied. Set d(pa , qa ) = d(pb , qb ) = 1, and set all pairwise distances between
{pa , qa } and {pb , qb } to 2. We also set d(pi , qi ) = 2 for all i 6= j.
Here are the distances for the first round.
d(pa , p1 ) = d(pa , q1 ) = 1.1, d(qa , p1 ) = d(qa , q1 ) = 1.2,
p
d(pb , p1 ) = d(pb , q1 ) = d(qb , p1 ) = d(qb , q1 ) = (1.12 + 1.22 )/2 ≈ 1.151.

Say we break ties by lexicographic order. Then p1 will merge first, and E 0 is the following.
1
1
(1.1α + 1.2α ) ≶ (1.151α + 1.151α ).
2
2
The unique solution in (1, 3) is α0 = 2. p1 merges to A for α ∈ (1, 2), and B for α ∈ (2, 3).
The merge equations for q1 are
1
(1.1α + 1.2α + 2α ) ≶
3
1
(1.1α + 1.2α ) ≶
2

1
(1.151α + 1.151α ) if p1 ∈ A, or
2
1
(1.151α + 1.151α + 2α ) otherwise.
3

As long as α ∈ (1, 3), q1 will merge to the opposite cluster as p1 . This is because we set d(p1 , q1 )
to be significantly larger than the other relevant distances.
We set the round two distances as follows.
d(pa , p2 ) = d(pa , q2 ) = 1.1,

d(qa , p2 ) = d(qa , q2 ) = 1.2,
p
d(pb , p2 ) = d(pb , q2 ) = d(qb , p2 ) = d(qb , q2 ) = (1.12 + 1.22 )/2 ≈ 1.151,
d(p1 , p2 ) = d(p1 , q2 ) = 1.5 + 10−4 ,

d(q1 , p2 ) = d(q1 , q2 ) = 1.5 − 10−4 .

Note the distances from {pa , qa , pb , qb } are the same to p1 as to p2 . Since we break ties lexicographically, this ensures p2 and q2 merge in round 2. Alternatively, we can add tiny perturbations
to the distances such that they do not affect our analysis, but ensure the correct merge orders regardless of the tiebreaking rule. The values were picked so that the pa , qa , pb , qb distances will have
the most influence in the merge equations. If it were just these four distances, then the value of α
at equality would be 2 again. But in this round, the p1 and q1 distances show up in the equation.
We set d(p1 , p2 ), d(q1 , p2 ) ≈ 1.5 but with small ‘offsets’ so that the values of α are on either side of
α0 = 2. Equations E[−1] and E[1] are the following.
1
1
(1.1α + 1.2α + 1.5001α = (2 · 1.151α + 1.4999α ),
3
3
1
1
(1.1α + 1.2α + 1.4999α ) = (2 · 1.151α + 1.5001α ).
3
3
Then α[−1] ≈ 1.884 and α[1] ≈ 2.124.
As in the previous round, it is straightforward to check all four merge equations for q2 send q2
to the opposite cluster as p2 , as long as α < 3. So far, our four intervals of α which lead to distinct
behavior are (1, 1.884), (1.884, 2), (2, 2.124), and (2.124, 3).

47

Now we specify the distances for the third round, the final round in our example. Again, we
set the distances from {pa , qa , pb , qb } the same way as in previous rounds. The new distances are
as follows.
d(p1 , p3 ) = d(p1 , q3 ) = 1.5 + 10−4 ,

d(q1 , p3 ) = d(q1 , q3 ) = 1.5 + 10−4 ,

d(p2 , p3 ) = d(p2 , q3 ) = 1.5 + 10−6 ,

d(q2 , p3 ) = d(q2 , q3 ) = 1.5 − 10−6 .

Again, if it were just the first four points, the value of α would be 2. The distances for {p1 , q1 }
differ by a small offset, and the distances for {p2 , q2 } differ by an even smaller offset, which causes
the latter distances to have less influence in the merge equations. This forces the α’s into the
correct intervals. In general, the offset value will decrease in higher and higher rounds.
The equations E[−1 −1] , E[−1 1] , E[1 −1] , and E[1 1] are as follows:
1
(1.1α + 1.2α + (1.5 + 10−4 )α + (1.5 + 10−6 )α ) =
4
1
(1.1α + 1.2α + (1.5 + 10−4 )α + (1.5 − 10−6 )α ) =
4
1
(1.1α + 1.2α + (1.5 − 10−4 )α + (1.5 + 10−6 )α ) =
4
1
(1.1α + 1.2α + (1.5 − 10−4 )α + (1.5 − 10−6 )α ) =
4

1
(2 · 1.151α + (1.5 − 10−4 )α + (1.5 − 10−6 )α ),
4
1
(2 · 1.151α + (1.5 − 10−4 )α + (1.5 + 10−6 )α ),
4
1
(2 · 1.151α + (1.5 + 10−4 )α + (1.5 − 10−6 )α ),
4
1
(2 · 1.151α + (1.5 + 10−4 )α + (1.5 + 10−6 )α ).
4

Solving for the α’s, we obtain α[−1 −1] ≈ 1.882, α[−1 1] ≈ 1.885, α[1 −1] ≈ 2.123, α[1 1] ≈ 2.125.
Furthermore, solving the equations for q3 , we find that it will merge to the opposite cluster for
α < 3. Therefore, we have 8 different ranges corresponding to the 8 equations.
This example suggests a general argument by induction which follows the same intuition. In
each round, the new distances have less and less influence in the merge equations, ensuring the α’s
stay in the correct ranges to double the number of behaviors.
In our argument, we will utilize the following fact (true by elementary calculus).
Fact 1. For all 0 ≤ z ≤ .01 and α ∈ (1, 3), the following are true about g(z, α) = (1.5 − z)α −
α
(1.5 + z)α and h(z, α) = (1.1 − z)α + (1.1 + z)α − 2 · (((1.1 − z)α + (1.1 + z)α )/2) 2 .
1. For z > 0, g(z, α) < 0,
2. for a fixed z, g is nonincreasing in α,
3. for a fixed α, g is nonincreasing in z,
4. h(0, α) = 0 and h is nondecreasing in z.
Here are the details for the general construction. All distances will be between 1 and 2 so that
the triangle inequality is satisfied. Given N , for all i,
d(pa , qa ) = d(pb , qb ) = 1,
d(pa , qa ) = d(pa , qb ) = d(pb , qa ) = d(pb , qb ) = 2,
∀i ≤ N, d(pa , pi ) = d(pa , qi ) = 1.1 − q, d(qa , pi ) = d(qa , qi ) = 1.1 + q,
r
1
d(pb , pi ) = d(pb , qi ) = d(qb , pi ) = d(qb , qi ) =
((1.1 − q)2 + (1.1 + q)2 ),
2
d(pi , qi ) = 2,
∀1 ≤ j < i ≤ N, d(pi , pj ) = d(pi , qj ) = 1.5 + oj

d(qi , pj ) = d(qi , qj ) = 1.5 − oj .

48

where q and oj are offset values in (0, .01) which we will specify later. Then for α ∈ (1, 3), the
following are true.
• The first two merges are pa to qa and pb to qb ,
• {pi } and {qi } will always prefer merging to A or B instead of merging to another singleton
{pj } or {qj }.
After the first two merges occur, all pi and qi are tied to first merge to A or B. For convenience,
we specify the tiebreaking order as {p1 , q1 , . . . , pN , qN }. Alternatively, at the end we can make tiny
perturbations to the distances so that tiebreaking does not occur.
Next, we choose the value for q, which must be small enough to ensure that qi always merges
to the opposite cluster as pi . Consider
!
X
N +2
h(α, q, o1 , . . . , oN , x) =
(1.1 + q)α + (1.1 − q)α +
xi (1.5 + oi )α + 1.5α
N +3
i<N
X
α
2
2
− 2 · (((1.1 + q) + (1.1 − q) )/2) 2 −
xi (1.5 + oi )α .
i<N

If this equation is positive for all x ∈ {−1, 1}N −1 , then qN will always merge to the opposite
cluster as pN (and qi will always merge to the opposite cluster as pi , which we can similarly show
by setting oj = 0 in h for all j > i).
Note
h(α, 0, 0, . . . , 0, x) =

N +2
(2 · 1.1α + (N + 1) · 1.5α ) − 2 · 1.1α − N · 1.5α > 0
N +3

for all x and all α ∈ (1, 3). Fact 1 implies there exists a 0 < q ∗ < .01 such that h(α, q, 0, . . . , 0, x)
stays positive. Similarly, there exists a cutoff value δ > 0 such that for all 0 < o1 , . . . , oN < δ,
α ∈ (1, 3), and x ∈ {−1, 1}N −1 , h(α, q ∗ , o1 , . . . , ok , x) > 0. Therefore, as long as we set all the
offsets oi less than δ, the merges will be as follows:
1. pa merges to qa and pb merges to qb .
2. For 1 . . . , N , pi merges to A or B, and qi merges to the opposite cluster. Then qN will always
merge to the opposite cluster as pN .
N
Now
S we showi that there are 2 intervals for α ∈ (1, 3) which give unique behavior. Recall for
x ∈ i<N {−1, 1} , Ex is defined as
X
α
1
(1.1 − q ∗ )α + (1.1 + q ∗ )α − 2 · ( ((1.1 − q ∗ )2 + (1.1 + q ∗ )2 )) 2 +
xi ((1.5 − oi )α − (1.5 + oi )α ).
2
i<N

For brevity, we denote

1
1
d = ( ((1.1 − q ∗ )2 + (1.1 + q ∗ )2 )) 2 .
2
We show the αs are correctly ordered by proving the following three statements with induction.
The first statement is sufficient to order the αs, and the second two will help to prove
S the first. i
1. There exist 0 < o1 , . . . , oN < δ such that if we solve Ex = 0 for αx for all x ∈ i<N {−1, 1} ,
then the α’s satisfy α[x −1] < α[x] < α[x 1] and for all i < N , α[x 1] < α[y −1] for x, y ∈ {−1, 1}i
and x1 . . . xi < y1 . . . yi .
2. For all k 0 ≤ N and α ∈ (1, 3),
X
(1.5 + ok0 )α − (1.5 − ok0 )α +
((1.5 − oi )α − (1.5 + oi )α ) > 0.

k0 <i<N

49

3.
X

(1.1 − q ∗ )3 + (1.1 + q ∗ )3 − 2 · d3 +
∗

∗

(1.1 − q ) + (1.1 + q ) − 2 · d +

i<N

X

i<N

((1.5 − oi )3 − (1.5 + oi )3 ) > 0, and

((1.5 + oi ) − (1.5 − oi )) < 0.

We proved the base case in our earlier example for n = 10. Assume for k ≤ N , there exist
0 < o1 , . . . , ok < δ which satisfy the three properties. We first prove the inductive step for the
second and third statements.
By inductive hypothesis, we know for all k 0 ≤ k and α ∈ (1, 3),
X
(1.5 + ok0 )α − (1.5 − ok0 )α +
((1.5 − oi )α − (1.5 + oi )α ) > 0,
k0 <i≤k

Since there are finite integral values of k 0 ≤ k, and the expression is > 0 for all values of k 0 , then
there exists an  > 0 such that the expression is ≥  for all values of k 0 . Then we define za such
that (1.5 + za )α − (1.5 − za )α < 2 for α ∈ (1, 3). Then for all 0 < z < za , k 0 ≤ k + 1, and α ∈ (1, 3),
(1.5 + ok0 )α − (1.5 − ok0 )α +

X

((1.5 − oi )α − (1.5 + oi )α ) > 0.

k0 <i≤k+1

So as long as we set 0 < ok+1 < za , the inductive step of the second property will be fulfilled. Now
we move to the third property. We have the following from the inductive hypothesis:
X
(1.1 − q ∗ )3 + (1.1 + q ∗ )3 − 2 · d3 +
((1.5 − oi )3 − (1.5 + oi )3 ) > 0,
i≤k0

(1.1 − q ∗ ) + (1.1 + q ∗ ) − 2 · d +

X

i≤k0

((1.5 + oi ) − (1.5 − oi )) < 0.

We may similarly find zb such that for all 0 < ok+1 < zb ,
(1.1 − q ∗ )3 + (1.1 + q ∗ )3 − 2 · d3 +
∗

∗

X

((1.5 − oi )3 − (1.5 + oi )3 ) > 0,

i≤k+1

(1.1 − q ) + (1.1 + q ) − 2 · d +

X

((1.5 + oi ) − (1.5 − oi )) < 0.

i≤k+1

Now we move to proving the inductive step of the first property. Given x ∈ {−1, 1}k , let
p(x), n(x) ∈ {−1, 1}k denote the vectors which sit on either side of αx in the ordering, i.e., αx is
the only αy in the range (αp(x) , αn(x) ) such that |y| = k. If x = [1 . . . 1], then set αn(x) = 3, and
if x = [0 . . . 0], set αp(x) = 1. Define
f (α, x, z) = Ex + (1.5 − z)α − (1.5 + z)α .
By inductive hypothesis, we have that f (αx , x, 0) = 0. We must show there exists zx such that
for all 0 ≤ z ≤ zx , f (αx , x, z) < 0 and f (αn(x) , x, z) > 0. This will imply that if we choose
0 < ok+1 < zx , then α[x 1] ∈ (αx , αn(x) ).

50

Case 1: x 6= [1 . . . 1]. Since f (αx , x, 0) = 0, and by Fact 1, then for all 0 < z < .01, f (αx , x, z) <
0. Now denote i∗ as the greatest index such that xi∗ = −1. Then n(x) = [x1 . . . xi∗ −1 1 − 1 · · · − 1].
By statement 1 of the inductive hypothesis (αn(x) is a root of En(x) = 0),
(1.1 − q ∗ )αn(x) + (1.1 + q ∗ )αn(x) − 2 · dαn(x) +

X
(n(x)i (1.5 − oi )αn(x) − n(x)i (1.5 + oi )αn(x) ) = 0
i≤k

From statement 2 of the inductive hypothesis, we know that
X
(1.5 − oi∗ )αn(x) − (1.5 + oi∗ )αn(x) +
((1.5 + oi )αn(x) − (1.5 − oi )αn(x) ) < 0.
i∗ <i≤k

It follows that
(1.1 − q ∗ )αn(x) + (1.1 + q ∗ )αn(x) − 2 · dαn(x) +

X

i<i∗

(n(x)i (1.5 − oi )αn(x) − n(x)i (1.5 + oi )αn(x) ) > 0,

and furthermore,
(1.1 − q ∗ )αn(x) + (1.1 + q ∗ )αn(x) − 2 · dαn(x) +

X

i<i∗

(xi (1.5 − oi )αn(x) − xi (1.5 + oi )αn(x) ) > 0.

Therefore, f (αn(x) , 0) > 0, so denote f (αn(x) , 0) =  > 0. Then because of Fact 1, there exists zx
such that ∀0 < z < zx , f (αn(x) , z) > 0.
Case 2: x = [1 . . . 1]. Since f (αx , 0) = 0, and by Fact 1, then for all 0 < z < .01, f (αx , z) < 0.
By property 3 of the inductive hypothesis, we have
X
(1.1 − q ∗ )3 + (1.1 + q ∗ )3 − 2 · d3 +
((1.5 − oi )3 − (1.5 + oi )3 ) > 0,
i≤k

so say this expression is equal to some  > 0. Then from Fact 1, there exists zx such that for all
0 < z < zx , 0 < (1.5 + z)3 − (1.5 − z)3 < 2 . Combining these, we have f (3, z) > 0 for all 0 < z < zx .
To recap, in both cases we showed there exists zx such that for all 0 < z < min(.01, zx ),
f (αx , z) < 0 and f (αn(x) , z) > 0. We may perform a similar analysis on a related function f 0 ,
defined as f 0 (α, x, z) = Ex + (1.5 + z)α − (1.5 − z)α to show there exists zx0 such that for all
0 < z < zx0 , f 0 (αp(x) , z) < 0 and f 0 (αx , z) > 0. We perform this analysis over all x ∈ {−1, 1}k .
Finally, we set ok+1 = minx (zx , zx0 , za , zb , .01). Given x ∈ {−1, 1}k , since f (αx , ok+1 ) < 0 and
f (αn(x) , ok+1 ) > 0, there must exist a root α[x 1] ∈ (αx , αn(x) ) (and by Fact 1, the function is
monotone in α in the short interval (αx , αn(x) ), so there is exactly one root). Similarly, there must
exist a root α[x −1] ∈ (αp(x) , αx ). Then we have shown α[x −1] and α[x 1] are roots of E[x −1] and
E[x 1] , respectively. By construction, α[x −1] < αx < α[x 1] , so condition 1 is satisfied. Now we
need to show condition 2 is satisfied. Given x, y ∈ {−1, 1}k , let k 0 be the largest number for which
xi = yi , ∀i ≤ k 0 . Let z = x[1...k0 ] = y[1...k0 ] . Then by the inductive hypothesis,
αx < αn(x) ≤ αz ≤ αp(y) < αy .
It follows that
α[x

−1]

< α[x

1]

< αz < α[y

proving condition 2. This completes the induction.

51

−1]

< α[y 1] ,

Now we are ready to prove Lemma 10.
Proof of Lemma 10. Given n, and setting N = b(n − 8)/4c, we will show there exists a clustering
instance (V, d) of size |V | = n, a witness r, and a set of 2N + 2 α’s 1 = α0 < α1 < · · · < α2N <
(p)
α2N +1 = 3, such that ΦA3 (α) (V) oscillates above and below r between each interval (αi , αi+1 ).
We start by using the construction from Lemma 10, which gives a clustering instance with
2N + 8 points and 2N + 2 values of α for which α-linkage creates a unique merge tree. The next
part is to add 2N more points and define a witness r so that the cost function alternates above
and below r along each neighboring α interval, for a total of 2N oscillations. Finally, we will finish
off the proof in a manner similar to Lemma 8.
Starting with the clustering instance (V, d) from Lemma 10, we add two sets of points, CA and
CB , which do not interfere with the previous merges, and ensure the cost functions alternates. Let
CA = {ca , c0a , a1 , a2 , . . . , aN } and CB = {cb , c0b , b1 , b2 , . . . , bN }. All distances between two points in
CA are 1, and similarly for CB . All distances between a point in CA and a point in CB are 2. The
distances between CA ∪ CB and A ∪ B are as follows (we defined the sets A and B in Lemma 10).
d(pa , ca ) = d(pa , c0a ) = d(qa , ca ) = d(qa , c0a ) = 1.51,
d(pb , cb ) = d(pb , c0b ) = d(qb , cb ) = d(qb , c0b ) = 1.51,
d(pa , cb ) = d(pa , c0b ) = d(qa , cb ) = d(qa , c0b ) = 2,
d(pb , ca ) = d(pb , c0a ) = d(qb , ca ) = d(qb , c0a ) = 2,
d(pa , c) = d(qa , c) = d(pb , c) = d(qb , c) = 2 ∀c ∈ CA ∪ CB \ {ca , c0a , cb , c0b },
d(c, pi ) = d(c, qi ) = 1.51 ∀1 ≤ i ≤ N − 1 and c ∈ CA ∪ CB .

We will specify the distances between {ca , c0a , cb , c0b } and {pN , qN } soon, but they will be in
[1.6, 2]. So at the start of the merge procedure, all points in CA merge together, and all points in
CB merge together. Then all merges from Lemma 10 take place, because all relevant distances are
smaller than 1.51. We end up with four sets: A, B, CA , and CB . The pairs (A, B) and (CA , CB ) are
dominated by distances of length 2, so the merges (CA , A) and (CB , B) will occur, which dominate
(CA , B) and (CB , A) because of the distances between {pa , qa , pb , qb } and {ca , c0a , cb , c0b }. The final
merge to occur will be (CA ∪ A, CB ∪ B), however, the 2-median pruning step will clearly pick the
2-clustering CA ∪ A, CB ∪ B, since no other clustering in the tree has almost all distances ≤ 1.51.
Then by construction, ca or c0a will be the best center for CA ∪ A, which beat pa and qa because
1.51 · (2N ) < 1.1 · N + 2 · N = 1.55 · (2N ). Similarly, cb or c0b will be the best center for CB ∪ B.
Note that centers {ca , c0a } and {cb , c0b } currently give equivalent 2-median costs. Denote this cost
by r0 (i.e., the cost before we set the distances to pN and qN ).
Now we set the final distances as follows.
d(ca , pN ) = d(cb , qN ) = 1.6,
d(c0a , pN ) = d(c0b , qN ) = 1.7,
d(c0a , qN ) = d(c0b , pN ) = 1.8,
d(ca , qN ) = d(cb , pN ) = 1.9.

If pN ∈ A and qN ∈ B, then ca and cb will be the best centers, achieving cost r0 + 3.2 for
(CA ∪ A, CB ∪ B). If pN ∈ B and qN ∈ A, then c0a and c0b will be the best centers, achieving cost
r0 + 3.6 for (CA ∪ A, CB ∪ B).
52

The distances are also constructed so that in the variant where the pruning outputs the optimal
centers, and then all points are allowed to move to their closest center, the cost still oscillates. First
note that no points other than pN and qN are affected, since d(ca , pi ) = d(ca , qi ) for i < N , and
similarly for cb . Then pN will move to the cluster with ca or c0a , and qN will move to the cluster
with cb or c0b . If pN was originally in A, then the cost is r0 + 3.2, otherwise the cost is r0 + 3.4.
In either scenario, we set r = r0 + 3.3. Then we have ensured for all x ∈ {−1, 1}N −1 , the cost
for α ∈ (αp(x) , αx ) is < r, and the cost for α ∈ (αx , αn(x) ) is > r.
We have finished our construction of a clustering instance whose cost function alternates 2N
times as α increases. To finish the proof, we will show there exists a set S = {V1 , . . . , Vs } of size
s = N = b(n − 8)/4c ∈ Ω(n) that is shattered by A. Such a set has 2N orderings total. For V1 ,
we use the construction which alternates 2N times. For V2 , we use the same construction, but we
eliminate (pN , qN ) so that there are only N − 1 rounds (the extra two points can be added to CA
and CB to preserve |V2 | = n). Then V2 ’s cost will alternate 12 · 2N times, between the intervals
(αp(x) , αx ) and (αx , αn(x) ), for x ∈ {−1, 1}N −2 . So V2 oscillates every other time V1 oscillates, as α
N

increases. In general, Vi will be the construction with only N − i + 1 rounds, oscillating 2 2i−1 times,
and each oscillation occurs every other time Vi−1 oscillates. This ensures for every x ∈ {−1, 1}N −1 ,
(αp(x) , αx ) and (αx , αn(x) ) will have unique labelings, for a total of 2N labelings. This completes
the proof.

Note C.2. As in Lemma 8, this lower bound holds even if the cost function is the symmetric
distance to the ground truth clustering. Merely let pN and qN belong to different ground truth
clusters, but for all i < N , pi and qi belong to the same ground truth cluster. Since in each
adjacent α interval, pN and qN switch clusters, this shows the symmetric distance to the ground
truth clustering oscillates between every interval.
Now we give an ERM algorithm for A2 , similar to Algorithm 4.
Algorithm 9 An algorithm for finding an empirical cost minimizing algorithm in A2

Input: Sample S = V (1) , . . . , V (m) .

1: Let T = ∅. For each sample V (i) = V (i) , d(i) ∈ S, and for all A, B, X, Y ⊆ V (i) , solve for α (if
a solution exists) in the following equation and add the solutions to T :
1
|A||B|

X

(d(p, q))α =

p∈A,q∈B

1
|X||Y |

X

(d(x, y))α .

x∈X,y∈Y

Order the elements of set T ∪ {−∞, +∞} as α1 < . . . < α|T | . For each 0 ≤ i ≤ |T |, pick an
arbitrary
α in the interval (αi , αi+1 ) and run A2 (α) on P
all clustering instances in S to compute
P
Φ
(V).
Let
α̂
be
the
value
which
minimizes
V∈S ΦA2 (α) (V).
V∈S A2 (α)
Output: α̂
2:

Theorem 21. Let Φ be a clustering objective
and let Ψ be a pruning function. Given an input


H 2
1
sample of size m = O
n + log δ , Algorithm 9 (, δ)-learns the class A2 × {Ψ} with respect

to the cost function Φ.
Proof. The sample complexity analysis follows the same logic as the proof of Theorem 6. To
prove that Algorithm 9 indeed finds the empirically best α, recall from the pseudo-dimension
analysis that the cost as a function of α for any instance is a piecewise constant function with
53

O(n2 32n ) discontinuities. In Step 1 of Algorithm 9, we solve for the values of α at which the
2 2n
discontinuities occur and add them to the set
PT . T therefore partitions α’s range into O(mn 3 )
subintervals. Within each of these intervals, V∈S ΦA2 (α) (V) is a constant function. Therefore, we
pick any arbitrary α within each interval to evaluate the empirical cost over all samples, and find
the empirically best α.

C.1

Restricted classes of clustering instances

Below we consider restricted classes of clustering instances and improve on the pseudo-dimension
bounds of HA2 as compared to Lemma 9. In particular, we consider the class Vβ that consists of
clustering instances in which the distances take one of at most β (β ∈ N) real values. A natural
example would be one in which all distances are integers and are less than some value H. Here,
β = H. For this case, we show a tight bound.
Theorem 22. For any objective function Φ, let

HA2 ,Φ = ΦA2 (α) : Vβ → R≥0 | α ∈ R ∪ {∞, −∞} .
Then Pdim(HA2 , Φ) = O (min(β log n, n)).

Proof. The proof for the upper bound follows a similar line of reasoning as that of Lemma 9. For a
particular instance V, let {d1 , d2 , . . . , dβ } denote the set of β values that its distances can take. The
Pβ
1
α
linkage criterion for merging A, B can be expressed as |A||B|
i=1 ai di where, each ai can take one
of at most O(n2 ) values corresponding to the number of pairs of points at a distance di . Therefore,
iterating over allpairs of subsets (A, B) like we did in the proof of Lemma 9, we can only list at
most O (n2 )β+1 potential linkage criteria. Therefore, the set of all pairs of subsets (A, B) and

(X, Y ) will induce at most O (n2 )2(β+1) unique comparisons between two linkage criteria. By the
same argument as in the proof of Lemma 9, since each such comparison has O(n2 ) roots, if S ∈ Vm
is a shatterable set, then 2m ≤ n2 ((n2 )2(β+1) ), which means that m = O(β log n).
Theorem 23. For any objective function Φ(p) , Pdim(HA2 ,Φ(p) ) = Ω (min(β, n)).
Proof. For the lower bound, we use a similar line of reasoning as in Lemma 10. In each round of
the construction in Lemma 10, only a constant number of distinct edge lengths are added. I.e. the
offsets oi define new distances 1.5 + oi and 1.5 − oi per round, but the set of the rest of the distances
has constant size. Therefore, we can easily modify the proof to construct a clustering instance with
Ω(m) rounds using m distinct distances. This instance will have 2Ω(β) distinct behaviors depending
on α, however this reasoning is only consistent for β = o(n). For β = Ω(n), we may inherit the
lower bound from Lemma 10, so the final pseudo-dimension lower bound is Ω (min(β, n)).

C.2

An Interpolation

So far, the linkage criteria have been based on the distances between either two pairs of points (A1
and A3 ), or every single pair between two sets considered for merging (A2 ). Now we provide an
interpolation between these two extremes. In particular, we define a linkage criterion which uses
σ different distances between the sets for comparison. In particular, for any two sets A and B, we
define an abstract rule to pick σ pairs of points (pi , qi ) from A × B. For example, a natural choice
would be to pick the (σ − 1)-th quantiles of the set of distances between points in A and B along
with the maximum and minimum distances. On picking these points, we define the criterion as a
function of these σ distances as follows.
54

A1,σ =
A2,σ =

( σ
X
i=1

αi d(pi , qi ) | α = (α1 , . . . , ασ ) ∈ Rσ


σ
 X


d(p, q))α

i=1

!1/α

)

| α ∈ R ∪ {∞, −∞}

,





(3)

.

(4)

Observe that A1,σ has multiple parameters unlike any of the classes of algorithms we have
discussed. Therefore, the analysis for A1,σ is considerably different from the rest as shown below.
We use notations similar to the previous sections.
Theorem 24. For any Φ, let

HA1,σ ,Φ = ΦA1,σ (α) : V → R≥0 | α ∈ Rσ .

The pseudo-dimension of Pdim(HA1,σ ,Φ ) = O(σ 2 log n).

Proof. The proof parallels that of Lemma 7. Consider two pairs of sets A, B and X, Y that can be
potentially merged. Regardless of the parameters chosen, we know that the linkage criterion first
chooses σ pairs of points (pi , qi ) ∈ A × B and (xi , yi ) ∈P
X × Y . Now, theP
decision to merge A, B
before X, Y or vice versa is determined by the sign of σi=1 αi d(pi , qi ) − σi=1 αi d(xi , yi ). If this
expression evaluates to zero, we will break ties arbitrarily but consistently.
Observe that for a given set of values for d(pi , qi ) and d(xi , yi ), the above expression is either 0 for all α, or is equal to zero for the hyperplane passing through the origin and normal to
(d(p1 , q1 ) − d(x1 , y1 ), . . . , d(pσ , qσ ) − d(xσ , yσ )) in the parameter space Rσ . This hyperplane divides
the parameter space into two half-spaces each of which correspond to merging one pair of sets
before the other.
Next we note that, for a given
 problem instance, as we iterate over all pairs of sets (A, B) and
(X, Y ), we can list only O n4σ possible choices for the hyperplane as there are only so many
4σ-tuples of points pi , qi , xi , yi . Thus, for m problem instances, we can list at most O mn4σ
different hyperplanes
in Rσ . These hyperplanes, can partition the parameter space into at most
σ 
4σ
O mn
regions such that all the parameter settings in a given region correspond to identical
merge trees and hence identical costs/labeling induced by the witnesses. By an argument similar
to the proof of Lemma 7, we can conclude that m = O(σ 2 log n).
Theorem 25. For any Φ, let

HA2,σ ,Φ = ΦA2,σ (α) : V → R | α ∈ R≥0 ∪ {∞, −∞ .

Then Pdim(HA2,σ ) = O (min(σ log n, n)).

Proof. This proof follows the same reasoning as in Lemma 9. The decision of whether to merge
any two pairs of sets
Pσ(A, αB) and (X,
PYσ ), isαdetermined by the sign of the difference in their linkage
criterion which is i=1 d (pi , qi ) − i=1 d (xi , yi ) where the points pi , qi , xi , yi are fixed for a given
pairs of set. We know from Theorem 20 that this expression has only O(n2 ) roots. Furthermore, as
we iterate over all pairs of sets (A, B) and (X, Y ), we can only generate as many such expressions
as there are 4σ-tuples of points pi , qi , xi , yi . In particular, we will list only O(n4σ ) such expression
each with O(n2 ) roots. In summary, similar to the proof of Lemma 9, we can argue that for a set
of samples in V m to be shattered, we need that 2m ≤ n4σ · n2 i.e., m = O(σ log n).
55

Theorem 26. For any Φ(p) Pdim(HA2,σ ,Φ(p) ) = Ω(σ).
Proof. We use a similar line of reasoning as in Lemma 10. In round i of the construction in Lemma
10, the merges were between a set of size 1 and a set of size i + 2. Therefore, we can easily modify
the proof to construct a clustering instance with Ω(σ) rounds, and the merge equations will be the
same as in Lemma 10. This instance will have 2Ω(σ) distinct behaviors depending on α, and so the
pseudo-dimension is Ω(σ).

Algorithm
Class

Linkage rule

Pseudodimension

Runtime
of
Learning Algorithm

A1

Θ(log n)

Õ(n8 talg )

Θ(n)

Õ(n2 32n talg )

A3

minp∈A,q∈B (d(p, q))α
+
α
maxp∈A,q∈B (d(p, q)) for α ∈ R
P
1
α
p∈A,q∈B d(A, B) for α ∈ R
|A||B|

α minp∈A, q∈B d(p, q) + (1 −
α) maxp∈A, q∈B d(p, q) for α ∈ (0, 1)

Θ(log n)

Õ(n8 talg )

A2

with β unique distances
Pσ
i=1 αi d(pi , qi ) for αi ∈ R
Pσ
α
i=1 d(pi , qi ) for αi ∈ R

Θ̃(min(β, n))

Õ(n4(β+1) talg )

A2

A1,σ
A2,σ

O(σ 2 log n)
Θ̃(σ)

Õ(n2σ+2 talg )

Table 2: The different classes of algorithms and their corresponding linkage rule, pseudo-dimension,
and runtime. talg denotes the runtime of the α-linkage algorithm for an arbitrary linkage rule.

56

