Core‐sets: An updated survey
By Dan Feldman. 2019
135 citations recorded by the source corpus.
In optimization or machine learning problems we are given a set of items, usually points in some metric space, and the goal is to minimize or maximize an objective function over some space of candidate solutions. For example, in clustering problems, the input is a set of points in some metric space, and a common goal is to compute a set of centers in some other space (points, lines) that will minimize the sum of distances to these points. In database queries, we may need to compute such a some for a specific query set of k centers. However, traditional algorithms cannot handle modern systems that require parallel real‐time computations of infinite distributed streams from sensors such as GPS, audio or video that arrive to a cloud, or networks of weaker devices such as smartphones or robots. Core‐set is a “small data” summarization of the input “big data,” where every possible query has approximately the same answer on both data sets. Generic techniques enable efficient coreset maintenance of streaming, distributed and dynamic data. Traditional algorithms can then be applied on these coresets to maintain the approximated optimal solutions. The challenge is to design coresets with provable tradeoff between their size and approximation error. This survey summarizes such constructions in a retrospective way, that aims to unified and simplify the state‐of‐the‐art.
Subfields: Artificial Intelligence
How researchers see this paper
The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.
In Artificial Intelligence
- Rishabh K. Iyer
- Ganesh Ramakrishnan
- Durga Sivasubramanian
- Abir De
- Indian Institute of Technology Bombay Institution One
- I. Two
- Krishnateja Killamsetty
- R. Dallas
Citations in the corpus
- GCR: Gradient Coreset based Replay Buffer Selection for Continual Learning (2021, neutral): “Coresets for Replay-based CL: Approaches include selecting replay buffers by maximizing criteria like sample gradient diversity ( GSS [8]), a mix of mini-batch gradient similarity and cross-batch diversity ( OCS [9]), adversarial Shapley value( ASER [40]), or representation matching (iCARL [22]).”
- GLISTER: Generalization based Data Subset Selection for Efficient and Robust Learning (2020, background): “Coresets are weighted subsets of the data, which approximate certain desirable characteristics of the full data (e.g. the loss function) (Feldman 2020).”
- GRAD-MATCH: Gradient Matching based Data Subset Selection for Efficient Deep Model Training (2021, background): “Coresets are weighted subsets of the data, which approximate certain desirable characteristics of the full data (, e.g., the loss function) (Feldman, 2020).”
- RETRIEVE: Coreset Selection for Efficient and Robust Semi-Supervised Learning (2021, unknown): “Coreset and subset selection methods: Coresets [13] are small and informative weighted data subsets that approximate original data.”