Chhaya, RachitChoudhari, JayeshDasgupta, AnirbanShit, Supratim2025-08-282025-08-282020-12-01http://arxiv.org/abs/2012.06522http://repository.iitgn.ac.in/handle/IITG2025/19794We present algorithms that create coresets in an online setting for clustering problems according to a wide subset of Bregman divergences. Notably, our coresets have a small additive error, similar in magnitude to the lightweight coresets Bachem et. al. 2018, and take update time O(d) for every incoming point where d is dimension of the point. Our first algorithm gives online coresets of size O~(poly(k,d,?,?)) for k-clusterings according to any ?-similar Bregman divergence. We further extend this algorithm to show existence of a non-parametric coresets, where the coreset size is independent of k, the number of clusters, for the same subclass of Bregman divergences. Our non-parametric coresets are larger by a factor of O(logn) (n is number of points) and have similar (small) additive guarantee. At the same time our coresets also function as lightweight coresets for non-parametric versions of the Bregman clustering like DP-Means. While these coresets provide additive error guarantees, they are also significantly smaller (scaling with O(logn) as opposed to O(dd) for points in Rd) than the (relative-error) coresets obtained in Bachem et. al. 2015 for DP-Means. While our non-parametric coresets are existential, we give an algorithmic version under certain assumptions.en-USData StructuresAlgorithms (cs.DS)Machine Learning (cs.LG)e-Printe-Print123456789/435