acceptodds
Under review as a conference paper at ICLR 2027

Axis-Aligned Projective Clustering

Abstract

We study axis-aligned -projective clustering of points in , where the objective sums the th powers of Euclidean distances to the nearest of axis-aligned -dimensional affine subspaces. For and every constant , we obtain total-sensitivity bounds of , independent of the ambient dimension and requiring no bounds on input coordinates. Sensitivity sampling then yields small weighted coresets, with ambient dimension entering only through the complexity of the query family. Complementary lower bounds show that logarithmic dependence on and exponential dependence on are unavoidable, already in . We also establish expected excess-risk bounds on the unit sphere for linear subspaces and affine subspaces within unit distance of the origin. This bound is optimal up to logarithmic factors for the linear class when and is sufficiently large relative to .

Primary area:
learning theory
Keywords:
axis-aligned, projective clustering, generalization bound

Reviews

Among:
Shape:
1234this paper, Top 15%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 3.00 over 4 reviews, above 85% of the others.
Reviewer_7eBNOpenReview ↗
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 (j,k,z)(j, k, z)-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 j,k≥2j, k \ge 2—without requiring bounded integer coordinates or intermediate steps involving L∞L_\infty-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
  1. 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 j,k≥2j, k \ge 2). They attempt to circumvent this limitation by imposing axis-aligned constraints, providing a well-motivated theoretical basis.

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

  3. 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
  1. 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.

  2. 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 Θ(log⁡n)\Theta(\log n) for fixed jj and kk, the coreset size also incorporates terms such as kRj,k(n)kR_{j,k}(n), the VC dimension, and Lj,k(n)L_{j,k}(n). Since the lower bounds cover only a portion of the parameter space, they are insufficient to support a strong claim regarding compact data reduction.

  3. 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
  1. 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?

  2. What is the specific order of magnitude for the coreset size in Theorem 9 under typical parameter settings (e.g., where jj and kk grow as functions of dd and nn)? Does it offer any practical advantages over existing coresets for general projection-based clustering or simpler baselines?

  3. Do the lower bounds cover the entire parameter space of the upper bounds—specifically for cases such as j≫kj \gg k, k≫jk \gg j, arbitrary z≥1z \ge 1, and general ϵ\epsilon-coresets? How is the tightness of the bounds in the uncovered regions justified?

  4. Is the k/nlog⁡2(en)\sqrt{k/n}\log^2(en) 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?

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

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 jj, kk, zz and δ\delta are all constants, the size of the coreset, as guaranteed by Theorem 9, is O(ϵ−2dlog⁡nlog⁡log⁡n)O(\epsilon^{-2} d\log n \log\log n). 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 jj and kk themselves grow, the bound can indeed become large; however, our lower bounds show that exponential dependence on min⁡{j,k}\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:

  • All our lower bound hard instances already work in dimension d=j+1d = j + 1.
  • For constant j≥2j\geq 2 and growing kk, Lemma 12 matches the sensitivity upper bound up to constants depending on jj in the stated regime.
  • For constants j≥1j\geq 1 and k≥2k\geq 2, the worst-case total sensitivity is Θj,k,z(log⁡n)\Theta_{j,k,z}(\log n). For k=1k=1 and constant jj, it is Θj(1)\Theta_j(1).
  • Lemma 13 shows that exponential dependence on min⁡{j,k}\min\{j, k\} is unavoidable for both total sensitivity and coreset size.
  • For constant k≥2k\geq 2 and growing jj, the dependence on jj is tight up to a log⁡n\log n factor when 1≤z≤21\leq z\leq2: the upper bound is Ok,z(jklog⁡n)O_{k,z}(j^k\log n), whereas Lemma 13 gives Ωk(jk)\Omega_k(j^k) in its stated regime. Matching the joint dependence on jj and nn remains open.

(4) Affine term: We thank the reviewer for raising this point. A refined analysis removes the additional log⁡2(en)\log^2(en) factor. The revised bound is Enaff≲z,γkj/nlog⁡3/2+γ(en/j)\mathcal E_n^{\mathrm{aff}} \lesssim_{z,\gamma} \sqrt{kj/n}\log^{3/2+\gamma}(en/j).

This improvement comes from controlling all translation parameters in Γ\mathcal{\Gamma} 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)O_{j,k,z,\delta}(nd) for constants j,k,z,δj, k, z, \delta, which is optimal since reading the input takes Ω(nd)\Omega(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 jj and capture unavoidable exponential dependence on min⁡{j,k}\min\{j,k\}. The VC-dimension argument supplies the final sampling step that converts these sensitivity bounds into coresets.

Reviewer_7eBNOpenReview ↗

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.

Reviewer_GhoTOpenReview ↗
Rating
3
Confidence
3
Informativeness
3
Presentation
2
Soundness
3
Read review
Paper summary

The paper studies axis-aligned projective clustering, which approximates a dataset using kk axis-aligned jj-dimensional affine subspaces under a distance-to-the-power-zz objective. For arbitrary real inputs and fixed z≥1z\geq1, it establishes total sensitivity bounds independent of the ambient dimension and uses sensitivity sampling to obtain constructive guarantees for small weighted coresets. Complementary lower bounds show that logarithmic dependence on the dataset size and exponential dependence on min⁡j,k\min \\{j,k\\} are unavoidable in the worst case. The paper also derives expected excess risk bounds of order O~z(kj/n)\widetilde O_z(\sqrt{kj/n}) for data on the unit sphere, covering linear subspaces and affine subspaces within unit distance of the origin. The linear bound matches a lower bound up to logarithmic factors in the specified parameter regime. Validation is entirely theoretical, through mathematical proofs and explicit lower bound constructions.

Critical strengths
  1. Valuable theoretical advances supported by substantial analysis. The paper establishes new coreset guarantees for axis-aligned projective clustering on arbitrary real inputs, including the regime with multiple subspaces of dimension at least two. Removing the bounded-coordinate assumption addresses a meaningful limitation of prior guarantees. The substantial theoretical development combines constructive upper bounds with complementary lower bounds, clarifying both the possibilities and inherent limitations of data reduction. This provides a substantive basis for acceptance.

  2. Strong statistical guarantees that complement the coreset results. For data on the unit sphere, the paper establishes expected excess risk bounds without explicit dependence on the ambient dimension. For axis-aligned linear subspaces, the bounds apply to every fixed distance exponent of at least one and are optimal up to logarithmic factors in the specified parameter regime. These results clarify how sample requirements depend on the number and dimension of the subspaces, adding a meaningful statistical contribution beyond the data reduction guarantees.

Critical weaknesses
  1. The overall running time of the coreset construction is not explicitly characterized. Appendix A.6 provides an arithmetic complexity bound for obtaining the initial approximation, but a consolidated bound covering the full construction, including all sampling scores, is not stated. For a theoretical paper, establishing compressibility and bounding the coreset size are already meaningful contributions, but providing more time analysis, with the dependence on input size and model parameters made explicit, would further strengthen the practical relevance of the results.

  2. The organization and introduction of notation could be improved. The paper lacks a dedicated conclusion or future work section, leaving its overall structure somewhat incomplete. A concluding discussion would help consolidate the main findings and identify remaining challenges. In addition, some symbols are used before being defined. For example, Gj,kG_{j,k} and aj,ka_{j,k} appear on page 3, lines 132 and 133, respectively, without preceding definitions. These issues interrupt the reading flow and make the main results harder to assess on first reading.

Questions for authors

Clarification of the existing construction: Appendix A.6 gives an arithmetic complexity bound for obtaining the initial approximation. What is the overall arithmetic running time of the complete construction in Theorem 9, including the computation of all sampling scores? In particular, how does it depend on nn and dd when j,k,zj,k,z and the approximation parameters are fixed? This clarification would help assess the computational content of the existing constructive guarantee.

4 comments

We thank the reviewer for the comments.

(1) The running time for the construction of the coreset is Oj,k,z,δ(nd)O_{j,k,z,\delta}(nd) for constants j,k,z,δj, k, z, \delta, which is optimal since reading the input takes Ω(nd)\Omega(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.

(2) We have revised the exposition and the introduction of notation, including defining the symbols identified by the reviewer before their first use. We have also clarified the set-clustering formulation and the roles of coordinate patterns and active coordinate sets in the sensitivity analysis. We shall add a short conclusion discussing the remaining gaps and directions for future work.

Reviewer_GhoTOpenReview ↗

Thank you for the thoughtful response.

Thank you for your thoughtful response. I think your response to my first question largely addressed my concerns. Since you have made changes to the paper, could you please add a short conclusion section in the revised paper now? I think that would make the structure of this paper more complete.

Thanks for the suggestion. We have added a conclusion section in the revised manuscript.

Reviewer_GhoTOpenReview ↗

Thank you for the addition.

Thank you for your response and your quick addition. I would love to maintain my score and recommend this paper for acceptance.

Reviewer_dequOpenReview ↗
Rating
3
Confidence
4
Informativeness
2
Presentation
2
Soundness
3
Read review
Paper summary

The paper studies an axis-aligned (k,j,z)-projective clustering. This problem is a generalization of both center-based clustering (like k-means and k-median) and subspace approximation. The problem is the following:

  • We receive as input a set of points x_1, ... , x_n, and we'd like to understand these points by simpler objects.
  • The goal is to find a partition of the points into k parts, and for each part, find a j-dimensional affine space which best fits the points.

By 'best', we mean minimizes the sum of z-th power distances from points to the mapped subspace. Note, if k = 1, then this is a subspace approximation problem -- find the j-dimensional subspace which best fits the points (wrt traversed distance to subspace). If k > 1 but j = 0, then we are trying to partition the points and approximate the points by a fixed center point, like in k-median and k-means.

This work studies a natural approach toward solving this problem efficiently: data reduction, or coresets. Here, the question is to find a (weighted) subset of the points which approximates the cost of every possible (k,j,z)-clustering. If one can find coresets of size m, then the dependence on n becomes a dependence on m. Coresets have been widely studied for this problem, and a critical approach for solving these problems with provable guarantees. An important point, which makes coresets interesting is that (uniform) random sampling does not work. Instead, one needs to carefully choose the distribution from which to sample, so that one could 'union bound' over all potential (k,j,z)-clustering solutions (a la uniform convergence bounds). The canonical approach is called sensitivity sampling, which gives a score to each point measuring the maximum fractional contribution against any (k,j,z)-clustering solution, and the relevant parameter which translates to coreset size is called the total sensitivity.

While the above problem has been studied before, the issue is that (k,j,z)-clustering is known not to have a bounded total sensitivity once k, j are both larger than 2. This has caused work in the literature to consider a restricted version of the problem where a discretized set of potential projective clusterings is used. This paper asks: if instead of discretizing the set of potential projective clusterings, we only guaranteed bounds for axis-aligned subspaces (i.e., the j-dimensional subspace specified j coordinates which are 'free', and the remaining are fixed), then can one obtain total sensitivity bounds?

The paper gives an affirmative answer, and gives upper and lower bounds on the total sensitivity.

Theorem 1: Total sensitivity is exponential in j and k, and logarithmic in n. Importantly, there is no dependence on dimension d. Furthermore, such bounds are necessary.

Then, the paper studies the statistical question. Suppose one finds the cost of the optimal (k,j,z)-projective clustering on a sample of n points from a distribution, how far is it from the optimal cost on the entirety of the distribution (i.e., how much is lost by focusing on a small sample). Note, one could proceed via a VC dimension argument, which would effectively give bounds of the form kjd; however, one can do better. I believe such bounds were known for (k,j,z)-projective clustering, but the paper shows that axis-aligned (k,j,z)-projective clustering bounds are better.

Theorem 2: Up to a logarithmic term, the excess cost is on the order of sqrt{kj/n}.

Critical strengths

The paper gives two theorems showing that a twist to the (k,j,z)-projective clustering problem (i.e., settling for axis-aligned subspaces) makes a previously impossible task now possible -- namely, there is no need to discretize with axis-aligned subspaces. The paper does so via a bounding the total sensitivity and excess risk, and results in qualitatively tight dependencies.

I think considering the axis-aligned case is a natural one, when one has identified important features which are tied to each dimension.

Critical weaknesses

The paper is being sent to a machine learning conference, but does not do a good job appealing to the machine learning community. I think the work could do a better job explaining the relevance to machine learning, and even better, provide a working implementation that people could try.

Questions for authors

In what context and how is projective clustering solved currently 'in practice'. Is there some heuristic used which your sensitivity sampling analysis could speed up?

1 comment

We thank the reviewer for the comments. Below we answer the reviewer's question.

For axis-aligned projective clustering algorithms, the coreset can be used as a preprocessing step. Any heuristic for this problem that supports weighted instances can be run on the coreset rather than on all nn points, and the coreset guarantee ensures that the cost of every candidate solution is preserved within a factor of 1±ϵ1\pm\epsilon. Thus an α\alpha-approximate solution on the coreset is an (α(1+ϵ)/(1−ϵ))(\alpha(1+\epsilon)/(1-\epsilon))-approximate solution on the original data.

We emphasize, however, that the present construction is aimed at establishing compressibility rather than a practically optimized preprocessing algorithm. The running time for the construction is Oj,k,z,δ(nd)O_{j,k,z,\delta}(nd) for constants j,k,z,δj, k, z, \delta, which is optimal since reading the input takes Ω(nd)\Omega(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.

Reviewer_HkNSOpenReview ↗
Rating
4
Confidence
3
Informativeness
3
Presentation
3
Soundness
3
Read review
Paper summary

The paper studies a restriction of projective clustering where, instead of general affine subspaces, the cluster representatives are restricted to axis-aligned affine subspaces. Projective clustering has an extensive body of prior work, but existing coreset guarantees for the general problem require additional assumptions, such as polynomially bounded integer coordinates. In this work, the authors study whether restricting to axis-aligned subspaces allows these assumptions to be removed.

Their main contribution is a bound of (j+k)Oz(min⁡j,k)log⁡n(j+k)^{O_z(\min{j,k})}\log n on the total sensitivity independent of the ambient dimension and without assumptions on input coordinates. The main technical idea is to project the points onto a constant-factor approximate solution and exploit the axis-aligned structure to reduce the resulting sensitivity problem to queries involving individual coordinates. These are further reduced to a set-clustering problem, for which the authors establish refined sensitivity bounds. The resulting coreset guarantees then follow using standard sensitivity-sampling arguments.

The authors also provide lower bounds showing that the logarithmic dependence on nn and exponential dependence on min⁡j,k\min{j,k} are unavoidable, with nearly matching bounds in some parameter regimes.

Critical strengths
  1. The paper is well-written and technically strong.

  2. The upper and lower bounds together provide a comprehensive understanding of the sensitivity of axis-aligned projective clustering.

Critical weaknesses

None.

Questions for authors

None.

2 comments

We thank the reviewer for the positive assessment.

We would like to add that the paper has been strengthened to include the running time for coreset construction. The runtime is Oj,k,z,δ(nd)O_{j,k,z,\delta}(nd) for constants j,k,z,δj, k, z, \delta, which is optimal since reading the input takes Ω(nd)\Omega(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.

Thanks. I am happy to keep my positive assessment.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.