PaperlayerView exact revision on arXiv

Source-linked AI summary

A New Coreset Framework for Clustering

Vincent Cohen-Addad, David Saulpic, Chris Schwiegelshohn

arXiv:2104.06133v4cs.DS

TL;DR

Coresets offer compact representations for clustering data, but prior analyses left open whether near-linear-in-k bounds were possible for several structured metrics. This paper develops an importance-sampling framework based on approximate centroid sets and improves coreset bounds across multiple metric families.

  • Problem

    It was open whether coresets near-linear in k could be achieved for doubling, minor-free, and bounded-treewidth metrics, where prior bounds left a gap to lower bounds.

    Source: §1 · p. 3

  • Method

    The paper analyzes importance sampling through a framework applicable to metrics admitting a bounded-size approximate centroid set.

    Source: §1 · p. 3, §1.1 · p. 3

  • Results

    The framework improves known coreset bounds across Euclidean, doubling, minor-free, bounded-treewidth, and general metric settings.

    Source: §1 · p. 3

  • Takeaways & Limitations

    The stated framework yields near-linear-in-k coreset sizes for several metric families, including doubling, minor-free, and bounded-treewidth metrics.

    Source: §1 · p. 3

    The theorem assumes a constant-factor clustering approximation and an A-approximate centroid set.

    Source: §1.1 · p. 3

Abstract

from arXiv · show

Given a metric space, the $(k,z)$-clustering problem consists of finding $k$ centers such that the sum of the of distances raised to the power $z$ of every point to its closest center is minimized. This encapsulates the famous $k$-median ($z=1$) and $k$-means ($z=2$) clustering problems. Designing small-space sketches of the data that approximately preserves the cost of the solutions, also known as \emph{coresets}, has been an important research direction over the last 15 years. In this paper, we present a new, simple coreset framework that simultaneously improves upon the best known bounds for a large variety of settings, ranging from Euclidean space, doubling metric, minor-free metric, and the general metric cases.

1 Introduction

Coresets compress clustering data while approximately preserving solution costs, addressing the memory and repeated-pass demands of large datasets. The paper introduces an importance-sampling framework that improves coreset bounds across several metric settings.

1 Introduction

  • Coresets are weighted point sets used in place of the full dataset, helping avoid multiple passes and reduce memory use on very large inputs.The paper frames this as a practical motivation for compact representations.Source: §1 · p. 2
  • The motivating question is whether coresets near-linear in k can be designed for doubling, minor-free, and bounded-treewidth metrics, or whether existing roadblocks are inherent.The paper points to prior bounds with at least Ω(k2) dependence in k as leaving a gap to Ω(k) lower bounds.Source: §1 · p. 3

1.1 Our Results

  • The framework improves coreset bounds across Euclidean, doubling, minor-free, bounded-treewidth, and finite metric spaces, including near-linear dependence on k in several settings.It applies when the metric admits a bounded-size approximate centroid set.Source: §1 · p. 3
  • The theorem constructs a coreset in O(n) time with probability at least 1 − π, assuming a constant-factor approximation and an A-approximate centroid set.Its stated size depends on z, ε, k, |C|, and π.Source: §1.1 · p. 3
  • O(Γ·k(d + log k)) improves on O(k3dε−2) for metrics with doubling dimension d.The cited prior bound is attributed to Huang et al..Source: §1.1 · p. 4
  • O(Γ·k(t + log k)) improves on the O(k2t/ε2) coreset bound for graphs with treewidth t.The comparison is with Baker et al..Source: §1.1 · p. 4
  • O(kε−2z·min(d, ε−2 log k)) improves on Huang and Vishnoi’s O(k log k·ε−4z·min(d, ε−2 log k)) bound for ℓp distance, p ∈ [1, 2).The comparison is for Rd and is attributed to.Source: §1.1 · p. 4

1.2 Overview of Our Techniques

  • The approach first structures the instance around k centers with roughly equal cluster costs and comparable distances to those centers, then samples across the clusters.This is the overview’s two-stage description of the technique.Source: §1.2 · p. 4

A Union-bound to Preserve all Solutions

The framework preserves costs for all solutions by using an approximate centroid set to make a union bound over a finite candidate family sufficient. It constructs such sets differently across metric families and applies them to interesting points, then extends preservation to arbitrary solutions.

A Union-bound to Preserve all Solutions

  • A union bound over C^k preserves interesting-point costs for every candidate solution, and an approximate centroid set transfers that guarantee to arbitrary solutions.For each solution S, the set supplies a k-tuple ˜S whose costs on interesting points differ only by a small error.Source: A Union-bound to Preserve all Solutions · p. 8
  • For doubling metrics, nets around input points provide candidate centers close to the centers serving interesting points.The construction uses an εcost(p, A)-net within a specified radius around each point p.Source: A Union-bound to Preserve all Solutions · p. 8
  • For treewidth-t graphs, small separators let the centroid set represent centers by approximately matching their distances to separator-boundary vertices.When interesting points lie in a region with a constant-size vertex boundary, matching a center's distance tuple to that boundary preserves their costs.Source: A Union-bound to Preserve all Solutions · p. 8
  • For minor-excluded graphs, the construction guesses distances from input points to centers because path separators do not support the treewidth argument for preventing centers from getting too close.The authors say this approach is broader than the alternative but produces larger centroid sets.Source: A Union-bound to Preserve all Solutions · pp. 8–9

1.3 Roadmap

  • The paper’s roadmap places the algorithm and structured-instance construction before the reduction and metric-specific centroid-set constructions.It also identifies a Euclidean dimension-reduction technique and an O(k^2ε^-2) construction in Appendix B.Source: §1.3 · p. 9

2 Related Work

Prior coreset work moved from Euclidean geometric decompositions toward importance sampling, whose bounds often rely on VC-dimension or related complexity measures. Results for doubling and graph metrics use additional structural arguments, while the literature also covers streaming and constrained clustering.

Coresets via Importance Sampling

  • Early Euclidean geometric decompositions typically produced coresets of size at least k·ε^-d, while Chen’s importance-sampling approach generalized to non-Euclidean metrics and gave O(k^2ε^-2 log^2 n) for general n-point metrics.The cited early Euclidean works are, and Chen’s result is described as the first coreset for general n-point metrics.Source: §2 · p. 9

Coresets via Bounded VC-Dimension

  • For Euclidean k-means and k-median, VC-dimension bounds lead to an O(kd log k) complexity bound, recently shown tight, while replacing d with log k yields a natural O(k log^2 k) barrier for known techniques.The ε-approximation result cited for bounded VC-dimension is due to.Source: §2 · p. 10

VC-Dimension and Doubling Dimension

  • VC-dimension and doubling dimension are incomparable in general, and bounded doubling dimension does not imply bounded VC-dimension [LL06, HJLW18].A distorted metric and bounded shattering dimension nevertheless yielded the first bounded-doubling coresets independent of n; their bound was ˜O(k^3dε^-2).Source: §2 · p. 10
  • Bounded-treewidth coresets use shattering dimension O(t), while excluded-minor work iterates a coreset construction to remove dependence on |X|.The iterative construction is also used by the paper for bounded-treewidth and excluded-minor settings.Source: §2 · p. 10

Further Related Work

  • Related coreset research also addresses streaming and distributed models, capacity constraints, generalized objectives, and problems including determinant maximization, diversity maximization, logistic regression, dependency networks, and low-rank approximation [FL11, FMS07, BEL13, BFLR19, BFL+17, FS05, FGS+13, CL19, HJV19, SSS19, BLL18, BJKW19, IMGR20, CPP18, IMMM14, HCB16, MSSW18, MMK18, MJF19].The paper distinguishes these topics from work targeting unconstrained k-median and k-means coresets.Source: §2 · pp. 10–11

3 Preliminaries

The preliminaries define the clustering objective and coreset guarantee, reduce weighted inputs to an unweighted instance, and introduce a ring-and-group partition used to structure the construction.

3.1 Problem Definitions

  • The (k, z)-clustering objective chooses k centers to minimize the total weighted cost, and an ε-coreset is a weighted subset intended to preserve that objective across center sets.The section also invokes a triangle-inequality variant for powered distances.Source: §3.1 · p. 11

3.2 From Weighted to Unweighted Inputs

  • For weighted inputs, the reduction makes weights integral so each point can be treated as multiple copies; it applies Theorem 1 to the resulting input and scales coreset-point weights by εwmin/2.Source: §3.2 · p. 12

3.3 Partitioning an Instance into Groups: Definitions

  • The partition groups points into rings and outer groups so points in one group can share an additive-error allowance, enabling the union of small group coresets.The supplied facts bound interesting groups by O(z^2 log^2(z/ε)) and interesting outer groups by O(z log(z/ε)).Source: §3.3 · p. 13

4 The Coreset Construction Algorithm, and Proof of Theorem 1

The algorithm partitions clients into groups, samples within well-structured groups and outer rings, and combines the resulting coresets. The proof bounds the coreset size and shows the construction runs in linear time.

4.1 The algorithm

  • The algorithm partitions the input into groups, samples well-structured groups with GroupSample and outer rings with SensitivitySample, then takes the union.The algorithm also assigns weights to the points sampled by each procedure.Source: §4.1 · pp. 13–15
  • GroupSample applies to groups whose points have comparable costs within each induced cluster and whose cluster costs meet a lower bound.Its lemma assumes an approximate centroid set and states a sample of size δ.Source: §4.1 · p. 14
  • SensitivitySample runs in O(|G|) time and its stated success probability does not depend on ε^-z, unlike Lemma 2's.The lemma states a guarantee for all sets of k centers.Source: §4.1 · p. 14
  • A coreset tailored to well-structured groups can replace GroupSample; improving that component improves the final size bound.The remark parameterizes the group coreset size by T.Source: §4.1 · p. 15

4.2 Proof of Theorem 1

  • Theorem 1 bounds the coreset size by O(z^2 log^2(z/ε)·δ + |A|).The proof sets δ through a sampling-size expression.Source: §4.2 · p. 16
  • The construction runs in O(n) time, including grouping the input and computing coresets for the groups.The proof accounts for linear-time grouping and linear-time group coreset computations.Source: §4.2 · p. 17

5 Sampling inside Groups: Proof of Lemma 2

This section proves the group-sampling guarantee using a cluster-representative estimator to reduce variance and analyze costs range by range. It establishes a deviation bound for Eℓ,S(LS) and bounds the sum of Fℓ,S(LS) under event E.

5.1 Description of the GroupSample Algorithm

  • GroupSample samples one point per round using cluster cost share and rescales sampled-point weights.The procedure runs for δ rounds; sampling probabilities depend on a cluster’s cost under A relative to its size and the group’s total cost.Source: §5.1 · pp. 17–18

5.2 Organization of the Proof

  • The proof separates tiny, interesting, and huge ranges; there are at most O(z log(z/ε)) interesting ranges, which form its main technical challenge.Interesting and huge ranges overlap to preserve slack when relating a solution to its representative from the approximate centroid set.Source: §5.2 · p. 18

5.3 Dealing with Tiny Type

  • Tiny ranges are handled first because their analysis is mostly separate from the other range cases.The section introduces a lemma for this case, but the supplied passage does not include its full conclusion.Source: §5.2 · p. 18, §5.3 · p. 18

5.4 Preserving the Weight of Clusters, and the Huge Type

  • With high probability, sampled cluster weights approximate cluster sizes within a (1 ± ε) factor, enabling cost preservation for clusters with huge ranges.The cluster-size event also supports the later analysis of interesting ranges.Source: §5.4 · pp. 20–21

5.5 Bounding Interesting Iℓ,S: a Simple but Suboptimal Analysis.

  • The initial interesting-range analysis uses an unbiased estimator and Bernstein’s inequality, but its variance depends on ε^-z, motivating the improved analysis.The paper says this first analysis can establish a coreset when combined with the tiny- and huge-range results, but yields a suboptimal size.Source: §5.5 · pp. 22–23, §5.6 · p. 23

5.6 Bounding Interesting Iℓ,S: Improved Analysis

  • The improved analysis replaces the high-variance estimator with a small-variance alternative, increasing GroupSample’s success probability.It estimates each interesting range separately and subtracts a representative-point cost to reduce variance.Source: §5.6 · p. 23, §5.6.1 · pp. 23–24

5.6.1 Designing a Good Estimator: Reducing the Variance

  • The improved estimator analyzes each interesting range separately and uses the difference from a representative point’s cost to reduce variance.This difference is smaller than using the sampled point’s cost alone, and the cluster-weight event supports concentration for the remaining estimate.Source: §5.6.1 · pp. 23–24
  • Lemma 9 uses a cluster representative q_i,S whose cost is within a factor 2 of other points in its cluster to relate sampled-point costs.Source: §5.6.1 · p. 25

5.6.2 Concentration of the Estimator Eℓ,S(LS)

  • For ℓ ≤ z log(4z/ε), Lemma 10 bounds |Eℓ,S(LS) − E[Eℓ,S(LS)]| by ε z log z/ε · (cost(G, A) + cost(Iℓ,S, S)).Source: §5.6.2 · pp. 25, 27

5.6.3 Concentration of Fℓ,S(LS)

  • For Fℓ,S(LS), the proof bounds the sum rather than an individual term; conditioned on E, cluster-mass preservation and minimum-cost representatives give E[FS(LS)] ≤ cost(LS, S) ≤ cost(G, S).Source: §5.6.3 · pp. 27–28

5.7 Combining Them All

The proof combines concentration bounds with an approximate centroid set to handle all candidate solutions. It separates huge points from interesting clusters and concludes with a coreset cost guarantee.

5.7 Combining Them All

  • The approximate centroid set makes union-bounding over candidate solutions possible, addressing the too-small success probability for a direct union bound over all S.The text says this union bound is needed only for interesting points, whose guarantee initially holds for a fixed S.Source: §5.7 · p. 28
  • Conditioned on event E, Lemma 12 bounds concentration for every S~ in the centroid set and every associated set of interesting clusters.The stated concentration bound is for deviations of Eℓ,S~ from its expectation.Source: §5.7 · pp. 28–29
  • The proof handles points far from S relative to A as huge, then applies Lemma 12 to the remaining interesting clusters.It maps S to an approximating S~ from the centroid set before applying that lemma.Source: §5.7 · pp. 30–31
  • The proof bounds the cost discrepancy by O(ε) times the combined costs of G and Ω for S and A, then removes the Ω terms.The final bound uses cost(G,S) and cost(G,A).Source: §5.7 · p. 32

6 Sampling from Outer Rings

The outer-ring sampling analysis establishes that sensitivity sampling preserves clustering costs by handling points close to candidate solutions and points far from them separately. Together, these bounds yield a coreset cost guarantee for every solution.

6 Sampling from Outer Rings

  • SensitivitySample selects δ points with probability proportional to their cost under A and assigns each sampled point a weight scaled by the group's cost.The procedure runs in O(|G|) time.Source: §6 · p. 33
  • For points close to a candidate solution from the approximate centroid set, sampling controls the difference between the group's cost and its sampled cost.The bound is expressed relative to the group's cost under A and under the candidate solution.Source: §6 · p. 33
  • For points far from a candidate solution, both the group's cost and its sampled cost are bounded relative to the cost of the full input under that solution.The analysis compares against full-input cost, rather than only the cost of group G.Source: §6 · p. 35
  • The sampled coreset approximates each solution's cost on an outer group within O(ε) z log(z/ε) times the sum of the group's cost under that solution and under A.The proof combines the close-point and far-point bounds.Source: §6 · pp. 38–39

7 Partitioning into Well Structured Groups

The section partitions points into well-structured groups and bounds how their costs change under any solution. It treats the inner ring and cheap groups separately to establish the partitioning guarantee.

7 Partitioning into Well Structured Groups

  • The partitioning lemma bounds the difference between the costs of D and P1 for every solution S.The proof combines the bounds for the inner ring and the cheap groups.Source: §7 · pp. 40–41

7.1 The Inner Ring: Proof of Lemma 16

  • For points in a cluster's inner ring, the analysis compares each point's cost under S with the cluster center's cost, then sums the bound over the ring.The pointwise bound includes an ε fraction of the point's cost and a term controlled by its distance to the cluster center.Source: §7.1 · p. 41

7.2 The Cheap Groups: Proof of Lemma 17

  • The cheap-group analysis aggregates cost bounds over clusters for groups Gj,min and GO_min.It uses the group's cost bound for Gj,min to complete the argument for the cheap groups.Source: §7.2 · p. 42

8 Application of the Framework: New Coreset Bounds for Various Metric Spaces

The framework applies its approximate-centroid-set approach to obtain coresets for different metric settings. For bounded doubling dimension, the construction uses local nets, while a structural reduction controls how solutions may be simplified.

8 Application of the Framework: New Coreset Bounds for Various Metric Spaces

  • The framework applies when the metric admits a small approximate centroid set, and the paper applies it across specific metric spaces to obtain coreset bounds.The theorem gives a linear-time construction when such a set exists.Source: §8 · pp. 42–43

8.1 Structural Property on Solutions

  • The structural lemma replaces a solution S with a subset S′ whose costs remain close, while ensuring that retained centers have no problematic point under the lemma's condition.The cost difference is bounded in terms of ε z log(z/ε) and the point's costs under S and A.Source: §8.1 · p. 43

8.2 In Metrics with Bounded Doubling Dimension

  • For doubling dimension d, the paper gives an ε-coreset algorithm with running time ˜O(nk) and a size bound depending on k, d, ε, z, and π.The approximate centroid set is constructed from local nets, whose union is identified as the desired set.Source: §8.2 · pp. 45–46

9 Graphs with Bounded Treewidth

For graphs of bounded treewidth, the paper constructs an approximate centroid set and applies its framework to obtain a coreset. The construction uses separators and rounded distances to group possible centers into a manageable set of classes.

9 Graphs with Bounded Treewidth

  • For treewidth t, the paper gives an ε-coreset algorithm with running time ˜O(nk) and a size bound depending on k, t, ε, z, and π.The bound includes terms involving k log k and kt.Source: §9 · p. 47
  • An alternative applies the algorithm repeatedly, reducing the number of distinct points to achieve the same coreset size in O(log* n) repetitions.The stated total running time is ˜O(nk), with success probability 1 − π.Source: §9 · p. 47
  • The approximate centroid-set construction uses graph separators and rounded distances to classify possible centers, then keeps a representative for each class.The resulting centroid set has size polynomial in |X|, with dependence on treewidth in its exponent.Source: §9 · pp. 47–49

10 Planar Graphs

For planar-graph (k,z)-clustering, the section constructs small centroid sets by decomposing the graph into regions bounded by a few shortest paths and rounding distances to selected landmarks. It establishes an approximation guarantee for replacing centers.

10 Planar Graphs

  • An A-approximate centroid set exists for planar-graph (k,z)-clustering, with size poly(|X|) times an exponential factor.The supplied size expression is incomplete.Source: §10 · p. 51
  • The planar decomposition partitions the graph into poly(|X|) regions, each containing at most two points of X and separated by a constant number of shortest paths.Removing the separator paths disconnects each region from the rest of the graph.Source: §10 · p. 51
  • For each region, the construction rounds distances to selected landmarks near a chosen input point, rather than to every vertex on its path boundaries.The section argues that shortest-path boundaries allow this subset of landmarks to suffice.Source: §10 · pp. 51–52
  • For points covered by the passage, replacing center s with s̃ changes cost by at most 3ε times the sum of cost(p, s) and cost(p, A).Source: §10 · p. 52

11 Minor-Excluded Graphs

For edge-weighted graphs excluding a fixed-size minor, the section constructs a small approximate centroid set and an ε-coreset algorithm for (k, z)-clustering. It also bounds the cost difference between a solution and its representative for interesting points, completing the proof of Lemma 25.

11 Minor-Excluded Graphs

  • The centroid set has size exp(O(log^2 |X| + log |X|/ε^4)) for a given clustering solution A on X.The result applies to edge-weighted graphs excluding a minor of fixed size.Source: §11 · p. 54
  • An algorithm with running time ˜O(nk) constructs an ε-coreset for (k, z)-clustering on a graph excluding a fixed minor.The supplied passage introduces the coreset size but does not provide its value.Source: §11 · p. 54

11.1 Construction of the centroid set.

  • The construction decomposes the graph into regions bounded by O(log |X|) paths, then selects representatives using nets and rounded distance tuples.The boundary paths are shortest paths in subgraphs, not necessarily in the original graph.Source: §11.1 · pp. 55–56, §11 · p. 55

11.2 C has Small Size

  • The constructed set C has size exp(O(log^2 |X| + log |X|/ε^4)), bounded by the number of possible rounded distance tuples.There is at most one point in C per rounded distance tuple.Source: §11.2 · pp. 56–57

11.3 C is an Approximate Centroid Set

  • For each p ∈ X, the representative s~ either has cost within ε(cost(p, s) + cost(p, A)) of s, or both distances to p exceed 10z·dist(p, A).This establishes the approximation guarantee used to show that C is an approximate centroid set.Source: §11.3 · p. 57
  • For any solution S and interesting point p, |cost(p, S) − cost(p, ˜S)| ≤ ε(cost(p, S) + cost(p, A)).Lemma 28 provides this guarantee, matching Eq. (30).Source: §11.3 · p. 60
  • Combining the guarantees from Lemmas 28 and 27 concludes the proof of Lemma 25.Source: §11.3 · p. 60

12 A Note on Euclidean Spaces

The section discusses removing dimension dependence from Euclidean coreset bounds using terminal embeddings. It combines the paper’s framework with existing constructions to obtain coreset-size corollaries for Euclidean and certain ℓp spaces.

12 A Note on Euclidean Spaces

  • Terminal embeddings reduce dimension dependence after obtaining a poly(k/ε)-size coreset, with target dimension O(ε^-2 log n).Here n is the number of points in the embedded set.Source: §12 · p. 60
  • The section cautions that conventional Johnson–Lindenstrauss embeddings do not obviously provide the same guarantee as terminal embeddings.The paper states that terminal embeddings can be combined with its framework for dimension reduction.Source: §12 · p. 60
  • Combining the framework with terminal-embedding constructions yields coreset-size corollaries for Euclidean spaces and ℓp spaces with p ∈ [1, 2).The supplied corollary passages omit the displayed size expressions.Source: §12 · p. 61
  • A terminal embedding transfers an ε-coreset between a point set and its embedding in either direction, with O(ε) error.The proposition specifies this transfer for a possibly weighted point set.Source: §12 · p. 61

A Missing Proof

This section supplies a proof for the triangle inequality for powers. It attributes the first inequality to prior work and handles the second by considering which point is closer to the center set.

A Missing Proof

  • The proof of the first inequality in the triangle inequality for powers is attributed to, Corollary A.2.The lemma assumes a positive integer z.Source: A Missing Proof · p. 66
  • For the second part, the proof splits into the cases where a or b is closer to S and bounds the difference of their powered distances in each case.The proof assumes d(b, S) ≤ d(a, S) in one case and d(a, S) ≤ d(b, S) in the other.Source: A Missing Proof · pp. 66–67

B A Coreset of Size k2ε−2

The section trades a factor of ε^-z for a factor of k in coreset size. Its analysis uses ring-based sampling and separates point groups into cases to establish cost-approximation guarantees.

B A Coreset of Size k2ε−2

  • Given an A-approximate centroid set, an O(n)-time algorithm constructs a coreset with high probability that works for every set of k centers.The theorem states the guarantee for any set of k centers.Source: B A Coreset of Size k2ε−2 · p. 67
  • The sampling scheme partitions points into distance rings, samples δ points uniformly from each ring, and keeps the whole ring when it contains at most δ points.The analysis also divides groups into tiny, interesting, and huge cases.Source: B A Coreset of Size k2ε−2 · pp. 67–68
  • For huge groups, preserving each ring's weight with high probability yields a good cost approximation; interesting groups have a separate guarantee when all huge groups are empty.The interesting-group guarantee is stated with probability at least 1 − log(z/ε) exp(− ε2 …), and its error bound is proportional to ε log(z/ε) times the ring costs under A and S.Source: B A Coreset of Size k2ε−2 · pp. 68–69
  • The construction replaces a factor of ε^-z with a factor of k in the coreset-size bound.The section presents this as a trade-off in coreset size.Source: B A Coreset of Size k2ε−2 · pp. 67, 70
Loading 2104.06133v4…