Abstract
Non-negative matrix factorization (NMF) is a highly celebrated algorithm for matrix decomposition that guarantees non-negative factors. The underlying optimization problem is computationally intractable, yet in practice, gradient-descent-based methods often find good solutions. In this paper, we revisit the NMF optimization problem and analyze its loss landscape in non-worst-case settings. It has recently been observed that gradients in deep networks tend to point towards the final minimizer throughout the optimization procedure. We show that a similar property holds (with high probability) for NMF, provably in a non-worst case model with a planted solution, and empirically across an extensive suite of real-world NMF problems. Our analysis predicts that this property becomes more likely with growing number of parameters, and experiments suggest that a similar trend might also hold for deep neural networks---turning increasing dataset sizes and model sizes into a blessing from an optimization perspective.
Introduction
Non-Negative Matrix Factorization (NMF) is a fundamental tool in data science, applied in fields ranging from collaborative filtering to hyperspectral imaging. The objective is to decompose a non-negative matrix $X$ into two lower-rank non-negative matrices $U$ and $V$ such that $X \approx UV$. Despite its widespread utility, NMF is theoretically NP-hard in the worst case. However, practitioners consistently observe that simple gradient-descent-based methods converge to high-quality solutions. This paper investigates this discrepancy, characterizing the "typical" NMF loss landscape to explain why it is so amenable to optimization.
Methodology: Star-Convexity and Path Curvature
The core of our analysis centers on the concept of star-convexity. A function is star-convex if, for any point in the landscape, there exists a straight-line path to the global minimum along which the function is monotonically decreasing and convex. In such a landscape, gradient descent is unlikely to be trapped by local minima.
Theoretical Framework
We analyze a "planted solution" model where the data matrix $X$ is generated from true underlying factors $(U^*, V^*)$ with random non-negative entries. Utilizing tools from Random Matrix Theory, we prove that as the matrix dimensions grow, the probability of the loss function being convex along the path to the solution approaches unity. Specifically, for a matrix of size $n$, this probability scales as $1 - \exp(-n^{1/3})$.
Empirical Results
To validate our theoretical findings, we examined the loss surfaces of eight diverse real-world datasets, including MovieLens, Netflix, and scientific datasets like "Metabolic" (yeast activity) and "Extragalactic" (star spectra). We measured the curvature of the loss along straight lines between random initializations and the final solutions found by gradient descent.
Across all datasets, the loss was consistently convex along these paths. Furthermore, we extended our investigation to deep learning using ResNet architectures on CIFAR-10. Our experiments revealed that increasing the "width" of the network (number of channels) significantly extends the length scale of local convexity, suggesting that larger models possess "flatter" and more easily navigable landscapes.
Discussion: The Blessing of Dimensionality
Our findings suggest that high dimensionality, often viewed as a "curse," can actually be a "blessing" for optimization. In high-dimensional spaces, "concentration of measure" occurs: random fluctuations in the loss surface tend to cancel out, resulting in a smoother, more convex-like landscape. This explains why massive neural networks and large-scale NMF problems are often easier to solve than their smaller counterparts. The gradients in these high-dimensional regimes are more likely to point directly toward the global optimum, a property we term "benign" optimization.
Conclusion and Future Work
While our results provide a robust explanation for the success of NMF in practice, several avenues for future research remain. Our theoretical proof currently assumes independent and identically distributed (iid) matrix entries; extending this to structured, real-world data is a priority. Additionally, the role of sparsity—common in datasets like Netflix—requires further investigation. Finally, while star-convexity suggests that local minima are rare in the "average" case, it does not entirely preclude their existence in distant regions of the parameter space.
Summary updated