Moment-based Uniform Deviation Bounds for k-means and Friends
Suppose k centers are fit to m points by heuristically minimizing the k-means cost; what is the corresponding fit over the source distribution? This question is resolved here for distributions with p ≥ 4 bounded moments; in particular, the difference between the sample cost and distribution cost decays with m and p as m min{−1/4,−1/2+2/p} . The essential technical contribution is a mechanism to uniformly control deviations in the face of unbounded parameter sets, cost functions, and source distributions. To further demonstrate this mechanism, a soft clustering variant of k-means cost is also considered, namely the log likelihood of a Gaussian mixture, subject to the constraint that all covariance matrices have bounded spectrum. Lastly, a rate with refined constants is provided for k-means instances possessing some cluster structure.
The paper adresses the problem of derivation of 
      generalization bounds for the k-means objective. If the distribution is 
      bounded, standard techniques provide good generalization bounds. Also, 
      good bounds can be obtained under strong tail assumptions (e.g. for 
      sub-gaussian distributions). The main focus of the current paper is to 
      derive generalization bounds based only on moment assumptions. The 
      main result of the paper is that if the distribution has p\ge 4 moments, 
      then the convergence rate is upper bounded by m^{min(-1/4,-1/2+2/p)} 
      (here, m is the number of examples). Evaluation: ----------- 
      In the realm of machine learning, boundness is fairly reasonable 
      assumption. Nevertheless, the centrality of the k-means objective 
      justifies research such as the one reported in this paper. 
      Unfortunately, I did not have enough time to read and understand 
      the proof, which seems quite involved. Therefore, I avoid evaluating 
      technical quality and novelty (however, as written, the results and the 
      proofs seems non trivial). Of course, I can't vouch for correctness. 
      Last remark - due to the lengthy proof and the centrality of the 
      result, I would fill more confident if the paper will undergo a journal 
      level refereeing. This is a pity and of course unfair for the authors. 
      Nevertheless, in the scientific community, correctness comes before 
      fairness.