Title: Frank-Wolfe Optimization for Symmetric-NMF under Simplicial Constraint,
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.