2018/02/21 by Elad Tolochinsky, Tolochinsky, Elad, Jubran, Ibrahim +1 · 1 citation
Computer Science · Engineering · #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Machine Learning (cs.LG) #Machine Learning and Algorithms #Machine Learning and Data Classification #Sparse and Compressive Sensing Techniques
paper · pdf · doi:10.48550/arxiv.1802.07382
openalex publication_date 2018/02/21 · openalex created_date 2018/06/13 · openalex updated_date 2026/07/28
Coreset (or core-set) is a small weighted subset Q of an input set P with respect to a given monotonic function f:ℝ→ℝ that provably approximates its fitting loss ∑p∈ Pf(p⋅ x) to any given x∈ℝd. Using Q we can obtain approximation of x^* that minimizes this loss, by running existing optimization algorithms on Q. In this work we provide: (i) A lower bound which proves that there are sets with no coresets smaller than n=|P| for general monotonic loss functions. (ii) A proof that, under a natural assumption that holds e.g. for logistic regression and the sigmoid activation functions, a small coreset exists for any input P. (iii) A generic coreset construction algorithm that computes such a small coreset Q in O(nd+nlog n) time, and (iv) Experimental results which demonstrate that our coresets are effective and are much smaller in practice than predicted in theory.