k-variates++: more pluses in the k-means++
  k-means++ seeding has become a de facto standard for hard clustering
algorithms. In this paper, our first contribution is a two-way generalisation
of this seeding, k-variates++, that includes the sampling of general densities
rather than just a discrete set of Dirac densities anchored at the point
locations, and a generalisation of the well known Arthur-Vassilvitskii (AV)
approximation guarantee, in the form of a bias+variance approximation bound of
the global optimum. This approximation exhibits a reduced dependency on the
"noise" component with respect to the optimal potential --- actually
approaching the statistical lower bound. We show that k-variates++ reduces to
efficient (biased seeding) clustering algorithms tailored to specific
frameworks; these include distributed, streaming and on-line clustering, with
direct approximation results for these algorithms. Finally, we present a novel
application of k-variates++ to differential privacy. For either the specific
frameworks considered here, or for the differential privacy setting, there is
little to no prior results on the direct application of k-means++ and its
approximation bounds --- state of the art contenders appear to be significantly
more complex and / or display less favorable (approximation) properties. We
stress that our algorithms can still be run in cases where there is \textit{no}
closed form solution for the population minimizer. We demonstrate the
applicability of our analysis via experimental evaluation on several domains
and settings, displaying competitive performances vs state of the art.
