Papers › New Frameworks for Offline and Streaming Coreset Constructions
New Frameworks for Offline and Streaming Coreset Constructions
Vladimir Braverman, Dan Feldman, Harry Lang, Adiel Statman, Samson Zhou
The archive published only this paper's code-link row. Authors, date and abstract are from arXiv's metadata (CC0), read from the Kaggle arXiv metadata snapshot of 2026-09-12 where its title matched the archive's; the title is the archive's.
A coreset for a set of points is a small subset of weighted points that approximately preserves important properties of the original set. Specifically, if P is a set of points, Q is a set of queries, and f:P×Q→ℝ is a cost function, then a set S⊆P with weights w:P→[0,∞) is an ϵ-coreset for some parameter ϵ>0 if ∑_(s∈S)w(s)f(s,q) is a (1+ϵ) multiplicative approximation to ∑_(p∈P)f(p,q) for all q∈Q. Coresets are used to solve fundamental problems in machine learning under various big data models of computation. Many of the suggested coresets in the recent decade used, or could have used a general framework for constructing coresets whose size depends quadratically on what is known as total sensitivity t. In this paper we improve this bound from O(t²) to O(tlogt). Thus our results imply more space efficient solutions to a number of problems, including projective clustering, k-line clustering, and subspace approximation. Moreover, we generalize the notion of sensitivity sampling for sup-sampling that supports non-multiplicative approximations, negative cost functions and more. The main technical result is a generic reduction to the sample complexity of learning a class of functions with bounded VC dimension. We show that obtaining an (ν,α)-sample for this class of functions with appropriate parameters ν and α suffices to achieve space efficient ϵ-coresets. Our result implies more efficient coreset constructions for a number of interesting problems in machine learning; we show applications to k-median/k-means, k-line clustering, j-subspace approximation, and the integer (j,k)-projective clustering problem.
In Syntology Open this paper in Syntology's Atlas, the map of the papers in Syntology's graph and their citations.
Code
Repository list and official/mentioned flags are the archive's, frozen 2025-07-28. Reachability, where shown, is from one Syntology probe window (2026-09-16 to 2026-09-18); repositories not probed show nothing. GitHub stars are not tracked.
Code Syntology ran Syntology
Not run by Syntology. Nothing on this page verifies that the listed code works.
Results from the paper archive 2025-07-28
No leaderboard rows for this paper in the archive.
Report a problem or propose a change · a person checks every report against the paper or source before anything changes; decisions are listed on /corrections