Are coreset weights necessarily integers?

No. The worked example uses positive fractional weights.

Does an exact one-center coreset also work for two centers?

Not necessarily; the fictional case gives a counterexample.

Can a heuristic subset still be useful?

Yes, but empirical usefulness should not be presented as a proved uniform approximation guarantee.

AI Glossary / Mathematics and optimization / Advanced

Coreset

Definition

A coreset is a compact representation of a dataset designed to preserve specified properties relevant to a particular task. It often consists of selected data points with weights. In a strong clustering coreset, the weighted clustering cost approximates the full dataset's cost for every allowed set of centers, within a stated error tolerance. A coreset is therefore defined in relation to an objective and its permitted queries.

What it means

The purpose is to perform useful calculations on less data while retaining a controlled connection to the original problem. A weight tells the calculation how much influence a retained point carries; it need not be a whole-number count of original records.
The task qualification matters. A compact representation that preserves one-center squared-distance costs may fail for two centers, another distance measure or a classification problem. Calling selected records representative does not establish the required guarantee. Some practical selection methods are heuristic and should be described accordingly.

How it works

Start by specifying the full-data objective, the candidate solutions and an acceptable approximation error. A construction then selects or creates a smaller weighted representation appropriate to that problem. The downstream solver must actually use those weights.
For a multiplicative error ε, a typical strong guarantee requires the coreset cost to lie between (1 − ε) and (1 + ε) times the full-data cost for every candidate solution. Randomized constructions may attach a probability to this guarantee. Construction cost, representation size and solver cost all contribute to the overall benefit; reducing the number of stored points alone does not measure total savings.

Three practical examples

A clustering team repeatedly compares candidate customer-segment centers. A suitable weighted coreset lets it estimate the specified clustering objective using fewer points, while retaining the original dataset for additional evaluation.
A distributed analytics system combines local summaries under a construction whose guarantees support that operation. The team checks the accumulated approximation error and communication requirements instead of assuming that any collection of local samples will work.
A training team selects examples to reduce experimentation costs. It distinguishes a formally supported coreset for a particular loss from a useful heuristic subset whose performance has only been measured empirically.

Think of it this way

Think of a scale model engineered to reproduce particular measurements. It may preserve the quantities needed for one experiment without reproducing every property of the original object. Changing the experiment requires checking whether the model still answers the right question. A smaller version is useful because of what it preserves, not simply because it is smaller.

Worked example

Take four one-dimensional data points: 0, 1, 2 and 3. For one candidate center c, their total squared-distance cost is c² + (1 − c)² + (2 − c)² + (3 − c)² = 4c² − 12c + 14.
Keep just three original points: 0 with weight 4/3, 2 with weight 2, and 3 with weight 2/3. Their weighted cost is (4/3)c² + 2(2 − c)² + (2/3)(3 − c)². Expanding gives exactly 4c² − 12c + 14 again.
This is an exact coreset for the one-center squared-distance objective in this example. The equality holds for every c, not only for the best center. At c = 0 both costs equal 14; at c = 4 both equal 30. Completing the square gives 4(c − 1.5)² + 5, so both problems have optimal center 1.5 and minimum cost 5.
The weights sum to four, their weighted first moment is six, and their weighted second moment is fourteen. Those three quantities explain the matching quadratic. This construction illustrates an exact small case; it is not a claim that the same three-point recipe solves arbitrary clustering tasks.

Illustrative case study

In a fictional service-planning project, an analyst reuses the worked example's coreset after changing from one service location to two. The proposed locations are 0 and 2, and each demand point is assigned to its nearest location.
On the full dataset, the squared-distance contributions are 0, 1, 0 and 1, totaling 2. On the weighted coreset, the contributions are 0, 0 and 2/3, totaling only 2/3. A representation that was exact for every single location now substantially understates this two-location cost.
The team records the number of centers as part of the coreset's specification and rebuilds the summary for the revised task. Its lesson is precise: excellent preservation under one objective family does not establish preservation under a different family. The change requires a new justification, even though the underlying records remain identical.

Common misconceptions and mistakes

A coreset is not automatically an ordinary random sample, an unweighted subset or a set of cluster centers. The construction and weights determine its role. Dropping the weights changes the calculation and can destroy the guarantee.
Matching the cost at one chosen solution is weaker than preserving costs across all permitted solutions. A clustering-objective guarantee also does not automatically preserve held-out prediction accuracy, every subgroup statistic or every downstream use. Those are separate questions that require relevant evaluation.

Business use

Coresets can support repeated analysis when full-data computation or communication is expensive. Specify what must be preserved before selecting a method. Record the objective, allowable solutions, weights, error tolerance and any randomization assumptions alongside the summary. Compare end-to-end cost with the full-data workflow and check whether later changes to the business question invalidate the original specification.

Check your understanding

Why is the one-center example exact?

Answer: Both weighted and full costs expand to the same quadratic for every center.

What is its optimal center?

Answer: 1.5, with cost 5.

What changes in the two-center case?

Answer: Each point uses its nearest center, and the preserved quadratic no longer describes the objective.

Related terms

Clustering
k-means
Sufficient statistic
Importance sampling
Objective function
Weighted sample
approximation algorithm
distributed computation

Learn next

Compare coreset guarantees for different objectives. Then examine how construction time, failure probability, approximation error and downstream optimization accuracy combine in a complete workflow.

Sources

Aalto Dictionary of Machine Learning, coreset: compact representations and weighting. https://aaltodictionaryofml.github.io/ADictML_Main.pdf Maria Florina Balcan, Steven Ehrlich and Yingyu Liang, Distributed k-Means and k-Median Clustering on General Topologies, 2013, section 2: uniform weighted-cost approximation. https://proceedings.neurips.cc/paper_files/paper/2013/file/7f975a56c761db6506eca0b37ce6ec87-Paper.pdf The exact weighted construction and fictional service-planning counterexample are original teaching illustrations.

Previous: Coreference resolution Next: Coring