- 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 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
- 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.
- 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.
- 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
- 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 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 belongs to the cone of an adjacent face, and its cone coordinate sum is , 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.
- Lack of comparison with directly related reverse-convex optimization precedents. In Sec. 2.2, the authors treat 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?).
- The ablation study cannot isolate the contributions of key components. In Sec. 5, setting B uses , but setting C simultaneously changes it to 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.
- 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
- How do you resolve the shared-edge augmentation counterexample to Theorem 3 and ensure that successive augmentations preserve a valid simplicial complex?
- What are ISCA's specific methodological contributions beyond the conical relaxation and branching framework of Nagai and Kuno (2005)?
- Can you provide controlled ablations to isolate each component's contribution, particularly holding fixed when evaluating near-degeneracy handling and deferral?
- 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
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 , 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 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 (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 -HC, there are reverse-convex constraints on sign-free normals, coupled with binary assignment variables. ISCA keeps one partition of all directions per normal, starting from the cones of a regular simplex inscribed in the ball, whose relaxation is within a tight factor (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 , ISCA uses the cone-restricted lower bound (Proposition 10), specific to -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.
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 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 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):
| Variant | Solved | Both | Ratio |
|---|---|---|---|
| ISCA | 217 | ||
| , which ignores the cone, in place of the bound | 201 | 194 | 1.25 |
| the relaxation's in place of the bound | 141 | 138 | 2.58 |
| every face of the cone evaluated (no interlacing test) | 216 | 216 | 1.02 |
| without the rule on the relaxation's bound | 108 | 107 | 1.58 |
| neither the bound nor the rule (setting A) | 125 | 122 | 2.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.
Reply to Reviewer yBbn (1/3)
We thank the reviewer for the comments, which we answer in turn.
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:
The revision states Theorem 3 for 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.