Provable Alternating Gradient Descent for Non-negative Matrix Factorization with Strong Correlations

By Yuanzhi Li, Yingyu Liang. 2017

18 citations recorded by the source corpus.

Non-negative matrix factorization is a basic tool for decomposing data into the feature and weight matrices under non-negativity constraints, and in practice is often solved in the alternating minimization framework. However, it is unclear whether such algorithms can recover the ground-truth feature matrix when the weights for different features are highly correlated, which is common in applications. This paper proposes a simple and natural alternating gradient descent based algorithm, and shows that with a mild initialization it provably recovers the ground-truth in the presence of strong correlations. In most interesting cases, the correlation can be in the same order as the highest possible. Our analysis also reveals its several favorable features including robustness to noise. We complement our theoretical results with empirical studies on semi-synthetic datasets, demonstrating its advantage over several popular methods in recovering the ground-truth.

Subfields: Computer Vision and Pattern Recognition, Optimization & Training, Signal Processing

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Computer Vision and Pattern Recognition

In Optimization & Training

In Signal Processing

Citations in the corpus

Feature Purification: How Adversarial Training Performs Robust Deep Learning (2020, methodology): “[10] provides a neurally-plausible algorithm for learning sparse coding along with other works using alternative minimization [1, 2, 37, 56, 59].”
Learning and Generalization in Overparameterized Neural Networks, Going Beyond Two Layers (2018, background): “ distribution (such as being random Gaussian), and/or make strong assumptions about the network (such as using linear activations). Other works focusing on structured data such as sparse coding model [5, 9, 37, 40] and Li and Liang [38] shows that two-layer ReLU networks can learn classication tasks”
Backward Feature Correction: How Deep Learning Performs Deep Learning (2020, background): “It is thus not surprising that most existing theoretical works on the efficient learning regime of neural networks either focus on (1) two-layer networks [4, 11, 15, 17, 27, 28, 43, 47, 48, 50, 50–52, 64, 69, 70, 73, 75, 77, 79, 82, 83] which do not have the hierarchical structure, or (2) a multi-la”
Towards Understanding Ensemble, Knowledge Distillation and Self-Distillation in Deep Learning (2020, background): “Most of the existing works proving that neural networks can learn features only focus on the case when the input is Gaussian or Gaussian-like [5, 11, 13, 17, 38, 39, 46, 53, 54, 56, 56–58, 60, 69, 78– 80, 84, 85, 87, 89].”
Making Method of Moments Great Again? -- How can GANs learn the target distribution (2020, background): “sparse coding/non-negative matrix factorization [18, 19, 49, 47, 7]”
Learning Over-Parametrized Two-Layer ReLU Neural Networks beyond NTK (2020, background): “…(2016); Soltanolkotabi et al. (2017); Tian (2017); Brutzkus and Globerson (2017); Boob and Lan (2017); Vempala and Wilmes (2018); Oymak and Soltanolkotabi (2019); Bakshi et al. (2018); Yehudai and Shamir (2019); Zhang et al. (2018); Li and Liang (2017); Li and Dou (2020); Allen-Zhu and Li (2020b).”