mlsanityData to 14 Oct 2026

On Generalization Bounds for Projective Clustering

arXiv 2310.09127 ↗First posted 13 Oct 2023cs.LGcited by 4

Not on the map. Why?

Abstract (arXiv)

Given a set of points, clustering consists of finding a partition of a point set into k clusters such that the center to which a point is assigned is as close as possible. Most commonly, centers are points themselves, which leads to the famous k-median and k-means objectives. One may also choose centers to be j dimensional subspaces, which gives rise to subspace clustering. In this paper, we consider learning bounds for these problems. That is, given a set of n samples P drawn independently from some unknown, but fixed distribution D, how quickly does a solution computed on P converge to the optimal clustering of D? We give several near optimal results. In particular, For center-based objectives, we show a convergence rate of tildeOleft(√k/nright). This matches the known optimal bounds of [Fefferman, Mitter, and Narayanan, Journal of the Mathematical Society 2016] and [Bartlett, Linder, and Lugosi, IEEE Trans. Inf. Theory 1998] for k-means and extends it to other important objectives such as k-median. For subspace clustering with j-dimensional subspaces, we show a convergence rate of tildeOleft(√frackj2nright). These are the first provable bounds for most of these problems. For the specific case of projective clustering, which generalizes k-means, we show a convergence rate of Omegaleft(√frackjnright) is necessary, thereby proving that the bounds from [Fefferman, Mitter, and Narayanan, Journal of the Mathematical Society 2016] are essentially optimal.

Key facts. Cited by 4 papers in the map (data through 14 Oct 2026). Builds on 20 of its 83 references that are in the map. First posted on arXiv 13 Oct 2023.

Builds on

20 of 83 references.

References · 20

  1. 2018Fair Clustering Through Fairletscited by 176
  2. 2016Generalization Properties of Learning with Random Featurescited by 164
  3. 2020Random Features for Kernel Approximation: A Survey on Algorithms, Theory, and Beyondcited by 109
  4. 2018Turning Big data into tiny data: Constant-size coresets for k-means, PCA and projective clusteringcited by 94
  5. 2018Performance of Johnson-Lindenstrauss Transform for k-Means and k-Medians Clusteringcited by 53
  6. 2014Dimensionality Reduction for k-Means Clustering and Low Rank Approximationcited by 48
  7. 2021A New Coreset Framework for Clusteringcited by 38
  8. 2020Coresets for Clustering in Euclidean Spaces: Importance Sampling is Nearly Optimalcited by 31
  9. 2018Strong Coresets for k-Median and Subspace Approximation: Goodbye Dimensioncited by 27
  10. 2022Towards Optimal Lower Bounds for k-median and k-means Coresetscited by 23
  11. 2022The Power of Uniform Sampling for Coresetscited by 18
  12. 2017Scalable Kernel K-Means Clustering with Nystrom Approximation: Relative-Error Boundscited by 16
8 more
  1. 2017On the Local Structure of Stable Clustering Instancescited by 13
  2. 2015Input Sparsity and Hardness for Robust Subspace Approximationcited by 12
  3. 2018Optimal terminal dimensionality reduction in Euclidean spacecited by 11
  4. 2019Statistical and Computational Trade-Offs in Kernel K-Meanscited by 7
  5. 2022An Empirical Evaluation of k-Means Coresetscited by 7
  6. 2020A Sub-linear Time Framework for Geometric Optimization with Outliers in High Dimensionscited by 3
  7. 2019Risk Bounds for Learning Multiple Components with Permutation-Invariant Lossescited by 2
  8. 2023Deterministic Clustering in High Dimensional Spaces: Sketches and Approximationcited by 2

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2024: 1; 2025: 1; 2026: 2.

4 papers.

  1. 2025Improved Learning via k-DTW: A Novel Dissimilarity Measure for Curvescited by 2
  2. 2026Hardness of High-Dimensional Linear Classificationcited by 1
  3. 2024Node Similarities under Random Projections: Limits and Pathological Casescited by 0
  4. 2026Dimension Reduction for Curves: Simplified and Generalizedcited by 0