PaperlayerView exact revision on arXiv

Source-linked AI summary

A Unified Framework for Approximating and Clustering Data

Dan Feldman, Michael Langberg

arXiv:1106.1379v4cs.LG

TL;DR

The paper addresses how to construct compact representations and approximations for clustering and shape-fitting problems when existing coreset methods are problem-specific or impossible at sublinear size. It introduces a unified reduction from coresets and bicriteria approximation to ε-approximations governed by VC dimension, and reports improved coreset, approximation, running-time, generalized-distance, and deterministic results. Its scope includes settings where strong coresets do not exist or optimization is computationally hard.

  • Problem

    Existing coreset constructions are usually tailored to specific problems, while some clustering problems have no coresets of size o(n) and some projective-clustering optimizations are hard to approximate.

  • Method

    The framework reduces clustering and coreset tasks to ε-approximations by analyzing generalized range spaces and VC dimension, then uses robust medians, bicriteria solutions, projections, and weighted samples.

  • Results

    The framework yields bicriteria approximations and structured coresets across function families, including a k-median strong coreset of size t = O(dk/ε^2) and generalized results for powers and deterministic constructions.

  • Takeaways & Limitations

    The reduction lets the framework reuse VC-dimension and ε-approximation results to obtain efficient, sometimes deterministic, constructions for diverse clustering and shape-fitting problems.

  • Takeaways & Limitations

    For general projective clustering with j ≥ 2 and arbitrary k, strong coresets of size o(n) do not exist, and for k > log n polynomial-time approximation is impossible unless P=NP.

Abstract

from arXiv · show

Given a set $F$ of $n$ positive functions over a ground set $X$, we consider the problem of computing $x^*$ that minimizes the expression $\sum_{f\in F}f(x)$, over $x\in X$. A typical application is \emph{shape fitting}, where we wish to approximate a set $P$ of $n$ elements (say, points) by a shape $x$ from a (possibly infinite) family $X$ of shapes. Here, each point $p\in P$ corresponds to a function $f$ such that $f(x)$ is the distance from $p$ to $x$, and we seek a shape $x$ that minimizes the sum of distances from each point in $P$. In the $k$-clustering variant, each $x\in X$ is a tuple of $k$ shapes, and $f(x)$ is the distance from $p$ to its closest shape in $x$. Our main result is a unified framework for constructing {\em coresets} and {\em approximate clustering} for such general sets of functions. To achieve our results, we forge a link between the classic and well defined notion of $\varepsilon$-approximations from the theory of PAC Learning and VC dimension, to the relatively new (and not so consistent) paradigm of coresets, which are some kind of "compressed representation" of the input set $F$. Using traditional techniques, a coreset usually implies an LTAS (linear time approximation scheme) for the corresponding optimization problem, which can be computed in parallel, via one pass over the data, and using only polylogarithmic space (i.e, in the streaming model). We show how to generalize the results of our framework for squared distances (as in $k$-mean), distances to the $q$th power, and deterministic constructions.

1 Introduction

The paper develops a unified framework for coresets and approximate clustering over general function sets, linking these constructions to ε-approximations and VC dimension. It addresses the need for reusable methods across clustering and shape-fitting problems with diverse computational properties.

  • 1 Introduction: Coresets are small representative subsets that approximately preserve the objective for every candidate query within a multiplicative factor of 1 ± ε.This formalizes compressed representations for clustering and shape fitting.
  • 1 Introduction: Many existing coreset constructions are tailored to individual problems, while some clustering problems provably admit no coresets of size o(n).Examples include approximation by planes, lines, and projective clustering problems.
  • 1 Introduction: The framework represents each data element as a function and evaluates a center or tuple of centers by summing the functions’ costs.For k-clustering, each function value is the distance from its data element to the closest center.
  • 1 Introduction: Its central reduction connects coreset construction to ε-approximations from VC-dimension theory, making the framework depend on the input family’s combinatorial complexity.The connection enables use of existing ε-approximation results, including deterministic constructions in some settings.
  • 1 Introduction: The paper organizes the framework’s contributions, proof techniques, and algorithms for constructing coresets and bicriteria approximations.The development proceeds from concrete results to conceptual techniques and algorithmic details.

2 Concrete Contributions

The framework yields strong, weak, and streaming coresets, bicriteria approximations, and improved construction or running times across clustering and subspace problems. Results include dimension-independent metric-space bounds, low-dimensional B-coresets, extensions to powered distances, and deterministic constructions.

  • General framework: The framework produces strong, weak, and streaming coresets, often with improved construction times and approximation algorithms across several clustering problems.For projective clustering, B-coresets combine a small set S with projections onto a bicriteria solution.
  • k-Median: O(dk/ε2) points suffice for a strong coreset for k-median, improving several prior bounds.The construction time is O(ndjk + t log n).
  • k-Median: O(k log(n)/ε2) points suffice for strong k-median coresets in general metric spaces, improving the O(k2 log(n)/ε2) bound of Ke Chen.The result replaces the Euclidean dimension d by log n.
  • k-Median: Weak k-median coresets have size O(k log(1/ε)/ε3) and yield a (1 + ε)-approximation in time O(ndk + 2poly(1/ε,k)).For integer z > 1, the corresponding time and space terms replace ε with ε2z.
  • Subspace approximation: For subspace approximation, strong coresets have size O(dj/ε2), while weak and streaming coresets have sizes O(j2 log(1/ε)/ε3) and O(j2 log(1/ε) log4 n/ε3).The strong bound is polynomial in d; streaming coresets use O(d · t) space.

3 Novelties in proof techniques

The framework introduces a reduction to ε-approximations, functional coreset representations, and generalized range spaces to unify and broaden coreset analysis. These ideas support improved sampling, deterministic and streaming constructions, and coresets that need not be subsets of the original data.

  • Reduction to ε-approximation: The framework reduces coreset analysis to ε-approximation theory, providing common analyses, smaller samples, and access to deterministic, convex-shape, and streaming constructions.The reduction uses VC-dimension and ε-approximation results from computational geometry and machine learning.
  • Functional representation of data elements and coresets: The abstract function representation treats data elements and coresets as functions whose values encode clustering costs for candidate centers.Some coresets are subsets of data elements, while others contain related functions with modified behavior.
  • Functional representation of data elements and coresets: Coresets may truncate function values or assign negative weights, yet a PTAS can be computed from them without the original data.These representations extend earlier constructions while preserving their algorithmic role.
  • Functional representation of data elements and coresets: Allowing nonstandard function-based representations is central to obtaining improved coreset results, despite differing from the traditional subset-of-data conception.The framework still seeks standard coresets in some cases, but prioritizes efficient approximation of clustering objectives.
  • Generalized range spaces: The framework unifies weak coresets with ε-approximations through generalized range spaces and a corresponding generalized dimension.Standard range spaces capture strong-coreset behavior, while the generalized theory addresses weak coresets.

4 Framework overview

The framework reduces coreset and bicriteria constructions to ε-approximations, then applies this reduction through robust medians, bicriteria solutions, and problem-specific coreset constructions.

  • Framework reduction: Theorem 4.1 converts a weighted sample of normalized function copies into an ε-coreset whose costs approximate those of the full function family.The construction samples from the expanded family and rescales sampled functions.
  • Framework reduction: ε-approximations of generalized range spaces provide the framework’s starting point for constructing coresets and bicriteria approximations.The reduction proceeds through generalized VC-dimension, robust medians, and bicriteria solutions.
  • Bicriteria approximation: An ε-approximation yields a robust median with adjusted parameters, which supports bicriteria approximation through the BICRITERIA algorithm.The robust-median reduction preserves clustering quality while changing the outlier and slackness parameters.
  • Bicriteria approximation: |B| ≤ β log^2 n and cost(B) ≤ (1 + ε)α times the optimum for BICRITERIA’s output.The guarantee applies to a function family of size n and uses BICRITERIA(F, ε/100, α, β).
  • Coreset constructions: The k-median construction returns a weighted ε-coreset of size t with running time O(ndk + log^2(1/δ) log^2 n + k^2 + t log n).Its analysis uses a random sample that is an ε-approximation to the k-median function family and assigns weights using a bicriteria solution.
  • Coreset constructions: For more complex settings, METRIC-B-CORESET projects points onto bicriteria lines, while B-CORESET combines projected or threshold functions with a weighted ε-approximation.The resulting structure can enable a second compression step when the projected data has specialized low-dimensional structure.

5 Road map

The appendix maps the paper’s framework from ε-approximations and generalized range spaces to robust coresets, bicriteria approximations, and concrete clustering applications. It also covers k-line median and planned applications to subspace approximation, with some material still incomplete.

  • Framework foundations: The appendix defines ε-approximations for function families and generalized range spaces, then connects ε-approximations to robust coresets.It also links robust coresets to robust medians and bi-criteria approximation.
  • Framework foundations: Centroid sets are introduced before the framework is used to derive bicriteria approximations for several clustering problems.Those bicriteria results then support constructions of B-coresets.
  • Concrete applications: The appendix specializes the framework to metric-space functions, metric k-median, and k-median in R^d.Many concrete results from Section 2 receive detailed proofs in these sections.
  • Concrete applications: Section 17 studies the k-line median problem and proves the results stated earlier in Section 2.
  • Concrete applications: Section 18 applies the framework to low-dimensional B-coresets and subspace-approximation coresets, but parts of that section remain unfinished.The authors state that the incomplete material will be uploaded in a future arXiv version.

6 ε-Approximations

This section defines ε-approximations for function families through their associated range spaces and proves that range-space approximations also approximate function costs. It extends the framework to k-tuples of inputs and random sampling guarantees.

  • Definitions: A range space for functions contains ranges range(F, x, r) = {f ∈ F | f(x) ≤ r} over all x ∈ X and r ≥ 0.
  • Core connection: For k inputs, replacing each function by its minimum value over the k inputs increases dimension by at most a factor of k.Lemma 6.5 states dim(F′) ≤ k · dim(F).
  • Definitions: An ε-approximation of a function set S approximates the average cost of ranges associated with F, with quality tied to ε and a value bound r.
  • Core connection: An ε-approximation of F’s range space is also an ε-approximation of the function family F.Theorem 6.8 provides the central reduction from range-space approximation to function-cost approximation.
  • Sampling guarantee: A sufficiently large i.i.d. sample from F is, with probability at least 1 − δ, an ε-approximation of F.The result follows by combining the standard range-space sampling theorem with Theorem 6.8.

7 ε-Approximations for High and Infinite Dimensional Spaces

For high- or infinite-dimensional range spaces, the paper restricts attention to ranges induced by sample-dependent subsets of inputs. It introduces generalized range spaces and proves sampling guarantees for the resulting function spaces.

  • Motivation: High-dimensional range spaces may admit small ε-approximations for a relevant subset of ranges rather than for every range.The paper presents this weaker approximation as sufficient for certain optimization problems.
  • Generalized range spaces: A generalized range space assigns each subset S ⊆ F a family Ranges(S) that grows monotonically when S expands.
  • Generalized range spaces: A function space pairs F with a subset-dependent input family X(S), inducing ranges from x ∈ X(S) and r ≥ 0.Its dimension is defined through the resulting generalized range space.
  • Function-family connection: An ε-approximation of the range space (F, Ranges(S)) is also an ε-approximation of the restricted function set F|X(S).This is the generalized analogue of the ordinary range-space-to-function-family connection.
  • Sampling guarantee: A sufficiently large i.i.d. sample from a dimension-d function space is, with probability at least 1 − δ, an ε-approximation for the sample-induced restricted family.The guarantee is obtained through Theorem 7.3 and Corollary 7.4.

8 From ε-approximations to (γ, ε)-coresets

The paper introduces robust (γ, ε)-coresets, which tolerate ignoring portions of both the full function set and the coreset, and proves that sufficiently accurate ε-approximations yield such coresets. Random samples therefore provide robust coresets with high probability.

  • Definition and motivation: A robust (γ, ε)-coreset permits a portion of the functions in both F and S to be neglected when evaluating approximation quality.The paper uses this relaxed notion in its study of robust medians.
  • Definition and motivation: For each x, Fx and Sx are the ⌈γ · |F|⌉ and ⌈γ · |S|⌉ functions with the smallest values f(x).These low-cost subsets are the objects compared in the robust coreset analysis.
  • Proof strategy: An ε-approximation of F’s range space is also an ε-approximation of F, enabling the robust-coreset proof to use range-space sampling.
  • Proof strategy: The analysis bounds the robust approximation error by 7ε · max f∈Fx∪Sx f(x).The bound is established by comparing costs of the lowest-valued subsets and controlling the threshold r.
  • Main guarantee: If ε ∈ (0, 1/4), γ ∈ (0, 1], and S is an (ε^2γ/63)-approximation with |S|, |F| ≥ 5/(ε^2γ), then S is a (γ, ε)-coreset.Theorem 8.3 gives the deterministic implication from an accurate range-space approximation to a robust coreset.
  • Main guarantee: A sufficiently large i.i.d. sample is, with probability at least 1 − δ, a (γ, ε)-coreset of F.This follows by combining the standard sampling theorem with Theorem 8.3, assuming |F| ≥ |S|.

9 Robust medians: From (γ, ε)-coresets to (γ, ε, α, β)-medians

The section connects robust medians on small coresets to robust medians on the full function set, preserving quality with controlled parameter loss.

  • From coresets to robust medians: A (1 −ε)γ, ε, α)-median of a (γ, ε)-coreset S is a (γ, 4ε, α)-median of F.This holds when |F| ≥ |S| ≥ 2/(εγ).
  • Multiple-center medians: For β > 1, the transfer requires a coreset for the enhanced function family hf(Y) = miny∈Y f(y).Under the theorem’s assumptions, the resulting median has approximation factor α(1 + 10ε).
  • Random-sample transfer: Random samples can serve as coresets, so medians computed on sufficiently large samples transfer to F with probability at least 1 −δ.The transfer applies under the stated sample-size and parameter conditions.
  • Algorithmic reduction: A robust median for a sample S can be computed by enumerating small subsets and selecting the candidate with minimum retained cost.The resulting reduction runs in SlowMedian + O(|S|) time with probability at least 1 −δ.

10 Centroid Sets

Centroid sets collect candidate medians for every subset, enabling robust median constructions to extend across clustering tuples.

  • Definition: A (γ, ε, α, β)-centroid set contains a suitable median for every subset S ⊆ F.The shorthand (γ, ε, α)-centroid set means β = 1.
  • Parameter relaxation: A centroid set with zero error and approximation α remains a centroid set for relaxed γ′ and ε′ parameters.This follows from the monotonicity of median guarantees.
  • Lifting to k-clustering: For k-clustering, partitioning tuples of centroid-set elements yields a centroid set of size |cent|^k for the lifted function family.The construction preserves the (1, 0, α, β) guarantee.
  • Lifted medians: If cent is a (1, 0, α)-centroid set for F, then some element of cent^k is a (γ, ε, α)-median for the lifted family Fk.This supplies candidate tuples for arbitrary γ and ε.

11 From (γ, ε, α, β)-medians to bicriteria approximations

The framework converts robust medians into bicriteria approximations by iteratively shrinking the function set and combining candidate centers.

  • Bicriteria construction: BICRITERIA returns at most log2 n candidate sets whose combined cost is within a multiplicative factor of the optimum.The basic construction produces X′ with |X′| ≤ log2 n and cost(F, X′) ≤ (1+ε)·minx∈X cost(F, x).
  • Required subroutines: A robust median algorithm and an ε-approximation algorithm suffice to implement BICRITERIA.The running time is O(1) · (nt + log2 n · SlowMedian + SlowEpsApprox).
  • Guarantee: Theorem 11.2 yields a ((1 + ε)α, β log n)-approximation with at most β log2 n returned centers.The guarantee is obtained by unioning the sets produced during the iterations.
  • Randomized implementation: The randomized implementation succeeds with probability at least 1 −δ while maintaining the stated near-linear dependence on n.The implementation’s total running time is Bicriteria.

12 Applications: Bicriteria for Projective Clustering

The framework applies to projective clustering by constructing finite centroid sets and sampling-based medians for flats and tuples of flats.

  • Problem formulation: For projective clustering, points induce distance functions over tuples containing at most k flats of dimension at most j −1.This embeds clustering objectives into the paper’s general function-family framework.
  • Finite candidate sets: For a sample S, the span-based candidate family X(S) has size O(|S|^j) and can be computed in O(dj^2)·|S|^j time.Its k-fold lift has function-space dimension O(jk) and forms a (1, 0, 2j)-centroid set.
  • Small j and k: A (2j+1, sO(j)k−1 log n)-bicriteria approximation can be computed with probability at least 1 −δ in time O(ndsO(j)).This is the small-j, small-k projective-clustering guarantee.
  • Near-optimal approximation: For small j and k, the framework also gives a (1 + ε, log n)-bicriteria approximation with the stated sampling-dependent running time.The construction uses a (1 + ε)-median subroutine on sampled functions.

13 From bicriteria to B-coresets

B-CORESET combines a bicriteria-derived function set with a weighted random sample, then analyzes their combined approximation quality under explicit assumptions.

  • Construction: B-CORESET constructs a coreset from a projection-like function set and a weighted random sample of the original functions.For general function families, the projection is supplied as an additional function set F′ because no natural projection may exist.
  • Analysis: The analysis partitions functions according to whether f′(x) is below the threshold s_f(x), treating the two groups through separate coreset components.The set M(x) contains functions satisfying f′(x) ≤ s_f(x); the proof separately controls contributions from M(x) and its complement.
  • Guarantees: Theorem 13.1 assumes 0 < ε < 1/4 and f(x) ≤ 2s_f(x) for functions retained by the threshold, and guarantees the resulting B-CORESET quality.The supplied theorem statement gives the assumptions and identifies C as B-CORESET(F, F′, s, m, ε).
  • Analysis: The coreset cost is decomposed as cost(C, x) = cost(T, x) + cost(U, x), enabling separate approximation bounds to be combined.The proof then compares the resulting expression with the original cost using the triangle inequality.
  • Guarantees: Corollaries specialize the general theorem to threshold choices and weighted constructions, including settings where weights may be negative.These corollaries are presented as consequences of Theorem 13.1 under additional conditions.

14 From B-Coresets to Metric B-Coresets

The metric specialization projects points onto a bicriteria solution and applies the B-CORESET framework to distance-power functions, yielding probabilistic relative-error guarantees.

  • Construction: METRIC-B-CORESET uses a weighted random sample S and a second subset derived by projecting P onto the bicriteria solution B.The metric analysis defines functions from distances to points and their projections, with weights determined by the bicriteria structure.
  • Distance-power functions: The power-distance comparison bounds |f(x) − f′(x)| by εf(x) when the projected distance is sufficiently large relative to the bicriteria distance.The proof uses the condition f′(x) ≥ f(B)/ε^z and assumes ε is sufficiently small compared with z.
  • Guarantee: With probability at least 1 − δ, the metric coreset satisfies |cost(F, x) − cost(C, x)| ≤ εcost(F, x) + εcost(F, B) for every x.This is the stated uniform guarantee for the constructed B-CORESET in the metric setting.
  • Guarantee: The framework preserves the original metric objective through weighted sampled functions, including the identity cost(P, x) = Σ_p∈P dist^z(p, x).The construction relates sampled weighted terms to the full point-set cost before applying the B-CORESET guarantee.
  • Distance-power functions: For distance-power objectives, the projected functions use dist^z(proj(p, B), x), while the original functions use dist^z(p, x).The construction compares these functions through a lemma relating powers of two nonnegative distance functions.

15 k-Median in a Metric Space

For metric k-median, the framework yields constant-factor approximation and strong coreset constructions with nonnegative weights, near-linear dependence on n, and explicit probability guarantees.

  • Constant-factor approximation: A k-tuple x ∈ P^k can be computed in O(ndk + k^2 + log^2(1/δ) log^2 n) time with probability at least 1 − δ.The resulting solution has cost(P, x) ≤ O(1)·cost(P, x*).
  • Constant-factor approximation: The approximation uses a bicriteria set B, projects points onto B, and optimizes over the resulting weighted projected points.The metric triangle inequality bounds both cost(P, x) and cost(proj(P, B), x*) through the bicriteria cost.
  • Strong coresets: Strong metric k-median coresets return D ⊆ P with |D| = t and a nonnegative weight function, with probability at least 1 − δ.The theorem states that the coreset can be computed with running time O(nk + log^2(1/δ) log^2 n + k^2).
  • Strong coresets: The sample complexity depends on the dimensionality of L(P), which is O(k log n) for metric k-median.The construction combines this dimensionality bound with nonuniform sampling and the k-MEDIAN-CORESET algorithm.
  • Distance powers: The framework also states strong coreset results for distance powers, with positive weights requiring an additional k log k term in the size bound.The paper notes that allowing negative weights can reduce the resulting coreset size.

16 k-Median in Rd

In Euclidean space, the framework bounds the relevant function dimensions using geometric arrangements and derives strong k-median coresets with either signed or positive weights.

  • Function dimension: For functions based on distance differences to a j-flat and its associated point, the dimension is O(d(j + 1)).This bound follows from representing the relevant ranges through inner products and bounding their arrangement complexity.
  • Function dimension: The dimension of thresholded distance-power functions for k tuples of j-flats in R^d is O(djk).The proof reduces the k-flat case to k = 1 and bounds the induced range complexity using geometric representations.
  • Strong coresets: Strong k-median coresets in R^d can use signed weights or positive weights, with construction time O(ndk + log^2(1/δ) log^2 n + |D|).The theorem presents two size alternatives corresponding to the signed- and positive-weight cases.
  • Strong coresets: The signed-weight construction uses dim(L(P)) = O(kd), replacing the metric-space bound O(k log n).The paper attributes this improvement to the Euclidean dimensionality analysis.
  • Strong coresets: For positive weights, the sampling requirement includes t ≥ k min{log k, d}.This condition is stated as arising from the positive-weight requirement and the dimensionality bound.

17 k-Line Median

The section develops coreset-based approximation results for k-line and related projective-clustering problems, using randomized constructions and VC-dimension bounds. It gives approximation guarantees, construction times, and extensions to broader clustering settings.

  • Analysis: The projective-clustering analysis bounds the relevant function-family dimension by O(kj2 log(1/ε)/ε).This bound is used with random sampling and ε-approximations in the coreset construction.
  • Approximation guarantee: With probability at least 1 − δ, the resulting approximation satisfies cost(P, y*) ≤ (1 + ε) min_x*∈X(j,k) cost(P, x*) + εcost(P, B).The guarantee is stated relative to a reference set B and applies to the output of METRIC-B-CORESET under the theorem’s conditions.
Loading 1106.1379v4…