Back to Search
Start Over
Coresets for the Average Case Error for Finite Query Sets.
- Source :
-
Sensors (14248220) . Oct2021, Vol. 21 Issue 19, p6689. 1p. - Publication Year :
- 2021
-
Abstract
- Coreset is usually a small weighted subset of an input set of items, that provably approximates their loss function for a given set of queries (models, classifiers, hypothesis). That is, the maximum (worst-case) error over all queries is bounded. To obtain smaller coresets, we suggest a natural relaxation: coresets whose average error over the given set of queries is bounded. We provide both deterministic and randomized (generic) algorithms for computing such a coreset for any finite set of queries. Unlike most corresponding coresets for the worst-case error, the size of the coreset in this work is independent of both the input size and its Vapnik–Chervonenkis (VC) dimension. The main technique is to reduce the average-case coreset into the vector summarization problem, where the goal is to compute a weighted subset of the n input vectors which approximates their sum. We then suggest the first algorithm for computing this weighted subset in time that is linear in the input size, for n ≫ 1 / ε , where ε is the approximation error, improving, e.g., both [ICML'17] and applications for principal component analysis (PCA) [NIPS'16]. Experimental results show significant and consistent improvement also in practice. Open source code is provided. [ABSTRACT FROM AUTHOR]
Details
- Language :
- English
- ISSN :
- 14248220
- Volume :
- 21
- Issue :
- 19
- Database :
- Academic Search Index
- Journal :
- Sensors (14248220)
- Publication Type :
- Academic Journal
- Accession number :
- 153039208
- Full Text :
- https://doi.org/10.3390/s21196689