Online Coresets for Clustering with Bregman Divergences
  We 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 $\tilde{O}(\mbox{poly}(k,d,\epsilon,\mu))$ for
$k$-clusterings according to any $\mu$-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(\log n)$ ($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(\log n)$ as opposed to $O(d^d)$ for
points in $\~R^d$) 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.
