- Rating
- 2
- Confidence
- 3
- Informativeness
- 2
- Presentation
- 2
- Soundness
- 2
Read review
Paper summary
This paper investigates the sensitivity, coresets, and statistical generalization of axis-aligned -projection clustering. The authors provide an upper bound on the total sensitivity and a sensitivity-sampling-based coreset for arbitrary real-valued inputs—covering the previously unresolved case where —without requiring bounded integer coordinates or intermediate steps involving -coresets. Furthermore, the authors establish several lower bounds using multi-scale constructions and derive excess risk bounds for axis-aligned linear or affine subspaces on the unit sphere. The validation is primarily theoretical, consisting of formal proofs and comparisons between upper and lower bounds; no empirical experiments or evaluations of practical algorithms are included.
Critical strengths
-
The authors explicitly point out that existing general projection-based clustering methods lack guarantees for small coresets when dealing with arbitrary real-valued inputs (for ). They attempt to circumvent this limitation by imposing axis-aligned constraints, providing a well-motivated theoretical basis.
-
The paper establishes a comprehensive theoretical framework—encompassing projection transformations, local sensitivity, clustering sensitivity, VC dimension, and sampling bounds—with the construction of lower bounds effectively complementing the mechanisms used for the upper bounds.
-
The inclusion of generalization bounds offers a learning-theoretic perspective on axis-aligned models; by comparing these with existing lower bounds, the paper broadens its overall theoretical scope.
Critical weaknesses
-
The assumption of axis-aligned subspaces is highly restrictive and often fails to hold in practical projection-clustering scenarios. Consequently, the claim of significantly reducing computational challenges appears more like an avoidance of difficulties within a constrained setting rather than a solution to the general projection-clustering problem. This substantially limits the paper's broader impact and its significance at the level of top-tier conferences like ICML, NeurIPS, or ICLR.
-
The upper and lower bounds do not align perfectly, furthermore, the bounds on the coreset size are complex, involving large constants and polynomial factors. While the total sensitivity reaches the order of for fixed and , the coreset size also incorporates terms such as , the VC dimension, and . Since the lower bounds cover only a portion of the parameter space, they are insufficient to support a strong claim regarding compact data reduction.
-
The technical contribution is primarily combinatorial in nature, relying heavily on projection shifts, coordinate reduction, sensitivity for set clustering, and standard VC-dimension-based tools. The paper lacks a deep exploration of the unique challenges—or the novel algorithmic approaches—that arise specifically from the axis-aligned setting. Moreover, the generalization bounds are restricted to the unit ball and axis-aligned models; the bounds for the affine case are significantly weaker than those for the linear case, and the practical effectiveness of the proposed methods remains unverified by experiments.
Questions for authors
-
What specific practical applications correspond to the axis-aligned assumption? If the primary applications are not naturally axis-aligned, how do the authors justify that this constraint is not an oversimplification?
-
What is the specific order of magnitude for the coreset size in Theorem 9 under typical parameter settings (e.g., where and grow as functions of and )? Does it offer any practical advantages over existing coresets for general projection-based clustering or simpler baselines?
-
Do the lower bounds cover the entire parameter space of the upper bounds—specifically for cases such as , , arbitrary , and general -coresets? How is the tightness of the bounds in the uncovered regions justified?
-
Is the term in the generalization bound for the affine case necessary? Can it be improved to match the linear case, or can a corresponding lower bound be provided?
-
Can the upper bounds on sensitivity and the sampling fractions be computed efficiently? How does the computational complexity of determining these values compare to that of existing algorithms for projection-based clustering?
3 comments
review
Thank you for your rebuttal. Could you please provide some experimental results? Without experimental validation, I do not feel confident enough to raise my score.
We thank the reviewer for the suggestion to include experiments. The main contribution of this paper is theoretical: we establish worst-case bounds, and Lemmas 10, 12, and 13 show that these bounds are tight in several regimes. Performance on particular datasets would not establish the general worst-case guarantees that are the focus of this work. We therefore hope that the paper can be assessed primarily on the significance and correctness of its theoretical contributions. In the revision, we have also added a Conclusion section. We would be glad to clarify any specific concerns about the results or their proofs.
We thank the reviewer for the thoughtful comments. We address the five questions, as well as the broader concern about novelty, below.
(1) Axis-alignment: Axis-aligned projective clustering has a direct interpretation as cluster-specific feature selection: different clusters may ignore different subsets of coordinates, while the selected features remain the original, interpretable coordinates. We do not view axis alignment as an attempt to solve unrestricted projective clustering. Rather, our results show that this structural restriction leads to qualitatively different behaviour; in particular, we show that axis alignment permits coreset guarantees for arbitrary real inputs, without the bounded integer-coordinate assumption used in prior guarantees for general projective clustering.
(2) Coreset size: When j, k, z and δ are all constants, the size of the coreset, as guaranteed by Theorem 9, is O(ϵ−2dlognloglogn). The main qualitative advantage over the known guarantees for general projective clustering is that our result applies to arbitrary real inputs and removes the bounded integer-coordinate assumption. When j and k themselves grow, the bound can indeed become large; however, our lower bounds show that exponential dependence on min{j,k} is unavoidable in the worst case.
(3) Lower bound regimes: Our lower bounds match the sensitivity upper bound in some parameter regimes, while gaps remain in others:
(4) Affine term: We thank the reviewer for raising this point. A refined analysis removes the additional log2(en) factor. The revised bound is Enaff≲z,γkj/nlog3/2+γ(en/j).
This improvement comes from controlling all translation parameters in Γ simultaneously instead of discretizing them by a net. The revised proof is included in the submission, with the changes highlighted in blue.
(5) Computation of sensitivities and coresets: The running time for the construction is Oj,k,z,δ(nd) for constants j,k,z,δ, which is optimal since reading the input takes Ω(nd) time. We have included in the revised version of the submission the more general time complexity as part of Theorem 9 with a full proof in Appendix A.6.
(6) Novelty: The VC-dimension argument is standard; the main technical contribution is the sensitivity analysis preceding it, as well as the added randomized algorithm to calculate the sensitivities. Lemma 6 reduces the local queries to queries involving at most one coordinate per term. Lemma 7 then groups these queries by their active coordinate sets and bounds their sensitivity through a set-clustering formulation. These reductions exploit axis alignment and yield sensitivity bounds independent of the ambient dimension, without restrictions on the input coordinates. The bounds match the lower bounds for constant j and capture unavoidable exponential dependence on min{j,k}. The VC-dimension argument supplies the final sampling step that converts these sensitivity bounds into coresets.