Semi-Supervised Algorithms for Approximately Optimal and
Accurate Clustering
Buddhima Gamlath
buddhima.gamlath@epfl.ch

Sangxia Huang
huang.sangxia@gmail.com

arXiv:1803.00926v1 [cs.DS] 2 Mar 2018

Ola Svensson
ola.svensson@epfl.ch
Abstract
We study k-means clustering in a semi-supervised setting. Given an oracle that returns whether
two given points belong to the same cluster in a fixed optimal clustering, we investigate the following
question: how many oracle queries are sufficient to efficiently recover a clustering that, with probability at least (1 − δ), simultaneously has a cost of at most (1 + ǫ) times the optimal cost and an
accuracy of at least (1 − ǫ)?
We show how to achieve such a clustering on n points with O((k2 log n) · m(Q, ǫ4 , δ/(k log n)))
oracle queries, when the k clusters can be learned with an ǫ′ error and a failure probability δ ′
using m(Q, ǫ′ , δ ′ ) labeled samples, where Q is the set of candidate cluster centers. We show that
m(Q, ǫ′ , δ ′ ) is small both for k-means instances in Euclidean space and for those in finite metric
spaces. We further show that, for the Euclidean k-means instances, we can avoid the dependency
on n in the query complexity at the expense of an increased dependency on k: specifically, we give
a slightly more involved algorithm that uses O(k4 /(ǫ2 δ) + (k9 /ǫ4 ) log(1/δ) + k · m(Q, ǫ4 /k, δ)) oracle
queries.
Finally, we show that the number of queries required for (1 − ǫ)-accuracy in Euclidean k-means
must linearly depend on the dimension of the underlying Euclidean space, whereas, for finite metric
space k-means, this number must at least be logarithmic in the number of candidate centers. This
shows that our query complexities capture the right dependencies on the respective parameters.

1

Introduction

Clustering is a fundamental problem that arises in many learning tasks. Given a set P of data points, the
˙ k of P according to some optimization criteria. In unsupervised
goal is to output a k-partition C1 ∪˙ . . . ∪C
clustering, the data points are unlabeled. The classic k-means problem and other well-studied clustering
problems such as k-median fall into this category.
In a general k-means clustering problem, the input comprises a finite set of n points P that is to be
clustered, a set of candidate centers Q, and a distance metric d giving the distances between each pair
of points in P ∪ Q. The goal is to find k cluster centers c1 , . . . , ck ∈ Q that minimizes the cost, which
is the sum of squared distances between each point in P and its closest cluster center. In this case, the
clustering C is defined by setting Ci = {x ∈ P : ci is the closest center to x} for all i = 1, . . . , k and
breaking ties arbitrarily. Two widely studied special cases are the k-means problem in Euclidean space
(where P ⊂ Rr , Q = Rr , and d is the Euclidean distance function) and the k-means problem in finite
metric spaces (where (P ∪ Q, d) forms a finite metric space).
Despite its popularity and success in many settings, there are two known drawbacks of the unsupervised k-means problem:
1. Finding the centers that satisfy the clustering goal is computationally hard. For example, even the
special case of 2-means problem in Euclidean space is NP-hard [9].
2. There could be multiple possible sets of centers that minimize the cost. However, in practical
instances, not all such sets are equally meaningful, and we would like our algorithm to find one
that corresponds to the concerns of the application.
Since k-means is NP-hard, it is natural to seek approximation algorithms. For the general k-means
problem in Euclidean space, notable approximation results include the local search by Kanungo et al. [15]
1

with an approximation guarantee of (9 + ǫ) and the recent LP-based 6.357-approximation algorithm by
Ahmadian et al. [1]. On the negative side, Lee et al. [16] ruled out arbitrarily good approximation
algorithms for the k-means problem on general instances. For several special cases, however, there exist
PTASes. For example, in the case when k is constant, Har-Peled and Mazumdar [12] and Feldman et
al. [10] showed how to get a PTAS using weak coresets, and in the case when the dimension d is constant,
Cohen-Addad et al. [7] and Friggstad et al. [11] gave PTASes based on a basic local search algorithm.
In addition, Awasthi et al. [4] presented a PTAS for k-means, assuming that the input is “clusterable”
(satisfies a certain stability criterion).
Even if we leave aside the computational issues with unsupervised k-means, we still have the problem
that there can be multiple different clusterings that minimize the cost. To see this, consider the 2-means
problem on the set of vertices of an equilateral triangle. In this case, we have three different clusterings
that give the same minimum cost, but only one of the clusterings might be meaningful. One way to
avoid this issue is to have strong assumptions on the input. For example, Balcan et al. [5] considered
the problem in a restricted setting where any c-approximation to the problem also classifies at least a
(1 − ǫ) fraction of the points correctly.
Ashtiani et al. [3] recently proposed a different approach for addressing the aforementioned drawbacks.
They introduced a semi-supervised, active clustering framework where the algorithm is allowed to make
queries of the form same-cluster(x, y) to a domain expert, and the expert replies whether the points x
and y belong to the same cluster in some fixed optimal clustering. Under the additional assumptions
that the clusters are contained inside k balls in Rr that are sufficiently far away from each other,
they presented an algorithm that makes O(k 2 log k + k(log n + log(1/δ))) same-cluster queries, runs in
O(kn log n+ k 2 log(1/δ)) time, and recovers the clusters with probability at least (1 − δ). Their algorithm
finds approximate cluster centers, orders all points by their distances to the cluster centers, and performs
binary searches to determine the radii of the balls. Although it recovers the exact clusters, this approach
works only when the clusters are contained inside well-separated balls. When the clusters are determined
by a general Voronoi partitioning, and thus distances to the cluster boundaries can differ in different
directions, this approach fails.
A natural question arising from the work of Ashtiani et al. [3] is whether such strong assumptions
on the input structure are necessary. Ailon et al. [2] addressed this concern and considered the problem without any assumptions on the structure of the underlying true clusters. Their main result is
a polynomial-time (1 + ǫ)-approximation scheme for k-means in the same semi-supervised framework
as in Ashtiani et al. [3]. However, in contrast to Ashtiani et al. [3], their work gives no assurance on
the accuracy of the recovered clustering compared to the true clustering. To achieve their goal, the
authors utilized importance sampling to uniformly sample points from small clusters that significantly
contribute to the cost. Their algorithm makes O(k 9 /ǫ4 ) same-cluster queries, runs in O(nr(k 9 /ǫ4 )) time,
and succeeds with a constant probability.
In this work, we investigate the k-means problem in the same semi-supervised setting as Ailon et
al. [2], but, in addition to approximating the cost, we seek a solution that is also accurate with respect
to the true clustering. We assume that the underlying true clustering minimizes the cost, and that there
are no points on cluster boundaries (i.e., the margin between each pair of clusters can be arbitrarily
small but not zero). This last assumption is what differentiates our setup from that of Ailon et al. [2].
It is reasonable to assume that no point lies on the boundary of two clusters, as otherwise, to achieve
constant accuracy, we would have to query at least a constant fraction of the boundary points. Without
querying each boundary point, we have no way of determining to which cluster it belongs.
Observe that if we label all the points correctly with respect to the true clustering, the resulting
clustering automatically achieves optimal cost. However, such perfect accuracy is difficult to achieve
as there may be points that are arbitrarily close to each other but belong to different clusters. Using
only a reasonable number of samples, the best we can hope for is to recover an approximately accurate
solution. PAC (Probably Approximately Correct) learning helps us achieve this goal and provides a
trade-off between the desired accuracy and the required number of samples.
Suppose that we have a solution where only a small fraction of the input points is incorrectly classified.
In this case, one would hope that the cost is also close to the optimal cost. Unfortunately, the extra cost
incurred by the incorrectly classified points can be very high depending on their positions, true labels,
and the labels assigned to them. Our main concern in this paper is controlling this additional cost.
We show that if we start with a constant-factor approximation for the cost, we can refine the clustering
with PAC learning. This yields a simple polynomial-time algorithm that, given a k-means instance and
(ǫ, δ) ∈ (0, 1)2 as parameters, with probability at least (1 − δ) outputs a clustering that has a cost
of at most (1 + ǫ) times the optimal cost and that classifies at least a (1 − ǫ) fraction of the points

2

correctly with respect to the underlying true clustering. To do so, the algorithm makes O((k 2 log n) ·
m(Q, ǫ4 , δ/(k log n))) same-cluster queries, where m(Q, ǫ′ , δ ′ ) is the number of labeled samples needed
by the PAC learning algorithm to learn k clusters in a k-means instance (P, Q, d) with an ǫ′ error and a
failure probability δ ′ (recall that Q is the set of candidate centers for a k-means instance). We further
show that our algorithm can be easily adapted to k-median and other similar problems that use the
ℓ’th power of distances in place of squared distances for some ℓ > 0. We formally present this result as
Theorem 11 in Section 3. An informal statement for the case of k-means is given below in Theorem 1.
Theorem 1 (An informal version of Theorem 11). There exists a semi-supervised learning algorithm
that, given a k-means instance, oracle access to same-cluster queries that are consistent with some fixed
optimal clustering, and parameters (ǫ, δ) ∈ (0, 1)2 , outputs a clustering that, with probability at least
(1 − δ), correctly labels (up to a permutation of the labels) at least a (1 − ǫ) fraction of the points and,
simultaneously, has a cost of at most (1 + ǫ) times the optimal cost. In doing so, the algorithm makes
O((k 2 log n) · m(Q, ǫ4 , δ/(k log n))) same-cluster queries.
Our algorithm is general and applicable to any family of k-means, k-median, or similar distance based
clustering instances that can be efficiently learned with PAC learning. As shown in Appendix A, these
include Euclidean and general finite metric space clustering instances. In contrast, both Ashtiani et al. [3]
and Ailon et al. [2], considered only the Euclidean k-means problem. To the best of our knowledge, ours
is the first such result applicable to finite metric space k-means and both Euclidean and finite metric
space k-median problems.
Ideally, we want m(Q, ǫ, δ) to be small. Additionally, the analysis of our algorithm relies on two
natural properties of learning algorithms. Firstly, we require PAC learning to always correctly label all
the sampled points. Secondly, we also require it to not ‘invent’ new labels and only output labels that
it has seen on the samples. We show that such learning algorithms with small m(Q, ǫ, δ) exist both
for k-means instances in Euclidean space and for those in finite metric spaces with no points on the
boundaries of the optimal clusters. For r-dimensional Euclidean k-means, m(Q = Rr , ǫ, δ) has a linear
dependency on r. For the case of finite metric spaces, m(Q, ǫ, δ) has a logarithmic dependency on |Q|,
which is the size of the set of candidate centers. In fact, these learning algorithms are applicable not
only to k-means instances but also to instances of any similar distance-based clustering problems whose
costs are defined in terms of the ℓ’th power (ℓ > 0) of distances as opposed to squared distances.
Our semi-supervised learning algorithm is inspired by the work of Feldman et al. [10] on weak coresets.
They construct the weak coresets by first obtaining an intermediate clustering with a constant-factor
approximation algorithm and refining each intermediate cluster using random samples. In order to get
good guarantees on the cost, they partition each cluster into an inner ball that contain the majority of
the points, and an outer region with the remaining points. We proceed similarly to this construction;
however, we further partition the outer region into O(log n) concentric rings and use PAC learning to
label the points in the inner ball and in each of the outer rings. For Euclidean k-means instances, the
number of same-cluster queries needed by the algorithm has a logarithmic dependency on the number
n of points that is similar (up to a poly(log log n) factor) to that of the algorithm by Ashtiani et al. [3].
The advantage of our algorithm is that it works for a much broader range of k-means instances whereas
the applicability of the algorithm of Ashtiani et al. [3] is restricted to those instances whose clusters are
contained in well-separated balls in Euclidean space.
This algorithm is effective in many natural scenarios where the number of clusters k is larger than
log n. However, as the size of the k-means instance (i.e., the number of points) becomes large, the
log n factor becomes undesirable. In Euclidean k-means, the number of samples needed by the learning
algorithm for error ǫ and failure probability δ does not depend on n. The log n dependency in the final
query complexity is exclusively due to repeating the PAC learning step on Ω(k log n) different partitions
of P . To overcome this problem, we present a second algorithm, which is applicable only to Euclidean kmeans instances, inspired by the work of Ailon et al. [2]. This time, we start with a (1 + ǫ)-approximation
for the cost and refine it using PAC learning. Unlike our first algorithm, we only run the PAC learning
once on the whole input, and thus we completely eliminate the dependency on n. The disadvantages of
this algorithm compared to our first algorithm are the slightly more involved nature of the algorithm
and its increased dependency on k in its query complexity. Theorem 2 below formally states this result.
The proof follows from the analysis our algorithm in Section 4.
Theorem 2. There exists a polynomial-time algorithm that, given a k-means instance in r-dimensional
Euclidean space, oracle access to same-cluster queries that are consistent with some fixed optimal clustering, and parameters (ǫ, δ) ∈ (0, 1)2 , outputs a clustering that, with probability at least (1 − δ), correctly
labels (up to a permutation of the labels) at least a (1 − ǫ) fraction of the points and, simultaneously, has
3

a cost of at most (1 + ǫ) times the optimal cost. The algorithm makes O(k 4 /(ǫ2 δ) + (k 9 /ǫ4 ) log(1/δ) +
k · m(Q, ǫ4 /k, δ)) same-cluster queries.
For the Euclidean setting, query complexities of both our algorithms have a linear dependency on the
dimension of the Euclidean space. The algorithm of Ashtiani et al. [3] does not have such a dependency
due to their strong assumption on the cluster structure, whereas the one by Ailon et al. [2] does not
have it as it only approximates the cost. We show that, in our scenario, such a dependency is necessary
to achieve the accuracy guarantee of our algorithms. For the finite metric space k-means, the query
complexity of our general algorithm has an O(poly(log |P |, log |Q|)) dependency. The dependency on |P |
comes from the repeated application of the learning algorithm on Ω(k log |P |) different partitions, and
whether we can avoid this is an open problem. However, we show that an Ω(log |Q|) query complexity
is necessary for the accuracy. Formally, we prove the following theorem in Section 5.
Theorem 3. Let K be a family of k-means instances. Let A be an algorithm that, given a k-means
instance in K, oracle access to same-cluster queries for some fixed optimal clustering, and parameters
(ǫ, δ) ∈ (0, 1)2 , outputs a clustering that, with probability at least (1 − δ), correctly labels (up to a
permutation of the cluster labels) at least a (1 − ǫ) fraction of the points. Then, the following statements
hold:
1. If K is the family of k-means instances in r-dimensional Euclidean space that have no points on
the boundaries of optimal clusters, A must make Ω(r) same-cluster queries.
2. If K is the family of finite metric space k-means instances that have no points on the boundaries
of optimal clusters, A must make Ω(log |Q|) same-cluster queries.
The outline of this extended abstract is as follows. In Section 2 we introduce the notation, formulate
the problem and present the learning theorems that we use in the subsequent sections. In Section 3
we present our first algorithm, which is simple and applicable to general k-means instances that admit
efficient learning algorithms, but has a dependency of log n in its query complexity. In Section 4 we
discuss how to remove the log n dependency in the query complexity for the special case of Euclidean
k-means instances and present our second algorithm. In Section 5, we prove our query lower bound
claims of Theorem 3. In Appendix A, we introduce the basic concepts and tools of PAC learning and
explain how to design learning algorithms for Euclidean and finite metric space k-means instances.

2

Preliminaries

In this section, we introduce the basic notation and two common families of k-means instances, and
formally define the k-means problem that we address in this work. We also introduce the notion of
learnability for families of k-means instances and state two learning theorems, which we prove later in
Appendix A.

2.1

k-Means Problem in a Semi-supervised Setting

Let P and Q be two sets of points where |P | = n, and let d : (P ∪ Q) × (P ∪ Q) → R+ be a distance
metric. We denote a k-means instance by the triple (P, Q, d). Two common families of k-means instances
we consider in this work are:
1. k-means instances in Euclidean space, where P ⊂ Rr , Q = Rr , and d(x1 , x2 ) = kx1 − x2 k is the
Euclidean distance between x1 and x2 , and
2. k-means instances in finite metric spaces, where (P ∪ Q, d) forms a finite metric space.
Let [k] := {1, . . . , k}. We identify a k-clustering C of (P, Q, d) by a labeling function fC : P → [k],
and a set of k centers, c1 , . . . , ck ∈ Q, associated with each label, 1, . . . , k. For each label i ∈ [k] of a
clustering C, let Ci := {p ∈ P : fC (p) = i} be the set of points whose label is i. For convenience, we may
use the labeling function fC or the set of clusters {C1 , . . . , Ck } interchangeably
to denote a clustering C.
P
2
d
(p,
q). For each i, define
For a subset C ⊆ P and a point q ∈ Q, define cost(C, q) :=
p∈C
center ci := argminq∈Q cost(Ci , q), i.e., each center is a point in Q that minimizes the sum of squared
distances between itself and
P each of the points assigned to it. For a k-clustering C, we define its kmeans cost as cost(C) := i∈[k] cost(Ci , ci ). Let C ∗ be the set of all k-clusterings of (P, Q, d). Then, the
4

optimal k-means cost of (P, Q, d) is defined as OP T := minC∈C ∗ cost(C). We say that a k-clustering C
α-approximates the k-means cost if cost(C) ≤ αOP T .
Let O be a fixed k-clustering of (P, Q, d) that achieves the optimal k-means cost, and let C be any
k-clustering of P . Let fO and fC be the labeling functions that correspond to O and C respectively.
We assume that we have oracle access to the labeling function fO of the optimal target clustering up
to a permutation of the labels. We can simulate a single query to such an oracle with O(k) queries
to a same-cluster oracle as explained in Algorithm 1. A same-cluster oracle is an oracle that answers
same-cluster(p1 , p2 ) queries with ‘yes’ or ‘no’ based on whether p1 and p2 belong to the same cluster in
the fixed optimal clustering O.
The error of a clustering C with respect to the clustering O for a k-means instance (P, Q, d) is now
defined as error(C, O) := |{p ∈ P : fO (p) 6= fC (p)}|. In other words, error(C, O) is the number of points
wrongly labeled by the clustering C with respect to the optimal clustering O. We note that the error
is only up to a permutation of the cluster labels because we only have access to a simulated (up to a
permutation of the cluster labels) version of fO instead of the true fO . We say that a k-clustering C is
(1 − α)-accurate with respect to O if error(C, O) ≤ αn.
Input : A point x ∈ X, oracle access to same-cluster(x1 , x2 ).
Output: A label i ∈ [k].
Global : A list of points S = [ ].
1
2
3
4
5

for 1 ≤ i ≤ length(S) do
if same-cluster(x, S[i]) then
Return i
Append x to S.
Return length(S).
Algorithm 1: Simulating a labeling oracle with the same-cluster oracle.

Given (P, Q, d), parameters k and (ǫ, δ) ∈ (0, 1)2 , and oracle access to fO , our goal is to output
a k-clustering Ô of (P, Q, d) that, with probability at least (1 − δ), satisfies error(Ô, O) ≤ ǫn and
cost(Ô) ≤ (1 + ǫ)OP T .

2.2

PAC Learning for k-Means

Let K be a family of k-means instances, and let m(Q, ǫ, δ) be a positive integer-valued function. We say
such a family K is learnable with sample complexity m if there exists a learning algorithm AL such that
the following holds: Let ǫ ∈ (0, 1) be an error parameter and let δ ∈ (0, 1) be a probability parameter.
Let (P, Q, d) be a k-means instance in class K. Let O be a fixed optimal k-means clustering and let fO
be the associated labeling function. Let T be a fixed subset of P , and let S be a multiset of at least
m(Q, ǫ, δ) independently and uniformly distributed samples from T . The algorithm AL , given input
(P, Q, d) and (s, fO (s)) for all s ∈ S, outputs a function h : P → [k]. Moreover, with probability at least
(1 − δ) over the choice of S, the output h agrees with fO on at least a (1 − ǫ) fraction of the points in T
(i.e., |{p ∈ T : h(p) = fO (p)}| ≥ (1 − ǫ)|T |).
We say that such a learning algorithm AL has the zero sample error property if the output h of AL
assigns the correct label to all the sampled points (i.e., h(s) = fO (s) for all s ∈ S). Furthermore, we
say that such a learning algorithm AL is non-inventive if it does not ‘invent’ labels that it has not seen.
This means that the output h of AL does not assign labels that were not present in the input (sample,
label) pairs (i.e., if h(x) = c for some x ∈ P , then for some sample point s ∈ S, fO (s) = c).
In Section 3, we present a simple algorithm for (1 + ǫ)-approximate and (1 − ǫ)-accurate k-means
clustering for a family K of k-means instances, assuming that K is learnable with a zero sample error,
non-inventive learning algorithm. In the analysis, zero sample error and non-inventive properties play a
key role in the crucial step of bounding the cost of incorrectly labeled points in terms of that of correctly
labeled nearby points.
We now present two learning theorems for the Euclidean setting and the finite metric space setting.
Assuming no point lies on cluster boundaries, the theorem states that the labeling function fO of the
optimal clustering is learnable with a zero sample error, non-inventive learning algorithm. We say that
a k-means instance (P, Q, d) has no boundary points if in any optimal clustering O with optimal clusters
O1 , . . . , Ok and respective centers o1 , . . . , ok , the closest center to any given point p ∈ P is unique (i.e.,
if p ∈ Oi , d(p, oi ) < d(p, oj ) for all j 6= i).
5

Theorem 4 (Learning k-Means in Euclidean Space). Let d(p1 , p2 ) = kp1 − p2 k be the Euclidean distance
function. Let K = {(P, Rr , d) : P ⊂ R, |P | < ∞, (P, Rr , d) has no boundary points} be the family of
k-means instances that are in r-dimensional Euclidean space and that have no boundary points. The
family K is learnable with sample-complexity1 m(Rr , ǫ, δ) = Õ((k 2 r log(k 2 r)(log(k 3 r/ǫ)) + log(1/δ))/ǫ).
Theorem 5 (Learning k-Means in Finite Metric Spaces). Let K = {(P, Q, d) : (P ∪ Q, d) is a finite
metric space, and (P, Q, d) has no boundary points} be the family of finite metric space k-means instances that have no boundary points. The family K is learnable with sample-complexity2 m(Q, ǫ, δ) =
Õ((k 2 (log k)(log |Q|)(log k + log 1/ǫ) + log(1/δ))/ǫ).
We prove Theorem 4 and Theorem 5 in Appendix A, where we also introduce the necessary PAC
learning concepts and tools.

A Simple Algorithm for (1 + ǫ) Cost and (1 − ǫ) Accuracy

3

Let K be a family of k-means instances that is learnable with sample complexity m using a zero sample
error, non-inventive learning algorithm AL . Let Aα be a constant-factor approximation algorithm, and
let A1 be a polynomial-time algorithm for the 1-means problem (i.e., given (P, Q, d) ∈ K, A1 finds
argminq∈Q cost(P, q) in polynomial time). We present a simple semi-supervised learning algorithm that,
given a k-means instance (P, Q, d) of class K and oracle access to the labeling function fO of a fixed
optimal clustering O of (P, Q, d), outputs a clustering Ô that, with probability at least (1 − δ), satisfies
cost(Ô) ≤ (1 + ǫ)OP T and error(Ô, O) ≤ ǫ|P |. Our algorithm uses Aα , A1 , and AL as subroutines
and makes O((k log |P |) · m(Q, ǫ4 , δ/(k log |P |))) oracle queries. We show that our algorithm can be
easily modified for (1 + ǫ)-approximate and (1 − ǫ)-accurate k-median and other similar distance-based
clustering problems. Towards the end of this section, we discuss several applications of this result,
namely, for Euclidean and finite metric space k-means and k-median problems.
Let us start by applying the learning algorithm AL to learn all the cluster labels. If we get perfect
accuracy, the cost will be optimal. A natural question to ask in this case is: what happens to the cost
if the learning output has ǫ error? In general, even a single misclassified point can incur an arbitrarily
large additional cost. To better understand this, consider the following: Let Oi , Oj ⊆ P be two distinct
optimal clusters in the target clustering, and let oi , oj be their respective cluster centers. Let p ∈ Oi be
a point that is incorrectly classified and assigned label j 6= i by AL . Also assume that the number of
misclassified points is small enough so that the centers of the clusters output by the learning algorithm
are close to those of the optimal clustering. Thus, in the optimal clustering, p incurs a cost of d2 (p, oi ),
whereas according to the learning outcome, p incurs a cost that is close to d2 (p, oj ). In the worst case,
d(p, oj ) can be arbitrarily larger than d(p, oi ).
Now suppose that, within distance r from p, there exists some point q ∈ Oj . In this case, we can
bound the cost incurred due to the erroneous label of p using the true cost of p in the target clustering.
To be more specific, using the triangle inequality, we get the following bound for any metric space:
d(p, oj ) ≤ d(p, q) + d(q, oj ) ≤ r + d(q, oj ). Furthermore, due to the optimality, d(q, oj ) ≤ d(q, oi ) ≤
d(q, p) + d(p, oi ) ≤ r + d(p, oi ). Hence, it follows that d(p, oj ) ≤ 2r + d(p, oi ). To utilize this observation
in an algorithmic setting, we need to make sure that, for every point that is misclassified into cluster
j, there exists a correctly classified nearby point q that belongs to the optimal cluster Oj . Luckily, this
is ensured by the combination of zero sample error and non-inventive properties of AL . If a point is
misclassified into cluster j, the non-inventive property says that AL must have seen a sample point q
from cluster j. The zero sample error property ensures that q is labeled correctly by AL . To make sure
that such correctly labeled points are sufficiently close to their incorrectly labeled counterparts, we run
AL separately on certain suitably bounded partitions of P .
The formal description of our algorithm is given in Algorithm 2. The outline is as follows: First, we
run Aα on (P, Q, d) and obtain an intermediate clustering C = {C1 , . . . , Ck }. For each Ci , we run A1 to
find a suitable center ci . Next, we partition each intermediate cluster Ci into an inner ball and O(log |P |)
outer rings centered around ci . We run the learning algorithm AL separately on each of these partitions.
We choose the inner and outer radii of the rings so that, in each partition, the points that are incorrectly
classified by the learning algorithm only incur a small additional cost compared to that of the correctly
classified points. The final output is a clustering Ô that is consistent with the learning outputs on each
of the partitions. For each cluster Ôi , we associate the output of running A1 on (Ôi , Q, d) as its center.
1 Õ
2 Õ

hides poly(log log k, log log r) factors.
hides poly(log log k, log log |Q|) factors.

6

Note that, due to the accuracy requirements, the cluster center to which a point is assigned in the output
may not be the cluster center closest to that point in the output. It remains an interesting problem to
find an accurate clustering in which every point is always assigned to its nearest cluster center.
Input : k-Means instance (P, Q, d), oracle access to fO , constant-factor approximation
algorithm Aα , 1-means algorithm A1 , zero sample-error, non-inventive learning
algorithm AL with sample complexity m, accuracy parameter 0 < ǫ < 1, and failure
probability 0 < δ < 1.
Output: A clustering Ô = {Ô1 , . . . , Ôk } defined by a labeling fÔ : P → [k]. The respective
cluster centers are ôi = argminq∈Q cost(Ôi , q). For each i ∈ [k], run A1 on (Ôi , Q, d) to
find ôi .
1
2

3
4
5
6

7
8
9
10
11
12
13
14

Let n = |P |, and let γ = ǫ2 /(288α).
Run Aα and obtain an α-approximate k-means clustering C = {C1 , . . . , Ck }. For each i ∈ [k], run
A1 on (Ci , Q, d) and find centers ci = argminq∈Q cost(Ci , q).
for Ci ∈ C do
p
Let ri = cost(Ci , ci )/(γ|Ci |).
Let Ci,0 be all points in Ci that are at most ri away from ci .
Let Ci,j be the points in Ci that are between 2j−1 ri and 2j ri away from ci for
j = 1, . . . , (log n)/2.
Let m′ = m(Q, γ 2 , δ/(k log n)).
for each non-empty Ci,j do
Sample m′ points x1 , . . . , xm′ ∈ Ci,j independently and uniformly at random.
Query the oracle on x1 , . . . , xm′ and let Si,j = {(xi , fO (xi )) : i = 1, . . . , m′ }.
Run AL on input (P, Q, d) and Si,j , and obtain a labeling hi,j : Ci,j → [k].
Output the clustering Ô defined by the following labeling function:
for each i, j, x ∈ Ci,j do
Set fÔ (x) = hi,j (x).

Algorithm 2: A simple algorithm for (1 + ǫ)-approximate (1 − ǫ)-accurate k-means clustering.
We now analyze Algorithm 2 and show that, with probability at least (1 − δ), it outputs a (1 + ǫ)approximate and (1 − ǫ)-accurate k-means clustering.
Let n = |P | be the total number of points in the k-means instance. Assume that 0 < γ < 1/2. For all
i, j, p, let Hi,j,p = {x ∈ Ci,j : hi,j (x) = p} be the set of points that are in Ci,j and labeled p by the output
hi,j of the learning algorithm AL . Call a point x ∈ P bad if x ∈ Hi,j,p but fO (x) 6= p; otherwise, call it
good. Denote the set of bad points by B and let the complement B c of B be the set of good points. For
each i, let oi = argminq∈Q cost(Oi , q) denote the center of cluster i in O. For any point x ∈ P , let o(x)
denote the center of the optimal cluster for x under the clustering O. Thus, o(x) = op ⇔ fO (x) = p.
Notice that, for all i, all the points in Ci belong p
to one of the Ci,j ’s. In other words, no point in
(log n)/2
Ci is more than 2
ri away from ci , where ri = cost(Ci , ci )/(γ|Ci |). To see this, suppose x ∈ Ci
is a point that is more than 2(log n)/2 ri away from ci . Then, d2 (x, ci ) ≥ 2log n · cost(Ci , ci )/(γ|Ci |) >
cost(Ci , ci ) which is a contradiction.
Lemma 6. With probability at least (1 − δ), all non-empty Ci,j ’s satisfy |Cij ∩ B| ≤ γ 2 |Cij |.
Proof. Recall that we run AL with mK (P, Q, d, γ 2 , δ/(k log n)) samples. Thus, by definition, AL , each
run of AL succeeds with probability at least (1 − δ/(k log n)). Since we only run AL at most k log n
times, the claim follows from the union bound.
We continue the rest of the analysis conditioned on |Ci,j ∩ B| ≤ γ 2 |Ci,j | for all Ci,j . In proving the
subsequent results, we use the following observations.
Observation 7. No two points in Ci,j are more than distance R = 2 · 2j ri apart. Note that, according
to the definition of Ci,j in the algorithm, R is the outer diameter of the ring that bounds Ci,j .
Observation 8. For j ≥ 1, the inner radius of the ring that bounds Ci,j is 2j−1 ri . Therefore, we have
the following lower bound for the cost of Ci,j : cost(Ci,j , ci ) ≥ |Ci,j |(2j−1 ri )2 .
Lemma 9. For all i, j and p, if x ∈ Hi,j,p ∩ B then d(x, op ) ≤ 4 · 2j ri + d(x, o(x)).
7

Proof. If x ∈ Hi,j,p ∩ B, then x is in some optimal cluster denoted by Oq for some q 6= p. Note that if hi,j
(i.e., the output of the algorithm AL ) gives label p to some point x, then the non-inventive property of
AL ensures that it has seen at least one point y ∈ Ci,j that is in Op , and the zero sample-error property
ensures that y is labeled correctly by hi,j . Thus, op = o(y) and oq = o(x). Hence, y is a good point with
label p, and consequently, we have
d(x, op ) ≤ d(x, y) + d(y, op ) ≤ d(x, y) + d(y, oq ) ≤ 2 d(x, y) + d(x, o(x))
≤ 4 · 2j ri + d(x, o(x)),
where the last inequality follows from Observation 7.
Lemma 10 (Squared Triangle Inequality). For any a, b ≥ 0 and 0 < ǫ < 1, we have

 

2 2
1 2
2
2
2
b ≤ (1 + ǫ)a +
b .
(a + b) ≤ (1 + ǫ)a + 1 +
ǫ
ǫ
Proof. The first inequality follows from the AM-GM inequality because 2ab ≤ ǫa2 + b2 /ǫ. The second
inequality holds because ǫ < 1 implies 1 < 1/ǫ.
Now, let us analyze the cost of the labeling output by Algorithm 2:
cost(P, Ô) =

X

cost(Ôp , ôp ) ≤

X

cost(Ôp , op ) =

cost(Hi,j,p , op ).

i,j,p

p∈[k]

p∈[k]

X

Splitting the cost contributions of good and bad points, we get
X
X
cost(Hi,j,p ∩ B, op )
cost(P, Ô) ≤
d2 (x, o(x)) +
i,j,p

x∈B c

=

X

2

d (x, o(x)) +

X

X

d2 (x, op ).

i,j,p x∈Hi,j,p ∩B

x∈B c

Applying Lemma 9 together with Lemma 10, for any ǫ ∈ (0, 1), we have


X
X
X
2·3
ǫ 2
j
2
2
d (x, o(x)) +
(4 · 2 ri )
cost(P, Ô) ≤
d (x, o(x)) +
1+
3
ǫ
i,j,p x∈Hi,j,p ∩B
x∈B c

X
X
ǫ X 2
96 j 2
≤ 1+
d (x, o(x)) +
(2 ri )
3
ǫ
i,j,p x∈Hi,j,p ∩B
x∈P

X X 96
ǫ
= 1+
(2j ri )2 .
OP T +
3
ǫ
i,j
x∈Ci,j ∩B

From Lemma 6, we have |Ci,j ∩ B| ≤ γ 2 |Ci,j |, and it follows that

X
96
ǫ
γ 2 |Ci,j | (2j ri )2
OP T +
cost(P, Ô) ≤ 1 +
3
ǫ
i,j


X
X
96
ǫ
96
γ 2 |Ci,0 | ri2 +
= 1+
OP T +
γ 2 |Ci,j | (2j ri )2 .
3
ǫ
ǫ
i

(1)

i,j:j≥1

Consider the last two terms of Equation 1 individually. For the first summation, we have
X

γ 2 |Ci,0 |

i

96 2 X 2
96 cost(Ci , ci ) X 96γ
96γα
γ |Ci,0 |
ri =
≤
cost(Ci , ci ) ≤
OP T.
ǫ
ǫ
γ|C
|
ǫ
ǫ
i
i
i

In the last inequality, we used the fact that C gives an α-approximation for the optimal cost. For the
second summation of Equation 1, Observation 8 gives
X

i,j:j≥1

γ 2 |Cij |

X 4 · 96γ 2
X 384γ 2
96 j 2
(2 ri ) =
|Cij |(2j−1 ri )2 ≤
cost(Cij , ci )
ǫ
ǫ
ǫ
i,j:j≥1

≤

i,j:j≥1

X 384γ 2
i

ǫ

384γ 2 α
cost(Ci , ci ) ≤
OP T.
ǫ

8

Here, we have again used the approximation guarantee of C in the final inequality.
Choosing γ = ǫ2 /(288α) makes sure that both 96γα/ǫ ≤ ǫ/3 and 384γ 2 α/ǫ ≤ ǫ/3, and consequently,
we get a final cost of at most (1 + ǫ)OP T . Recall that we established this bound conditioned on
|Ci,j ∩ B| ≤ γ 2 |Ci,j | for all i, j. In Lemma 6, we saw that all the O(k log n) runs of the learning algorithm
AL succeed with probability at least (1 − δ). Hence, the condition |Ci,j ∩ B| ≤ γ 2 |Ci,j | is true for all i, j
with the same probability. Summing the inequality over all i, j yields |B| ≤ γ 2 |P | ≤ ǫ|P |. Consequently,
the output of Algorithm 2, with probability at least (1 − δ) over the choice of samples in step 10, outputs
a (1 + ǫ)-approximate and (1 − ǫ)-accurate k-means clustering.
In Algorithm 2, instead of an exact algorithm A1 for the 1-means problem, we can also use a PTAS.
Using a PTAS to approximate 1-means up to a (1 + ǫ) factor will only cost an additional (1 + ǫ) factor
in our cost analysis. As a result, we get the same approximation and accuracy guarantees if we replace
ǫ with ǫ/3.
Algorithm 2 makes O((k log n) · m(Q, ǫ4 , δ/(k log n))) queries to the oracle fO in total. Recall that
simulating an oracle query to fO takes O(k) same-cluster queries. Therefore, the total number of samecluster queries is O((k 2 log n) · m(Q, ǫ4 , δ/(k log n))).
Our definition of a learning algorithm in Section 2.2 has nothing to do with whether the input is a
k-means instance or a k-median instance. In fact, it applies to any similar clustering scenario where the
cost is defined in terms of the ℓ’th power (ℓ > 0) of distances instead of squared distances. The analysis
of Algorithm 2 can be adapted to any fixed ℓ where we have a suitable triangle inequality analogous
to Lemma 10. For example, when ℓ ≤ 1, we can simply use the trivial inequality (a + b)ℓ ≤ aℓ + bℓ .
Thus, for such clustering problems, Algorithm 2, with a slight modification on choice of radii in Step 4
and a little adjustment to the parameter γ, will give the same guarantees. Hence, we have the following
theorem which is the formal version of Theorem 1. The proof follows from the analysis of Algorithm 2.
Theorem 11. Let K be a family of k-means (k-median) instances. Suppose that K is learnable with
sample complexity m(Q, ǫ, δ) using a zero sample error, non-inventive learning algorithm AL . Let Aα be
a constant-factor approximation algorithm, and let A1 be a PTAS for the 1-means (1-median) problem.
There exists a polynomial-time algorithm that, given an instance (P, Q, d) ∈ K, oracle access to samecluster queries for some fixed optimal clustering O, and parameters (ǫ, δ) ∈ (0, 1)2 , outputs a clustering
that, with probability at least (1 − δ), is (1 − ǫ)-accurate with respect to O, and simultaneously has a cost
of at most (1 + ǫ)OP T . The algorithm uses AL , Aα , and A1 as subroutines. The number of same-cluster
queries made by the algorithm is
1. O((k 2 log |P |) · m(Q, ǫ4 , δ/(k log |P |))) for the k-means setting and
2. O((k 2 log |P |) · m(Q, ǫ2 , δ/(k log |P |))) for the k-median setting.
For k-means and k-median instances in Euclidean space and those in finite metric spaces, there exist several constant-factor approximation algorithms (for example, Ahmadian et al. [1] and Kanungo
et al. [15]). Solving the 1-means problem
in Euclidean space is straightforward: The solution to
P
argminq∈Rr cost(P, q) is simply q = ( p∈P p)/|P |. For the k-median problem in Euclidean space, the
problem of 1-median does not have an exact algorithm but several PTASes exist (for example, Cohen et
al. [6]). In a finite metric space, to solve argminq∈Q cost(P, q), we can simply try all possible q ∈ Q in
polynomial time, and this holds for the k-median setting as well. Thus, for Euclidean and finite metric
space k-means and k-median instances that have no boundary points, Theorem 11, together with Theorem 4 and Theorem 5, gives efficient algorithms for (1 + ǫ)-approximate, (1 − ǫ)-accurate semi-supervised
clustering.

4

Removing the Dependency on Problem Size in the Query Complexity for Euclidean k-Means

For the family of Euclidean k-means instances, the query complexity of Algorithm 2 suffers from a
Õ(log n) dependency (where n is the number of points in the input k-means instance, and Õ hides
poly(log log n) factors) due to the repeated use of the learning algorithm AL . Specifically, we run AL
with a failure probability of δ/(k log n), O(log n) times per cluster. Note that the sample complexity of
AL itself, in the case of Euclidean k-means instances, does not have this dependency.
In this section, we show that we can avoid this dependency on n using a slightly more involved
algorithm at the cost of increasing the query complexity by an extra poly(k) factor. Nevertheless, this

9

algorithm has superior performance when the size of the input instance (i.e., the number of points) is
very large (when log n = Ω(k 10 ) for example).
RecallPthat, for a set C ⊂ Rr , cost(C, y) is minimized when y is the centroid of C, denoted by
µ(C) = ( x∈C x)/|C|. Define the fractional size of an optimal cluster Oi as the fraction of points that
belong to Oi , i.e., the ratio |Oi |/n. Suppose we only want to get a good approximation for the cost, and
that we know that all the clusters in the target solution have sufficiently large fractional sizes. In this
case, naive uniform sampling will likely pick a large number of samples from each of the clusters. This
observation, together with Lemma 12, allows us to approximate the centroid and the cost of each cluster
to any given accuracy.
Lemma 12 (Lemma 1 and Lemma 2 of Inaba et al. [13]). Let (ǫ, δ) ∈ (0, 1)2 , let m ≥ 1/(ǫδ) be a positive
integer, and let S = {p1 , . . . , pm } be a multiset of m i.i.d. samples from the uniform distribution over
some finite set C ⊂ Rr . With probability at least (1 − δ), d2 (µ(S), µ(C)) ≤ ǫ · cost(C, µ(C))/|C| and
cost(C, µ(S)) ≤ (1 + ǫ) cost(C, µ(C)).
However, the above approach fails when some clusters in the optimal target solution contribute significantly to the cost, but have small fractional sizes (that is because uniform sampling is not guaranteed to
pick sufficient numbers of samples from the small clusters). Ailon et al. [2] circumvented this issue with
an algorithm that iteratively approximates the centers of the clusters using a distance-based probability
distribution (D2 -sampling). We will refer to their algorithm as A∗ .
Note that when it comes to accuracy, we can totally disregard clusters with small fractional sizes; we
only have to correctly label a sufficiently large fraction of the points in large clusters. With this intuition,
we present the outline of our algorithm.
Let (P, Rr , d) be a k-means instance in Euclidean space that has no boundary points. For simplicity,
we refer to the instance (P, Rr , d) by just P where possible, as for Euclidean k-means, the other two
parameters are fixed. We start with a naive uniform sampling step that gives a good approximation for
the centers of large clusters. Starting with these centers, we run a slightly modified version of algorithm
A∗ to approximate the centers of the remaining small clusters. Thus, at this point, we have a clustering
with a good cost and we know which clusters are large. We now run the learning algorithm AL on input
P and obtain a labeling of the points. For each point, we assign its final label based on
1. the label assigned to it by the learning algorithm AL , and
2. its proximity to large cluster centers.
In particular, if the output of AL decides that a point p should be in some large cluster i, and if p is
sufficiently close to the approximate center for cluster i, we label it according to the learning output;
otherwise, we label it according to its nearest approximate center. We show that this approach retains
a cost that is close to the cost of the clustering output by A∗ . The accuracy guarantee comes from the
facts that a large fraction of the points are sufficiently close to the centers of large clusters, and that AL
labels most of them correctly with a good probability.
We now review the key properties of algorithm A∗ (the algorithm of Ailon et al. [2]). Let 0 < ǫ < 1.
Call a k-means instance P is (k, ǫ)-irreducible if no (k−1)-means clustering gives an (1+ǫ)-approximation
for the k-means problem, i.e., if OP T k denotes the optimal k-means cost of P , then P is (k, ǫ)-irreducible
if OP T k−1 > (1 + ǫ)OP T k . Suppose that P is (k, ǫ)-irreducible. Let O = {O1 , . . . , Ok } be the target
optimal clustering, and let o1 , . . . , ok be the respective centers. Let Ci = {c1 , . . . , ci } denote a set of i
centers and let Z(i) denote the following statement: There exists a set of i distinct indices j1 , . . . , ji such
that, for all r ∈ [i], cost(Ojr , cr ) ≤ (1 + ǫ/16) cost(Ojr , ojr ). To put it differently, Z(i) says that Ci is a set
of good candidate centers for i-many distinct clusters in the target optimal solution. Assuming P is (k, ǫ)irreducible, the algorithm A∗ yields a method to incrementally construct sets C1 , . . . , Ck (i.e., Ci+1 =
Ci ∪{ci+1 }) such that, conditioned on Z(i) being true, Z(i + 1) is true with probability at least (1 − 1/k).
Now suppose that P is (k, ǫ/(4k))-irreducible. Then A∗ gives a (1 + ǫ/(4 · 16k))-approximation for kmeans with probability at least (1 − 1/k)k ≥ 1/4. Otherwise, A∗ gives a (1 + ǫ/(4 · 16k))-approximation
for the i-means problem for some i < k, where i is the largest integer such that P is (i, ǫ/4k)-irreducible.
In the latter case, it will give a (1 + ǫ/(4 · 16k))(1 + ǫ/(4k))k−i -approximation with probability at least
1/4. In either case, the output of A∗ is a (1 + ǫ)-approximation.
In our algorithm, we first find the centers of large clusters using uniform sampling, and then run A∗
find the remaining centers. This allows us to know which clusters are large, which is a crucial information
needed for the final labeling. Suppose that in the target optimal solution we have k0 ≤ k clusters whose
fractional sizes are at least ǫ/k. Note that k0 is at least 1 due to the Pigeonhole Principle, since at
10

least one cluster should have a fractional size of at least 1/k > ǫ/k. By Lemma 12, using uniform
sampling, we can approximate the centroid of each of these large clusters with a good accuracy. Hence,
we can have a set Ck0 of k0 centers such that Z(k0 ) is true with probability (1 − δ). Afterwards, we
use A∗ to incrementally construct Ck0 +1 , . . . , Ck . Conditioned on Z(k0 ) being true, the output Ck will
be a (1 + ǫ)-approximation with probability (1 − 1/k)k−k0 ≥ (1 − 1/k)k ≥ 1/4 for k ≥ 2. However, by
independently running this incremental construction O(log(1/δ)) times and choosing the set of centers
with the minimum total cost, we can boost this probability to (1−δ). This observation gives the following
generalization of Theorem 10 of Ailon et al. [2].
Theorem 13. Consider a Euclidean k-means instance (P, Rr , d). Let O1 , . . . , Ok be a fixed optimal
clustering with respective centers o1 , . . . , ok . Let k0 ≤ k and let Ck0 = {c1 , . . . , ck0 } be a set of points
such that, with probability at least p0 , cost(Oi , ci ) ≤ (1 + ǫ/(64k)) cost(Oi , oi ) for all i ∈ [k0 ]. There
exists an algorithm Acost that, given P , Ck0 , andPparameters (ǫ, δ) ∈ (0, 1)2 as
P input, outputs a set
cost(O
,
c
)
≤
(1
+
ǫ)
of centers Ck = Ck0 ∪ {ck0 +1 , . . . , ck } such that
i
i
i∈[k] cost(Oi , oi ) with
i∈[k]
probability at least p0 (1 − δ). Moreover, Acost uses O((k 9 /ǫ4 ) log(1/δ)) same-cluster queries and runs in
time O(nr(k 9 /ǫ4 ) log(1/δ)).
Theorem 13 implies a method to get a good approximation for the cost that also reveals which
clusters are large. Specifically, we first perform uniform sampling over the whole set P and approximate
the centers of the large clusters. If we get a sufficient number of samples, the approximate centers
will satisfy the precondition of Theorem 13 with a good probability. Thus, using algorithm Acost from
Theorem 13, we get the desired approximation for the cost. What remains now is to use PAC learning
and to appropriately label the points according to the learning outcome.
We present the pseudo-code of our algorithm in Algorithm 3, where we use the algorithm Acost from
Theorem 13 and the learning algorithm AL guaranteed by Theorem 4. In Algorithm 3, Q1 (k, ǫ, δ) =
256k 3 /(ǫ2 δ) is the number of samples needed to ensure that we pick a sufficient number of samples
from each of the clusters with fractional sizes of at least ǫ/k, Q2 (k, ǫ, δ) is the sample complexity of the
algorithm Acost , and Q3 (k, r, ǫ, δ) = m(Rr , ǫ, δ) is the sample complexity of the learning algorithm AL for
an error ǫ and a failure probability δ. Note that Algorithm 3 only outputs a labeling; the corresponding
centers are the centroids of the clusters defined by the labeling. As with Algorithm 2, the center that a
point is assigned to in the final output may not be the closest center to that point.
Input : Point set P ⊂ Rr , oracle access to fO , parameter k, accuracy parameter ǫ, failure
probability δ, and algorithms Acost and AL .
Output: A clustering Ô defined by the labeling fÔ : P → [k]. The cluster centers are the
centroids of the clusters defined by fÔ .
1

2

3

4

5

Draw Q1 (k, ǫ, δ) samples from P independently and uniformly at random, and query fO to get
their true cluster labels in O. Denote the set of sampled points by S, and for all i ∈ [k], denote
the set of sampled points that belong to class i by Si .
Let k ′ be the number of distinct cluster labels with more than (ǫ/(2k))Q1 (k, ǫ, δ) samples. Let
Ck′ := {µ(Si ) : |Si | > (ǫ/(2k))Q1 (k, ǫ, δ)}. Without loss of generality, assume that the class labels
for centers in Ck′ are 1, . . . , k ′ .
Run the algorithm Acost , starting from Ck′ as the partial set of centers. This takes Q2 (k, ǫ, δ)
more queries. Let Ck = {c1 , . . . , ck } be the output, and let OP T ∗ be the cost of the clustering
obtained by assigning each point to its nearest ci .
Use the PAC learning algorithm AL on Q3 (k, r, ǫ4 /k, δ) uniform i.i.d. samples from P to learn a

classifier for the k classes that is 1 − ǫ4 /k -accurate with probability at least (1 − δ). Let
H1 , . . . , Hk be the sets of points that are labeled 1, . . . , k respectively by the classifier.
Output the clustering Ô defined by the following labeling function: for each i ∈ [k ′ ] and p ∈ Hi
such that d2 (p, ci ) ≤ kOP T ∗ /(nǫ3 ), set fÔ (p) = i. For any other point p, set fÔ (p) = i if the
nearest cluster center to p in Ck is ci .
Algorithm 3: Algorithm whose query complexity is independent of n

4.1

Analysis of Algorithm 3

Assume 0 < ǫ < 1/4. For an optimal cluster Oi with center oi , denote by ∆(Oi ) := cost(Oi , oi )/|Oi | the
average squared distance from the points in Oi to their center oi . Let c1 , . . . , ck′ be the points in Ck′
where ci is the approximate centroid for the cluster with label i found in Step 2 of Algorithm 3.
11

First, we show that Step 2 of Algorithm 3 approximates all the large cluster centers accurately enough
so that the precondition for applying Theorem 13 is satisfied (recall that the precondition is to have a set
of k ′ < k approximate centers for k ′ distinct optimal clusters in the target solution). Lemma 14 ensures
this, and also makes sure that the clusters that are too small are not picked as large clusters. This last
fact is useful in the proof of Lemma 15.
Lemma 14. With probability at least 1 − δ, the following statements are true:
1. For all i ∈ [k ′ ], d2 (oi , ci ) ≤ (ǫ/(64k)) ∆(Oi ).
2. For all i ∈ [k ′ ], cost(Oi , ci ) ≤ (1 + ǫ/(64k)) cost(Oi , oi ).
3. Let L = {i ∈ [k] : |Oi | ≥ (ǫ/k)n} be the set of the labels of the optimal clusters with a fractional
size of at least ǫ/k. Then, L ⊆ [k ′ ].
4. Let T = {i ∈ [k] : |Oi | ≤ (ǫ2 /k)n} be the set of the labels of the optimal clusters with fractional size
of at most ǫ2 /k. Then T ∩ [k ′ ] = ∅.
Proof. Notice that for each i ∈ [k ′ ], we have at least (ǫ/(2k))Q1 (k, ǫ, δ) = 128k 2/(ǫδ) samples in Step 2.
Thus, using Lemma 12 on each cluster with error parameter ǫ/(64k) and failure probability δ/(2k), and
applying the union bound, the first two statements hold with probability at least (1 − δ/2).
As for the final two statements, note the following. Let q = Q1 (k, ǫ, δ), and let the random variables
Xi,j : P
j = 1, . . . , q be such that Xi,j = 1 if the j-th sample is from Oi . Otherwise, Xi,j = 0. Let
Xi =
j∈[q] Xi,j be total number of samples picked from Oi and pi = Pr[Xi,j = 1]. Since we pick
identical samples, this probability does not depend on j.
If i ∈ L, then pi ≥ ǫ/k and E[Xi ] = q · pi ≥ q · ǫ/k. Applying a standard Chernoff bound, we get







32k 2
δ
q·ǫ 
1
1 ǫ
≤ exp −
≤
.
Pr Xi < · q ≤ Pr Xi < E[Xi ] ≤ exp − 2
2 k
2
2 ·3·k
3ǫδ
2k
For i ∈ T , observe that pi ≤ ǫ2 /k and E[Xi ] = q · pi ≤ q · ǫ2 /k. Since ǫ < 1/4, we further have that
ǫ/(2k) > 2ǫ2 /k. Applying another standard Chernoff bound, we now get




ǫ2
1 ǫ
Pr Xi > · q ≤ Pr Xi > 2 · q ≤ Pr [Xi > 2 E[Xi ]]
2 k
k




q · ǫ2
32k 2
δ
≤ exp − 2
≤ exp −
≤
.
2 ·3·k
3δ
2k
Applying the union bound, we get that the final two statements are also true with probability at
least (1 − δ/2). Thus, all four statements are true with probability at least (1 − δ).
Recall that OP T ∗ is the cost of the clustering defined by the centers Ck after Step 3 of Algorithm 3.
Lemma 14, together with Theorem 13, implies that, with probability at least (1 − 2δ),
X
X
cost(Oi , oi ) ≤ (1 + ǫ)OP T.
cost(Oi , ci ) ≤ (1 + ǫ)
OP T ∗ ≤
i∈[k]

i∈[k]

Also note that the PAC learning of Step 4 has at most ǫ4 /k error with probability at least (1 − δ).
The following lemma thus provides the final ingredient of our proof. Conditioned on Steps 1, 2, 3,
and 4 of Algorithm 3 being successful, Lemma 15 shows that the clustering defined in Step 5 achieves
the desired accuracy of the algorithm with only a marginal increase in the cost.
Lemma 15. Consider an P
outcome of Algorithm 3 where all four statements of Lemma 14 are true.
Additionally, suppose that
i∈[k] cost(Oi , ci ) ≤ (1 + ǫ)OP T , and that the PAC learning of Step 4 of

Algorithm 3 has at most ǫ4 /k error. Then, the output clustering Ô is (1 − 6ǫ)-accurate with respect to
the target optimal clustering O and (1 + 3ǫ)-approximates the k-means cost.
Proof. It is easy to see that the points that are incorrectly labeled by fÔ are fully contained inside the
union of the following three disjoint sets:
1. Points that belong to the target optimal clusters whose fractional sizes are at most ǫ/k.

12

2. Points that are incorrectly labeled by the clustering algorithm in Step 4 but are not in the set
defined above.
3. Points that do not satisfy the distance criterion in Step 5 but are correctly classified and are
assigned a label from {1, . . . , k ′ } by the PAC learning output in Step 4.
At most a k(ǫ/k) = ǫ fraction of the points are in the first set. By the accuracy of the PAC learning
step, the second set has at most ǫ4 /k fraction of the points. As for the third set, we consider the following:
By the fourth statement of Lemma 14, for i = 1, . . . , k ′ , Oi has a fractional size of at least ǫ2 /k; therefore,
cost(Oi , oi )/(n(ǫ2 /k)) ≥ ∆(Oi ). Recall that Hi is the set of points that are assigned label i in the PAC
learning step. Let i ∈ {1, . . . , k ′ }, and let p ∈ Hi be a point that is correctly labeled in the PAC learning
output and that satisfies d2 (p, ci ) > kOP T ∗ /(nǫ3 ). For such a point p, we can lower bound the distance
to its approximate center at follows:
d2 (p, ci ) >

kOP T ∗
kOP T
k cost(Oi , oi )
∆(Oi )
≥
≥
≥
.
nǫ3
nǫ3
nǫ3
ǫ

Also, since 2 d2 (p, oi ) + 2 d2 (oi , ci ) ≥ d2 (p, ci ), and d2 (oi , ci ) ≤ (ǫ/(64k)) ∆(Oi ) by Lemma 14 (1), we get




∆(Oi )
1 ∆(Oi )
1 ∆(Oi )
ǫ ∆(Oi )
d2 (p, oi ) >
>
− 2 d2 (oi , ci ) >
−2
.
2
ǫ
2
ǫ
64k
4ǫ
Hence, there can be at most 4ǫ|Oi | such points. Summing over all Oi , we conclude that at most 4ǫ
fraction of the points are in the final set. Hence, the resulting clustering isP
at least (1 − 6ǫ) accurate.
It remains to show that the cost increase in Step 5 is small. Let cost′ = i∈[k] cost(Oi , ci ) be the cost
of assigning each optimal cluster Oi to its approximate center ci . We know cost′ is close to the optimal
cost by Theorem 13. We now show that the label assignment in Step 5 does not increase this cost by
too much. Observe that for the points that are not labeled according to the PAC learning output, the
contribution to cost′ can only decrease by assigning it to the nearest ci . For the points that are labeled
according to the PAC output, if the learning algorithm has assigned them the correct labels, then there
is no change in their contribution to cost′ .
Thus, it is sufficient to bound the cost of those points that are incorrectly labeled by the PAC learning
and are labeled according to the learning output in the final assignment. There can be at most (ǫ4 /k)n
such points due to the learning accuracy, and assigning such a point p to ci can incur at most an extra
d2 (p, ci ) cost. However, due to the distance constraint of Step 5 of Algorithm 3, d2 (p, ci ) ≤ kOP T ∗ /(nǫ3 ).
Therefore, the total cost increase by these points is at most
ǫ4 n kOP T ∗
≤ ǫOP T ∗ ≤ ǫ(1 + ǫ)OP T ≤ 2ǫOP T.
k
nǫ3
Consequently, the cost of the output clustering of the algorithm is at most (1 + 3ǫ)OP T .
Combining Lemma 14, Theorem 13, and Lemma 15, we have the proof of Theorem 2. We need each of
the Steps 1, 3, and 4 to succeed with probability at least (1−δ/3) so that we get a final failure probability
of δ, which can be easily achieved by replacing the probability parameter δ of Algorithm 3 with δ/3.
Furthermore, according to the statement of Lemma 15, we also need to replace the accuracy parameter ǫ
by ǫ/6. As for the claim on the query complexity, we recall that we only need O(k) same-cluster queries
per single fO query, and Algorithm 3 makes a total number of Q1 (k, ǫ, δ) + Q2 (k, ǫ, δ) + Q3 (k, r, ǫ4 /k, δ)
queries to fO . We remark that the sample complexity m(P, Rr , d, ǫ, δ) for learning Euclidean k-means
instances is independent of P .

5

Lower Bounds for (1 − ǫ)-Accurate k-Means

The results we presented in Section 3 and Section 4 uses PAC learning to achieve (1 − ǫ)-accuracy.
Considering the class of Euclidean k-means instances, the query complexities of both our results have a
linear dependency on the dimension of the Euclidean space. This is in contrast to the query complexities
of the algorithms in Ashtiani et al. [3], which had strong assumptions on the input, and Ailon et al. [2],
which was only aiming to approximate the optimal cost. In this section, we argue that the linear
dependency on dimension is necessary for accuracy for Euclidean k-means instances. This result, as
shown in the latter half of this section, also implies that the dependency on log |Q| is necessary for the
k-means instances in finite metric spaces, where Q is the set of candidate centers.
13

Let r > 0 be an integer, and e1 , . . . , er be the standard basis in Rr . Consider the 2-means instance
(P, Rr , d) in r-dimensional Euclidean space, where P = {−e1 , e1 , . . . , −er , er }. There are 2r points in P .
In Lemma 16, we show that any optimal solution for this instance contains exactly one of ±ei in each
optimal cluster for all i = 1, . . . , r. Hence, there are 2r different optimal solutions. This means that,
without querying at least one of ±ei , it is information-theoretically impossible to know which cluster ei
and −ei each belong to, and thus to achieve constant classification error, the query complexity must be
linear in r. This proves the first claim of Theorem 3.
Lemma 16. Consider the k-means instances (P, Rr , d) defined as above. Let O = {O1 , O2 } be any fixed
optimal clustering on (P, Rr , d). For each i ∈ [r], either ei ∈ O1 and −ei ∈ O2 or ei ∈ O2 and −ei ∈ O1 .
˙ = {±e1, . . . , ±er }. We first observe the following: Let i ∈ [r] be
Proof. Consider a bi-partition A∪B
such that −ei ∈ A and ei ∈ B. Define A′ := A \ {−ei } ∪ {ei } and B ′ := B \ {ei } ∪ {−ei }. Then the cost
of the solution (A, B) is the same as the cost of (A′ , B ′ ). This is because ei and −ei are at the same
distance to all points in P \ {±ei }.
Therefore, without loss of generality, we only need to consider bi-partitions where the set A can
be described as A = {er0 +1 , . . . , er0 +r1 } ∪ {±er0 +r1 +1 , . . . , ±er0 +r1 +r2 } , for some r0 , r1 and r2 where
r0 + r1 + r2 = r. Consequently, we have that B = {±e1 , . . . , ±er0 } ∪ {−er0 +1 , . . . , −er0 +r1 } . To put
differently, A contains only the positive points on axes r0 + 1, . . . , r0 + r1 whereas B contains only the
negative points on the same axes. For axes r0 + r1 + 1, . . . , r0 + r1 + r2 , A contains both positive and
negative points on those axes. Similarly, for axes 1, . . . , r0 , B contains both points on those axes. The
center of A is
1
1
,...,
, 0, . . . , 0) ,
(0, . . . , 0,
| {z } r1 + 2r2
r1 + 2r2 | {z }
|
{z
}
r0
r2
r1

and the center of B is

1
1
,...,−
, 0, . . . , 0) .
(0, . . . , 0, −
| {z } r1 + 2r0
r1 + 2r0 | {z }
|
{z
}
r0
r2
r1

The cost of set A is

r1 ·
1−

1
r1 + 2r2

2

!


+ 2r2 · 1 + r1

1
(r1 + 2r2 )2

r1 (r1 + 2r2 − 1)2 + r1 (r1 − 1) + 2r2 (r1 + 2r2 )2 + 2r1 r2
1
+ (r1 − 1)
(r1 + 2r2 )2



1
(r1 + 2r2 )2

1
=
r1 (r1 + 2r2 )2 − 2r1 (r1 + 2r2 ) + r1 + r1 (r1 − 1) + 2r2 (r1 + 2r2 )2 + 2r1 r2
2
(r1 + 2r2 )

1
(r1 + 2r2 )3 − r1 (r1 + 2r2 )
=
2
(r1 + 2r2 )
r1
= (r1 + 2r2 ) −
.
r1 + 2r2
=

Similarly, the cost of set B is
!


2
1
1
1
+
2r
·
1
+
r
r1 ·
+ (r1 − 1)
0
1
r1 + 2r0
(r1 + 2r0 )2
(r1 + 2r0 )2
r1
.
= (r1 + 2r0 ) −
r1 + 2r0

1−

The total cost of this clustering is therefore

2r −

r1
r1
+
r1 + 2r2
r1 + 2r0



.

It remains to show that the maximum of
 


r1
r1
r1
r1
=
+
+
r1 + 2r2
r1 + 2r0
r1 + 2r2
2r − 2r2 − r1

14

is achieved by setting r1 = r and r0 = r2 = 0. For a fixed r1 , the last expression gives a convex function
in variable r2 , and therefore either r2 = 0 or r2 = r − r1 maximizes the expression. In either case, we
have that the maximum of this expression for a fixed r1 is
1+

r1
2r
=
,
2r − r1
2r − r1

which in turn achieves maximum when r1 = r.
Now consider the hard example for Euclidean setting with r = (log n/2). Thus,
Pwe have log n points
in P . Start with an empty set Q, and for each subset P ′ of P , add µ(P ′ ) = ( p ∈ P ′ p)/|P ′ | to Q.
This forms a finite metric space k-means instance (P, Q, d) that has no boundary points. From the claim
on dimension dependency for the Euclidean setting discussed above, it follows that Ω(r) = Ω(log n) =
Ω(log |Q|) samples are necessary to achieve (1 − ǫ)-accuracy. This proves the second claim of Theorem 3.

References
[1] Sara Ahmadian, Ashkan Norouzi-Fard, Ola Svensson, and Justin Ward. Better guarantees for kmeans and euclidean k-median by primal-dual algorithms. 2017 IEEE 58th Annual Symposium on
Foundations of Computer Science (FOCS), pages 61–72, 2017.
[2] Nir Ailon, Anup Bhattacharya, Ragesh Jaiswal, and Amit Kumar. Approximate clustering with
same-cluster queries. In 9th Innovations in Theoretical Computer Science Conference, ITCS 2018,
January 11-14, 2018, Cambridge, MA, USA, pages 40:1–40:21, 2018.
[3] Hassan Ashtiani, Shrinu Kushagra, and Shai Ben-David. Clustering with same-cluster queries.
In Proceedings of the 30th International Conference on Neural Information Processing Systems,
NIPS’16, pages 3224–3232, USA, 2016. Curran Associates Inc.
[4] P. Awasthi, A. Blum, and O. Sheffet. Stability yields a PTAS for k-median and k-means clustering.
In 2010 IEEE 51st Annual Symposium on Foundations of Computer Science, pages 309–318, Oct
2010.
[5] Maria-Florina Balcan, Avrim Blum, and Anupam Gupta. Clustering under approximation stability.
J. ACM, 60(2):8:1–8:34, May 2013.
[6] Michael B. Cohen, Yin Tat Lee, Gary Miller, Jakub Pachocki, and Aaron Sidford. Geometric median
in nearly linear time. In Proceedings of the Forty-eighth Annual ACM Symposium on Theory of
Computing, STOC ’16, pages 9–21, New York, NY, USA, 2016. ACM.
[7] Vincent Cohen-Addad, Philip N. Klein, and Claire Mathieu. Local search yields approximation
schemes for k-means and k-median in euclidean and minor-free metrics. In IEEE 57th Annual
Symposium on Foundations of Computer Science, FOCS 2016, 9-11 October 2016, Hyatt Regency,
New Brunswick, New Jersey, USA, pages 353–364, 2016.
[8] Amit Daniely, Sivan Sabato, Shai Ben-David, and Shai Shalev-Shwartz. Multiclass learnability and
the ERM principle. J. Mach. Learn. Res., 16(1):2377–2404, January 2015.
[9] S. Dasgupta. The Hardness of K-means Clustering. Technical report (University of California, San
Diego. Department of Computer Science and Engineering). Department of Computer Science and
Engineering, University of California, San Diego, 2008.
[10] Dan Feldman, Morteza Monemizadeh, and Christian Sohler. A PTAS for k-means clustering based
on weak coresets. In Proceedings of the Twenty-third Annual Symposium on Computational Geometry, SCG ’07, pages 11–18, New York, NY, USA, 2007. ACM.
[11] Zachary Friggstad, Mohsen Rezapour, and Mohammad R. Salavatipour. Local search yields a PTAS
for k-means in doubling metrics. In IEEE 57th Annual Symposium on Foundations of Computer
Science, FOCS 2016, 9-11 October 2016, Hyatt Regency, New Brunswick, New Jersey, USA, pages
365–374, 2016.

15

[12] Sariel Har-Peled and Soham Mazumdar. On coresets for k-means and k-median clustering. In
Proceedings of the thirty-sixth annual ACM symposium on Theory of computing, pages 291–300.
ACM, 2004.
[13] Mary Inaba, Naoki Katoh, and Hiroshi Imai. Applications of weighted voronoi diagrams and randomization to variance-based k-clustering: (extended abstract). In Proceedings of the Tenth Annual
Symposium on Computational Geometry, SCG ’94, pages 332–339, New York, NY, USA, 1994. ACM.
[14] Thorsten Joachims. Advances in kernel methods. chapter Making Large-scale Support Vector
Machine Learning Practical, pages 169–184. MIT Press, Cambridge, MA, USA, 1999.
[15] Tapas Kanungo, David M. Mount, Nathan S. Netanyahu, Christine D. Piatko, Ruth Silverman, and
Angela Y. Wu. A local search approximation algorithm for k-means clustering. In Proceedings of
the Eighteenth Annual Symposium on Computational Geometry, SCG ’02, pages 10–18, New York,
NY, USA, 2002. ACM.
[16] Euiwoong Lee, Melanie Schmidt, and John Wright. Improved and simplified inapproximability for
k-means. Inf. Process. Lett., 120:40–43, 2017.
[17] S. Shalev-Shwartz and S. Ben-David. Understanding Machine Learning: From Theory to Algorithms.
Understanding Machine Learning: From Theory to Algorithms. Cambridge University Press, 2014.

A

PAC Learning

In this section, we introduce some fundamental concepts and tools from PAC learning theory, and prove
Theorem 4 and Theorem 5. We start by introducing some necessary notations.
Let X be an arbitrary domain set, Y be a label set, and H ⊆ {h : X → Y} be a hypothesis class.
Let D be some arbitrary distribution over X × Y. The error of a hypothesis h ∈ H with respect to D is
defined as
LD (h) := Pr [h(x) 6= y] .
(2)
(x,y)∼D

We say that H satisfies the realizability assumption if there exists some h∗ ∈ H such that LD (h∗ ) = 0.
A learning algorithm A for hypothesis class H receives as input a sequence S := ((x1 , y1 ), . . . , (xm , ym ))
of m pairs of domain points and their labels, where each domain point is sampled independently from D.
The learning algorithm should output a predictor A(S) ∈ H. The goal of the algorithm is to minimize
the generalization error LD (A(S)) with respect to the unknown D. We define the empirical error (risk)
on S for a hypothesis h as
|{i ∈ [m] : h(xi ) 6= yi }|
LS (h) :=
.
(3)
m
We call the algorithm A an empirical risk minimization (ERM) algorithm if
A(S) ∈ argmin LS (h) .
h∈H

Let H be a hypothesis class for some discrete domain X . If the realizability assumption holds for H,
and if A is an ERM algorithm for H, then LS (A(S)) = 0.
Clearly, A(S) depends on S. Hence, the generalization error, LD (A(S)), is a random variable whose
randomness depends on S. We are interested in establishing an upper bound on the number of samples
that A needs in order to guarantee that the generalization error is small with a good probability.
Definition 17 (Sample Complexity of a Learning Algorithm). Let A be a learning algorithm for a
hypothesis class H. We define the sample complexity of A, mA,H (ǫ, δ), as the minimum natural number
such that, if S is sequence of m ≥ mA,H (ǫ, δ) i.i.d. samples from D, with probability at least 1 − δ,
LD (A(S)) ≤ ǫ.
We now introduce some terminology from learning theory. We first define the notions of shattering
and VC-dimension for a binary hypothesis class H ⊆ {h : X → {1, 2}}.
Definition 18 (Shattering). We say a binary hypothesis class H shatters a finite set
C = {c1 , . . . , cm } ⊆ X ,
|C|

if {(h(c1 ), . . . , h(cm )) : h ∈ H} = {1, 2}

.
16

Definition 19 (Vapnik–Chervonenkis (VC) Dimension). The VC-dimension of a binary hypothesis class
H, denoted VCdim(H), is the maximum size of a set C ⊂ X that can be shattered by H. If H shatters
sets of arbitrarily large size, we say that H has infinite VC-dimension.
By definition, to shatter a set C, a hypothesis class H must have at least 2|C| distinct elements.
Hence, we have the following lemma.
Lemma 20. Let H be a finite hypothesis class. Then, VCdim(H) = O(log |H|).
For a k-ary hypothesis class H ⊆ {h : X → [k]}, we define the analogous notions of multiclass
shattering and Natarajan dimension. As we will see below, the notion of multiclass shattering is a
generalization of the notion of shattering for the binary hypothesis classes. Consequently, the Natarajan
dimension is a generalization of the VC-dimension.
Definition 21 (Multiclass Shattering). We say that a set C ⊆ X is shattered by a k-ary hypothesis class
H if there exist two functions f0 , f1 : C → [k] such that,
• For every x ∈ C, f0 (x) 6= f1 (x).
• For every B ⊂ C, there exists a function h ∈ H such that,
∀x ∈ B, h(x) = f0 (x) and ∀x ∈ C\B, h(x) = f1 (x).
Definition 22 (Natarajan Dimension). The Natarajan dimension of a k-ary hypothesis class H, denoted
by Ndim(H), is the maximal size of a set C ⊆ X that can be shattered by H.
Suppose k = 2. If a binary hypothesis class Hbin : X → {1, 2} shatters a set C ⊆ X according to
Definition 18, then for all subsets B of C, there exists a hypothesis h ∈ Hbin that maps all points in B to
1 and all points in C\B to 2. Thus, setting f0 (x) = 1 and f1 (x) = 2 to be constant functions, it follows
that Hbin shatters C according to Definition 21 as well.
For the converse, suppose that Hbin is hypothesis class that shatters a set C ⊆ X according to
Definition 21. Definition 21 essentially says that, any mapping C → {1, 2}|C| must be achievable with
one of the hypotheses in Hbin which is equivalent to Definition 18. To see this, notice that f0 (x) 6= f1 (x),
and that we only have two labels.
In the remainder of this appendix, we prove Theorem 4 and Theorem 5. We proceed with defining a
new hypothesis class for binary classification which is associated with non-homogeneous halfspaces in Rr .
Formally, given a non-homogeneous hyperplane ℓ ⊂ Rr , let hℓ be the binary classifier that assigns labels
±1 to points based on which side of the hyperplane the point lies on. We define the binary hypothesis
class HbEUC as
HbEUC = {hℓ : ℓ is a (non-homogeneous) hyperplane in Rr }.
Lemma 23 (Theorem 9.3 of Shalev-Shwartz and Ben-David [17]). The VC-dimension of HbEUC is r + 1.
Let (P, Rr , d) be a k-means instance in Euclidean space. Let O be a fixed optimal clustering of P ,
and let fO be the labeling function of O. Assume that (P, Rr , d) has no boundary points (i.e., in an
optimal clustering, for any given point p ∈ P , the closest optimal center is unique). Let A, B ⊂ P two
non-empty disjoint subsets of points of two different labels under fO . Due to the assumption of having
no boundary points, there exists a hypothesis h ∈ HbEUC that perfectly separates points in A from those
in B. That is to say, it assigns −1 to all points in A and +1 to all points in B. Such a hypothesis h can
be learned in polynomial-time using standard SVM (Support Vector Machine) training algorithms like
the one proposed by Joachims [14].
Let S = {(x1 , y1 ), . . . , (xm , ym )} be a multiset of sample-label pairs from P × Q. Fix a pair of distinct
cluster labels a, b ∈ [k ′ ] and let Sa,b be the subset of the samples-label pairs in S whose labels are either
a or b. Since each pair of original clusters can be separated with a hyperplane in Rr , there exists a
hypothesis ga,b ∈ HbEUC that perfectly labels the samples in Sa,b ; that is to say that for all (x, y) ∈ Sa,b ,
ga,b (x) = 1 if y = a and ga,b (x) = −1 ifPy = b. Suppose for each pair a, b ∈ [k], a 6= b, we find a hypothesis
ga,b . Then, for
P all samples (x, a) ∈ S, b6=a ga,b (x) = k − 1. Moreover, for any sample (x, a) ∈ S, and for
any a′ 6= a, b6=a′ ga′ ,b (x) < k − 1. This is because ga′ ,a (x) = −1. Consequently, the function g defined
as
X
ga,b (x)
g(x) = argmax
a∈[k]

b∈[k],b6=a

17

returns the correct label y for all (x, y) ∈ S. Hence, the aforementioned procedure gives an ERM
algorithm for the hypothesis class H∗ which is formally defined follows: for ḡ = (ga,b )[a,b∈[k],a6=b] ∈
k(k−1)
P
HbEUC
, a (k(k − 1))-tuple of binary hypotheses, let hḡ (x) = argmaxa∈[k] b∈[k],b6=a ga,b (x). Define
n
k(k−1) o
H∗ = hḡ : ḡ ∈ HbEUC
.

The pseudo-code of the algorithm is presented in Algorithm 7. This algorithm is an adaptation of
the All-Pairs algorithm described in Chapter 17.1 of Shalev-Shwartz and Ben-David [17]. An observant
reader may notice that learning two hypotheses, namely ga,b and gb,a , per each distinct a, b is redundant
as one can set ga,b (x) = −gb,a (x). However, for the ease of presentation, we stick with the idea that ga,b
and gb,a are picked independently from each other.
Input : A set of samples S = (x1 , y1 ), . . . , (xm , ym ) and an ERM algorithm B for learning HbEUC .
Output: A hypothesis g ∈ H∗ .
1
2
3
4
5
6
7

for a, b ∈ [k] such that a 6= b do
Let Sa,b = [ ] be an empty list.
for t = 1, . . . , m do
If yt = a add (xt , 1) to Sa,b .
If yt = b add (xt , −1) to Sa,b .
Let ga,b = B(Sa,b ).
Let g(x) = argmaxa∈[k]

P



b∈[k],b6=a ga,b (x)

.

Algorithm 4: An ERM algorithm for k-category classification.
The corollary to the following lemma bounds the Natarajan dimension of H∗ .
Lemma 24 (Lemma 29.6 of Shalev-Shwartz and Ben-David [17]). Consider a multiclass predictor derived
in the following way. Train l binary classifiers from a binary hypothesis class Hbin and let v : {−1, 1}l →
v
[k] be a mapping from the l predictor results to a class label. Let Hbin
be the class of multiclass predictors
v
obtained in this manner. If VCdim(Hbin ) = d then, Ndim(Hbin ) ≤ 3dl log(ld).
Corollary 25. The Natarajan dimension of the hypothesis class H∗ is O(rk 2 log(rk)) where r is the
dimension of the Euclidean space and k is the number of clusters in the k-means instance.
The following lemma, combined with Corollary 25 yields that
  3 

k 2 r log(k 2 r) log kǫ r
+ log
mERM,H∗ (ǫ, δ) = O 
ǫ

1
δ



.

Lemma 26 (Theorem 3.7 of Daniely et al. [8]). Let H ⊆ {h : X → [k]} be a hypothesis class, for which
the realizability assumption holds with respect to some distribution D, and let d = Ndim(H). Let
mERM,H (ǫ, δ) =

sup mA,H (ǫ, δ),

A∈ERM

where the supremum is taken over all ERM algorithms for H. Then,

!
1
+
log
d log kd
ǫ
δ
.
mERM,H (ǫ, δ) = O
ǫ
Thus, if m ≥ mERM,H∗ (ǫ, δ) i.i.d. samples from Q and their respective labels were input to Algorithm
7, the output hypothesis h, with probability at least (1 − δ), will have at most an ǫ error.
To prove Theorem 4, what remains is to ensure that the learned hypothesis does not output class
labels that the learning algorithm has not seen in the samples. For this, we propose a simple modification
to Algorithm 7. That is, if a′ is a class label that is not present in the samples, for all class labels a from
which we have seen at least 1 sample, we set ga,a′ (x) = 1 and ga′ ,a (x) = −1 to be constant functions
which may correspond to hyperplanes that are infinitely far away from the origin. Without loss of
generality, assume that we have seen samples with labels 1, . . . , k ′ , and we have not seen samples with
18

labels k ′ + 1, . . . , k. Let a ∈ k ′ be a label that that we have seen and let a′ ∈ [k]\[k ′ ] be a label that we
have not seen. Therefore we have
X
X
X
ga,b (x) ≥ −(k ′ − 1) + (k − k ′ ) = k − 2k ′ + 1,
ga,b (x) +
ga,b (x) =
b6=a

and

X

b6=a′

b∈[k]\[k′ ]

b∈[k′ ],b6=a

ga′ ,b (x) =

X

b∈[k′ ]

ga′ ,b (x) +

X

ga′ ,b (x) ≤ −k ′ + (k − k ′ − 1) = k − 2k ′ − 1.

b∈[k]\[k′ ],b6=a′

Consequently, the output g(x) of Algorithm 7 will never assign a label from [k]\[k ′ ] to any x ∈ Rd .
To prove Theorem 5, all we need to do is to replace the binary hypothesis class HbEUC used in the
preceding discussion with the binary hypothesis class HbFMS which we introduce next. We show that
HbFMS satisfies the realizability assumption. We further show that there exists an ERM algorithm for
HbFMS and the VC-dimension of HbFMS is small.
Let (P, Q, d) be k-means instance in a finite metric space where |Q| < ∞, and define the binary
hypothesis class HbFMS as follows:
HbFMS = {hq1 ,q2 : (q1 , q2 ) ∈ Q × Q},
where hq1 ,q2 : P → {−1, +1} is a binary labeling function define as
(
−1, if d(p, q1 ) ≥ d(p, q2 )
hq1 ,q2 (p) =
+1, otherwise.
Observe that this is a finite hypothesis class with at most |Q|2 hypotheses. Furthermore, based on the
assumption on no boundary points, for any two subsets P of two different labels, there exists an h ∈ HbFMS
that perfectly separates them. Hence, pairwise binary classification of any two labels is realizable under
Hb . To find such h in polynomial-time, we simply iterate over all possible hypotheses and pick the one
that gives zero error. Lemma 20 yields that the VC-dimension of HbFMS is O(log |Q|).

19

