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$.
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.
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