Frank-Wolfe Optimization for Symmetric-NMF under Simplicial Constraint

Han Zhao, Geoff Gordon
Proceedings of the 34th Conference on Uncertainty in Artificial Intelligence, PMLR R16:123-133, 2018.

Abstract

Symmetric nonnegative matrix factorization has found abundant applications in various do- mains by providing a symmetric low-rank de- composition of nonnegative matrices. In this paper we propose a Frank-Wolfe (FW) solver to optimize the symmetric nonnegative matrix factorization problem under a simplicial con- straint, which has recently been proposed for probabilistic clustering. Compared with exist- ing solutions, this algorithm is simple to imple- ment, and has no hyperparameters to be tuned. Building on the recent advances of FW algo- rithms in nonconvex optimization, we prove an O(1/$\varepsilon$2) convergence rate to $\varepsilon$-approximate KKT points, via a tight bound $\Theta$(n2) on the cur- vature constant, which matches the best known result in unconstrained nonconvex setting using gradient methods. Numerical results demon- strate the effectiveness of our algorithm. As a side contribution, we construct a simple nons- mooth 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.

Cite this Paper

BibTeX
@InProceedings{pmlr-vR16-zhao18a, title = {{F}rank-{W}olfe Optimization for Symmetric-{NMF} under Simplicial Constraint}, author = {Zhao, Han and Gordon, Geoff}, booktitle = {Proceedings of the 34th Conference on Uncertainty in Artificial Intelligence}, pages = {123--133}, year = {2018}, editor = {Globerson, Amir and Silva, Ricardo}, volume = {R16}, series = {Proceedings of Machine Learning Research}, month = {06--10 Aug}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/r16/main/assets/zhao18a/zhao18a.pdf}, url = {https://proceedings.mlr.press/r16/zhao18a.html}, abstract = {Symmetric nonnegative matrix factorization has found abundant applications in various do- mains by providing a symmetric low-rank de- composition of nonnegative matrices. In this paper we propose a Frank-Wolfe (FW) solver to optimize the symmetric nonnegative matrix factorization problem under a simplicial con- straint, which has recently been proposed for probabilistic clustering. Compared with exist- ing solutions, this algorithm is simple to imple- ment, and has no hyperparameters to be tuned. Building on the recent advances of FW algo- rithms in nonconvex optimization, we prove an O(1/$\varepsilon$2) convergence rate to $\varepsilon$-approximate KKT points, via a tight bound $\Theta$(n2) on the cur- vature constant, which matches the best known result in unconstrained nonconvex setting using gradient methods. Numerical results demon- strate the effectiveness of our algorithm. As a side contribution, we construct a simple nons- mooth 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.}, note = {Reissued by PMLR on 04 October 2026.} }
Endnote
%0 Conference Paper %T Frank-Wolfe Optimization for Symmetric-NMF under Simplicial Constraint %A Han Zhao %A Geoff Gordon %B Proceedings of the 34th Conference on Uncertainty in Artificial Intelligence %C Proceedings of Machine Learning Research %D 2018 %E Amir Globerson %E Ricardo Silva %F pmlr-vR16-zhao18a %I PMLR %P 123--133 %U https://proceedings.mlr.press/r16/zhao18a.html %V R16 %X Symmetric nonnegative matrix factorization has found abundant applications in various do- mains by providing a symmetric low-rank de- composition of nonnegative matrices. In this paper we propose a Frank-Wolfe (FW) solver to optimize the symmetric nonnegative matrix factorization problem under a simplicial con- straint, which has recently been proposed for probabilistic clustering. Compared with exist- ing solutions, this algorithm is simple to imple- ment, and has no hyperparameters to be tuned. Building on the recent advances of FW algo- rithms in nonconvex optimization, we prove an O(1/$\varepsilon$2) convergence rate to $\varepsilon$-approximate KKT points, via a tight bound $\Theta$(n2) on the cur- vature constant, which matches the best known result in unconstrained nonconvex setting using gradient methods. Numerical results demon- strate the effectiveness of our algorithm. As a side contribution, we construct a simple nons- mooth 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. %Z Reissued by PMLR on 04 October 2026.
APA
Zhao, H. & Gordon, G.. (2018). Frank-Wolfe Optimization for Symmetric-NMF under Simplicial Constraint. Proceedings of the 34th Conference on Uncertainty in Artificial Intelligence, in Proceedings of Machine Learning Research R16:123-133 Available from https://proceedings.mlr.press/r16/zhao18a.html. Reissued by PMLR on 04 October 2026.

Related Material