2020/06/09 by Alaa Maalouf, Maalouf, Alaa, Ibrahim Jubran +5
Computer Science · #Algorithms and Data Compression #Domain Adaptation and Few-Shot Learning #FOS: Computer and information sciences #Machine Learning (cs.LG) #Machine Learning (stat.ML) #Machine Learning and Algorithms
paper · pdf · doi:10.48550/arxiv.2006.05441
openalex publication_date 2020/06/09 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
PAC-learning usually aims to compute a small subset (ε-sample/net) from n items, that provably approximates a given loss function for every query (model, classifier, hypothesis) from a given set of queries, up to an additive error ε∈(0,1). Coresets generalize this idea to support multiplicative error 1±ε. Inspired by smoothed analysis, we suggest a natural generalization: approximate the average (instead of the worst-case) error over the queries, in the hope of getting smaller subsets. The dependency between errors of different queries implies that we may no longer apply the Chernoff-Hoeffding inequality for a fixed query, and then use the VC-dimension or union bound. This paper provides deterministic and randomized algorithms for computing such coresets and ε-samples of size independent of n, for any finite set of queries and loss function. Example applications include new and improved coreset constructions for e.g. streaming vector summarization [ICML'17] and k-PCA [NIPS'16]. Experimental results with open source code are provided.