Everything about Coreset
Computational geometry and optimization concept
In computational geometry and approximation algorithms, a coreset is a small, possibly weighted subset of an input point set that approximately preserves the value of a specified optimization problem. Solving the problem on the coreset yields a solution whose cost is provably close to the optimal solution for the full dataset. Coresets are widely used in geometric optimization, cluster analysis, data streams, and large-scale machine learning to reduce computational complexity while maintaining theoretical guarantees. Wikipedia →
🧠Start here: a 6-step reading path
- Read the overview: CoresetA 5-minute orientation
- Skim a recent paper: Extending Contrastive Learning to Unsupervised Coreset SelectionInfluential work since 2022
- Read the landmark paper: GoodCore: Data-effective and Data-efficient Machine Learning through Coreset Selection over Incomplete DataCited 34 times
- Go sideways: Approximation algorithmA closely related topic
- Go sideways: Sauer–Shelah lemmaA closely related topic
đź“– Definitions
Noun A small set of points that approximates the shape of a larger point set, in the sense that applying some geometric measure to the two sets (such as their minimum bounding box volume) results in approximately equal numbers.
🗂️ The subject at a glance
🏆 Landmark papers (most cited)
GoodCore: Data-effective and Data-efficient Machine Learning through Coreset Selection over Incomplete Data
Robust Coreset Construction for Distributed Machine Learning
Coreset Clustering on Small Quantum Computers
Continuous $k$-Regret Minimization Queries: A Dynamic Coreset Approach
Coreset Learning-Based Sparse Black-Box Adversarial Attack for Video Recognition
Coreset: Hierarchical neuromorphic computing supporting large-scale neural networks with improved resource efficiency
Assembly of a Coreset of Earth Observation Images on a Small Quantum Computer
A Unified Approach to Coreset Learning
🆕 Influential since 2022
Extending Contrastive Learning to Unsupervised Coreset Selection
Adversarial Coreset Selection for Efficient Robust Training
Feature Distribution Matching by Optimal Transport for Effective and Robust Coreset Selection
Contributing Dimension Structure of Deep Feature for Coreset Selection
Dynamic Confidence Variance for Generalized Coreset in Active Learning
đź“š Books worth reading
Open Library didn't respond; try again in a moment.
đź”— Related topics
- Approximation algorithm In computer science and operations research, approximation algorithms are efficient algorithms that find approximate solutions to optimization problems…
- Sauer–Shelah lemma In combinatorial mathematics and extremal set theory, the Sauer–Shelah lemma states that every family of sets with small VC dimension consists of a small…
- Ε-net (computational geometry) In computational geometry, an ε-net (pronounced epsilon-net) is the approximation of a general set by a collection of simpler subsets. In probability theory…
- Maximum satisfiability problem In computational complexity theory, the maximum satisfiability problem (MAX-SAT) is the problem of determining the maximum number of clauses, of a given…
- Ellipsoid method In mathematical optimization, the ellipsoid method is an iterative method for minimizing convex functions over convex sets. The ellipsoid method generates…
- Multi-objective optimization In multiple-criteria decision making, multi-objective optimization or Pareto optimization (also known as multi-objective programming, vector optimization…
- Stochastic approximation Stochastic approximation methods are a family of iterative methods typically used for root-finding problems or for optimization problems. The recursive…
- Kinodynamic planning In robotics and motion planning, kinodynamic planning is a class of problems for which velocity, acceleration, and force/torque bounds must be satisfied…