- Rating
- 3(+2)
- Confidence
- 3(−1)
- Informativeness
- 2
- Presentation
- 2
- Soundness
- 1
Read review
Paper summary
This paper studies the computability of SOSPs for NMF. Existing saddle-escaping algorithms for constrained optimization, such as SNAP and MWU, cannot be applied directly to standard NMF because its feasible set is unbounded, and its objective thus lacks a globally Lipschitz gradient and Hessian. To address this issue, the paper restricts the problem to an -norm sphere (i.e., simplex-NMF), yielding a compact feasible region on which the required smoothness properties hold. Because the original NMF problem admits FOSP-symmetry under the action of the positive diagonal group (which essentially only rescales the coordinates), the set of all FOSPs admits an orbit decomposition, with each orbit consisting entirely of FOSPs. (At this point, I'm not sure whether the decomposition can be made finite and, if so, whether the resulting decomposition constitutes a Whitney/Verdier stratification.) The very ingenious idea of the paper is to let the simplex constraint cut all FOSP-orbits transversely (there is no need to cut SOSP- or higher-order stationary orbits separately, as they form subfamilies of the FOSP-orbits), and the paper establishes a uniform upper bound on the tangency levels of these orbits (Lemma 4.3). This establishes a connection between the two optimization landscapes, yielding critical-value inclusion and stationarity transfer properties that are then "combined" with existing algorithmic results to obtain the desired SOSP-computability guarantees.
I believe that the paper presents an excellent idea. However, the fundamental concerns to be detailed in the "Weaknesses" section lead me to recommend a strong reject at this stage. I sincerely hope that the authors could address these concerns convincingly and explain how the paper could be revised within the constraints of this conference, so that I can raise my score.
Critical strengths
- The paper presents an excellent idea.
- The analysis in this paper makes a useful contribution to the field.
Critical weaknesses
- There is a substantial mismatch between what the paper establishes and the algorithmic results it invokes. Using the terminology of the SNAP paper, if I understand correctly, the paper (under review) proves the transfer property for SOSP2, while the cited guarantees for both SNAP and MWU concern SOSP1. These notions can differ even for NMF. Consider, e.g.,
Questions for authors
- It would be illuminating to mention that NMF can exhibit even spurious local minima, not merely spurious SOSPs; see "Zhang, R. Y. (2026). Nonnegative low-rank matrix recovery can have spurious local minima. Optimization Letters, 20(4), 683-704."
- It would also be helpful to note that NMF is already strongly NP-hard even at rank two; see https://arxiv.org/abs/2610.21874
3 comments
answers to questions
We thank the reviewer for appreciating our idea (calling it "excellent"), and for their careful review. You raised two important points that require attention, and that we address below:
1. Comment on SOSP1 versus SOSP2:
We thank the reviewer for their comment and we will clarify SOSP1 and SOSP2. You are correct in the example you provided, however the structural landscape transfer does extend to SOSP1, as we should have clarified. Our Lemma 4.5 used only support-preserving directions, so it also establishes that a simplex SOSP1 satisfies the original NMF first-order conditions. Under our stated threshold for the constant , any support preserving negative-curvature direction for the original NMF can be adjusted by adding a tangent direction generated by the product preserving scaling symmetry to satisfy the simplex equality. Crucially, at this first-order stationary point, the adjustment preserves the support restrictions and the Hessian quadratic form, as in Lemma A.7, so the resulting direction still has negative curvature.
We will include this observation and distinguish SOSP1-to-SOSP1 transfer from SOSP2-to-SOSP2 transfer. Our MWU consequence concerns SOSP1 of the original NMF, with the convergence premise in Corollary A.8 given explicitly. We will not infer SOSP2 from a SOSP1 guarantee or assume strict complementarity.
2. Comment on approximate stationarity:
We agree that exact transfer alone does not establish quantitative approximate transfer. Again, we will make the distinction with SOSP1 and SOSP2, and we will restrict the finite-time SNAP/SNAP+ guarantees to approximate SOSP1 of the Simplex-NMF. In the Appendix, we will correct Definition A.5 accordingly, remove the broader original-NMF claim from Appendix A.3 (and our abstract), and make Theorem 3 consistent.
These corrections preserve our geometric reduction, while narrowing only the algorithmic consequences.
Of course, we will include the two suggested references and discuss them.
Overall, we truly appreciate your willingness to reconsider your score, and hope that this addressed your concerns. We thank you for pointing out the above, and we still think the main essense of our result on the landscape analysis is interesting and novel. Of course, feel free to let us know of any other question.
Thanks so much for your responses. I'm sorry for my late response, but I also have to take care of my own submissions on this final rebuttal day.
The switch to SOSP1-to-SOSP1 transfer is indeed what I had in mind earlier. However, this fix nonetheless weakens your main computability results, which now concern SOSP1, a weaker notion than SOSP2. Moreover, the approximate computability guarantees now apply only to simplex-NMF, rather than original NMF. I thus can't 100% recommend acceptance.
I've raised my score to 3 (in fact, I'm more inclined to give 3.5, but there is no such an option!). At the same time, I need to lower my confidence slightly, as the revision appears to require a few new technical details that I won't have opportunity to review (still, I trust the authors will do an excellent job with the revision). But I guess your current scores should already suffice for an acceptance at this conference.
Anyway, I fully agree that the essence of your paper is interesting and novel, and I believe your paper still makes a substantial contribution to the field even in this weaker form. I like your paper :)
As the rebuttal ddl approaches, could the authors please respond to my concerns? I'd really like to recommend acceptance, but I just can't persuade myself to do so in view of these concerns. I think the paper's idea is very nice.
I'll be here until the ddl.