Avoiding Saddle Points in Non-Negative Matrix Factorization via Simplex Constraints

Provably avoiding saddle points in Non-negative Matrix Factorization (NMF) has been an open question since the influential work of [Lin07]. While algorithms like [LS99] and SNAP [lu2020finding] empirically perform well, there are no guarantees on whether they avoid the many (suboptimal) saddle points present in the non-convex optimization landscape of NMF. Unfortunately, the extensive literature on escaping saddle points in non-convex settings does not apply to NMF, as NMF is defined over a non-compact domain (non-negative orthants) and the loss is non-Lipschitz (both gradient and Hessian are non-Lipschitz). This paper shows how to avoid saddle points in NMF, obtaining convergence to second-order stationary points (SOSPs). Specifically: a) Asymptotic Convergence: we show that a natural modification of Multiplicative Weights Updates (MWU) asymptotically converges to exact SOSPs of NMF, with probability 1 for any random initialization in the simplex; b) Rates: we also give non-asymptotic rates of convergence to approximate SOSPs of NMF. Our novelty lies in analyzing the landscape of a carefully modified NMF problem with one additional constraint, showing that this modification essentially preserves the SOSPs of the original NMF landscape and their quality.