Portal de Periódicos da CAPES

Coresets for the Average Case Error for Finite Query Sets

2021; Multidisciplinary Digital Publishing Institute; Volume: 21; Issue: 19 Linguagem: Inglês

10.3390/s21196689

1424-8220

Alaa Maalouf, Ibrahim Jubran, Murad Tukan, Dan Feldman,

Stochastic Gradient Optimization Techniques

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