Data Summarization via Weighted Coresets

516 concepts328 papers1 proposal

As datasets grow exponentially, standard machine learning algorithms encounter severe computational bottlenecks. Running an optimization loop—whether it is Lloyd's algorithm for $k$-means clustering, gradient descent for logistic regression, or computing a kernel matrix—becomes prohibitively expensive when the number of data points $N$ reaches millions or billions.

A naive solution is uniform random sampling. However, uniform sampling fails when data distribution is highly non-uniform or when rare structural features (such as outliers or small, tight clusters) heavily influence the global objective function.

Coreset construction solves this problem by compressing a massive dataset into a small, weighted subset that acts as a high-fidelity mathematical proxy for the entire collection. Crucially, a coreset guarantees that evaluating an objective function on the compressed subset yields nearly the exact same result as evaluating it on the full dataset, up to a tiny error margin $\epsilon$.

Massive Dataset (N points) ---> [ Coreset Construction ] ---> Tiny Weighted Subset (n << N points)
                                                                   |
                                                                   v
                                                      Run ANY Downstream Algorithm

The Core Mechanism: Why Weights Matter

To understand why coresets work, we must look at how they preserve the geometry of the data space. If we simply select a subset of points without modifying them, we lose the "mass" or density of the regions we discarded. Coresets fix this by assigning a real-valued weight to each selected point.

Imagine a dense cluster of 10,000 points. A coreset algorithm might replace this entire cluster with a single representative point at its center, assigning it a weight of 10,000. In the eyes of any downstream optimization algorithm, computing the cost against this single weighted point is mathematically identical to computing the cost against all 10,000 original points.

As shown by Ailon et al. in the context of streaming $k$-means, this weighted point reduction allows complex hierarchical processes to compress data across multiple stages without losing the underlying statistical properties. By substituting large clusters with single weighted representatives, the data size shrinks dramatically while preserving the global objective cost.

Overcoming Uniform Sampling: The Power of Sensitivity

How do we decide which points to keep and how to weight them? The foundational framework relies on importance sampling based on sensitivity.

The sensitivity of a data point measures its maximum possible relative contribution to the total objective function across all potential parameter configurations.

  • A point sitting deep inside a massive, dense cluster has low sensitivity because its individual contribution is easily drowned out or compensated for by its neighbors.
  • An isolated point or a structural outlier has high sensitivity because if an algorithm places a cluster center far away from it, that single point can dominate the total error.

If we sample data uniformly, we will almost certainly miss high-sensitivity outliers, catastrophically undermining the accuracy of our model. Coreset algorithms overcome this by sampling points with a probability proportional to their sensitivity.

To ensure the final estimator remains unbiased, the weight of each sampled point is set to the inverse of its sampling probability:

$$\text{Weight}(x) \propto \frac{1}{\text{Sampling Probability}(x)}$$

This creates a elegant balancing act: low-sensitivity points are sampled rarely but receive massive weights when they are chosen (representing their dense neighborhoods), while high-sensitivity points are sampled frequently but receive small weights. Huang et al. leveraged this exact sensitivity-bounding approach to construct coresets for panel data regression, compressing massive longitudinal datasets to less than 1% of their original size while maintaining rigorous empirical accuracy.

Strong vs. Weak Coresets

Coresets generally fall into two categories based on the strength of their mathematical guarantees:

  1. Weak Coresets: Guarantee approximation only for the optimal parameter configuration (e.g., the absolute best cluster centers).
  2. Strong Coresets: Guarantee approximation for all possible parameter configurations simultaneously.

Strong coresets are vastly more powerful because they completely decouple data reduction from optimization. Because the approximation holds true everywhere across the parameter space, you can construct a strong coreset once and then run any downstream heuristic, local search, or streaming algorithm directly on it.

For instance, Lou et al. developed the first strong coresets for kernel $k$-means clustering. Their construction preserves the objective function approximation for all possible center configurations in a way that is entirely independent of both the total dataset size and the dimensionality of the feature space, enabling near-linear time approximations for otherwise intractable kernel problems.

Deterministic and Greedy Alternatives

While importance sampling relies on randomized algorithms, coresets can also be built deterministically using geometric or optimization frameworks.

One prominent approach adapts the Frank-Wolfe optimization framework. As explored by Feldman et al. for vector summarization, a deterministic coreset can be constructed by iteratively selecting the data point that lies furthest from the current weighted average of the coreset. This greedy approach builds a summary whose size depends purely on the desired error tolerance, perfectly preserving properties like the mean and covariance of high-dimensional data streams.

This greedy, deterministic reduction is highly effective in deep learning and computer vision applications where feature distributions must be memorized efficiently. For example, Roth et al. utilized greedy coreset subsampling to compress nominal feature memory banks in industrial anomaly detection systems. By iteratively eliminating redundant feature vectors, they achieved a 99% reduction in stored data and enabled real-time inference speeds with negligible loss in detection accuracy.

Breaking the Dependency on Dataset Size

The most remarkable property of coreset construction is that the size of the resulting summary is often completely independent of $N$ (the number of points in the original dataset).

Why is this possible? The complexity of representing a dataset depends on the complexity of the query space (the model itself), not the volume of the raw data. Once a specific region of the parameter space is sufficiently covered by a weighted representative, adding more points to the original dataset simply increases the weights of the existing coreset points rather than requiring new ones.

In work on hard and soft Bregman clustering, such as Strong Coresets for Hard and Soft Bregman Clustering, researchers demonstrated that the cardinality of a coreset can scale strictly with the number of clusters $k$ and the error tolerance $\epsilon$. To push this boundary further, Braverman et al. introduced an "iterative size reduction" technique. By applying importance sampling in multiple successive stages, they gradually stripped away logarithmic dependencies, reducing massive graph and high-dimensional Euclidean datasets down to constant-sized summaries.

Ultimately, whether through randomized sensitivity sampling or deterministic greedy selection, coresets shift the computational burden of big data. By compressing millions of rows into a few hundred highly descriptive, weighted points, they allow practitioners to execute complex statistical modeling, nonparametric estimation, and deep learning inference at a fraction of the time and memory cost.

History & citationVersion 2 · 2026-10-04

Current · Permanent link

  1. Version 2 (latest) · 2026-10-04 · 342 papers
  2. Version 1 · 2026-10-04 · 225 papers
Cite this direction

Latest version (a living page):

@misc{lacuna_coreset_construction_462eac9f,
  title = {coreset construction},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/coreset-construction/rdr_462eac9f11544546bd6dbf15a6d40993},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-21},
}

This exact version (version 2, frozen text):

@misc{lacuna_coreset_construction_462eac9f_v2,
  title = {coreset construction},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/coreset-construction/rdr_462eac9f11544546bd6dbf15a6d40993/v/2},
  note = {Version 2, frozen 2026-10-04. Accessed 2026-11-21},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake