A Unified Framework for Approximating and Clustering Data

Introduction

In this work, we present a unified framework for the efficient construction of coresets for clustering problems corresponding to a given function set $F$. Our coresets are obtained via a new and natural reduction to the well studied notion of $\varepsilon$-approximation from the theory of VC dimension [VC71]. The reduction from coresets to $\varepsilon$-approximations allows our framework to rely only on the combinatorial complexity of the input family $F$ of functions (i.e., the combinatorial complexity of the clustering problem at hand), and to use the vast literature on $\varepsilon$-approximation to obtain improved results (that are at times deterministic). For several function families $F$ for which coresets are known not to exist, or the corresponding (approximate) optimization problems are hard, our framework yields bicriteria approximation, or coresets that are large, but contained in a low-dimensional space.

In the body of the paper, we give an overview of the contributions of our work. We start by presenting, in Section 2, several concrete results that follow from our algorithmic paradigm, including a detailed comparison with corresponding previous work. We then present the main proof techniques and conceptual novelties in our approach in Section 3. Finally, in Section 4, we present a detailed overview of our algorithms for the construction of corestes and bicriteria approximation. The above discussion will take up the body of this extended abstract. All of the technical details of our results appear in the (self contained) appendix. A first application of our framework (for HD-image processing) already appeared in [FFS11].

Concrete Contributions

All the algorithms that are described in this section are randomized, and succeed with probability at least $1/2$ (or any other constant approaching $1$).

The construction time of the strong and weak coresets is $O(ndjk+t\log n)$. All our coresets and running times below are generalized to sum of distances to the power of $z>1$, after replacing the term $\varepsilon$ in the corresponding results by $1/\varepsilon^{2z}$.

2 k𝑘k-Median and its generalizations

3 k𝑘k-Line median and its generalizations

4 Subspace approximation

For the case $z=2$, Boutsidis et al. [BDMI11] provide $(2+\varepsilon)$ randomized and deterministic CUR decompositions using $m=O(j/\varepsilon)$ columns. They also provide an updated reference for this long line of research. Mahoney and Drineas suggested a randomized algorithm that yields a $(1+\varepsilon)$-approximation for the case $z=2$ [MD09].

5 Projective clustering

Note that this result does not have the reduction property of weak coresets as defined in the beginning of this section. That is, even if we have an algorithm that computes the optimal set $x^{*}$ of $k$ $j$-subspaces for any given set of points, it is not clear how to use it with $V$ in order to have a more efficient solution for the original problem. Similarly, it seems that this result can not be generalized for the streaming model when the subspace $V$ needs to be computed for a stream of $n$ points $P$ using less than $O(nd)$ space.

For these problems (where $k,j>1$), we suggest strong, weak, and streaming coresets contained in low-dimensional subspaces, and therefore take sub-linear space. Our coresets, referred to as $B$-coresets, were described in Section 2.1, and are used as the first step for the construction of all the coresets presented in this section (including when $j=1$ or $k=1$).

Novelties in proof techniques

As specified in Section 2, our unified framework yields a number of improved results in the context of approximate clustering and shape fitting. In what follows, we briefly touch on the major new ideas used in our algorithms allowing theses improved results. Reduction to $\varepsilon$-approximation: The main reason that our framework is able to address a spectrum of clustering and approximation problems lies in our reduction from the inconsistent definition of coresets to the notion of $\varepsilon$-approximation. Using this reduction we can: (i) use a common ground in our analysis, thus removing the specialized (and sometimes tedious) analysis of the required sampling sizes used in many of the related works mentioned in Section 2. (ii) use smaller sample sizes that improve on those obtained in previous works, due to recent results taken from the context of Machine Learning [LLS00]. (iii) apply numerous results from the field of Computational Geometry, dated back to [HW86], regarding the study of VC-dimension and $\varepsilon$-approximations. For example: deterministic constructions [Mat95], for convex shapes (which have unbounded VC-dimension) [CEG+95], and in the streaming model [BCEG07].

Our reduction includes multiple stages and uses the new notions of robust approximation and robust corests as intermediate points. We elaborate on our reduction to $\varepsilon$-approximation (including our new notions) in the upcoming Section 4 which addresses a detailed overview of our framework. Functional representation of data elements and coresets: To study coresets over a wide range of objectives, we present an abstract framework in which the data points are considered as functions. Namely, for a center $x$, the value $f(x)$ represents the cost of clustering the data element corresponding to $f$ with $x$. This representation is not superficial, and is in a sense crucial, as in our setting the coresets we construct are no longer “data elements” (as is common in the literature) but rather functions as well. Indeed, in some cases, our coresets will correspond to a subset of data elements, and thus their representation by functions will have no special meaning. However, in several cases the coreset consists of a small set of functions, that are closely related to the original data functions, however differ in certain behaviors.

For example, several of our coresets use functions $g$ corresponding to the data functions $f$ such that $g(x)=f(x)$ only if $f(x)$ is smaller than a certain threshold; otherwise $g(x)$ will be neglected and equal to zero. Another example includes the use of functions $g$ that correspond fully to data elements $f$, but appear in the coreset as having negative weight. We extend and generalize results from [FMSW10] that had such properties. However, unlike in [FMSW10], a PTAS for the optimization problem can be computed from the coresets without using the original data.

One may argue that this skewed succinct representation of the original data violates the traditional line of thought in which a coreset consists of a subset of “real” data elements, and thus in many cases we make an effort in finding such “standard” coresets. However, when considering the computational objective in the construction of coresets, namely a tool to allow the efficient approximation of clustering problems, our notion of coresets plays a role equivalent to that of standard coresets. The flexibility in allowing our coresets to deviate from standard conception is a key point in our ability to obtain improved results. Generalized range spaces: In the vast literature on clustering, the notion of coresets is defined in several ways. Two common definitions include strong and weak coresets, which roughly speaking, address the combinatorial and computational aspects of clustering respectively. Namely, strong coresets require a similar behavior when compared to the data set for every set of centers, while weak coresets require “just enough” so that the coreset can be used in the design of efficient algorithms for approximate clustering.

In this work we unify the study of weak coresets that was used recently in [AHPV05, FMS07, FMSW10] with older results related to $\varepsilon$-approximation [CF90], called $\varepsilon$-frames. As our work reduces the study of coresets to that of $\varepsilon$-approximation in certain range spaces, this unification is captured by the development of a new notion: a generalized range space and a corresponding generalized dimension.

More specifically, in the standard study of range spaces, an $\varepsilon$-approximation captures the propertied of the original space with respect to any range in the space. This intuitively corresponds to the study of strong coresets. For the (more delicate) study of weak coresets, we enhance the standard definition of a range space, to obtain a generalized definition and theory. In our generalized view, an $\varepsilon$-approximation captures the propertied of the original space with respect to a subset of predetermined ranges in the space (and not necessarily all of the ranges). Choosing the predefined subsets carefully, one may capture the essence of weak coresets. The study of generalized range spaces enables us to use the same algorithms in our constructions of coresets, whether weak or strong, where the difference in the obtained results (in size and running time) is now easily traced back to the notion of the generalized dimension of the range space at hand.

Framework overview

We now review the concept of $\varepsilon$-approximations and $\varepsilon$-coresets followed by a detailed overview of our general framework.

For a multi-set $F$ of non-negative functions on a set $X$, we say that $S\subseteq F$ is an $\varepsilon$-approximation for $F$, if for every every $x\in X$ and $r\geq 0$ we have

where $\mathbf{range}(S,x,r)=\left\{f\in S\mid f(x)\leq r\right\}$. For a set $F$ of non-negative functions on a set $X$, we say that $D$ is an $\varepsilon$-coreset for $F$, if for every $x\in X$ we have

For each $f\in F$, let $g_{f}:X\rightarrow[0,\infty)$ be defined as $g_{f}(x)=f(x)/m(f)$. Let $G_{f}$ consists of $m_{f}$ copies of $g_{f}$, and let $S$ be an $(\varepsilon\cdot n/\sum_{f\in F}m(f))$-approximation of the set $G=\bigcup_{f\in F}G_{f}$. Then $D=\left\{g_{f}\cdot|G|/|S|\mid g_{f}\in S\right\}$ is an $\varepsilon$-coreset for $F$. That is, for every $x\in X$,

2 Bicriteria approximation

The first part of our framework yields a general paradigm for bicriteria approximations, that essentially reduces the task at hand to that of $\varepsilon$-approximations from the theory of Machine/PAC Learning and VC dimension [VC71, HW86]. Roughly speaking our reduction includes three steps. In the first step, we determine the combinatorial complexity of the clustering problem at hand by defining a corresponding generalized range space and studying its generalized VC-dimension (we elaborate on these notions shortly). We then show that an $\varepsilon$-approximation to the corresponding range space, yields a relaxed notion of bicriteria clustering we refer to as a robust median. Finally, we show how to use these robust medians in able to obtain a bicriteria solution. An outline of our framework follows. Generalized VC dimension: Given the clustering problem at hand (i.e., the function family $F$), one starts by defining a corresponding range space and by studying its combinatorial complexity (i.e., dimension).

Let $F$ be a finite set of functions from a set $X$ to $[0,\infty)$. The dimension $\dim(F)$ of $F$ is the dimension of the range space \big{(}F,\mathbf{ranges}(F)\big{)}, where $\mathbf{ranges}(F)$ is the range space of $F$, that is defined as follows. For every $x\in X$ and $r\geq 0$, let $\mathbf{range}(x,r)=\left\{f\in F\mid f(x)\leq r\right\}$. Let the set $\mathbf{ranges}(F)$ be defined as $\left\{\mathbf{range}(x,r)\mid x\in X,r\geq 0\right\}$. The dimension of $(F,\mathbf{ranges})$ is the minimum $d$ such that

To allow the unified study of both strong and weak coresets, we enhance the definition above to that of a generalized range space. In a generalized range space corresponding to $F$, for every subset $S$ of functions one defines a corresponding subset of important ranges $\mathbf{ranges}(S)\subset\mathbf{ranges}(F)$. In our context of clustering, the set $\mathbf{ranges}(S)$ will be defined by a subset $\mathcal{X}(S)$ of centers $x\in X$ that are guaranteed to include a good center to be used in the clustering of $S$. More precisely:

Let $F$ be a finite set of functions from a set $X$ to $[0,\infty)$. Let $\mathcal{X}$ be a function that maps every subset $S\subseteq F$ to a set of items $\mathcal{X}(S)\subseteq X$. The pair $(F,\mathcal{X})$ is called a generalized function space, if for any $S\subseteq S^{\prime}$ it holds that $\mathcal{X}(S)\subseteq\mathcal{X}(S^{\prime})$. The dimension of $(F,\mathcal{X})$ is the smallest integer $d$, such that

where $\mathbf{ranges}(S)=\left\{\mathbf{range}(x,r)\mid x\in\mathcal{X}(S),r\geq 0\right\}$.

For a generalized function space $(F,\mathcal{X})$, we now seek small subsets $S\subseteq F$ that are $\varepsilon$-approximations to the range space $(F,\mathbf{ranges}(S))$. Loosely speaking, such sets will approximate the function set $F$ with respect to the centers in $\mathcal{X}(S)$ that are (by definition) of “importance” to the approximation of $S$. Combining this with a proof that centers that approximate $S$ also approximate $F$, will yield the weak coresets we desire. Notice that in the above definition we have required the function $\mathcal{X}$ to be monotone. This allows us to obtain the following (immediate) connection between random sampling and $\varepsilon$-approximation (e.g., via [LLS01]).

Let $(F,\mathcal{X})$ be a function space of dimension $d$ from $X$ to $[0,\infty)$. Let $\varepsilon,\delta>0$. Let $S$ be a sample of $|S|=\frac{c}{\varepsilon^{2}}\left(d+\log\frac{1}{\delta}\right)$ i.i.d functions from $F$, where $c$ is a sufficiently large constant. Then, with probability at least $1-\delta$, $S$ is an $\varepsilon$-approximation of the range space $(F,\mathbf{ranges}(S))$.

Let $F$ be a set of $n$ functions from a set $X$ to $[0,\infty)$. Let $0<\varepsilon,\gamma<1$, and $\alpha>0$. For every $x\in X$, let $F_{x}$ denote the \big{\lceil}\gamma n\big{\rceil} functions $f\in F$ with the smallest value $f(x)$. Let $Y\subseteq X$, and let $G$ be the set of the $\lceil(1-\varepsilon)\gamma n\rceil$ functions $f\in F$ with smallest value $f(Y)=\min_{y\in Y}f(y)$. The set $Y$ is called a $(\gamma,\varepsilon,\alpha,\beta)$-median of $F$, if $|Y|=\beta$ and

Notice that a set of centers $Y$ which are a $(1,0,\alpha,\beta)$-median are (by definition) an $(\alpha,\beta)$ bicriteria approximation. Thus, one is interested in finding good robust medians for $F$. We show that this is possible via $\varepsilon$-approximations $S$ to the function space $(F,\mathcal{X})$. In the lemma below we use $\beta=1$. We note that a similar lemma, for general $\beta$, also holds, and appears in the appendix.

Let $(F,\mathcal{X})$ be a function space of dimension $d$. Let $\gamma\in(0,1]$, $\varepsilon\in(0,1/10)$, $\delta\in(0,1/10)$, $\alpha>0$. Let $S$ be a random sample of $s=\frac{c}{\varepsilon^{4}\gamma^{2}}\left(d+\log\frac{1}{\delta}\right),$ i.i.d functions from $F$, where $c$ is a sufficiently large constant. Suppose that $x\in\mathcal{X}(S)$ is a $((1-\varepsilon)\gamma,\varepsilon,\alpha,1)$-median of $S$, and that $|F|\geq s$. Then, with probability at least $1-\delta$, $x$ is a $(\gamma,4\varepsilon,\alpha,1)$-median of $F$.

Once the connection between $\varepsilon$-approximation and robust medians is established, one can find robust medians for $F$ via an exhaustive (or sometimes more efficient) algorithm that addresses the $\varepsilon$-approximation $S$. From robust medians to bicriteria. We are now ready to present our algorithm for bicriteria approximation. Before presenting our algorithm, we note that although an $(\alpha,\beta)$-bicriteria approximation is precisely a $(1,0,\alpha,\beta)$-median, we cannot use Lemma 4.6 above to obtain a bicriteria solution (as in Lemma 4.6, $\varepsilon>0$ and there is a slackness in the reduction w.r.t. $\gamma$).

Our algorithm Bicriteria$(F,\varepsilon,\alpha,\beta)$ for bicriteria approximation appears in Figure 1. The algorithm receives the function family $F$ and parameters $\alpha,\beta,\varepsilon$ and outputs a subset of centers of size logarithmic (in $|F|$) that act as a bicriteria approximation to the median problem on $F$. The main recursive call for “$(3/4,\varepsilon,\alpha,\beta)$-median” in Bicriteria is to the computation of a $(3/4,\varepsilon,\alpha,\beta)$-median for $F$ which is essentially done via the connection to $\varepsilon$-approximation specified above. Namely, to compute a $(3/4,\varepsilon,\alpha,\beta)$-median for the function set $F_{i}$ (defined in the algorithm), we take a random sample $S$ of $F_{i}$, find a corresponding robust median for $S$, and return it as a robust median for $F_{i}$. Our main theorem in the context of bicriteria approximation follows.

$O(\mbox{\bf RobustMedian})$ is the time it takes to compute a $(3/4,\varepsilon,\alpha,\beta)$-median for a set $F^{\prime}\subseteq F$.

$O(\mbox{\bf ExahstiveBicriteria})$ is the time it takes to compute an $(\alpha,\beta)$ bicriteria for a set $F^{\prime}\subseteq F$ of size $|F^{\prime}|=O(1/\varepsilon)$.

The size and running time are specified in Theorem 4.7 in an abstract manner as a function of $\alpha$, $\beta$, $\varepsilon$, RobustMedian, ExhaustiveBicriteria, and implicitly $d$ - the generalized VC dimension of the function space $(F,\mathcal{X})$. In Section 2, we presented some concrete examples in which the size and running time specified in Theorem 4.7 are computed for specific well studied clustering problems. More examples appear in the appendix of this work. As we show, our framework improves upon previously best known results.

3 From bicriteria to coresets

Once one has established an $(\alpha,\beta)$ bicriteria approximation for the clustering problem at hand, we present a paradigm for obtaining coresets (both strong and weak as defined in Section 2).

This general algorithmic paradigm in itself is the basis of several coreset constructions that have been recently suggested, e.g., [Che06, FMSW10, FMS07, LS10]. However, the main novelty in our algorithm is in its second step, which essentially adds the bicriteria centers as additional elements in the coreset. Adding the bicriteria centers to the coreset, combined with a delicate weighting mechanism (that may assign negative weights), enables the proof of the following theorem. In what follows, we assume $B$ is an $(O(1),O(k))$ bicriteria approximation. This can be obtained from previous works (e.g., [Che06]) or by the use of our framework in an enhanced version of Theorem 4.7 (details appear in the appendix).

The main idea governing the proofs of Theorems 4.8 and 4.9 lies in the fact the the random sample $\mathcal{S}$ of algorithm $k$-Median-Coreset is an $\varepsilon$-approximation to (a slightly modified version of) the function family $F$ corresponding to $k$-median clustering of $P$. To obtain our succinct setting for $t$, we perform a delicate analysis which determines the weights $\{m_{p}\}$, $\{w(p)\}$ and $\{w(b)\}$ specified in $k$-Median-Coreset. In the case of $k$-median clustering, our coresets consist of points in the data set $P$ (as common in the study of coresets for approximate clustering). In the coresets to come, this will no longer be the case, and the functional representation of our data will be central.

However, as the reader may have noticed, the size of our coreset is larger than the set we started with, so where is the gain? The gain is in the structure of the coreset $D$ compared to the data set $P$: it is (essentially) the union of a small set $\mathcal{S}$ with a set $P^{\prime}$ that lies in a low dimensional space. Specifically, $P^{\prime}$ can be partitioned to sets, each consisting of points on a single line (from $B$). Thus, if $B$ is small (and using Theorem 4.7 it is logarithmic), we have conceptually reduced the problem of finding a coreset for $P$ to that of finding a coreset for $D$, which can now be done via its specialized structure (e.g., via [FFS06]). The following theorem summarizes the quality of the resulting algorithm, which (a) first runs Metric-B-Coreset to obtain $D$ corresponding to $\mathcal{S}$ and $P^{\prime}$, (b) then uses [FFS06] and a few additional ideas to find a small set of points $\mathcal{S}^{\prime}$ that are a good approximation to $P^{\prime}$ (including a corresponding weight function), and (c) returns a succinct function set corresponding to $\mathcal{S}$ and $\mathcal{S}^{\prime}$.

The general setting: We now address the general setting in which we are given a general function family $F$. As in the previous case, our algorithm first finds a $B$-coreset, and only then may try to utilize the nature of the $B$-coreset to obtain a standard coreset. Our algorithm B-Coreset for finding the $B$-coreset is presented in Figure 4 and is phrased in an abstract manner that captures the previously defined coreset algorithms Metric-B-Coreset and $k$-Median-Coreset.

We now turn to discuss the set $U$ returned as output by B-Coreset. Notice, that there is no use of random sampling in algorithm B-Coreset. Instead, to construct the set $U$ we use the more general notion of $\varepsilon$-approximation, again on a weighted and threshold defined variant of $F$. To be precise, we could have used the notion of $\varepsilon$-approximation in the previously defined coreset algorithms as well, but instead represented them in terms of random sampling for ease of presentation.

All in all, algorithm B-Coreset returns two sets, the function set $T$ that corresponds to a threshold version of $F^{\prime}$ (which intuitively corresponds to a projected version of $F$ onto a given bicriteria solution), and the function set $U$ which corresponds to a small sized $\varepsilon$-approximation to (a threshold and weighted version) of the family $F$. Our main theorem in the this general setting is now:

Some remarks are in place. Primarily, our presentation of Theorem 4.11 is very general and involves several parameters and function sets. From this presentation, both the the size and quality of our coreset $D$ is hard to decipher. The abstract nature of Theorem 4.11 allows us to apply it on several function families $F$. In Section 2 we have presented a number of concrete algorithmic applications. These applications are proven in detail in the appendix.

Secondly, as discussed in Section 3, the output of algorithm B-Coreset is a new set of functions $D$ that may not be a subset of $F$. Indeed, this is the case, however we stress that the set $U$ is essentially a subset of $F$ which differs only by our weights $m_{f}$ and threshold cut-off $s_{f}$. Moreover, the function set $F^{\prime}$ and thus the set $T$ will be a set of functions that are typically easy to compute from a bicriteria of $(F,X)$. As we have shown, in certain cases, such as the $k$-median problem discussed previously, we are able to slightly modify our algorithm so that it returns a set of points $D\subset F$ as the desired coreset and not a function set that may have cut-off thresholds.

Acknowledgment

We wish to thank Christos Boutsidis, Michael Mahoney and Leonard Schulman for helpful discussions on this paper.

References

Appendix 5 Road map

The body of this extended abstract holds a detailed discussion of our results, without elaborating on the rigorous technical content. In this self contained appendix, we present the complete definitions and proofs of all our claims discussed in the body of this work. The appendix is organized as follows.

In Section 6, we review the notion of $\varepsilon$ approximation for range spaces and define and analyze the new notion of $\varepsilon$-approximations for function families.

In Section 7, we define and analyze the notion of generalized range spaces and generalized dimension, including the connection between these notions and the classical notions of Section 6.

In Section 8, we show a connection between $\varepsilon$-approximations and a new relaxed notion of coresets we refer to as robust coresets.

In Section 9, we further study the notion of robust coresets and link them with the notion of a robust median discussed in the body of the paper. This connection ties the notion of robust medians with that of $\varepsilon$-approximations.

In Section 10 we define the notion of a centroid set to be used in the sections to come.

In Section 11 we tie the notion of robust coresets with that of bi-criteria approximation, a connection discussed in the body of this work.

In Section 12, we use the analysis of previous sections to obtain concrete results on the bicriteria approximation of several clustering problems, some of which were discusses in Section 2 in the body of the paper.

In Section 17 we study the $k$-line median problem, and prove the results stated in Section 2.

In Section 18, we show how to apply our framework in order to construct (low-dimensional) $B$-coresets and coresets for subspace approximation. We apologize to the reader, and note that we are currently still writing parts of this section, which will be uploaded to a future version on arXiv.

Appendix 6 ε𝜀\varepsilon-Approximations

In this section we will discuss the basic definitions of $\varepsilon$-approximation used throughout this work.

A range space is a pair $(F,\mathbf{ranges})$ where $F$ is a set, and $\mathbf{ranges}$ is a set of subsets of $F$. The dimension of the range space $(F,\mathbf{ranges})$ is the smallest integer $d$, such that for every $G\subseteq F$ we have

The dimension of a range space relates (but is not equivalent) to a term known as the VC-dimension of a range space.

A set $S$ of functions is an $\varepsilon$-approximation of the range space $(F,\mathbf{ranges})$, if for every $\mathbf{range}\in\mathbf{ranges}$ we have

Usually $S\subseteq F$, otherwise $S$ is called in the literature a weak $\varepsilon$-approximation.

The following well known theorem states that a random sampling from a set is also an $\varepsilon$-approximation of $F$. See discussion in [HP09].

Let $(F,\mathbf{ranges})$ be a range space of dimension $d$. Let $\varepsilon,\delta>0$. Let $S$ be a sample of

i.i.d items from $F$, where $c$ is a sufficiently large constant. Then, with probability at least $1-\delta$, $S$ is an $\varepsilon$-approximation of $(F,\mathbf{ranges})$.

Let $F$ be a finite set of functions from a set $X$ to $[0,\infty)$. The dimension $\dim(F)$ of $F$ is the dimension of the range space \big{(}F,\mathbf{ranges}(F)\big{)}, where $\mathbf{ranges}(F)$ is the range space of $F$, that is defined as follows. For every $x\in X$ and $r\geq 0$, let $\mathbf{range}(F,x,r)=\left\{f\in F\mid f(x)\leq r\right\}$. Let $\mathbf{ranges}(F)=\left\{\mathbf{range}(F,x,r)\mid x\in X,r\geq 0\right\}$.

The following lemma follows directly from our definitions:

Let $F$ be a set of functions from $X$ to $[0,\infty)$, and let $k\geq 1$. For every $f\in F$ define a corresponding function $f^{\prime}:X^{k}\rightarrow[0,\infty)$ such that $f^{\prime}(x_{1},\cdots,x_{k})=\min_{1\leq i\leq k}f(x_{i})$, for every $x_{1},\cdots x_{k}\in X$. Let $F^{\prime}=\left\{f^{\prime}\mid f\in F\right\}$ be the union of these functions. Then $\dim(F^{\prime})\leq k\cdot\dim(F).$

We now define the notion of an $\varepsilon$-approximation for a function set $F$ and tie it to an $\varepsilon$-approximation of the corresponding range space. This notion plays a central part in our work. Roughly speaking, an $\varepsilon$-approximation for a function set $F$ is a subset $S$ that approximates the average cost of ranges in the range space corresponding to $F$. To allow invariance by constant multiplication, the quality of the approximation defined below is necessarily related to the parameter $r$ bounding the value of our functions in the range being considered.

Let $F$ be a set of functions from $X$ to $[0,\infty)$, and let $\varepsilon\in(0,1)$. An $\varepsilon$-approximation of $F$ is a set $S\subseteq F$ that satisfies

where $\mathbf{range}(x,r)=\left\{f\in F\mid f(x)\leq r\right\}$.

We now show the connection between $\varepsilon$-approximations for range spaces and for function families.

Let $F$ be a set of functions from $X$ to $[0,\infty)$, and let $\varepsilon\in(0,1)$. Let $S$ be an $\varepsilon$-approximation of the range space of $F$. Then $S$ is an $\varepsilon$-approximation of $F$.

Proof. Let $x\in X$ and $r\geq 0$. For every $b\geq 0$, let $\mathbf{range}(b)=\mathbf{range}(x,b)$. Let $\mathbf{range}(r)=\left\{f_{1},\cdots,f_{n}\right\}$ denote the $n$ functions in $\mathbf{range}(r)$, sorted by their $f(x)$ value. Let $a_{0}=a_{1}=0$, and $m=n/\lceil\varepsilon n\rceil$. For every $i$, $1\leq i\leq m$, let $a_{2i}=a_{2i+1}=f_{i\lceil\varepsilon n\rceil}(x)$. We define the partition $\left\{F_{1},\cdots,F_{2m+1}\right\}$ of $\mathbf{range}(r)$, where $F_{1}=\left\{f\in F\mid f(x)=0\right\}$ and, for $1\leq i\leq m$,

Let $r_{j}=F_{j+1}\cup\cdots\cup F_{2m+1}$ for every $1\leq j\leq 2m$. Summing the last term of (3) over $2\leq i\leq 2m+1$ yields

Hence, summing (3) over $2\leq i\leq 2m+1$ yields

We now bound each term in the right hand side of the last equation. Using (5), we have

Since $S$ is an $\varepsilon$-approximation for $(F,\mathbf{ranges}(F))$, we have

Combining the last inequality in (10) bounds (8), as

Combining (9), (12) and the last inequality bounds the left hand side of (6), as

By plugging Theorem 6.3 in Theorem 6.8 we obtain the following corollary.

Let $F$ be a set of functions from $X$ to $[0,\infty)$, and let $\varepsilon\in(0,1)$. Let $S$ be a sample of

i.i.d items from $F$, where $c$ is a sufficiently large constant. Then, with probability at least $1-\delta$, $S$ is an $\varepsilon$-approximation of $F$.

Appendix 7 ε𝜀\varepsilon-Approximations for High and Infinite Dimensional Spaces

Suppose that we have a range space of a high (maybe infinite) dimension $d$. In this section we show that for several natural families of high dimensional range spaces, a small $\varepsilon$-approximation can be constructed that approximates (not all, but rather) a subset of the ranges in the range space. This weaker type of $\varepsilon$-approximation suffices to solve certain optimization problems in high dimensional space. Towards this end, we will define the notion of a generalized range space, the notion of a corresponding function space, and the notion of $\varepsilon$-approximation in this context. As before, these notions will play a major role in our analysis.

Let $F$ be a set. Let $\mathbf{Ranges}$ be a function that maps every subset $S\subseteq F$ to a set $\mathbf{Ranges}(S)$ of subsets of $F$. The pair $(F,\mathbf{Ranges})$ is a generalized range space if for every two sets $S,G$ such that $S\subseteq G\subseteq F$, we have $\mathbf{Ranges}(S)\subseteq\mathbf{Ranges}(G)$. The dimension of a generalized range space $(F,\mathbf{Ranges})$ is the smallest integer $d$, such that

We now define the generalized dimension of a family of functions:

Let $F$ be a finite set of functions from a set $X$ to $[0,\infty)$. Let $\mathcal{X}$ be a function that maps every subset $S\subseteq F$ to a set of items $\mathcal{X}(S)\subseteq X$. The pair $(F,\mathcal{X})$ is called a function space, if the pair $(F,\mathbf{Ranges})$ is a generalized range space, where $\mathbf{Ranges}$ is defined as follows. For every $x\in X$ and $r\geq 0$, let $\mathbf{range}(x,r)=\left\{f\in F\mid f(x)\leq r\right\}$. For every $S\subseteq F$, let $\mathbf{Ranges}(S)=\left\{\mathbf{range}(x,r)\mid x\in\mathcal{X}(S),r\geq 0\right\}$. The dimension $\dim(F,\mathcal{X})$ of the function space $(F,\mathcal{X})$ is the dimension of the generalized range space $(F,\mathbf{Ranges})$.

We note that it is not hard to verify that for $\mathcal{X}\equiv X$ it holds that $\dim(F,X)=\dim(F,\mathcal{X})$. For a subset $S$ of $F$, let $F_{|\mathcal{X}(S)}:\ \mathcal{X}(S)\rightarrow[0,\infty)$ be the function set which is defined by restricting the functions $F$ to inputs in $\mathcal{X}(S)$. The following theorem is an immediate consequence of the proof in [LLS00] and can be seen as a corollary of Theorem 6.3.

Let $(F,\mathcal{X})$ be a function space of dimension $d$ from $X$ to $[0,\infty)$. Let $\varepsilon,\delta>0$. Let $S$ be a sample of

i.i.d functions from $F$, where $c$ is a sufficiently large constant. Then, with probability at least $1-\delta$, $S$ is an $\varepsilon$-approximation of the range space $(F,\mathbf{Ranges}(S))$.

The following is a simple corollary of Theorem 6.8 that connects between the notion of $\varepsilon$-approximation for range spaces and $\varepsilon$-approximation for function sets in the generalized setting.

Let $(F,\mathcal{X})$ be a function space of dimension $d$. Let $S$ be an $\varepsilon$-approximation of the range space $(F,\mathbf{Ranges}(S))$ for some $\varepsilon>0$. Then $S$ is an $\varepsilon$-approximation of $F_{|\mathcal{X}(S)}$.

Using Corollary 7.4 with Theorem 7.3, we now conclude:

Let $(F,\mathcal{X})$ be a function space of dimension $d$. Let $0<\varepsilon,\delta<1$, and let $S$ be a random sample of at least

i.i.d functions from $F$, where $c$ is a sufficiently large constant. Then, with probability at least $1-\delta$, $S$ is an $\varepsilon$-approximation of $F_{|\mathcal{X}(S)}$.

Appendix 8 From ε𝜀\varepsilon-approximations to (γ,ε)𝛾𝜀(\gamma,\varepsilon)-coresets

In this section we define and analyze the notion of $(\gamma,\varepsilon)$-coresets: a relaxed notion of coresets (that we refer to as robust coresets) that we will use in our study of robust medians discussed in the Introduction. Roughly speaking, we show that $\varepsilon$-approximators for $F$ are also $(\gamma,\varepsilon)$-coresets.

Let $\varepsilon\in(0,1/2)$, and $\gamma\in(0,1]$. Let $F$ and $S$ be two sets of functions from a set $X$ to $[0,\infty)$. For every $x\in X$:

Let $F_{x}$ denote the \big{\lceil}\gamma|F|\big{\rceil} functions $f\in F$ with the smallest value $f(x)$

Let $S_{x}$ denote the \big{\lceil}(1-\varepsilon)\gamma|S|\big{\rceil} functions $f\in S$ with the smallest value $f(x)$

Let $G_{x}\subseteq F_{x}$ denote the \big{\lceil}(1-2\varepsilon)\gamma|F|\big{\rceil} functions $f\in F$ with the smallest value $f(x)$

The set $S$ is $(\gamma,\varepsilon)$-good for $F$ if

The set $S$ is a $(\gamma,\varepsilon)$-coreset of $F$ if for every $\gamma^{\prime}\in[\gamma,1]$, and $\varepsilon^{\prime}\in[\varepsilon,1/2)$, we have that $S$ is $(\gamma^{\prime},\varepsilon^{\prime})$-good for $F$.

Our definition of robust coresets has the flavor of approximating with outliers. Namely, in our definition, we allow a portion of the functions in both $F$ and $S$ to be neglected when considering the quality of $S$. In what follows, we show that an $\varepsilon$-approximation $S$ to a function set $F$ is also a robust coreset.

Let $\varepsilon\in(0,1)$. Let $F$ be a set of functions from $X$ to $[0,\infty)$, and let $S$ be an $(\varepsilon/7)$-approximation of the range space corresponding to $F$. Suppose that $|F|,|S|\geq 5/\varepsilon$. Let $\gamma\in(0,1]$, and for every $x\in X$:

Let $F_{x}$ denote the $\lceil\gamma\cdot|F|\rceil$ functions $f\in F$ with the smallest value $f(x)$

Let $S_{x}$ denote the $\lceil\gamma\cdot|S|\rceil$ functions $f\in S$ with the smallest value $f(x)$

Proof. Let $\varepsilon\in(0,1/7)$, and let $S$ be an $\varepsilon$-approximation to the range space corresponding to $F$. By Theorem 6.8, $S$ is also an $\varepsilon$ approximation to $F$. Let $S_{x}$ denote the $\lceil\gamma\cdot|S|\rceil$ functions $f\in S$ with the smallest value $f(x)$. Let $\gamma$, $S_{x}$, and $F_{x}$ be defined as in the statement of the theorem. We will prove that

This suffices to prove the theorem for $\varepsilon\in(0,1)$.

Indeed, for every $x\in X$ and $r\geq 0$, we define $\mathbf{range}(x,r)=\left\{f\in F\mid f(x)\leq r\right\}$. By our definitions,

Fix $x\in X$, and let $r=\max_{f\in F_{x}\cup S_{x}}f(x)$, $Y=\left\{f\in F\mid f(x)<r\right\}$. We have

Let $c_{1}=5$. Since $|S|,|F|\geq c_{1}/\varepsilon$, we have that

We now bound each of the terms in the right hand side of (18). Using the triangle inequality,

Combining the last two equations in (18) yields

By (15) we bound the first term in the right hand side of (19) by $\varepsilon r$. Using (16) we bound the second term by $\varepsilon$. We thus obtain

We now bound the other terms in the right hand side of (19). By the definition of $r$ and $Y$, we have either $Y\subset F_{x}$, or $Y\cap S\subset S_{x}$ (or both). Hence, $|Y|<|F_{x}|$ or $|Y\cap S|<|S_{x}|$. By (16) we have

Using the last three equations and (17), we obtain

Since both $F_{x}$ and $Y$ contain the functions with the smallest values $f(x)$, we have $|F_{x}\cap Y|=\min\left\{|F_{x}|,|Y|\right\}$. Together with the previous equation, we obtain

Similarly, we bound the rightmost term in (19). As stated above, we have $|Y|<F_{x}$ or $|Y\cap S|<|S_{x}|$. Using (21) with the last two inequations yields

where the last derivation follows from (17). We have $|Y\cap S\cap S_{x}|=\min\left\{|Y\cap S|,|S_{x}||\right\}$. Together with the previous equation, we obtain

Combining (20), (22) and the last equation in (19) proves (14) as follows.

We are now ready to state the connection between $\varepsilon$-approximations and $(\gamma,\varepsilon)$ coresets.

Let $\varepsilon\in(0,1/4)$, and $\gamma\in(0,1]$. Let $F$ be a set of functions from a set $X$ to $[0,\infty)$, and let $S$ be an $(\varepsilon^{2}\gamma/63)$-approximation of the range space corresponding to $F$ (and thus also of the function set $F$), such that $\displaystyle|S|,|F|\geq 5/(\varepsilon^{2}\gamma)$. Then $S$ is a $(\gamma,\varepsilon)$-coreset of $F$.

Proof. Let $\varepsilon\in(0,1/12)$ and let $S$ be an $(\varepsilon^{2}\gamma/7)$-approximation of $F$ such that $|S|\geq 5/(\varepsilon^{2}\gamma)$. We will prove that $S$ is $(\gamma,3\varepsilon)$-good for $F$; see Definition 8.1. By our definitions, $S$ is also an $(\varepsilon^{\prime 2}\gamma^{\prime}/7)$-approximation of $F$, for every $\gamma^{\prime}\geq\gamma$ and $\varepsilon^{\prime}\geq\varepsilon$. Hence, $S$ is $(\gamma^{\prime},3\varepsilon^{\prime})$-good for every $\gamma^{\prime}\geq\gamma$ and $\varepsilon^{\prime}\geq\varepsilon$. This suffices to prove that $S$ is a $(\gamma,\varepsilon)$-coreset by replacing $\varepsilon$ with $\varepsilon/3$.

Indeed, let $G_{x}$ be the \big{\lceil}(1-6\varepsilon)\gamma|F|\big{\rceil} functions $f\in F$ with the smallest value $f(x)$, and $S_{x}$ denote the \big{\lceil}(1-3\varepsilon)\gamma|S|\big{\rceil} functions $f\in S$ with the smallest value $f(x)$. In order to prove that $S$ is $(\gamma,3\varepsilon)$-good for $F$, we need to prove that

Fix $x\in X$, and let $H_{x}$ denote the \big{\lceil}\gamma(1-3\varepsilon)|F|\big{\rceil} functions $f\in F$ with the smallest value $f(x)$. We first bound the right hand side of (23). By Theorem 8.2, we have

Since $1\leq\varepsilon\gamma|F|$, we have

By the last equation and Markov’s inequality,

Let $U=\left\{f\in F\mid f(x)<\max_{f\in S_{x}}f(x)\right\}$. Since $S\cap U\subset S_{x}$, we have

Since $S$ is an $(\varepsilon^{2}\gamma/7)$-approximation of $(F,\mathbf{ranges}(F))$, we have

Since this theorem assumes $\varepsilon\gamma|F|\geq 1$, we have

Combining the last equation and (27) in (24) yields

Multiplying the last equation by $|S|/|S_{x}|$ bounds the right hand side of (23) as follows.

We now bound the left hand side of (23) in a similar way. Let $T_{x}$ denote the \big{\lceil}\gamma(1-6\varepsilon)|S|\big{\rceil} functions $f\in S$ with the smallest value $f(x)$. Since $1\leq\varepsilon\gamma|S|$, we have

By the last equation and Markov’s inequality,

Let $Y=\left\{f\in F\mid f(x)<\max_{f\in G_{x}}f(x)\right\}$. Since $Y\subset G_{x}$, we have $|Y|\leq(1-6\varepsilon)\gamma|F|$. Since $S$ is an $(\varepsilon^{2}\gamma/7)$-approximation of $F$, substituting $r=\max_{f\in Y}f(x)$ in Definition 6.2 yields

That is, $|S\cap Y|<(1-2\varepsilon)|S_{x}|$. Hence,

Since $\varepsilon\gamma|S|\geq 1$, we have

Combining the last three equations yields

Multiplying the last equation by $(1-3\varepsilon)|F|/|G_{x}|$ yields

The last equation and (29) proves (23) as desired. $\sqcap$$\sqcup$

Using Theorems 6.3 and 8.3, we get the following corollary.

Let $\varepsilon\in(0,1/4)$, and $\gamma\in(0,1]$. Let $F$ be a set of functions from a set $X$ to $[0,\infty)$. Let $S$ be a sample of at least

i.i.d functions from $F$, where $c$ is a sufficiently large constant. Suppose $|F|\geq|S|$. Then, with probability at least $1-\delta$, $S$ is a $(\gamma,\varepsilon)$-coreset of $F$.

In this section we discuss the notion of robust medians stated in the Introduction and tie it to the notion of $(\gamma,\varepsilon)$-coresets discussed in the last section. Roughly speaking, a robust median is a subset of points $Y$ from $X$ that acts as a bi-criteria clustering of $F$ when considering outliers. More specifically, our robust medians will be parametrized by four parameters: $\gamma,\varepsilon,\alpha$ and $\beta$. The parameter $\gamma$ (or to be precise $1-\gamma$) will specify the fraction of outliers considered. The parameter $\varepsilon$ is a slackness parameter crucial to the proof of our theorems to come. The parameter $\alpha$ is the approximation ratio between the obtained clustering by $Y$ and the optimal $1$-median clustering. Finally, the parameter $\beta$ will denote the size of $Y$. In several cases, we will just take $\beta$ to be $1$, and will remove the parameter $\beta$ from our notation.

Let $F$ be a set of $n$ functions from a set $X$ to $[0,\infty)$. Let $0<\varepsilon,\gamma<1$, and $\alpha>0$. For every $x\in X$, let $F_{x}$ denote the \big{\lceil}\gamma n\big{\rceil} functions $f\in F$ with the smallest value $f(x)$. Let $Y\subseteq X$, and let $G$ be the set of the $\lceil(1-\varepsilon)\gamma n\rceil$ functions $f\in F$ with smallest value $f(Y)=\min_{y\in Y}f(y)$. The set $Y$ is called a $(\gamma,\varepsilon,\alpha,\beta)$-median of $F$, if $|Y|=\beta$ and

For simplicity of notation, a $(\gamma,\varepsilon,\alpha)$-median is a shorthand for a $(\gamma,\varepsilon,\alpha,1)$-median.

Let $F$ be a set of functions from $X$ to $[0,\infty)$. In the previous section we proved that a small $(\gamma,\varepsilon)$-coreset of $F$ can be constructed using algorithms that compute $\varepsilon$-approximation of $F$. In particular, a random sample $S$ of $F$ is such a $(\gamma,\varepsilon)$-coreset. In this section we prove that the $(\gamma,\varepsilon,\alpha)$-median of $S$ is also an $(O(\gamma),O(\varepsilon),\alpha)$-median of $F$. In other words, if we have a (possibly inefficient) algorithm for computing the $(\gamma,\varepsilon)$-median of a small coreset $S$, then we can compute a similar median for the original set $F$ in time linear in $n$.

Let $F$ be a set of functions from a set $X$ to $[0,\infty)$. Let $\varepsilon\in(0,1/10)$, $\gamma\in(0,1]$. Suppose that $S$ is a $(\gamma,\varepsilon)$-coreset of $F$, and that $|F|\geq|S|\geq 2/(\varepsilon\gamma)$. Let $\alpha>0$. Then a \big{(}(1-\varepsilon)\gamma,\varepsilon,\alpha)-median of $S$ is also a $(\gamma,4\varepsilon,\alpha)$-median of $F$.

Proof. For every $x\in X$, let $F_{x}$ denote the \big{\lceil}\gamma|F|\big{\rceil} functions $f\in F$ with the smallest value $f(x)$.

Let $x^{\prime}$ be a \big{(}(1-\varepsilon)\gamma,\varepsilon,\alpha)-median for $S$

Let $G$ denote the \big{\lceil}(1-4\varepsilon)\gamma|F|\big{\rceil} functions $f\in F$ with the smallest value $f(x^{\prime})$

Let $S^{\prime}$ denote the \big{\lceil}(1-3\varepsilon)\gamma|S|\big{\rceil} functions $f\in S$ with the smallest value $f(x^{\prime})$

Let $S^{*}$ denote the \big{\lceil}(1-\varepsilon)\gamma|S|\big{\rceil} functions $f\in S$ with the smallest value $f(x^{*})$

Since $1\leq 1$, we have $|S^{*}|=\lceil(1-\varepsilon)\gamma|S|\rceil\geq\lceil(1-\varepsilon)\gamma|S|\rceil$. Using this, (31) and the fact that $x^{\prime}$ is a \big{(}(1-\varepsilon)\gamma,\varepsilon,\alpha\big{)}-median of $S$, we have

Since $S$ is a $(\gamma,4\varepsilon)$-coreset of $F$, it is $(\gamma,\varepsilon)$-good for $F$; see Definition 8.1. By this, and since |G|\leq\big{\lceil}(1-2\varepsilon)\gamma|F|\big{\rceil}, and $|S^{\prime}|\geq(1-\varepsilon)\gamma|S|$, we obtain

Since $S$ is a $(\gamma,\varepsilon)$-coreset of $F$, we have that

By (32) and the last two equations, we obtain

By the assumption of the theorem, we have $|S|\geq 2/(\varepsilon\gamma)$, so $1\leq\varepsilon\gamma|S|/2$. Hence,

Similarly, since $1\leq 4\varepsilon\gamma|F|/2$,