Coreset

Let P be a finite set of points and let f(P, x) denote the cost of a candidate solution x to an optimization problem defined on P. For example, in k-means clustering, x may represent a set of k centers and f(P, x) the sum of squared distances from points in P to their nearest center. A (strong) ε-coreset for P with respect to f is a (possibly weighted) subset S ⊆ P such that for all candidate solutions x, : (1 - \epsilon)\, f(P, x) \le f(S, x) \le (1 + \epsilon)\, f(P, x), where ε > 0 is a user-defined approximation parameter. In many constructions, S is equipped with weights w(p) so that : f(S, x) = \sum_{p \in S} w(p)\, c(p, x), where c(p, x) is the contribution of point p to the cost. Some literature distinguishes between: • Strong coresets: The approximation guarantee holds uniformly for all candidate solutions x. • Weak coresets: The guarantee holds only for solutions near the optimum. == Construction techniques ==

Coresets are typically constructed using one or more of the following techniques: • Importance sampling: Points are sampled with probability proportional to their sensitivity (their maximum relative influence on the objective function). • Random sampling and ε-approximations: Techniques from VC theory are used to guarantee uniform convergence. • Geometric partitioning: Space is partitioned and representative points are selected from each region. • Merge-and-reduce frameworks: Used in streaming and distributed settings to maintain coresets over time. For many problems, the size of the coreset is O(g(ε, d)), where d is the dimension and the bound does not depend on the input size n. == Applications ==

Clustering Coresets are widely used in clustering problems such as k-means clustering, k-median, and metric k-center . For example, in k-means clustering in Euclidean space, one can construct a coreset of size O(k / ε²) (up to logarithmic factors in some settings), independent of n. Running an exact or heuristic clustering algorithm on the coreset yields a (1 + ε)-approximation for the original dataset. This enables scalable clustering in large datasets and forms the basis of several practical machine learning systems. Geometric optimization Coresets have been developed for problems including: • Minimum enclosing ball • Facility location • Projective clustering • Shape fitting In low-dimensional settings, coresets often yield polynomial-time approximation schemes. Regression and machine learning In regression problems such as least-squares fitting, coresets provide smaller weighted datasets that preserve the objective value. They are also used in: • Support vector machines • Subspace approximation • Hyperparameter optimization More recently, coresets have been explored for dataset summarization and acceleration of training in large-scale machine learning pipelines. == Streaming and distributed computation ==

In streaming models, data points arrive sequentially and storage is limited. Merge-and-reduce techniques maintain a small coreset whose size depends only on ε and problem parameters. Similarly, in distributed systems, composable coresets allow each machine to compute a local coreset, which can then be combined centrally while preserving approximation guarantees. == Related concepts ==

Coresets are related to: • ε-approximations and ε-nets in range spaces • Randomized sketching techniques • Dimensionality reduction • Sublinear and streaming algorithms == References ==