Geometric Approximation via Coresets

By Pankaj Kumar Agarwal, Sariel Har-Peled, Kasturi R. Varadarajan. 2007

459 citations recorded by the source corpus.

View Paper: https://www.semanticscholar.org/paper/9d713f1f79554a28b9788c0299cb07d34d782022

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

Citations in the corpus

Training Mixture Models at Scale via Coresets (2017, background): “Notably, coresets also imply streaming algorithms for many of these problems (Har-Peled and Mazumdar, 2004; Agarwal et al., 2005; Frahling and Sohler, 2005; Feldman et al., 2007).”
Private coresets (2009, background): “Coresets also imply streaming algorithms for many of these problems [1, 25, 32, 27, 36, 26, 9].”
Submodularity in Data Subset Selection and Active Learning (2015, methodology): “For example, another common approach for training data summarization in the supervised and unsupervised setting is to use the concept of a coreset (Agarwal et al., 2005).”
Coresets for polytope distance (2009, methodology): “For a nice review on existing coreset algorithms we refer to [2].”
Automated Scalable Bayesian Inference via Hilbert Coresets (2017, background): “The concept of a coreset originated in computational geometry and optimization (Agarwal et al., 2005; Feldman and Langberg, 2011; Feldman et al., 2013; Bachem et al., 2015; Lucic et al., 2016; Bachem et al., 2016; Feldman et al., 2011; Han et al., 2016).”
Coreset-Based Neural Network Compression (2018, background): “They were introduced ﬁrst by Agarwal et al. [1] for approximating a set of points with a smaller set, while preserving some desired criteria, on k-means and k-median problems.”
Towards Total Recall in Industrial Anomaly Detection (2021, background): “Finally, for practical applicability, PatchCore additionally introduces greedy coreset subsampling [1] for nominal feature banks as a key element to both reduce redundancy in the extracted, patch-level memory bank as well as significantly bringing down storage memory and inference time, making Patch”
Practical Coreset Constructions for Machine Learning (2017, background): “For an excellent survey on the results from computational geometry consult Agarwal et al. [2005] and Har-Peled [2011].”
Core‐sets: An updated survey (2019, methodology): “First coresets were deterministic of size exponential in their (VC-)dimension d (P. Agarwal et al., 2005; Feldman, Fiat, & Sharir, 2006), random constructions whose output is polynomial in d replaced them (Chen, 2009), and independency of d is sometimes possible using either weak coresets (Feldman…”
Distribution Density, Tails, and Outliers in Machine Learning: Metrics and Applications (2019, background): “Prototypes of a given task share some intuition with the notion of coresets (Agarwal et al., 2005; Huggins et al., 2016; Bachem et al., 2017; Tolochinsky & Feldman, 2018) because both prototypes and coresets describe the dataset in a more compact way—by returning a (potentially weighted) subset of t”
Mining Individual Life Pattern Based on Location History (2009, methodology): “We resort to corsets [21] and geometric approximation via corsets [20].”
Training Gaussian Mixture Models at Scale via Coresets (2017, methodology): “Notably, coresets also imply streaming algorithms for many of these problems (Har-Peled and Mazumdar, 2004; Agarwal et al., 2005; Frahling and Sohler, 2005; Feldman et al., 2007).”
Coresets for Scalable Bayesian Logistic Regression (2016, methodology): “[1]), but then became popular in theoretical computer science as a way to efficiently solve clustering problems such as k-means and PCA (see [9, 11] and references therein).”
Revisiting Training Strategies and Generalization Performance in Deep Metric Learning (2020, methodology): “UsingM, we mine mini-batches by first randomly sampling B∗ fromM with b∗ = 1024 and subsequently find a mini-batch B to match its data statistics by using one of the following criteria: Greedy Coreset Distillation (GC): Greedy Coreset (Agarwal et al., 2005) finds a batch B by iteratively adding samp”
Universal ε-approximators for integrals (2010, background): “A typical scenario: (a)X is Euclidean Rd. (b) is Lebesgue measure restricted to [0; 1 ]d, or to a ball, or is”
Matrix approximation and projective clustering via volume sampling (2006, background): “An extent measure is just a statistic on the point set (for example, the diameter of a point set, or the radius of the minimum enclosing cylinder); typically, it measures the size of the point set or the minimum size of an object that encloses the point set [ 2 ].”
Data-Dependent Coresets for Compressing Neural Networks with Applications to Generalization Bounds (2018, background): “Coresets Coreset constructions were originally introduced in the context of computational geometry [2] and subsequently generalized for applications to other problems via an importance sampling-based, sensitivity framework [32, 9].”