Non-negative matrix factorization (NMF) is fundamental non-convex optimization problems with numerous applications in machine learning (music analysis, document clustering, speech-source separation etc.). Despite having received extensive study, it remains an open question whether or not there exist natural algorithms that can provably converge to a second-order stationary point. We answer the question in the affirmative by reducing the standard NMF over the non-negative orthant to a new formulation over a scaled simplex. We show that in the modified NMF problem, even if new stationary points are created, these are actually strict saddles and moreover for every second-order stationary point of the original NMF problem, there exists a second-order stationary point in the modified version of the same "properties".

Xiao Wang got his Ph.D. in differential geometry from the University at Buffalo, advised by Mohan Ramachandran, and B.S. from China University of Geosciences (Beijing). Xiao is now an assistant professor in Shanghai University of Finance and Economics. Before joining SUFE, Xiao was a postdoc researcher in Singapore University of Technology and Design (SUTD). He is interested in non-convex and manifold optimization, representation learning and game theory. His work combines and develops new techniques in algorithms, dynamical systems, optimization and learning theory.