acceptodds
Under review as a conference paper at ICLR 2027

Avoiding Saddle Points in Non-Negative Matrix Factorization via Simplex Constraints

Abstract

Provably avoiding saddle points in Non-negative Matrix Factorization (NMF) has been an open question since the influential work of [Lin07]. While algorithms like [LS99] and SNAP [lu2020finding] empirically perform well, there are no guarantees on whether they avoid the many (suboptimal) saddle points present in the non-convex optimization landscape of NMF. Unfortunately, the extensive literature on escaping saddle points in non-convex settings does not apply to NMF, as NMF is defined over a non-compact domain (non-negative orthants) and the loss is non-Lipschitz (both gradient and Hessian are non-Lipschitz). This paper shows how to avoid saddle points in NMF, obtaining convergence to second-order stationary points (SOSPs). Specifically: a) Asymptotic Convergence: we show that a natural modification of Multiplicative Weights Updates (MWU) asymptotically converges to exact SOSPs of NMF, with probability 1 for any random initialization in the simplex; b) Rates: we also give non-asymptotic rates of convergence to approximate SOSPs of NMF. Our novelty lies in analyzing the landscape of a carefully modified NMF problem with one additional constraint, showing that this modification essentially preserves the SOSPs of the original NMF landscape and their quality.

Primary area:
optimization
Keywords:
saddle points, NMF, second-order stationary points, convergence, MWU, simplex constraints

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 3 reviews, above 85% of the others.
Reviewer_CxvMOpenReview ↗
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 ℓ1\ell_1-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
  1. The paper presents an excellent idea.
  2. The analysis in this paper makes a useful contribution to the field.
Critical weaknesses
  1. 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.,
\\\\ 1&2\end{pmatrix},\qquad W=\begin{pmatrix}6&0 \\\\ 6&0\end{pmatrix},\qquad H=\begin{pmatrix}\tfrac14&\tfrac14 \\\\ 0&0\end{pmatrix},$$ where $n=m=r=2$. This point violates the SC condition, and is an SOSP1 but not an SOSP2. Hence, the paper's claimed computability results do not appear to be justified as currently presented. 2. Even setting aside the SOSP1/SOSP2 mismatch, the paper establishes transfer only for *exact* SOSPs, while SNAP computes only *approximate* SOSPs. Hence, the claimed non-asymptotic guarantees for the original NMF, e.g., "the first analysis proving convergence to second-order stationary points for the original (NMF) with non-asymptotic rates" in the paper, and "b) \textit{Rates}: we also give non-asymptotic rates of convergence to \textit{approximate} SOSPs of NMF" in this webpage, remain unsupported by the current analysis.
Questions for authors
  1. 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."
  2. 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

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.

AuthorsOpenReview ↗

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 CC, 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 :)

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

This paper addresses the nonnegative matrix factorization (NMF) problem under a standard least-squares loss. Specifically, it is concerned with deriving algorithms with guarantees regarding convergence to second-order stationary points (SOSP). To achieve this goal, the authors propose a modified formulation of the problem where a linear equality constraint is added, whose optimization domain is then compact. With this modification, existing results can be invoked to deliver the sought guarantees.

The paper is well written, with some moderately minor issues that I believe can be fixed without much difficulty. I am willing to improve my score if they are satisfactorily addressed by the authors.

Critical strengths
  1. Overall, I find that this paper is quite well written. I appreciate in particular the author's efforts in making its contents highly pedagogical, in particular by providing a simple yet telling 1D example, equipped with a very informative illustration (Figure 2) that facilitates understanding.

  2. The paper is also well organized, without too much technical details or other inessential materials, which are left to the appendices.

  3. The proposed approach is simple and seems to bring benefits in practice, as per the numerical experiments section.

Critical weaknesses
  1. The approach consists in normalizing the NMF factors in a way that may feel unusual. Other choices exist and could conceivably lead to results of the same kind. Yet, this choice is not discussed in the paper (see Question 1 below).

  2. This is not a critical issue but is still a relevant one: some contents are imprecise/unclear and should be revised. Specifically:

  • Line 44: finding global minima of NMF is not "impossible", but intractable (not feasible in polynomial time in general).
  • Line 64 "Observe that NMF is a case of non-smooth optimization". This seems strange, given that the loss is a polynomial, and the domain is an open set of an Euclidean space. The terminology seems inappropriate. I believe the authors mean a "non-strongly smooth problem"?
  • Why does Definition 4.1 appear to not take into account degenerate saddles, which are technically second-order stationary points?
  • Line 328: what does it mean to say that the "lemma first moves towards" some given point?
  1. The Experiments section is too short. It should be expanded to include more examples, ideally showcasing the practical benefits of adopting the proposed approach. If more space is needed, I believe that other parts can be a bit simplified/shortened without losing essential information.

  2. It is strange that the whole contents of the paper focus on an equality constraint, and then the algorithm evaluated in Section 6 actually enforces an inequality constraint. Do all the results still hold for this formulation? Why this choice?

Questions for authors
  1. The fact that the standard NMF formulation (even for other loss functions) is not coercive---thus allowing for the parameters to diverge (or simply be rescaled arbitrarily) while keeping the loss constant---is quite well known. This has been circumvented in other works by a combination of regularization and introduction of constraints (see, e.g., "Majorization-minimization for Sparse Nonnegative Matrix Factorization with the β-divergence" by Marmin et al.). One can argue that imposing unit-norm constraints is more natural than constraining the sum: for instance, the columns of W can be interpreted as dictionary atoms, which are often normalized. Similarly, one could impose unit ℓ1\ell_1 norms in the columns of H, so that they would represent mixing proportions. Why haven't the authors explored these other possibilities, choosing instead this "scaled-simplex" constraint?

  2. Aren't assumptions regarding the nature of the saddle points of Simplex-NMF required for the guarantees to hold? What happens if there are degenerate saddles (which are thus also SOSP)? Or is this impossible?

3 comments
AuthorsOpenReview ↗

answering reviewer's questions

We thank the reviewer for the feedback and for the overall positive score!

We provide answers to your questions below:

1. Reviewer's comment regarding NMF choice of normalization vs other types of normalizations:

Thank you for pointing to the paper by Marmin, Goulart, and Fevotte. We will cite and discuss this work in a revised version. For now, while we agree that dictionary normalization is natural, it is not clear how to obtain our results with that type of normalization. As we noted in the introduction, part of the challenge in NMF is the unbounded domains (non-negative orthants), so using normalization only for one matrix, say the W matrix that as you wrote may correspond to the dictionary atoms, will not make the entire feasible domain compact. Here our intention was to have the Simplex constraint for both factors W and H, without affecting their product, and under this consttaint, we established the landscape's analyses for NMF, i.e., we showed how to avoid saddle points in NMF, obtaining convergence to SOSPs of the original NMF landscape.

As you suggested, for your type of normalization on only W, perhaps there is another argument, but that would require its own separate analysis for the landscapes. Of course, our paper does not claim that our Simplex constraint and general approach is the only useful choice, or that alternatives cannot yield comparable guarantees.

2. Reviewer's comment regarding degenerate saddles and our assumptions:

We thank the reviewer in pointing that in general an SOSP can be a degenerate saddle. In our Definition 4.1, we used the term "saddle points" too narrowly, but we meant those FOSPs that indeed violate the relevant second-order stationarity test. Of course, there was no intention to say that every SOSP is a local minimum necessarily, and we do not assume that degenerate saddles or violations of strict complementarity are impossible.

To make it more precise, we can distinguish SOSPs in the two categories: SOSP1, which tests curvature within the active face, and SOSP2, which tests the critical cone. For our main theorem, the landscape structural transfer holds separately for each notion, while the algorithmic consequences and rates are stated for SOSP1. In particular, our algorithmic guarantee does not exclude every boundary saddle. This means that the structural landscape transfer holds separately for SOSP1 and SOSP2. Our MWU consequence concerns SOSP1 of original NMF, while the finite-time SNAP/SNAP+ guarantees concern approximate SOSP1 of Simplex-NMF

3. Clarification on Experiments, regarding the choice of constant C:

Here we just observed experimentally that using inequality constraint, we would often get better numerical stability. Notice we don't mind the inequality for the constant CC since our Theorem (please see Case 1 of Th. 1 line 169) establishes the landscape analyses for all choices of CC above the appropriate threshold that we stated. More specifically, for the inequality constraint utilized in our experiments, the exact SOSP transfer follows by considering two cases. First, if the inequality is strict, the additional constraint is locally inactive, so the original NMF stationarity conditions apply directly. Second, if the equality holds, an exact SOSP of the inequality-constrained problem is also an exact SOSP of the equality-constrained problem: imposing equality only restricts the admissible directions. So, our corresponding exact transfer theorem applies for this choice of the constant CC.

Regarding the main experimental section being too compressed, please see Table 1 and Figure 6, 7 and 8, since we incldued in the appendix results for MovieLens, MNIST, and LfW. We can move those to the main paper. We wanted to highlight that our main contribution in the paper was theoretical.

Once again, we appreciate your comments and your willingness to reconsider your assessment. Please let us know if there are other questions :)

AuthorsOpenReview ↗

addressing arxiv concern

We thank the reviewer for their comment. We will leave it to the chair to decide on this, based on the ICLR policy.

Thank you for your response. In my view your responses are satisfying, but I don't see any changes yet in the pdf. For now I am thus keeping my score.

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

Paper addresses the problem of avoiding saddle points in non-negative matrix factorization (NMF), a problem in non-convex non-smooth optimization. Existing literature results on avoiding saddle points do not apply to NMF, and the paper finds that a modification of multiplicative weights algorithm that provably avoids saddle points. The algorithm has asymptotic convergence to second order stationary points. Moreover, modifications of prior SNAP algorithm leads to approximate second order stationary points with nice rates of convergence. The paper presents empirical evidence for the latter algorithm.

Critical strengths

I have informed the AC to try to get another qualified reviewer.

Paper is generally well-written, and the problem + results seem relevant to the community. However, it's been quite a while since I worked on NMF research and the proof ideas and techniques are beyond my level of reviewing expertise.

Critical weaknesses
  • minor: the red NMF and Simplex NMF colors are distracting while reading, so I'd suggest that the authors just use black.
Questions for authors

none

1 comment
AuthorsOpenReview ↗

thank you!

We thank the reviewer for the overall positive assessment and for appreciating our presentation effort.

We used the highlighting of “NMF” and “Simplex-NMF” in red to be more easily readable. We can of course replace it.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.