# On Generalization Bounds for Projective Clustering

arXiv: https://arxiv.org/abs/2310.09127 · HTML: https://mlsanity.com/paper/2310.09127/

## 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 (most cited first, 20 of 20)

- [Fair Clustering Through Fairlets](https://mlsanity.com/paper/1802.05733/) (2018)
- [Generalization Properties of Learning with Random Features](https://mlsanity.com/paper/1602.04474/) (2016)
- [Random Features for Kernel Approximation: A Survey on Algorithms, Theory, and Beyond](https://mlsanity.com/paper/2004.11154/) (2020)
- [Turning Big data into tiny data: Constant-size coresets for k-means, PCA and projective clustering](https://mlsanity.com/paper/1807.04518/) (2018)
- [Performance of Johnson-Lindenstrauss Transform for k-Means and k-Medians Clustering](https://mlsanity.com/paper/1811.03195/) (2018)
- [Dimensionality Reduction for k-Means Clustering and Low Rank Approximation](https://mlsanity.com/paper/1410.6801/) (2014)
- [A New Coreset Framework for Clustering](https://mlsanity.com/paper/2104.06133/) (2021)
- [Coresets for Clustering in Euclidean Spaces: Importance Sampling is Nearly Optimal](https://mlsanity.com/paper/2004.06263/) (2020)
- [Strong Coresets for k-Median and Subspace Approximation: Goodbye Dimension](https://mlsanity.com/paper/1809.02961/) (2018)
- [Towards Optimal Lower Bounds for k-median and k-means Coresets](https://mlsanity.com/paper/2202.12793/) (2022)
- [The Power of Uniform Sampling for Coresets](https://mlsanity.com/paper/2209.01901/) (2022)
- [Scalable Kernel K-Means Clustering with Nystrom Approximation: Relative-Error Bounds](https://mlsanity.com/paper/1706.02803/) (2017)
- [On the Local Structure of Stable Clustering Instances](https://mlsanity.com/paper/1701.08423/) (2017)
- [Input Sparsity and Hardness for Robust Subspace Approximation](https://mlsanity.com/paper/1510.06073/) (2015)
- [Optimal terminal dimensionality reduction in Euclidean space](https://mlsanity.com/paper/1810.09250/) (2018)
- [Statistical and Computational Trade-Offs in Kernel K-Means](https://mlsanity.com/paper/1908.10284/) (2019)
- [An Empirical Evaluation of k-Means Coresets](https://mlsanity.com/paper/2207.00966/) (2022)
- [A Sub-linear Time Framework for Geometric Optimization with Outliers in High Dimensions](https://mlsanity.com/paper/2004.10090/) (2020)
- [Risk Bounds for Learning Multiple Components with Permutation-Invariant Losses](https://mlsanity.com/paper/1904.07594/) (2019)
- [Deterministic Clustering in High Dimensional Spaces: Sketches and Approximation](https://mlsanity.com/paper/2310.04076/) (2023)

## Built on by (most cited first, 4 of 4)

- [Improved Learning via k-DTW: A Novel Dissimilarity Measure for Curves](https://mlsanity.com/paper/2505.23431/) (2025)
- [Hardness of High-Dimensional Linear Classification](https://mlsanity.com/paper/2603.19061/) (2026)
- [Node Similarities under Random Projections: Limits and Pathological Cases](https://mlsanity.com/paper/2404.10148/) (2024)
- [Dimension Reduction for Curves: Simplified and Generalized](https://mlsanity.com/paper/2607.03112/) (2026)

## 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.