Frank-Wolfe Optimization for Symmetric-NMF under Simplicial Constraint

We propose a Frank-Wolfe (FW) solver to optimize the symmetric nonnegative matrix factorization problem under a simplicial constraint. Compared with existing solutions, this algorithm is extremely simple to implement, and has almost 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 stationary points, via a tight bound $\Theta(n^2)$ on the curvature constant. 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.