Frank-Wolfe Optimization for Symmetric-NMF under Simplicial Constraint

Han Zhao, Geoffrey J. Gordon

Abstract

Symmetric Nonnegative Matrix Factorization under a simplicial constraint (SSymNMF) is a powerful tool for probabilistic clustering, yet its nonconvex and NP-hard nature makes it difficult to solve efficiently. Traditional penalty methods are computationally expensive and require extensive hyperparameter tuning. We present a hyperparameter-free Frank-Wolfe (FW) algorithm for SSymNMF. By leveraging an efficient Linear Minimization Oracle (LMO) and providing a tight bound on the curvature constant, we demonstrate that FW achieves state-of-the-art convergence rates while being significantly faster and more robust than existing methods.

Introduction

Symmetric Nonnegative Matrix Factorization (SymNMF) decomposes a similarity matrix into a low-rank representation, facilitating effective clustering. Simplicial SymNMF (SSymNMF) adds a constraint where the rows of the factor matrix $W$ must sum to one, allowing for a "soft" probabilistic interpretation of cluster assignments. Despite its utility, the optimization landscape of SSymNMF is challenging. Previous solutions often relied on penalty methods that are sensitive to initialization and require tuning up to six hyperparameters. This paper introduces a Frank-Wolfe approach that simplifies the optimization process by replacing expensive projections with a simple linear oracle.

Methods

The proposed method utilizes the Frank-Wolfe (FW) algorithm, also known as the Conditional Gradient method. FW is particularly effective for simplicial constraints because it avoids the overhead of projection steps.

Efficient Linear Minimization Oracle (LMO)

For a product of simplices, the LMO can be computed in $O(nk)$ time. It involves identifying the index of the minimum entry in each row of the gradient matrix. This structural advantage allows the algorithm to scale efficiently with the number of instances $n$ and clusters $k$.

Algorithm 1: Frank-Wolfe step for SSymNMF.

Curvature and Convergence

A key theoretical contribution is the analysis of the curvature constant $C_f$, proven to be $\Theta(n^2)$. This tight bound ensures a non-asymptotic convergence rate of $O(1/\epsilon^2)$ to an $\epsilon$-approximate Karush–Kuhn–Tucker (KKT) point, matching the performance of gradient methods in unconstrained settings.

Experimental Evaluation

The algorithm was evaluated on four standard datasets transformed into co-cluster affinity matrices using a Gaussian kernel. These datasets vary significantly in scale and feature dimensionality, providing a robust test for the algorithm's efficiency.

Table 1: Summary of datasets used for clustering evaluation.

Results

Numerical experiments reveal that the FW algorithm is orders of magnitude faster than traditional penalty methods. While FW may require more iterations than Projected Gradient Descent (PGD) in certain scenarios, the computational cost per iteration is significantly lower due to the absence of projection overhead. Furthermore, FW consistently achieves lower objective function values and exhibits high robustness, operating effectively without manual tuning of step sizes or penalty coefficients.

Conclusion and Future Work

The Frank-Wolfe algorithm provides a simple, efficient, and theoretically grounded solver for SSymNMF. While it successfully identifies KKT points, the nonconvexity of the problem means global optimality is not guaranteed. Future research will explore the uniqueness of SSymNMF solutions and investigate sufficient conditions for FW convergence in nonsmooth settings, as the authors identified specific cases where FW fails on piecewise linear functions with infinite curvature.

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