Frank-Wolfe Optimization for Symmetric-NMF under Simplicial Constraint

Han Zhao, Geoffrey J. Gordon

Abstract

Symmetric nonnegative matrix factorization has found abundant applications in various domains by providing a symmetric low-rank decomposition of nonnegative matrices. In this paper we propose a Frank-Wolfe (FW) solver to optimize the symmetric nonnegative matrix factorization problem under a simplicial constraint, which has recently been proposed for probabilistic clustering. Compared with existing solutions, this algorithm is simple to implement, and has no hyperparameters to be tuned. Building on the recent advances of FW algorithms in nonconvex optimization, we prove an $O(1/\varepsilon^2)$ convergence rate to $\varepsilon$-approximate KKT points, via a tight bound $\Theta(n^2)$ on the curvature constant, which matches the best known result in unconstrained nonconvex setting using gradient methods. Numerical results demonstrate the effectiveness of our algorithm. As a side contribution, we construct a simple nonsmooth convex problem where the FW algorithm fails to converge to the optimum. This result raises an interesting question about necessary conditions of the success of the FW algorithm on convex problems.

Introduction

Nonnegative Matrix Factorization (NMF) is a fundamental technique for extracting interpretable, low-rank features from data. A critical variant, Symmetric NMF (SymNMF), factors a symmetric affinity matrix (representing pairwise similarities) into the form $W W^T$. This paper focuses on simplicial SymNMF, where the factor matrix $W$ is constrained such that each row sums to 1. This constraint is vital for probabilistic clustering, allowing each row of $W$ to be interpreted as a probability distribution over clusters.

Historically, solving this constrained non-convex problem has relied on penalty methods that convert constraints into unconstrained objectives. However, these methods are often slow, require tuning up to six hyperparameters, and lack strong theoretical convergence guarantees. This work introduces a Frank-Wolfe (FW) solver that eliminates hyperparameter tuning while providing robust theoretical bounds.

The Frank-Wolfe Solver

To address the limitations of penalty methods, the authors utilize the Frank-Wolfe algorithm, also known as conditional gradient descent. FW is particularly suited for constrained optimization because it avoids expensive projection steps, instead utilizing a Linear Minimization Oracle (LMO) to determine the optimal step direction within the feasible set.

The Frank-Wolfe update step for simplicial SymNMF.

The proposed approach features several key innovations:

  • Hyper-efficient LMO: Since the simplicial constraint is a product of probability simplices, the LMO can be solved exactly in $O(nk)$ time and $O(1)$ space. The resulting sparse matrix (one '1' per row) ensures that update steps are computationally inexpensive.
  • Non-convex Analysis: The authors extend standard FW analysis to the non-convex SymNMF objective. By using the FW-gap as a convergence certificate, they prove that a gap of zero corresponds to Karush-Kuhn-Tucker (KKT) stationarity.

Experimental Evaluation

The algorithm was evaluated across four standard clustering datasets, with symmetric co-cluster affinity matrices constructed using Gaussian kernels.

Summary of datasets used for clustering evaluation.

Key Theoretical Insights

  • NP-Hardness: The authors demonstrate that the decision version of simplicial SymNMF is geometrically equivalent to the strong membership problem for the Completely Positive (CP) cone, suggesting the problem is NP-hard.
  • Curvature Bounds: Using matrix differential calculus, the authors established a tight $\Theta(n^2)$ bound on the curvature constant. This allows for a rigorous $O(1/\epsilon^2)$ convergence rate guarantee.
  • FW Failure Case: In a surprising side result, the authors identified a simple, piecewise-linear convex problem where the standard FW algorithm fails to reach the global optimum due to an infinite curvature constant. This underscores the importance of finite curvature for FW's success.

Results and Performance

  • Efficiency: The FW algorithm is guaranteed to find an $\epsilon$-approximate KKT point in $O(n^3k/\epsilon^2)$ time.
  • Empirical Dominance: In practice, the FW algorithm is orders of magnitude faster than penalty-based baselines and consistently reaches superior local optima.
  • Comparison with PGD: While Projected Gradient Descent (PGD) has similar theoretical rates, FW outperforms it in wall-clock time. The per-iteration cost of FW is significantly lower, leading to faster total convergence.

Conclusion and Future Work

While the algorithm is highly effective, it is limited by the non-convexity of the objective, guaranteeing convergence only to stationary (KKT) points rather than global optima. Furthermore, the quadratic scaling of the curvature bound with $n$ suggests potential challenges for massive datasets. Future research will investigate the necessary and sufficient conditions for FW success on non-smooth convex problems, building on the failure case identified in this study.

Summary updated

Abstract

Symmetric nonnegative matrix factorization has found abundant applications in various domains by providing a symmetric low-rank decomposition of nonnegative matrices. In this paper we propose a Frank-Wolfe (FW) solver to optimize the symmetric nonnegative matrix factorization problem under a simplicial constraint, which has recently been proposed for probabilistic clustering. Compared with existing solutions, this algorithm is simple to implement, and has no hyperparameters to be tuned. Building on the recent advances of FW algorithms in nonconvex optimization, we prove an $O(1/\varepsilon^2)$ convergence rate to $\varepsilon$-approximate KKT points, via a tight bound $\Theta(n^2)$ on the curvature constant, which matches the best known result in unconstrained nonconvex setting using gradient methods. Numerical results demonstrate the effectiveness of our algorithm. As a side contribution, we construct a simple nonsmooth convex problem where the FW algorithm fails to converge to the optimum. This result raises an interesting question about necessary conditions of the success of the FW algorithm on convex problems.
BibTeX
@inproceedings{zhao2018frank,
  author = {Han Zhao and Geoffrey J. Gordon},
  title = {{Frank-Wolfe Optimization for Symmetric-NMF under Simplicial Constraint}},
  booktitle = {Conference on Uncertainty in Artificial Intelligence},
  year = {2018},
  url = {https://openreview.net/forum?id=hMCQmnKtCI},
}
Figure