Certified Sub-Linear Lower Bounds for K-Means Clustering
summary
Claims a sub-linear certifier for k‑means that computes probabilistic lower bounds by solving an SDP on random subsets of the data, so total work depends on sample count not full N. Empirically a small number of samples often yields lower bounds close to kmeans++ results; for spherical Gaussian mixtures sample size scales like log N and the method gives a 3‑approx with 99% confidence. Practical failure modes: SDP solvers sometimes return infeasible outputs requiring rounding that weakens the certificate.
AI-written summary · about
chapters (16)
- 0:00Intro
- 2:13Clustering Objective
- 4:13KMeans Problem
- 4:43KMeans Plus
- 5:15Optimization Problem
- 5:37Finding a Lower Bound
- 8:35probabilistic Lower Bound
- 11:01caimans Lower Bound
- 12:15sophistical test
- 14:25number of points
- 16:03optimization
- 16:37review
- 17:50plots
- 19:18example
- 21:34other problems
- 22:41affinity clustering
related talks
42mk-means and k-medians under Dimension Reduction
37mThe Sum-of-Squares Approach to Clustering Non-Spherical Gaussian Mixtures
01h 02mTheory and Big Data
01h 00mStreaming Euclidean k-median and k-means with o(log n) Space
34mSubspace Clustering using Ensembles of K-Subspaces
29mLatent Variable models and Subset Smoothing
42mRobust Mixture Learning when Outliers Overwhelm Small Groups
29mApproximating Spherical Gaussian Mixtures