Provable Data Summarization for Scalable Optimization

You are reading version 1 of this direction, frozen 2026-10-04. The latest version is version 2.

Version 1 of 2225 papers292 conceptsfrozen 2026-10-04

As datasets grow to billions of points, traditional optimization algorithms—from $k$-means clustering to neural network training—hit a fundamental wall: the computational cost scales linearly (or worse) with the number of samples $N$. The research direction of coresets offers a way around this wall. Instead of designing faster algorithms for the full dataset, this field focuses on "distilling" the massive dataset into a tiny, weighted proxy that behaves almost identically to the original for a specific optimization task.

The Intuition of the Weighted Proxy

The central idea is that not all data points are equally important to an optimization objective. In a clustering problem, points deep within a dense cluster are redundant, while points near the boundaries or isolated outliers are critical for defining the cluster's shape.

A coreset is a small subset of the original data where each point is assigned a weight. The goal, as framed by Dan Feldman and Ibrahim Jubran in Minimizing Sum of Non-Convex but Piecewise log-Lipschitz Functions using Coresets, is to ensure that for any potential solution (e.g., any set of cluster centers), the cost calculated on the weighted coreset is a $(1 \pm \epsilon)$ approximation of the cost on the full dataset.

This allows a practitioner to run their existing, potentially expensive optimization algorithm on the coreset instead of the full data. Because the coreset size is often independent of $N$—depending instead on the complexity of the model and the desired precision $\epsilon$—this leads to massive speedups. For instance, Shaofeng H.-C. Jiang and colleagues demonstrated speedups of over 500x in Coresets for Ordered Weighted Clustering.

How Coresets are Built: Sensitivity and Sampling

The most common mechanism for building a coreset is importance sampling based on "sensitivity." Sensitivity measures how much a single data point can influence the total cost function in the worst-case scenario.

  1. High Sensitivity: Points that are "unique" or far from the majority have high sensitivity. If we miss them, our approximation of the total cost could be wildly off.
  2. Low Sensitivity: Points in dense regions have low sensitivity because their contribution to the cost is shared by many neighbors.

Researchers like Mario Lučić and Andreas Krause utilize Bregman divergences to scale this sampling to billions of points, as shown in Strong Coresets for Hard and Soft Bregman Clustering. By sampling points with a probability proportional to their sensitivity and weighting them inversely to that probability, the resulting coreset becomes an unbiased estimator of the full cost function with low variance.

While sophisticated sampling is standard, Lingxiao Huang and Shaofeng H.-C. Jiang recently showed in The Power of Uniform Sampling for k-Median that if a dataset is "balanced," even simple uniform sampling can suffice to create a "weak" coreset, which preserves the cost for high-quality solutions even if it fails for poor ones.

Beyond Points: Handling Complex Structures

The power of the coreset framework lies in its flexibility across different data types and constraints:

  • Geometric Objects: Yair Marom extended these ideas to k-Means Clustering of Lines, allowing for the summarization of trajectories or linear trends rather than just static points.
  • Missing Data: In real-world scenarios where features are often missing, Vladimir Braverman and Robert Krauthgamer developed coresets that maintain clustering quality by reducing the problem to coordinate-specific subsets in Coresets for Clustering with Missing Values.
  • Neural Networks: Coresets are not limited to classical geometry. Abhimanyu Dubey and Narendra Ahuja applied coreset decomposition to compress neural network filters in Coretset-Based Neural Network Compression, achieving massive model reduction without retraining.

Scalability in Streams and Distributed Systems

Coresets are particularly effective for streaming and distributed environments. Because coresets are "mergeable"—the union of two coresets is a coreset for the union of the two datasets—they can be computed in parallel across different servers or updated incrementally as new data arrives.

In Streaming Balanced Clustering, Hossein Esfandiari and Vahab Mirrokni demonstrate how to maintain these summaries even when data points are being both added and removed (the "turnstile" model). This allows for real-time analysis of massive data flows where storing the entire dataset is impossible.

Why It Works: The Moment-Preserving Intuition

Ultimately, a coreset works because it preserves the "moments" or the statistical skeleton of the data. As explored by Marco Capó and Aritz Pérez in their work on Recursive Partition Based K-means, large groups of points can be replaced by their center of mass and a weight representing their count. By focusing refinement only on the "boundaries" where cluster assignments are uncertain, these algorithms decouple the computational cost from the raw number of points, focusing instead on the geometric complexity of the underlying distribution.

Papers in this version

Showing 60 of 225 papers.

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 1, frozen text):

@misc{lacuna_provable_data_summarization_for_scalable_462eac9f_v1,
  title = {Provable Data Summarization for Scalable Optimization},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/provable-data-summarization-for-scalable-optimization/rdr_462eac9f11544546bd6dbf15a6d40993/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-21},
}