Introduction to Coresets: Accurate Coresets

Understand

A coreset (or core-set) of an input set is its small summation, such that solving a problem on the coreset as its input, provably yields the same result as solving the same problem on the original (full) set, for a given family of problems (models, classifiers, loss functions).

• Over the past decade, coreset construction algorithms have been suggested for many fundamental problems in e.g.
• machine/deep learning, computer vision, graphics, databases, and theoretical computer science.
• This introductory paper was written following requests from (usually non-expert, but also colleagues) regarding the many inconsistent coreset definitions, lack of available source code, the required deep theoretical background from different fields, and the dense papers that make it hard for beginners to apply coresets and develop new ones.