acceptodds
Under review as a conference paper at ICLR 2027

ISCA: an Iterative Simplicial-Complex Approximation Method to Solve k-Hyperplane Clustering to Global Optimality

Abstract

We propose the Iterative Simplicial-Complex Approximation (ISCA) method to solve to global optimality the k-HC - the k-Hyperplane Clustering problem that asks to find k hyperplanes that minimize the sum of squared 2-norm (Euclidean) distances between each point and its closest hyperplane. ISCA is based on Spatial Branch and Bound (SBB) and approximates the infeasible unit ball of the hyperplane normals featured in k-HC from the inside with a growing simplicial complex, which is adaptively refined by gluing to it, via multiway branching, new simplices whose apexes are the radial projections onto the unit sphere of infeasible relaxation solutions. We prove that ISCA never discards a feasible solution, thereby certifying global optimality when its gap closes, and that the relaxation given by its initial simplex yields lower bounds within a tight multiplicative factor of 1/n^2. Experimentally, we show that ISCA improves upon the state of the art as the ambient dimension grows: on the instances with n >= 4, it reduces the mean optimality gap by 25% and it proves a nonzero lower bound on nine instances on which that of the state of the art is still zero, while the converse never occurs; with n in 5, 6, 7, it also solves more instances and is 1.7x faster in geometric mean.

Primary area:
optimization
Keywords:
hyperplane clustering, subspace clustering, unsupervised learning, global optimization, spatial branch-and-bound, nonconvex optimization, adaptive relaxations

Reviews

Among:
Shape:
1234this paper, Top 49%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.33 over 3 reviews, above 51% of the others.
Reviewer_yBbnOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper studies global optimization for k-hyperplane clustering under squared Euclidean distance and proposes ISCA to address the issue that conventional spatial branch-and-bound allows zero normal vectors, thereby producing zero lower bounds. The method starts from a regular simplex within the unit ball, performs multiway cone subdivision along the radial projection of the current infeasible relaxation solution, and constructs nested node regions with linear up-extension constraints. The paper provides a local feasibility covering, an initial 1/n21/n^2 approximation bound, and several implementation enhancements, including local Big-M, bound correction for near-degenerate nodes, and eigenvalue certification after fixing assignments. On 64 small synthetic instances, the method's advantages are mainly concentrated in the higher-dimensional, two-hyperplane case.

Critical strengths
  1. Reasonable motivation with concrete mathematical basis. Designing geometric branching for the relaxation degeneracy of reverse-convex ball constraints is easier to explain than merely proposing empirical branching rules.
  2. The local theory and initial approximation analysis are valuable. Theorem 2 provides verifiable arguments for the discrimination, covering, and nesting of degenerate subfaces. Theorem 7 shows correct multiplicative bounds and tightness examples.
  3. Some instances show significant gains, and failure ranges are disclosed. Tables 1–2 show order-of-magnitude time gains, and Sec. 5 also explicitly reports weaker performance.
Critical weaknesses
  1. The inductive invariant of Theorem 3 does not hold under the degenerate augmentation cases allowed in the paper. In lines 809–817, the authors take S∩cone⁡(F)=conv⁡(F∪{0})S\cap\operatorname{cone}(F)=\operatorname{conv}(F\cup\{0\}) as the invariant and infer from the "pairwise disjoint interiors" of the cones that it still holds after augmentation. However, for the regular case in Sec. 4.3.2, after radially projecting and augmenting one face at the midpoint of a shared edge, the new vertex u=(1,0,0)u=(1,0,0) belongs to the cone of an adjacent face, and its cone coordinate sum is 3>1\sqrt3>1, which immediately invalidates the equality. When continuing to augment the adjacent face in the other direction along the same shared edge, the two newly added tetrahedra can intersect in a two-dimensional region that is not a common face, violating the definition of a simplicial complex in Sec. 2.
  2. Lack of comparison with directly related reverse-convex optimization precedents. In Sec. 2.2, the authors treat U(F)={Eλ:λ≥0,1⊤λ≥1}\mathcal U(F)=\{E\lambda:\lambda\ge0,\mathbf1^\top\lambda\ge1\} as an important component of the method, but the 2005 Nagai–Kuno report (Hidetoshi, Nagai, and K. U. N. O. Takahito. "A conical branch-and-bound algorithm for a class of reverse convex programs." Technical Report of Department of Computer Science (2005): 1-9.) already had an equivalent form. This paper does not discuss this cone-branch optimization line of work. The authors should clarify which parts constitute their specific contribution (projection-driven subdivision, degeneracy handling, multi-normal-vector combination, or the implementation of k-HC?).
  3. The ablation study cannot isolate the contributions of key components. In Sec. 5, setting B uses ρ=0.7\rho=0.7, but setting C simultaneously changes it to ρ=0.9\rho=0.9 and adds near-degeneracy handling and a deferral strategy. Subsequently, based on the per-instance best envelope of A, A/B, and A/B/C, it is claimed that both components contribute. Such a design cannot distinguish a looser Big-M cut-adding threshold from the near-degeneracy strategy, nor can it quantify the contributions of the initial rotation, random branching, or fixed-assignment eigenvalue closure.
  4. Reasonableness of cross-machine time conversion. MultiNorm runs on Xeon 8260, while some ISCA experiments run on the faster Xeon 8358. Therefore, the authors tested both machines using the same MultiNorm search tree and found that the faster machine is about 1.36–1.52 times faster, so they uniformly multiplied the experimental times on the faster machine by 1.4. However, this approach relies on a presupposition, i.e., the speedup ratio for ISCA from changing hardware is close to that for MultiNorm. This is because, compared with MultiNorm, ISCA also performs eigenvalue decomposition, LU/SVD matrix computations, and arbitrary-precision integer arithmetic when necessary. How much these operations can be accelerated on the new CPU is unknown. Therefore, the factor 1.4 obtained by calibrating only with MultiNorm cannot accurately convert ISCA's time.
Questions for authors
  1. How do you resolve the shared-edge augmentation counterexample to Theorem 3 and ensure that successive augmentations preserve a valid simplicial complex?
  2. What are ISCA's specific methodological contributions beyond the conical relaxation and branching framework of Nagai and Kuno (2005)?
  3. Can you provide controlled ablations to isolate each component's contribution, particularly holding ρ\rho fixed when evaluating near-degeneracy handling and deferral?
  4. Can you validate the 1.4 time-conversion factor using ISCA-specific cross-machine benchmarks, or reproduce the main comparisons on identical hardware?
3 comments
AuthorsOpenReview ↗

Reply to Reviewer yBbn (1/3)

We thank the reviewer for the comments, which we answer in turn.

W1 / Q1. The inductive invariant of Theorem 3 does not hold under the degenerate augmentation cases allowed in the paper. [...] How do you resolve the shared-edge augmentation counterexample to Theorem 3 and ensure that successive augmentations preserve a valid simplicial complex?

Thanks for the careful check. The counterexample concerns degenerate augmentations, which ISCA never makes, and it affects neither the statement of Theorem 3 nor the validity of ISCA:

  • ISCA never makes a degenerate augmentation. When the ray through the relaxation solution meets the facet on or very close to its relative boundary, ISCA takes the normalized barycenter of the facet as the new vertex (Section 4). With nondegenerate augmentations, each new simplex meets the complex only in its base facet, and the glued simplices form a simplicial complex.
  • The validity of ISCA (Remark 4) uses Theorem 3 only at the root, where no augmentation has taken place, and, at every geometric branching, Theorem 2, which concerns a single cone.
  • With degenerate augmentations too, Theorem 3 holds, since its proof uses the invariant only on the interiors of the cones. There it still holds, S∩int⁡cone⁡(F)=conv⁡(F∪{0})∩int⁡cone⁡(F)\mathcal S\cap\operatorname{int}\operatorname{cone}(F)=\operatorname{conv}(F\cup\lbrace 0\rbrace)\cap\operatorname{int}\operatorname{cone}(F), as each new simplex lies in a closed cone that does not meet the interior of any other cone. The union of the up-extensions is still the weak complement of S\mathcal S, and their interiors are still disjoint.

The revision states Theorem 3 for S\mathcal S the union of the glued simplices and the facets the augmentations produce, its proof treats both cases, and Section 2 says when the glued simplices form a simplicial complex.

AuthorsOpenReview ↗

Reply to Reviewer yBbn (2/3)

W2 / Q2. Lack of comparison with directly related reverse-convex optimization precedents. [...] What are ISCA's specific methodological contributions beyond the conical relaxation and branching framework of Nagai and Kuno (2005)?

Thanks for the pointer. Both methods belong to conical branch and bound (Tuy, 1991; Horst and Tuy, 1996): they partition the space into cones from a point inside the excluded convex set, bound each cone through the set U(F)U(F), the natural convex relaxation of a reverse-convex constraint over a cone, and refine the partition by adding generators on the boundary of that set. They differ in how they branch, in the problem they solve, and in how they bound:

  • Nagai and Kuno bisect the longest edge of the cone, which gives two children whatever the relaxation solution. ISCA splits the cone along the ray through the relaxation solution, into up to nn children, each of which cuts this solution off. The refinement thus goes where the relaxation violates the norm constraint, and the facets shrink there, which tightens the relaxation by the factor 1−h2/21-h^2/2 (Proposition 8). Theorem 2 characterizes the degenerate children of this split exactly and shows that dropping them loses no solution.
  • Nagai and Kuno solve a linear program with one reverse-convex constraint; in kk-HC, there are kk reverse-convex constraints on sign-free normals, coupled with binary assignment variables. ISCA keeps one partition of all directions per normal, starting from the n+1n+1 cones of a regular simplex inscribed in the ball, whose relaxation is within a tight factor 1/n21/n^2 (Theorem 7), and interleaves geometric branching with branching on the assignment, in an LP-based spatial branch and bound with finite termination (Proposition 12).
  • Beyond U(F)U(F), ISCA uses the cone-restricted lower bound (Proposition 10), specific to kk-HC: it keeps the norm constraint exact within the cone, uses the points already assigned to each hyperplane, and is computed exactly through eigenvalue problems on the faces of the cone. With it, ISCA solves 555 of the 789 instances instead of 344, and is 4.27 times faster on those both solve.

We made this clearer in the revised version of the paper, which cites the report together with this line of work.

AuthorsOpenReview ↗

Reply to Reviewer yBbn (3/3)

W3 / Q3. The ablation study cannot isolate the contributions of key components. [...] Can you provide controlled ablations to isolate each component's contribution, particularly holding ρ\rho fixed when evaluating near-degeneracy handling and deferral?

Thanks for the comment. Yes: we replaced the per-instance envelope with controlled ablations that change one ingredient at a time, in a first pass with a time limit of 120 s and one thread per run. They show that the speed of ISCA comes from the cone-restricted bound and its branching rule.

Settings B and C added two ingredients to setting A, which is ISCA without the cone-restricted bound: node-local Big-M constants, and the treatment of nearly degenerate facets with its deferral. Added one at a time to setting A on the 64 benchmark instances, with ρ\rho fixed at 0.7 and then at 0.9, each changes the geometric mean time by a factor between 0.96 and 1.02, and every variant solves between 19 and 21 instances. We therefore dropped both from ISCA and from the revised paper.

Removing the initial rotation, or taking the barycentric apex at every geometric branching, changes little as well: 30 and 31 instances solved against 32, with time ratios of 0.99 and 1.05 (Appendix D).

The cone-restricted bound and its rule, instead, make the difference: within 7,200 s, ISCA solves 20 more benchmark instances than setting A and is 4.17 times faster. The revised paper now reports the ablation of these two new components, on 470 instances, in Section 5 (Table 2) and Appendix D (Table 16); each part is compared with ISCA on the instances both solve (ratio of the geometric mean times; above 1: ISCA faster):

VariantSolvedBothRatio
ISCA217
λmin⁡(CPj)\lambda_{\min}(C_{P_j}), which ignores the cone, in place of the bound2011941.25
the relaxation's βjU\beta^U_j in place of the bound1411382.58
every face of the cone evaluated (no interlacing test)2162161.02
without the rule on the relaxation's bound1081071.58
neither the bound nor the rule (setting A)1251222.82

Without the interlacing test, the search is the same and only slightly slower.

Geometric branchings are 1.4% of the branchings of ISCA on the benchmark. The eigenvalue closure at the nodes with a fixed assignment guarantees that ISCA terminates (as we said to reviewer 8LB8); it is invoked in 38 of the 64 runs and closes every node on which it is invoked.

W4 / Q4. Reasonableness of cross-machine time conversion. [...] Can you validate the 1.4 time-conversion factor using ISCA-specific cross-machine benchmarks, or reproduce the main comparisons on identical hardware?

Thanks for the comment. The revised version reproduces all comparisons on identical hardware, computing nodes of a single type (two AMD EPYC 9654 CPUs per node), with one thread per run, the same limits for every method, and the runs of all the methods on an instance in the same job; no conversion factor is used.

Reviewer_8LB8OpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper proposes an exact global-optimization method for kk-hyperplane clustering. The method addresses weak relaxations of the reverse-convex normal constraints by approximating the infeasible unit ball from inside using an adaptively refined simplicial complex. These refinements are incorporated into spatial branch and bound. The authors establish coverage and nesting properties of the branching regions and prove a tight initial-relaxation bound:

\le \mathrm{OPT}_{\Delta} \le \mathrm{OPT},$$ where $n$ is the ambient dimension. Experiments indicate improvements on some higher-dimensional instances with few hyperplanes. Strengths: 1. Refining the approximation in directions exposed by relaxation solutions is a meaningful alternative to using a fixed polyhedral approximation. 2. The treatment of degenerate facets, coverage of feasible solutions, and nesting of child regions supports the validity of the approach. 3. Node-local Big-$M$ constants, corrections for discarded nearly degenerate nodes, and exact-arithmetic eigenvalue certificates show considerable implementation effort. Weakness: 1. Section 5 and Tables 1–2 select the best ISCA configuration among A/B/C separately for each test instance, whereas the baseline uses one configuration. 2. Some runs use different processors and substantially different memory allocations, followed by a $1.4\times$ runtime correction. 3. MultiNorm performs better overall on LowDim and HighDim, while ISCA’s strongest improvements concentrate on higher-dimensional instances with $k=2$. All benchmarks are small synthetic low-noise instances. In addition, the initial $1/n^2$ relaxation coefficient does not improve the earlier MultiNorm coefficient of $1/\sqrt n$; the contribution instead concerns adaptive refinement and branching structure. This tradeoff deserves a more in-depth discussion.
Critical strengths
  1. Refining the approximation in directions exposed by relaxation solutions is a meaningful alternative to using a fixed polyhedral approximation.

  2. The treatment of degenerate facets, coverage of feasible solutions, and nesting of child regions supports the validity of the approach.

  3. Node-local Big-MM constants, corrections for discarded nearly degenerate nodes, and exact-arithmetic eigenvalue certificates show considerable implementation effort.

Critical weaknesses
  1. Section 5 and Tables 1–2 select the best ISCA configuration among A/B/C separately for each test instance, whereas the baseline uses one configuration. These results characterize the attainable performance of a configuration portfolio, rather than that of a predetermined algorithm. On SuperHighDim, configuration A solves only three instances, compared with eight after per-instance selection. This difference materially affects the conclusions.

  2. Some runs use different processors and substantially different memory allocations, followed by a 1.4×1.4\times runtime correction. Although this is disclosed, calibration using identical MultiNorm search trees may not accurately capture ISCA’s different mixture of linear algebra, exact arithmetic, and memory access.

  3. MultiNorm performs better overall on LowDim and HighDim, while ISCA’s strongest improvements concentrate on higher-dimensional instances with k=2k=2. All benchmarks are small synthetic low-noise instances. In addition, the initial 1/n21/n^2 relaxation coefficient does not improve the earlier MultiNorm coefficient of 1/n1/\sqrt n; the contribution instead concerns adaptive refinement and branching structure. This tradeoff deserves a more in-depth discussion.

Questions for authors
  1. What are the complete results for fixed configurations A, B, and C on identical hardware? Can configuration selection be specified without observing test-instance outcomes?

  2. Beyond certifying optimality when the gap closes, what termination or convergence conditions hold for the implemented refinement and branching strategy?

  3. Can the evaluation include other strong configurations from the preceding work, together with appropriately sized real-data or varying-noise instances?

5 comments
AuthorsOpenReview ↗

Reply to Reviewer 8LB8 (1/3)

We thank the reviewer for the comments, which we answer in turn.

W1. Section 5 and Tables 1–2 select the best ISCA configuration among A/B/C separately for each test instance, whereas the baseline uses one configuration. These results characterize the attainable performance of a configuration portfolio, rather than that of a predetermined algorithm. On SuperHighDim, configuration A solves only three instances, compared with eight after per-instance selection. This difference materially affects the conclusions.

Thanks for the comment. We reran all the experiments, on a much larger set of instances: the 64 of the submission and 725 new ones, among which real-world data and point sets extracted from images. The revised version no longer selects anything per instance: ISCA is now a single algorithm, run the same way on every instance, with a new lower bound (the cone-restricted bound, Proposition 10). To answer the point directly, we also ran settings A, B and C of the submission, each on its own, on every instance. These runs, and the runs of ISCA in this comparison, used 8 GB of memory per run; their rerun with 32 GB, the memory of all our other results, is under way, and we will post its results as soon as it completes. ISCA solves more instances than each of them on every instance set: 552 of 789, against 329, 332 and 326; on SuperHighDim, the reviewer's example, 12, against 3, 4 and 5. Instances solved within 7,200 s:

Instance set#ISCAABC
High-noise benchmark6448262629
Low-noise benchmark256176999696
Balanced benchmark320226126131124
Isotropic-noise6348403939
UCI4434222423
Images4220161615
All789552329332326

On the instances that both solve, ISCA is also about four times faster than each of them: 3.87, 3.88 and 3.97 times in geometric mean.

W2. Some runs use different processors and substantially different memory allocations, followed by a 1.4× runtime correction. Although this is disclosed, calibration using identical MultiNorm search trees may not accurately capture ISCA's different mixture of linear algebra, exact arithmetic, and memory access.

Thanks for the comment. No conversion remains. Every method now runs on computing nodes of a single type (two AMD EPYC 9654 CPUs per node), with one thread per run, the same time and memory limits, and the runs of all the methods on an instance in the same job.

AuthorsOpenReview ↗

Reply to Reviewer 8LB8 (2/3)

W3. MultiNorm performs better overall on LowDim and HighDim, while ISCA's strongest improvements concentrate on higher-dimensional instances with k=2k=2. All benchmarks are small synthetic low-noise instances. In addition, the initial 1/n21/n^2 relaxation coefficient does not improve the earlier MultiNorm coefficient of 1/n1/\sqrt{n}; the contribution instead concerns adaptive refinement and branching structure. This tradeoff deserves a more in-depth discussion.

Thanks for the comment. Over all 789 instances, ISCA solves the most, 555, against 508, 442 and 405 for MultiNorm with ℓ1, ℓ∞ and ℓ1+ℓ∞, and it is 1.41, 1.30 and 3.34 times faster in geometric mean on the instances both solve. Its advantage grows with the dimension, where exact methods struggle most:

High-noise benchmark, within 7,200 sISCAMultiNorm ℓ1MultiNorm ℓ∞MultiNorm ℓ1+ℓ∞
LowDim (16)15151516
HighDim (24)19231614
SuperHighDim (24)12845
n≥5n\ge5 (28)161278

With n≥5n\ge5, ISCA is also 3.00 times faster than MultiNorm with ℓ1 on the 12 instances both solve.

The submitted benchmark is in fact not low-noise: its noise has a standard deviation 8.4 to 10 times the side of the box in which the points are drawn, which the revision now states, calling it the high-noise benchmark. We added 725 instances of comparable sizes: real-world data from UCI, point sets extracted from images, and synthetic instances with a truly low noise, down to 390 times below the benchmark's.

On the coefficient: the factor 1/n21/n^2 (Theorem 7) holds at the root only. ISCA's relaxation tightens with every refinement: a node whose facets have diameter at most hh has a relaxation within a factor 1−h2/21-h^2/2 (Proposition 8), which tends to 1 as the facets shrink, and is tighter than any fixed relaxation with factor c<1c<1, MultiNorm's included, as soon as h2≤2(1−c)h^2\le2(1-c). MultiNorm's approximation stays fixed for the whole search; ISCA's becomes as tight as needed where the search goes.

AuthorsOpenReview ↗

Reply to Reviewer 8LB8 (3/3)

Q1. What are the complete results for fixed configurations A, B, and C on identical hardware? Can configuration selection be specified without observing test-instance outcomes?

Thanks for the comment. Yes, and yes. A, B and C, each fixed, ran on the same nodes as every other method, on every instance; the table in our answer to W1 gives them per instance set. The configuration of ISCA is fixed in advance and is the same on every instance: no choice depends on test-instance outcomes.

Q2. Beyond certifying optimality when the gap closes, what termination or convergence conditions hold for the implemented refinement and branching strategy?

Thanks for the comment. ISCA terminates finitely with a certified optimum when the number of geometric branchings per normal is bounded along every path of the tree (Proposition 12): assignment branching is finite, and a node at which every assignment is fixed is closed exactly, by the closed-form eigenvector solution and its exact-arithmetic certificate (Section 4). The implementation enforces such a bound with a cap of GG geometric branchings per normal on every path (Appendix D). No run of the main comparison exceeds 42 geometric branchings on one normal along a path, and a cap that is never reached changes no decision of ISCA. Each reported run is thus a run of ISCA with the cap G=43G=43, to which Proposition 12 applies (Appendix F).

Q3. Can the evaluation include other strong configurations from the preceding work, together with appropriately sized real-data or varying-noise instances?

Thanks for the comment. Yes to both.

MultiNorm now runs in each of its three configurations, ℓ1, ℓ∞ and ℓ1+ℓ∞, on every instance; the submission compared with ℓ1+ℓ∞ only.

Besides the 64 instances of the submission, which we now call the high-noise benchmark, we added 725 instances of comparable sizes (Appendix C), three families of which vary the noise:

  • 44 real-world instances, obtained by downsampling 9 UCI data sets (MAGIC Gamma Telescope, Skin Segmentation, Breast Cancer Wisconsin Diagnostic and Prognostic, Occupancy Detection, Rice, Liver Disorders, Ionosphere, and Iris) to mm from 12 to 28, nn from 2 to 7 and kk from 2 to 4;
  • 42 point sets extracted from images, with n=2n=2;
  • the low-noise benchmark, 256 instances: the shapes and the generator of the benchmark, with the noise turned down to as little as 1/391/39 of the side of the box, 390 times below the benchmark's;
  • the balanced benchmark, 320 instances: the same shapes with an equal share of the points for every hyperplane, with the noise from 1/391/39 of the side of the box up to the benchmark's;
  • 63 isotropic-noise instances: 21 small shapes, each at three noise levels, with the noise added to every coordinate.

Instances solved within 7,200 s:

Instance set#ISCAMultiNorm ℓ1MultiNorm ℓ∞MultiNorm ℓ1+ℓ∞
High-noise benchmark6446463535
Low-noise benchmark256178171147136
Balanced benchmark320228231203178
Isotropic-noise6348151418
UCI4435302724
Images4220151614
All789555508442405

ISCA solves the most instances overall, and the most on the low-noise benchmark, the real-world data, the images and the isotropic-noise instances; on the UCI instances, it is also 4.96, 4.01 and 11.54 times faster than MultiNorm with ℓ1, ℓ∞ and ℓ1+ℓ∞ in geometric mean on the instances both solve.

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

This paper proposes Iterative Simlicial-Complex Approximation (ISCA), a spatial branch-and-bound method for solving the k-hyperplane clustering problem to global optimality. The method iteratively approximates the infeasible unit ball using simplicial complexes and adaptively refines the relaxation based on intermediate solutions. The authors provide theoretical guarantees for the validity of the branching scheme and the quality of the relaxation. Experimental results demonstrate improved optimality gaps and computational efficiency over an existing method, particularly for higher-dimensional instances with a small number of hyperplanes.

Critical strengths
  1. The paper proposes a novel geometry-based branch-and-bound method that adaptively refines the relaxation of nonconvex constraints, providing an interesting and well-motivated approach to k-hyperplane clustering.
  2. The method is supported by rigorous theoretical analysis, including global optimality guarantees and relaxation bounds. Experimental results demonstrate its advantages on higher-dimensional instances with a small number of hyperplanes.
Critical weaknesses
  1. The proposed method provides an interesting geometric relaxation of the nonconvex norm constraints, but its relationship to the overall difficulty of k-hyperplane clustering remains insufficiently understood. The weak relaxation of the assignment variables may dominate the optimization process, limiting the benefits of geometric refinement.
  2. Does achieving global optimality in k-hyperplane clustering necessarily lead to more meaningful clustering results? Can the authors demonstrate whether the globally optimal solutions provide better recovery of the underlying hyperplanes or cluster assignments compared with conventional heuristic methods?
  3. What makes the relaxation-driven geometric refinement particularly effective? While the paper establishes that smaller simplicial facets lead to tighter relaxations, it remains unclear whether the proposed refinement strategy systematically promotes this improvement or whether its effectiveness depends heavily on the structure of the optimization problem.
Questions for authors

Please see the weaknesses

3 comments
AuthorsOpenReview ↗

Reply to Reviewer ckZd (1/3)

We thank the reviewer for the comments, which we answer in turn.

W1. The proposed method provides an interesting geometric relaxation of the nonconvex norm constraints, but its relationship to the overall difficulty of k-hyperplane clustering remains insufficiently understood. The weak relaxation of the assignment variables may dominate the optimization process, limiting the benefits of geometric refinement.

Thanks for the comment. To address it, we added the cone-restricted lower bound (Proposition 10), the main methodological change of the revision. The reviewer is correct in saying that the assignment aspect leads to a weak relaxation as long as the xx variables are fractional. The new cone-restricted lower bound is both geometric and combinatorial, and it does not depend on the fractional part of the assignment. At each node and for each hyperplane jj, we obtain it by computing the smallest cost of fitting the points already assigned to jj with a hyperplane whose normal wjw_j has unit 2-norm and lies in the cone generated by the node's facet FjF_j, namely, βj=min⁡{u⊤CPju: u∈cone⁡(Fj), ∥u∥2=1}\beta_j=\min\lbrace u^\top C_{P_j}u:\ u\in\operatorname{cone}(F_j),\ \lVert u\rVert_2=1\rbrace, where CPjC_{P_j} is the scatter matrix of those points. ISCA computes it exactly: its minimizer is an eigenvector of the smallest eigenvalue of CPjC_{P_j} restricted to the span of some face of the cone, so ISCA solves one eigenvalue problem per face. The new bound (which links the assignment and the geometry) grows with every assignment decision, like a combinatorial bound, and with every geometric branching, as the cone narrows, and it keeps the norm constraint exact within the cone.

All the methods were run again on a much larger set of instances, relying on computing nodes of a single type (two AMD EPYC 9654 CPUs per node), with one thread per run and one configuration per method, the same on every instance. On these machines and within 7,200 s, ISCA solves 555 of the 789 instances with the new bound and 344 without it. Of these instances, 218 are solved to optimality only when the bound is adopted, and 7 only without it. On the 337 instances that both solve, ISCA with the new bound is 4.27 times faster in geometric mean and explores 3.25 times fewer nodes.

AuthorsOpenReview ↗

Reply to Reviewer ckZd (2/3)

W2. Does achieving global optimality in k-hyperplane clustering necessarily lead to more meaningful clustering results? Can the authors demonstrate whether the globally optimal solutions provide better recovery of the underlying hyperplanes or cluster assignments compared with conventional heuristic methods?

Thanks for the comment. We ran two new tests, which show that the optimal solutions found with ISCA (Test 1) recover the hyperplanes that generated the data better than kk-plane clustering (Bradley and Mangasarian, 2000), and (Test 2) predict points not used in the fit better.

(Test 1) The first test is a recovery experiment on low-noise instances (on high-noise instances, the optimal hyperplanes are not the ones that we used to generate the data, whatever the method that finds them). We built them either by running the generator of Amaldi and Coniglio (2013) with the noise at σ=1/39\sigma=1/39 of the side of the box in which the points are drawn (the low-noise benchmark), or by also giving every hyperplane an equal share of the points, at least n+1n+1 (the balanced benchmark; Appendix C.1). On every instance on which ISCA certifies the optimum, we measured the percentage of points that end up in their original cluster, and the angle between each original hyperplane and the fitted one:

σ=1/39\sigma=1/39points in their original cluster (%), optimumsame, kk-planemedian angle to the original hyperplane (°), optimumsame, kk-plane
low-noise benchmark75.669.73.710.1
balanced benchmark80.566.35.941.3

On both sets, the optimal solution found with ISCA assigns more points to their original cluster than kk-plane clustering, and its hyperplanes lie closer to the original ones. The margin is largest on the balanced benchmark, where the optimum found with ISCA assigns 14.2 percentage points more of the points correctly on average, and its median angle is 5.9° against 41.3°.

(Test 2) The second test is an 80%/20% training/testing experiment, which measures how well the hyperplanes found by an algorithm fit points that were not seen by that algorithm. Five random splits of each instance of the high-noise benchmark, UCI, the images, and the balanced benchmark at σ=0.1\sigma=0.1, 1 and 10 give 1,710 instances (Appendix C.2). We clustered the 80% with ISCA (within 7,200 s) and with kk-plane clustering from one start and from 100 starts, and measured the mean squared distance of the testing (held-out) points to the nearest hyperplane. On the synthetic instances, which have generator hyperplanes, we also drew 1,000 fresh points from those hyperplanes and scored them. The error of kk-plane clustering divided by that of ISCA (shifted geometric mean; above 1: ISCA predicts better) is:

points scoredinstanceskk-plane, 1 startkk-plane, 100 starts
the held-out 20%1,7101.541.16
the held-out 20%, every cluster of every method with at least nn points1,4181.471.13
1,000 fresh points from the generator hyperplanes (instances of the previous row that have them)1,0991.341.11

In every case, the solutions found by ISCA predict new points better than kk-plane clustering, both from one start and from 100: they generalize better, mainly because they avoid the large errors of poor local optima.

AuthorsOpenReview ↗

Reply to Reviewer ckZd (3/3)

W3. What makes the relaxation-driven geometric refinement particularly effective? While the paper establishes that smaller simplicial facets lead to tighter relaxations, it remains unclear whether the proposed refinement strategy systematically promotes this improvement or whether its effectiveness depends heavily on the structure of the optimization problem.

Thanks for the comment. The refinement is effective because it captures the geometry of the problem directly. The difficulty of kk-HC is the requirement that every normal have unit norm, i.e., lie outside the open unit ball. ISCA approximates this infeasible ball from the inside, by simplices whose vertices lie on its boundary, and every refinement adds a vertex where the current relaxation solution violates the requirement. Where the search refines it, the approximation converges to the ball itself, so the relaxation converges to the exact problem there.

In ISCA, every geometric branching splits the facet of a node into facets whose cones partition its cone and whose up-extensions lie in its up-extension (Theorem 2(iii)). The relaxation of every child is thus never looser than that of its parent, and the cone-restricted bound (Proposition 10) never smaller. How much tighter is controlled by the size of the facets: for a fixed assignment, the relaxation of a node is within a factor 1−12h21-\frac12h^2 of the optimal value in its region, where hh bounds the diameters of its facets (Proposition 8), and this factor tends to 1 as the facets shrink.

Refining a relaxation where its solution violates the original constraints is the central mechanism of global optimization by branch and bound (Horst and Tuy, 1996); ISCA applies it to the reverse-convex norm constraint of kk-HC, which the usual spatial branch and bound handles poorly, as its relaxation admits a zero normal vector. What depends on the data, as for any relaxation in branch and bound, is how many refinements are needed before the bound closes the gap.

Comments on the paper

1 comment
AuthorsOpenReview ↗

General comment

To the Area Chair, the Senior Area Chair, the Program Chairs, and all reviewers

We thank the three reviewers for their careful reading. We have uploaded a revised version, in which all new text is in blue. Its main changes:

  1. The revised ISCA adds a new lower bound, the cone-restricted bound (Proposition 10). At each node and for each hyperplane, it is the smallest cost of fitting the points already assigned to it with a unit normal in the cone of the node's facet, computed exactly through eigenvalue problems on the faces of the cone. Unlike the relaxation of the node, it does not vanish while the assignment is fractional. With it, ISCA solves 555 of the 789 instances instead of 344, and is 4.27 times faster on the 337 both solve. The paper's ablation isolates its parts (Table 2; ckZd W1, yBbn W3).
  2. All the experiments were run again on computing nodes of a single type (two AMD EPYC 9654 CPUs per node), with one thread per run, a time limit of 7,200 s and 32 GB of memory per run, one configuration per method, the same on every instance, and every run reported: no time conversion and no per-instance selection remain (8LB8 W1–W2, yBbn W4). A run counts as solved when the relative gap between the value of a solution of kk-HC found by the run and its lower bound is at most 10−610^{-6}, for every method (Appendix E).
  3. MultiNorm is reported in each of its three configurations. Instances solved within 7,200 s:
Instance set#ISCAMultiNorm ℓ1MultiNorm ℓ∞MultiNorm ℓ1+ℓ∞
High-noise benchmark6446463535
Low-noise benchmark256178171147136
Balanced benchmark320228231203178
Isotropic-noise6348151418
UCI4435302724
Images4220151614
All789555508442405

On the instances both solve, ISCA is 1.41, 1.30 and 3.34 times faster in geometric mean.

  1. Besides the 64 instances of the submission, which we now call the high-noise benchmark (its noise is 8.4 to 10 times the side of the box in which the points are drawn), we added 725 instances of comparable sizes (Appendix C): 44 real-world instances from 9 UCI data sets, 42 point sets extracted from images, the low-noise and the balanced benchmarks on the shapes of the original one, with noise down to 390 times below its own, and 63 isotropic-noise instances (ckZd W2, 8LB8 Q3).
  2. Two new tests show that the optimum is worth computing: at low noise, it recovers the hyperplanes that generated the data better than kk-plane clustering, and it predicts points not used in the fit better (Appendices C.1 and C.2; ckZd W2).
  3. ISCA no longer uses node-local Big-M constants or the treatment of nearly degenerate facets, the ingredients of settings B and C of the submission: their ablation, given in our reply to yBbn, shows no measurable gain, and the revised paper no longer describes them.
  4. Theorem 3 now covers degenerate augmentations (yBbn W1); the paper discusses conical branch and bound, with Nagai and Kuno (2005) (yBbn W2); Proposition 12 gives finite termination with a cap on geometric branchings, which covers every reported run (8LB8 Q2).

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.