On Generalization Bounds for Projective Clustering

Summary

The authors study the generalization bounds for two clustering problems: center-based clustering and subspace (projective) clustering. The authors argue that the problems reduce to bounding the Gaussian complexity of the set of cost functions over all possible solutions. To achieve this, they apply the union bound on the telescoping sum over a nested sequence of solutions sets that are increasingly more accurate. To find a set of solutions at a specific level of accuracy, the authors use the \emph{terminal embedding} for the center-based clustering, and they propose a new dimensionality reduction method for the projective clustering.

Strengths

- The authors provide the first provable bound for projective clustering. For a specific case with the squared cost, they show that the previous bound by Fefferman, Mitter, and Narayanan (2016) is optimal. - I find the chaining technique to be quite interesting, and it could be applied to other learning problems. - The authors did a decent job of giving a high level idea of their proofs - The experimental result on real datasets agree with the theoretical results.

Weaknesses

My only concerns are regarding the applications and experiments. Since this is mainly theoretical paper, these should not be major concerns. - The problem of projective clustering should be better motivated in the introduction. What are some real applications of projective clustering? What are the common choices of $j$? - The experiment are performed with $j\in \{1,2,5\}$, with only $j=1$ presented in the main paper. In my opinion, there should be a bit of discussion on how the experimental results conform (or deviate) from theory as $j$ increases.

Questions

- As the authors mentioned in D.2, the projective clustering is serverly limited in computational aspect. Has there been any attempt to solve this issue? The authors probably should mention this limitation somewhere in the paper as well.

Rating

7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.

Confidence

3: You are fairly confident in your assessment. It is possible that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.

Soundness

4 excellent

Presentation

3 good

Contribution

3 good

Limitations

The authors have mentioned several open problems related to this work, but I think the most important problem is whether the projective clustering rate of $\tilde{O}(\sqrt{kj^2/n})$ is optimal for $z\not= 2$.

Summary

This paper investigates generalization bounds for center based and subspace clustering, providing upper bounds on excess risk for $(k,z)$ and $(k,j,z)$ clustering and lower bound for $(k,j,z)$ clustering for special case of $z=2$. The bounds for $(k,j,z)$ clustering are novel and lower bounds helps establish optimality of previously known bounds.

Strengths

The paper is well written and proof sketch is easy to follow. This work provides improvements over existing work in extending $(k,z)$ clustering bounds. Getting chaining type analysis to work in this setting is non-trivial. The techniques used for proving upper bounds for subspace clustering are novel and using multiple dimensionality reductions for analysis is indeed interesting. The lower bound construction is clean. Overall, I like the results in this paper. I have not verified all the proofs in the appendix but the proof sketch and flow seems right to me.

Weaknesses

The bounds are interesting in certain parameter regimes, specifically when $j$ and $z$ are constants. Limitations in current approach to extend beyond this is not discussed.

Questions

Q1: Could this approach also help obtain improvements for when additional structural assumptions are imposed on $\mathcal{D}$? Q2: What changes in bound for Lemma 4.4 when points do not lie in low-dimensional space?

Rating

7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.

Confidence

3: You are fairly confident in your assessment. It is possible that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.

Soundness

3 good

Presentation

4 excellent

Contribution

3 good

Limitations

Please refer weakness and questions. Work is theoretical in nature, negative societal impact is not apparent.

Summary

This paper presents several generalization bounds for clustering objectives such as k-median and subspace clustering. When the centers are points or constant dimensional subspaces, the upper bounds are optimal up to logarithmic terms. For projective clustering, this work gives a lower bound showing that the results obtained by [34] are nearly optimal. A key technique was using an ensemble of dimension reduction methods with guarantees.

Strengths

This paper has the following contributions: For center-based objectives, this work shows a convergence rate, which matches the known optimal bounds for k-means, and extends it to other important objectives such as k-median. For subspace clustering with j-dimensional subspaces, this work also shows a convergence rate. For the specific case of projective clustering, which generalizes k-means, a converge rate is provided.

Weaknesses

1.Insufficient research on related work. This work is not the first random projection clustering work, such as papers [1,2]. These papers are not cited in this paper. The superiority of this work cannot be verified. Please compare them from the theoretical analysis, experimental results, algorithm complexity, etc. [1]Yin R, Liu Y, Wang W, et al. Randomized Sketches for Clustering: Fast and Optimal Kernel $ k $-Means[J]. Advances in Neural Information Processing Systems, 2022, 35: 6424-6436. [2]Yin R, Liu Y, Wang W, et al. Scalable Kernel $ k $-Means with Randomized Sketching: From Theory to Algorithm[J]. IEEE Transactions on Knowledge and Data Engineering, 2022. 2.The experiments is not enough. There are many related works in this field. If this paper can be compared with related work through experiments and the performance of the work can be analyzed in detail, it would be better. 3.The presentation of references is not standardized, such as: [20] P. Chou. The distortion of vector quantizers trained on n vectors decreases to the optimum as Op(1/n). In Proceedings of 1994 IEEE International Symposium on Information Theory, pages 457–, 1994. doi: 10.1109/ISIT.1994.395072. [28] V. Cohen-Addad, D. Saulpic, and C. Schwiegelshohn. Improved coresets and sublinear algorithms for power means in euclidean spaces. Advances in Neural Information Processing Systems, 34, 2021. [50] Y. Liu, S. Liao, S. Jiang, L. Ding, H. Lin, and W. Wang. Fast cross-validation for kernel-based algorithms. IEEE Transactions on Pattern Analysis and Machine Intelligence, PP:1–1, 01 2019. doi: 10.1109/TPAMI.2019.2892371. 4.The organization and presentation of this paper can be further improved.

Questions

See “Weaknesses”.

Rating

5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.

Confidence

4: You are confident in your assessment, but not absolutely certain. It is unlikely, but not impossible, that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work.

Soundness

3 good

Presentation

3 good

Contribution

3 good

Limitations

N/A

Summary

The authors study two clustering problems from the perspective of generalization: -standard center-based clustering objectives such as k-means, k-median and more generally the different norms associated with the objective -projective subspace clustering: where the goal is to find a k subspaces such that if you project the points there, you minimise a natural distance objective. The main question addressed for both of these problems is: If we are given a sample set of n data points drawn independently from a fixed (unknown) distribution, and we perform clustering on those n points, how fast will the solution on the sample converge to the optimal clustering on the fixed (unknown) distribution?

Strengths

+presentation and literature review is done in a careful manner +results for both clustering objectives are novel and interesting +generalization bounds almost tight

Weaknesses

-A lot of the tools needed by the authors seem to have been used in prior works too. Having said that, there are some proposed new techniques for dimension reduction which, though tailored to the problem at hand, seems interesting.

Questions

N/A

Rating

7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.

Confidence

3: You are fairly confident in your assessment. It is possible that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.

Soundness

3 good

Presentation

4 excellent

Contribution

3 good

Limitations

N/A

Summary

This paper studies generalization bounds for clustering problems, including ceter-based clustering and subspace clustering. For center-based clustering, they recover the optimal bound (up to log term) of $\widetilde{O}(\sqrt{k/n})$; the technique can be extended to k-median also. For subspace clustering, the derive the first bound $\widetilde{O}(\sqrt{kj^2/n})$ for the generalized $(k, j, z)$-clustering objectives, which had been established only for the scenario $z = 2$; for the special case $z=2$, they further refine the bound to $\widetilde{O}(\sqrt{kj/n})$ that meets the current upper-bound in the literature, and prove that this is tight. Experiments are given.

Strengths

The paper advances the knowledge on generalization bound for general subspace clustering, which is the main merit of this paper. The authors also prove the tightness for the case $z=2$. Given the intricate relevance between the clustering problem with coreset construction, dimension reduction and so on, the paper did a good job on discussing the relevant work and laying out their proof sketch, while pointing out the challenges for generalizing the results (from $z=2$ as in the paper's reference [34]) to the case $(k, j, z)$. It is then clear that the chaining technique, which has resulted in tight bounds for coreset clustering and especially $(k, j, 2)$ clustering, is not compatible with existing (generic) dimension reduction techniques. From there, the authors design an ad-hoc dimension reduction technique for subspace clustering to overcome the obstacle. Several insights and techniques in the paper are thus new and of independent interests, while such arguments seem restrictively applicable to only clustering case.

Weaknesses

While the paper is good in terms of technicality and novelty, it can be made more interesting if the authors can discuss better on use cases and importance of $z > 2$. In fact, the case $z=2$, which would correspond to the $\ell_2$ loss seems much more prevalent and important in practice. The current few-line discussion in the paper is a bit succinct and also does not point to any reference.

Questions

N.A.

Rating

7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.

Confidence

2: You are willing to defend your assessment, but it is quite likely that you did not understand the central parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.

Soundness

3 good

Presentation

3 good

Contribution

3 good

Limitations

Limitations are addressed. There is no negative societal impact of the work.

Official comment

Thanks for the response and indulging the questions. I believe the paper makes significant contribution so I maintain my score.

Response

I thank the authors for addressing my concerns and for the references. As the proved convergence rates are quite general and distribution-free, I think the paper provides significant contribution.