Star-Convexity in Non-Negative Matrix Factorization
Authors: Johan Bjorck
Carla Gomes
Kilian Weinberger
Venue:  (2020)
Keywords: nmf
convexity
nonconvex optimization
average-case-analysis

Abstract: Non-negative matrix factorization (NMF) is a highly celebrated algorithm for matrix decomposition that guarantees strictly non-negative factors. The underlying optimization problem is computationally intractable, yet in practice gradient descent based solvers often find good solutions. This gap between computational hardness and practical success mirrors recent observations in deep learning, where it has been the focus of extensive discussion and analysis. 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. 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 data sets and models into a blessing from an optimization perspective. 

Under review as a conference paper at ICLR 2020
STAR-CONVEXITY IN NON-NEGATIVE MATRIX FAC- TORIZATION
Anonymous authors Paper under double-blind review
ABSTRACT
matrix factorization (NMF) is a highly celebrated algorithm for ma- trix decomposition that guarantees non- non-negative factors. The underlying optimiza- tion problem is computationally intractable, yet in practice gradient descent based solvers often find good solutions. This gap between computational hardness and practical success mirrors recent observations in deep learning, where it has been the focus of extensive discussion and analysis. 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. We show that similar property holds (with high probability) for NMF, provably in a non-worst case model with planted solution, and empirically across an extensive suite of real-world NMF problems. Our analysis predicts that this property becomes more likely with grow- ing number of parameters, and experiments suggest that a similar trend might also hold for deep neural networks - turning increasing data sets and models into a blessing from an optimization perspective.
INTRODUCTION
Non-negative matrix factorization (NMF) is a ubiquitous technique for data analysis where one tempts to factorize measurement matrix X into the product of non-negative matrices U. V (Lee) and Seung, 1999). This simple problem has applications in recommender systems (Luo al. 2014). scientific analysis (Berne et al. 2007: Trindade et al.) 2017), computer vision (Gillis) (012). inter- net distance prediction (Mao et al.) 2006), audio processing (Schmidt et al., (007) and many more domains. Often, the non-negativity is crucial for interpretability for example, in the context of crys- tallography, the light sources, which are represented as matrix factors, have non-negan non-negative intensity Suram et al. 2016).
Like many other non-convex optimization problems, finding the exact solution to NMF NP-hard (Pardalos and Vavasis 1991 Vavasis 2009). NMF's tremendous practical success is however at odds with such worst-case analysis, and simple algorithms based upon gradient descent are known to find good solutions in real-world settings (Lee and Seung 2001). At the time when NMF was proposed, most analyses of optimization problems within machine learning focused on convex for- mulations such as SVMs (Cortes and Vapnik 1995). but owing the success of neural networks, non-convex optimization has experienced resurgence in interest. Here, we revisit NMF from a fresh perspective, utilizing recent tools developed in the context of optimization in deep learning. Specifically, our main inspiration is the recent work of Kleinberg et al. (2018) and Zhou et al. (2019) that empirically demonstrate that gradients typically point towards the final minimizer for neural networks trained on real-world datasets and analyze the implications of such convexity properties for efficient optimization.
In this paper, we show theoretically and empirically that similar property called star-convexity holds NMF, From a theoretical perspective, we consider an NMF instance with planted solution, inspired by the stochastic block model for social networks (Holland et al.) 1983 Decelle et al.) 2011) and the planted clique problem studied sum-of sum-of-squares literature (Barak et al.) (016). We prove that between two points the loss is convex with high probability. and conclude that the loss surface is star-convex in the typical case - even the loss is computed over unobserved data. From empirical perspective, we verify that theoretical results hold for extensive collection

---

Under review as a conference paper at ICLR 2020
b)
10
X
0.0
1.0
0.0
0.5
1,0
À
X
Figure 1: A non-convex loss surface is illustrated in a). In general, the loss will be non-convex on straight paths connecting random points X2, X₁ and the global minimizer x*. We consider model of NMF with planted solution, and as shown in b) the loss is typically convex on straight paths between points X, and planted solution x*. Additionally, illustrated in c), the loss is typically convex on straight paths between points X, and Xg.
of real-world datasets spanning collaborative filtering (hhou et al. 2008 Kula 2017 Harper and Konstan 2016), signal decomposition (Zhu, 2016 Li and Ngom| 2013 Li et al. 2001 Erichson et 2018) and audio processing (Flenner and Hunter 2017; canto Foundation). and demonstrate that the star-convex behavior results in efficient optimization. Finally, show that star-convex behavior becomes more likely with growing number of parameters, suggesting that a similar result may hold neural networks become wider. We provide supporting empirical evidence for this hypothesis on modern network architectures.
NMF AND STAR-CONVEXITY
The aim of NMF to decompose some large measurement matrix X x into two non-negative matrices U R4 and V E RR"*m such that X > UV. The canonical formulation of NMF is
E(U, V), where ((U, UV - X
min V.0
(I)
NMF is commonly used in recommender systems where entries (i.j) of X for example correspond to the rating user has given to movie j (Luo et al.) 2014). In such settings, data might be missing all users have not rated all movies. In those observed data (Zhang et al. 2006; Candès and Recht 2009). We let ((.,) be an indicator variable that is if entry (i,j) is "observed" and ( otherwise. The loss function is then
is common to only consider the loss over
1 Las - =
(LVV -X1y
min U.V
((U.V)
(2)
2
NMF is similar to PCA which admits spectral strategies; however, the non-negative constraints in NMF prevent such solutions and result in NP-hardness (Vavasis) 2009). Work on the computational complexity of NMF has shown that the problem is tractable for small constant dimensions via algebraic methods (Arora et al.) 2012). In practice, however, these algorithms are not used, and simple variants of gradient descent. possibly via multiplicative updates (Lee and Seung (001). popular and are known to work reliably (Koren et al.) 2009). This gap between theoretical hardness and practical performance also found deep learning. Optimizing neural networks ha-hard in general (Blum and Rivest 1989), but in practice they can be optimized with simple stochastic gradient descent algorithms to outmatch humans in tasks such as face verification (Lu and Tang 2015) and playing Atari gariegames (Mnih et al., 2015). Recent work on understanding the geometry of neural network loss surfaces has promoted the idea of convexity properties. The work of [zmailov al. (2018) shows that the loss surface is convex around the local optimum, while Salle/Zhu et al. (2019) and Kleinberg et al. (018)) show that the gradients during optimization typically point towards the local minima the network eventually converges to. Of central importance in this line of work is star-convexity, which a property of a function f that guarantees that convex along straight paths towards the optima x See Figure 2 for an example. Formally, it is defined as follows.
2

---

Under review as a conference paper at ICLR 2020
Definition 1. A function R R is star-convex towards x" for all X E [0, 1] and e R", we have f>x + (1- A) x*) & (x + (1 ))x(x))
Optimizing star-convex functions can be done in polynomial time (Lee and Valiant 2016), in Kleinherg et al. (2018) it is shown how the function only needs to be star-convex under natural noise model. NMF not star-convex in general as is NP-hard, however, it is natural to conjecture that NMF is star- convex in the rypical case. Such property could explain the practical success of NMF on real-world datasets, which is not worst-case. This will be the working hypothesis of this paper, where the typical case is formalized in Theorem [ Indeed, one can verify numerically that NMF is typically star-convex for natural distributions and realistically sized matrices, see Figure 1 where we consider rank 10 decomposition of (100, 100)- matrices with iid half-normal entries and a planted solution, sampled per Assumption given in the next section. Fol- lowing sections will be dedicated to proving that NMF is star- convex with high probability in planted model, and to con- firm that this phenomenon generalizes to datasets from the real world, which are far from worst-case.
008
Raz OCE
Figure 2:
The function (|æ|/ + lulP) is an example of star- convex function for 0 < p < 1. is non-convex in general, but con- vex towards (0, 0).
PROVING TYPICAL-CASE STAR-CONVEXITY
Our aim now is to prove that the NMF foss-function is typically star-convex for natural non-worst- case distribution of NMF instances. We will consider a slighly weaker notation of star-convexity where s(xx (1 A) x*) & A/(x) + (1 (x*( holds not for all but for random with high probability. This is in fact the best achievable, an NMF instance with un 1, 1, = 0 and U1 0, x 1 is not star-convex. Our results hold with high probability high dimensions, similar to Dvoretzky's 's theorem in convex geometry (Dvoredsky 1961; Davis).
Inspired by the stochastic block model of social networks (Holland et al. 1983 Decelle al. 2011 and the planted clique problem (Barak el al. 2016)), we will focus on a setting with a planted random solution. In section 4 we verify conclusions drawn from this model transfers to real-world datasets. We will assume that there is a planted optimal solution (U*, V*), where entries of these matrices are sampled iid from a class of distributions with good concentration properties that include the half- normal distribution and bounded distributions. As is standard in random matrix theory (Vershynin) 2010), we will develop non-asymptotic results that hold with a probability that grows as the matrices of shape (nt, r) and (r, m) become large. For this reason, we will need to specify how r and m depend on n..
Assumption 1. For (U, Raxr x Rrxm we assume that the entries of the matrices U, V are sampled idd from a continuous distribution with non-negative support that either (i) bounded or assume
(ti) can be expressed that r grows as n² up to a constant factor for E [1/2, 1], and m as n up to a constant factor.
1-Lipschitz function of Gaussian distribution. As
We are now ready to state our main results, that the loss function equation 1 is convex on straight line between points samples as per Assumption [ and thus satisfy our slightly weaker notion of star-convexity, with high probability. The probability increases the size of the problem increases, suggesting a surprising benefit of high dimensionality. We also show similar results for the loss function of equation 2 with unobserved data under the assumption that the event that any entry is observed occurs independently with constant probability p. Below we sketch the proof idea and key ingredients, the formal proof is given in Appendix [D]
Theorem 1. (Main) Let matrices UI, V1, U2, V2, U*, V* be sampled according to Assumption
I Then there exists positive constants Ct, C2. such that with probability > Ci exp( 1/3
the loss function E(U, V) in equation 7 is convex on the straight line (U1, V1) - (U2, V2). The same holds along the line (U,.V) independently with constant probability p. but with probability > 1 Ci exp( exp(-c2r_13 1/3).
(U*, V*). It also holds if any entry (i, is observed
3

---

Under review as a conference paper at ICLR 2020
3.1 PROOF STRATEGY
Let us parametrize the NMF solution one gets along the line (U2, V2) - (U1, Vi) as
x())= AU, ( + (1- NJUz)) (AV.)(vVV.. +
Proving Theorem 1 amounts to showing that the loss function E(A) ((() X is convex in À with high probability, our strategy is to show that its second-derivan is non-negative. For fixed matrices U1, U2, U*, V1, 22, V*, the function {(A) is fourth-degree polynomial in X, so its second derivate w.r.t. will be a second-degree polynomial in A. For a general second-degree polynomial p(z) az² + br we have p(z) _ + ) + (ac } If 0, which in 6a the case here (see Appendix D showing that it's positive could be done by showing ac 2 4. This equivalent to showing that
W. 21 (1 111 WWW W2)) 3 w2))
(3)
Where the matrices Wo. W1, W2 are given as Wo U2V. U*V* W1 - (U, U2) V2 +
U2 U2(Vi V2). W (U1 U2) (V1- V2). By slight abuse of notation, have used (A. B) to
denote Tr(AA") for matrices A, of the same shape. By exchanging terms in equation by their means one gets
((4rmno))(rmmnn + 4rmnp 0² + 2rmma* > 3( 4rmno*)2
(4)
Here, o² is the variance of the distribution of the entries in the matrices, while μ is the mean. By just counting terms of order (rmno")² we see that the LHS has 64 such terms while the RHS has only 48. Thus, if all matrices Wo. W1 and W₂ would exactly be equal their mean, inequality equation 3 would hold. In proving that it holds in general, we will use concentration of measure results from random matrix theory to show that the terms will be concentrated around their means and that large deviations are exponentially unlikely.
Concentration of measure Consider the matrix W₂ (U, (2) (2) V2). Given that all matrices are iid we can center the variables such that W2 = (U1 - U2) (V1 (V1- V2) U2) (V, V2), where the bar denotes the centered matrices. The term W2 can then be written as Tr (V--V,) as per Assumption D we would expect some concentration of measure to hold. Bernstein-type inequalities turns out to be too weak for our purposes, but the field of random matrix theory offer stronger results for matrices with independent sub-Gaussian entries (Ahlswede and Winter 2002 Tropp 2012] Guionnet et al., 2000 [Mckes and Szarek 2012). Via such results one can achieve the following concentration result, see Appendix
(U,
(U, (V) Vz). Given that all matrix entries are independent
P(| 2 E (2ll)] > trn?) & c3 exp (- C₁ min(t (12) n)
(5)
where C32 C4 are positive constants. In some expression we will however not be able to center all variables, and for such expression one gets similar but slightly weaker concentration results where the exponent scales n instead of n, see Appendix D
Proof sketch Given that 22 = 4rmno*, equation says that the probability that the term deviates from its mean by relative factor e is less than 03 exp (-c5e2n) for some small e. By applying similar arguments to terms (Wa, W2) and <W,, 1, W2), can show that the probability that they will deviate by a relative factor e is less than es exp(-cc722113 A problematic term is | which contains term of the type Tr (V1 V²) pT - V2) which has weak concentration properties. Matrices of type A A psd, and psd matrices have non-negative trace. Hence, this term will be non-negative, and since it occurs on the LHS of equation 3 we can simply omit it to lower bound the convexity. Using union bound, we bound the probability that at least on term deviate with a relative factor by e₁ exp(-cge'12) 1/3) for positive constants C1, Ca. Now, set e = 0.01 If neither variable deviates by a factor of more than 0.01, then equation 10 still holds since 0.992 * 64 > 1.013 + 48. Thus, inequality is violated with probability at most e exp - C2n 1/3) for positive C2-
4

---

Under review as a conference paper at ICLR 2020
extregaleciicc
goodbooks
53
1.5
3.2
0.3232
0.222
1.2
movielens
nettix
satelltte
4.6
0.117
9.005
3.5
4.0
2.8
X
Figure 3: We here illustrate the loss surface of NMF on straight paths connecting two random points for 8 real-world datasets. We overlap 5 independent lines for each dataset. Note that the curves are always convex, suggesting that the loss surface is "typically" convex.
Table 1: Dataset details. References contain suggested rank See Appendix A for details.
name
shape (n, m, r)
sparsity
reference
birdsong
(5120, 1246, 88)
Flenner and Hunter 2017)
extragalactic
(2760, 2820, 10)
goodbooks
(10000, 43461, 50)
0.0022
Kula 2017)
metabolic
(9335, 36,
Li and Ngom 2013
moviclens
(3953, 6041, 20)
0.0419
Harper and Konstan 2016
netflix
(47928, 8963, 20)
0.0121
Zhou al. 2008
ORL faces
(400, 10304, 49)
ei al. 2001).
satellite
(162, 94249,4)
tErccsonn et al.
2018
Proof sketch for unobserved data If the entries in equation are "observed" independently with probability for fixed matrices U1, U2, U*, V1, V2, V such that Theorem hold, we have
x 19 + X" (X, X x.)) ) - >
(() = Σ (0.5 13
-P
+
X.y) > 0
Thus, the expectation of (*) is convex. To show that it is convex with high probability, one first observes that with high probability, no entry (i,j) in (*()) is particularly large. Assuming this holds via union bound, for fix matrices U2, U2 U*, V1, V2, V with elements that are "observed" independently with probability p. one gets that (*) is concentrated around its convex mean via Hoeffding bounds (Hoeffding 1994).
4
EXPERIMENTS
4.1 VERIFYING THEORETICAL PREDICTIONS
To verify that the conclusions from our planted model hold more broadly, we now consider real- world datasets previously studied in NMF literature. Some have ranks outside the scope of our theoretical model but still display star-convexity properties, indicating that it might be a general phenomenon. We focus handful of representative datasets spanning image analysis, scientific applications and collaborative filtering. In Table I we list these datasets together with references and sparsity, the decomposition rank use is based upon values previously used in the literature.
We perform a non-negative matrix factorization via gradient descent, starting with randomly initial- ized data. To enable comparison between datasets, scale all data matrices that the variance of
5

---

Under review as a conference paper at ICLR 2020
birdsong
actragilactic
goodbooks
0.21
L2
0.02
0.34
1.0
movielens
ORL
0.2
6.05
X
X
Figure 4: The loss surface of NMF along the straight line from a random point up to the local optima w* found via gradient descent from an independent starting point. We overlap 5 independent lines, zoom for detail. For all datasets, this loss surface convex, which is in line with what one would expect from Theorem I
observed entries is and divide the loss function by the number of (observed) entries. The initializa- tion is performed with half-normal distribution scaled so that the means match with the dataset. For simplicity we use the same gradient descent parameters for all datasets, a learning rate of 1e-7 with 1e4 gradient steps which gives convergence for all datasets. For the collaborative filtering datasets (movielens, netflix, and goodbooks) we have unobserved ratings, as is standard NMF we only compute the loss over observed ratings (Zhang al., (2006). In Figure 3 we plot the loss function between two random points drawn from the initialization distribution and see that the loss is convex. In Figure we plot the loss function from an initialization point to an independent local optima. These results agree with our planted model; the NMF loss-surface of real-world datasets seem to be largely convex along straight paths. Gradient descent of course only gives local optima but these still display nice star-convexity properties, however, finding the true global optima remains challenge.
4.2 ABLATION EXPERIMENTS
Theorem Daneemm[ssggee suggests that as the matrices become larger, NMF is increasingly likely to be star-convex. We are interested to see if this is the case for our real-world datasets, and to this end, we perform ablation experiments varying the dimensions of the matrices. We decrease the number of data points n by subsampling rows and columns uniformly randomly. Our measure of curvature at point x, given some optimal solution x* is
(xx min L" ("(xx" + (1 (1-))x) xE[0.1]
(6)
Note that 0 implies star-convexity. In practice, x and x obtained by random initialization and gradient descent as per the earlier section. For each dataset and subsample rate, we find 100 optima and evaluate the curvature from 50 random points, thus giving 5000 samples of a. Figure 5 show how the relative deviation, n of a decrease as the dataset becomes larger. As shown in Appendix C the curvature is always positive, thus the curvature becomes increasingly concentrated around its positive mean for larger matrices. We are also interested in investigating whether the loss surface is star-convex during training. In Figure []] we show that the cosine similarity between the negative gradients - (U V) and the straight line from Xg to x* is always positive, and how the loss surface is always star-convex during training. As per (Lee and Valiant 2016), star-convexity implies efficient optimization. In Figure 7 we illustrate the spectrum of singular values for U* found for the birdsong dataset, and random matrix of the same shape with iid entries from half- normal distribution. The spectra are similar, and while U is not random, seems to share structural qualities with the random matrices used in proofs. See Appendix for figures more datasets.

---

Under review as a conference paper at ICLR 2020
brddson
metabollo
0.12
0.035
0.30
0.06
0.221
0.03
4000
100
Figure 5: Illustration of how the relative deviation о/μ of the curvature equation 6 depend the dataset size. For all datasets, the relative deviations decrease with more samples, suggesting that the (positive) curvature become increasingly concentreated around its mean for larger matrices.
6)
0.59
0.55
0.0
0.04
0.00
0.80
Pep
Figure 6: a)) and b) show the cosine similarity between the negative gradient - -V, V) and the straight line (Un, Vo) (U*, V*), during training, for the ORL and movielens dataset. Notice that the cosine similarity is large and non-negative throughout training, showing that the gradients largely follow a straight line. c) and d) illustrate how the curvature equation varies during training for the ORL and movielens dataset. Note that it is always positive, and thus that the function satisfies star-convexity. Shaded regions represents 95 % confidence computed over iterations.
4.3 IMPLICATIONS FOR NEURAL NETWORKS
We have seen how increasing the number of parameters makes NMF problems more likely to be star- convex, and Figure 5 shows how more parameters make the curvature tend towards its positive mean. Theorem I suggest that this is a result of concentration of measure, and it is natural to believe that similar phenomenon would persist in the context of neural networks. has previously been observed how neural networks are locally convex (Tzmailov et al.) 2018 Kleinberg et al. (018)). and also how overparameterization important deep learning (Arora et al.) [018]] Frankle and Carbin 2018)) Based upon our observations in NME, we hypothesise that a major benefit of overparamettrrzztion making the loss surface more convex via concentration measure w.r.t. weights.
To verify this hypothesis, we consider image classification on CIFARIO (Krizhevsky et al. 2014) with Resnet networks (He ctt al. 2016) trained with standard parameters (see Appendix B) Networks are typically only locally convex, a property we quantify the length of subsets of random "lines" in parame- ter space, along which the loss is convex. We sample a random direction and then consider subspace of length one along this direction centered around the current parameters w. We then define the convexity length scale as the length of the max- imal sub-interval [}x A2] containing on which E(w + Ar) is convex. Directions are sampled from Gaussian distributions and then normalized for each filter f to have the same norm as the weights of f. Table 2 show how this length-scale of local convexity varies with depth, width, and training, where width is varied by multiplying the number of channels by k. Increased width indeed makes the landscape increasingly lo- cally convex for all but the most shallow networks, results that support our hypothesis. See Appendix for extended tables.
rnd mabrix
-2
log 5. -1
Fmax
Figure 7: Histogram of singular
values a; for found U* and ran- dom matrix. Note the similarity of the spectrum. Best viewed in color.

---

Under review as a conference paper at ICLR 2020
1.00
-.00
0.50 1.00
-2.00 6.02
3.5
0.25
Figure 8: The loss landscape of 110-layer Resnet architecture epoch 200 along two random directions, visualized as in Li et al. (2018). The network in the right image is four times as wide, and its loss landscape is increasingly convex. In Table 2 we generalize this idea, showing that the length scale of local convexity increases with network width.
Table 2: Typical length scales of local convexity for Resnet networks with various depth and width (indicated by k). We sample 25 random "lines" in parameter space of length centered on current parameters, and report average length of convex subset of such "lines". Increased width makes the loss surface increasingly locally convex, while convexity decreases with depth and during training.
20-layers
layers
68-layers
1 110-layers
epoch
k=2
k=4
k=l
k=2
k=4
k=l
k=2
k=4
k=1
k=2
k=4
0.96
1.0
1.0
1.0
1.0
1.0
1.0
1.0
1.0
0.94
0.94
0.94
100
0.87
0.84
0.87
0.72
0.79
0.83
0.71
0.76
0.87
0.79
0.75
0.91
200
0.81
0.74
0.73
0.66
0.68
0.76
0.6
0.71
0.8
0.71
0.71
0.82
300
0.71
0.72
0.75
0.57
0.68
0.78
0.58
0.67
0.81
0.63
0.68
0.82
5
RELATED WORK
Our work was initially motivated by findings in Kleinberg al.] (2018) and Zhou et (0019) re- garding star-convexity in neural networks. As the success of deep learning has become apparent, re- searchers have empirically investigated neural network trained on real-world datasets (Li and Yuan 2017 Keskar al., 2016). In the context of sharp flat local minima (Keskar et al. 2016). Li ct al. (018 illustrate how width improved flatness in a Resnet network, an observation Table quanti- fies. In general, real-world datasets
to be far that training neural networks are NP-hard (Blum and Rivest 1989). There is extensive work on non- worst-case analysis of algorithms and machine learning models, and what problem distributions can guarantee tractability which addresses such gaps (Bilu and Linial 2012 Afshani et al.) 2017). On the positive side Arora al. 2012) has shown exact algorithm for NMF that nomial time for small constant and there are positive results for 'separable' NMF (Donoho and Stodden 2004). Compressive sensing (Candes et al. 2004). smoothed analysis (Spiclman and Teng 2004) and problems with "planted" solutions (Barak et al. 2016) (Holland et al. 1983) similarly makes assumptions on the input. Researchers have also been interested theoretical convergence properties of shallow and linear networks (Lu and Kawaguchi 2017). where common theme is that functions with only saddle points and global minima can be effectively optimized (Ge et al.) 2013). In analysis of neural networks, random matrix theory often plays a role, directly or indirectly and Bahni 2017
well-behaved than the worst case, given
poly-
Choromanska et al. 2015 Glorot and Bengio
Xiao et al. 2018
CONCLUSIONS
This paper revisits NMF, a non-convex optimization problem machine learning. We have shown that NMF is typically star-convex. provably for natural average-cast -aae model and empirically observation that opti-
extensive set of real-world datasets. Our results support the mization might sometimes be easier in higher dimensions due concentration of measure effects.
8

---

Under review as a conference paper at ICLR 2020
REFERENCES
P. Afshami, J. Barbay, and T. M. Chan. Instance-optimal geometric algorithms. Journal of the ACM (JACM), 64(1):3, 2017.
R. Ahlswede and A. Winter. Strong converse for identification via quantum channels. IEEE Trans- actions Information Theory, 48(3):569-579, 2002.
N. Ampazis. Collaborative filtering via concept decomposition on the netflix dataset. In ECAI, volume 8, pages 26-30, 2008
Arora, R. Ge, R. Kannan, and A. Moitra. Computing a nonnegative matrix factorization-provablly. In Proceedings of the forty-fourth annual ACM symposium on Theory of computing, pages 145- 162. ACM, 2012.
Arora, N. Cohen, and E. Hazan. On the optimization of deep networks: Implicit acceleration by 2018.
overparameterization. arXiv preprint
B. Barak, S. Hopkins. Kelner, P. Kothari, A. Moitra, and A. Potechin. nearly tight sum-of- squares lower bound for the planted clique problem. In 2016 IEEE 57th Annual Symposium on Foundations of Computer Science (FOCS), pages 428-437. IEEE, 2016.
O. Berne, C. Joblin, Y. Deville, J. Smith, M. Rapacioli, J. Bernard, J. Thomas, W. Reach, and A. Abergel. Analysis of the emission of very small dust particles from spitzer spectro-imagery data using blind signal separation methods. Astronomy & Astrophysics, 469(2)-575-586, 2007.
Y. Bilu and N. Linial. Are stable instances easy? Combinatorics, Probability and Computing, 21 (5):643-660 2012.
A. Blum and R. L. Rivest. Training 3-node neural network is np-complete. In Advances in neural information processing systems, pages 494-501 1989.
D. D. Bourgin. Testing Models of Cognition at Scale. PhD thesis, University of California, Berkeley, 2018.
E. Candes, J. Romberg, and T. Tao. Robust uncertainty principles: Exact signal reconstruction from highly incomplete frequency information. arXiv preprint math/0409186, 2004.
E. Candès and B. Recht. Exact matrix completion via convex optimization. Foundations of Computational mathematics, 9(6):717, 2009.
X. canto Foundation. xeno-canto: Sharing bird sounds from around the world. https://wwe xeno-canto..og Accessed: 2019-04-19.
A. Choromanska, M. Henaff, M. Mathieu, G. B. Arous, and Y. LeCun. The loss surfaces of multi- layer networks, In Artificial Intelligence and Statistics, pages 192-204 2015.
C. Cortes and V. Vapnik. Support-vector networks. Machine learning, 20(3):273-297, 1995.
D. Davis. Mathematics of data science, https://people.ooee.ccmeeee... orie6340. html Accessed: 2019-04-19.
A. Decelle, F. Krzakala, C. Moore, and I.. Zdeborová. Asymptotic analysis of the stochastic block model for modular networks and its algorithmic applications. Physical Review E, 84(6):066106 2011.
D. Donoho and V. Stodden. When does non-negative matrix factorization give correct decom- position into parts? In Advances in neural information processing systems, pages 1141-1148, 2004.
A. Dvoredsky. Some results on convex bodies and banach spaces. 1961.
N. B. Erichson, A. Mendible, Wihlborn, and J. N. Kutz. Randomized nonnegative matrix factor- ization. Pattern Recognition Letters, 104:1-7, 2018.

---

Under review as a conference paper at ICLR 2020
J. Flenner and B. Hunter. A deep non-negative matrix factorization neural network. 2017.
J. Frankle and M. Carbin. The lottery ticket hypothesis: Finding sparse, trainable neural networks. arXiv preprint (ad3::/803303333 2018.
R. Ge. F. Huang, C. Jin, and Y. Yuan. Escaping from saddle tensor decomposition. Conference on Learning Theory, pages 797-842, 2015.
stochastic gradient for
N. Gillis. Sparse and unique nonnegative matrix factorization through data preprocessing. Journal of Machine Learning Research, (3(Nov)3334--3366 2012.
N. Gillis. The why and how of nonnegative matrix factorization. Regularization, Optimization, Kemels, and Support Vector Machines, 12(257), 2014. 2014.
X. Glorot and Y. Bengio. Understanding the difficulty of training deep feedforward neural networks. In Proceedings of the thirteenth international conference on artificial intelligence and statistics, pages 249 256, 2010.
A. Guionnet, O. Zeitouni, al. Concentration of the spectral measure for large matrices. Electronic Communications Probability, 5:119-136, 2000.
M. Harper and J. A. Konstan. The movielens datasets: History and context. Acm transactions on interactive intelligent systems (tiis), 5(4):19, 2016.
K. He, X. Zhang, S. Ren, and J. Sun. Deep residual learning for image recognition. In Proceedings of the IEEE conference on computer vision and pattern recognition, pages 770-778, 2016.
W. Hoeffding. Probability inequalities for sums of bounded random variables. In The Collected Works of Wussily Hoeflding, pages 409-426. Springer, 1994.
W. Holland, K. B. Laskey, and S. Leinhardt. Stochastic blockmodels: First steps. Social networks, 5(2):109-137, 1983.
P. O. Hoyer. Non-negative matrix factorization with sparseness constraints. Journal of machine learning research, 5(Nov): 2004.
P. Izmailov, D. Podoprikhin, T. Garipov, D. Vetrov, and A. G. Wilson. Averaging weights leads to wider optima and better generalization. arXiv preprint 1at::::8000050000 2018.
N. S. Keskar, D. Mudigere, Nocedal, M. Smelyanskiy, and P. Tang. On large-batch training for deep learning: Generalization gap and sharp minima. arXiv preprint arXiv: fitv:1609 (609.04836, 2016.
R. Kleinberg, Y. Li, and Y. Yuan. An alternative view: When does sgd escape local minima? arXiv preprint ar 1802.068 2018.
Y. Koren, R. Bell, and C. Volinsky. Matrix factorization techniques for recommender systems. Computer, (8):30-37, 2009.
A. Krizhevsky, V. Nair, and G. Hinton. The 10 dataset. online: http://ww.. cs. toronto. edu/kriz/ifar: html, 55, 2014.
M. Kula. Mixture-of-taste models for representing users with diverse interests. arXiv preprint 1rX1v:1711.0839, 2017.
M. Ledoux. The concentration of measure phenomenon. Number 89, American Mathematical Soc., 2001.
D. D. Lee and Seung. Learning the parts of objects by non-negative matrix factorization. Nature, 4015575)) 1999.
D. D. Lee and H. S. Scung. Algorithms for non-negative matrix factorization. Advances in neural information processing systems, pages 556-562, 2001.
C. Lee and Valiant. Optimizing star-convex functions. 2016 IEEE 57th Annual Symposium Foundations of Computer Science (FOCS), pages 603-614. IEEE, 2016.
10

---

Under review as a conference paper at ICLR 2020
H. Li, Z. Xu, G. Taylor, C. Studer, and T. Goldstein. Visualizing the loss landscape of neural nets. In Advances in Neural Information Processing Systems, pages 6389-6399 2018.
L. Li, G. Lebanon, and H. Park. Fast bregman divergence nmf using taylor expansion and coordi- nate descent. In Proceedings of the 18th ACM SICKDD international conference on Knowledge discovery and data mining, pages 307-315. ACM, 2012.
S. Z. Li, X. Hou, H. Zhang, and Q. Cheng. Learning spatially localized, parts-based representation. CVPR (1), 207:212, 2001.
Y. Li and A. Ngom. The non-negative matrix factorization toolbox for biological data mining. Source code for biology and medicine, 8(1):10, 2013.
Y. Li and Yuan. Convergence analysis of two-layer neural networks with relu activation. In Advances in Neural Information Processing Systems, pages 597-607, 2017.
C. Lu and X. Tang. Surpassing human-level face verification performance Ifw with gaussianface. In Twenty-ninth AAAI conference on artificial intelligence, 2015.
H. Lu and K. Kawaguchi. Depth creates no bad local minima. arXiv preprint 170.:8170,.08580, 2017.
X. Luo, M. Zhou, Y. Xia, and Q. Zhu. An efficient non-negative matrix-factorization--oo approach to collaborative filtering for recommender systems. IEEE Transactions on Industrial Informatics, 10(2): 2014.
Y. Mao, L. K. Saul, and M. Smith. Ides: An internet distance estimation service for large networks. IEEE Journal on Selected Areas in Communications, 24(12):2233-2284, 2006.
M. Meckes and S. Szarek. Concentration for noncommutative polynomials in random matrices. Proceedings of the American Mathematical Society, 140(6):1803-181) 2012.
V. Mnih, K. Kavukcuoglu, D. Silver, A. Rusu, J. Veness, M. Bellemare, Graves, Ried- miller, A. K. Fidjeland, G. Ostrovski, et al. Human-level control through deep reinforcement learning. Nature, 518(7540):529, 2015.
M. Pardalos and S. A. Vavasis. Quadratic programming with one negative eigenvalue is np-hard. Journal of Global Optimization, 1(1):15-22, 1991.
Pennington and Bahri. Geometry of neural network loss surfaces via random matrix theory. In Proceedings of the 34th International Conference on Machine Learning- Volumee 70, pages 2798- 2806. JMLR. org, 2017.
M. N. Schmidt, J. Larsen, and F.-T. Hsiao. Wind noise reduction using non-negative sparse coding. In 2007 IEEE workshop on machine learning for signal processing, pages 431-436. IEEE, 2007.
D. A. Spielman and S.-H. Teng. Smoothed analysis of algorithms: Why the simplex algorithm usually takes polynomial time. Journal of the ACM (JACM), 51(3))385-466) 2004.
S. K. Suram, Y. Xue, J. Bai, R. Le Bras, B. Rappazzo, R. Bernstein, J. Bjorck, L. Zhou, R. B. van Dover, C. P. Gomes, et al. Automated phase mapping with agilefd and its application to light absorber discovery in the v-mn-nb oxide system. ACS combinatorial science, 19(1)337-4,, 2016.
G. Trindade, M.-L. Abel, and J. F. Watts. Non-negative matrix factorisation of large mass spec- trometry datasets. Chemometrics and Intelligent Laboratory Systems, 163:76-85, 2017.
J. A. Tropp. User-friendly tail bounds for sums of random matrices. Foundations of computational mathematics, 12(4):389-434, 2012.
S. A. Vavasis. On the complexity of nonnegative matrix factorization. SIAM Journal on Optimiza- tion, 20(3): 364-1377, 2009.
R. Vershynin. Introduction to the non-asymptotic analysis random matrices. 1011 2010.
arXiv preprint
11

---

Under review as a conference paper at ICLR 2020
R. Vershynin. High-dimensional probability: An introduction with applications in data science, volume 47. Cambridge University Press, 2018.
L. Xiao, Y. Bahri, J. Sohl-Dickstein, S. S. Schoenholz, and J. Pennington. Dynamical isometry and mean field theory of cnns: How train 10,000-layer vanilla convolutional neural networks. arXiv preprint (1060058030333 2018.
S. Zhang, W. Wang. J. Ford, and F. Makedon. Learning from incomplete ratings using non-negative matrix factorization. Proceedings of the 2006 SIAM international conference data mining, pages 549-553. SIAM, 2006.
Y. Zhou, D. Wilkinson, R. Schreiber, and R. Pan. Large-scale parallel collaborative filtering for the netflix prize. In International conference on algorithmic applications in management, pages Springer, 2008
Y. Zhou, J. Yang, H. Zhang, Y. Liang, and V. Tarokh. Sgd converges to global minimum in deep learning via star-convex path. arXiv preprint arXiv:1901.00455 2019.
G. Zhu. Nonnegative matrix factorization (nmf) with heteroscedastic uncertainties and missing data. arXiv preprint arXiv: 1612,60077 2016.
12

---

Under review as a conference paper at ICLR 2020
A DATASETS
Here we describe the datasets we used to evaluate our results on and provide references for them.
Birdsong:
time series for bird calls, (Flenner and Hunter 2017
canto Foundation).
Extragalactic: dataset for extragalactic light sources, see (Zhu (2016).
Goodbooks: ratings for books, (Kula 2017 Bourgin 2018).
Metabolic:
Yest metabolic activity time series, see Li and Ngom 20133
Movielens: user ratings for movies, see (Harper and Konstan 2016 2006).
al. 2012
Zhang al.,
Netflix: User ratings for movies, see (Zhou et al.
2008 Ampazis 2008 et
2012).
ORL faces: black and white facial images, see (Li al. [200]] Hoyer 2004).
Satellite: satellite urban spectral-image see (Erichson et al. 2018 Gillis 2014).
B DNN PARAMETERS
Table presents the hyper-parametee used for training the neural networks. Data augmentation consists of randomized cropping with 4-padding and randomized horizontal flipping. The learning rate is decreased by a factor of after epochs (150, 225, 275). We use the standard Resnet architec- ture for CIFARIO with three segments with (16, 32, 64) channels each, and the standard blocks (i.e. not bottleneck blocks) (He et al. (016).
Table 3: Hyper-parameters used for training.
Parameter
Value
init. learning rate
0.1
SGD momentum
0.9
batch size
128
weight decay
0.0005
initialization
Kaiming
loss
cross-entropy
C EXTENDED NMF FIGURES
D PROOFS
D.1 OVERVIEW
We here provide the proof of Theorem In section D.2 we present the notation and derive the main inequality. In Section D.3 prove that the loss function is convex between any random points with high probability. Section D.4] we prove that this also holds towards the planted solution. For the case with unobserved data, we prove that the loss function convex between any two random points with high probability in Rection[D.5) That this holds towards the planted solution in the case of unobserved data follows from previous sections, and the proof of this fact omitted. Together, these results form Theorem as stated in the main text. Section D.6 presents the concentration
Table 4: Continuation Table
32-layers
56-layers
80-layers
epoch
k=l
k=2
k=4
k=
k=2
k=4
k=2
k=4
1.0
1.0
1.0
1.0
1.0
1.0
1.0
1.0
1.0
100
0.77
0.8
0.84
0.7
0.81
0.84
0.72
0.85
0.81
200
0.61
0.68
0.8
0.63
0.67
0.8
0.59
0.7
0.77
300
0.55
0.68
0.82
0.57
0.66
0.79
0.63
0.71
0.79
13

---

Under review as a conference paper at ICLR 2020
Table 5: Table for architectures without skip-connections
20-layers
32
44-layers
epoch
k=1
k=2
k=4
k=1
k=2
k=4
k=1
k=2
k-4
0
0.15
0.62
0.15
0.2
0.84
1.0
0.43
0.33
1.0
100
0.71
0.79
0.93
0.68
0.7
0.83
0.57
0.61
0.6
200
0.74
0.67
0.8
0.63
0.63
0.86
0.57
0.6
0.67
300
0.69
0.63
0.82
0.5
0.63
0.84
0.47
0.56
0.67
birds
extragalactic
goodbooks
2.4
0.004
1.6
0.6
5000
10000
0
5000
10000
5000
10000
metabolic
netfixx
sateliite
0.3
0.02
0.0
0.00
5000
10000
5000
10000
5000
10000
stop
stop
step
Figure 9: The curvature equation 6 during training, in Figure for various datasets. Note that is always positive, and thus that the function satisfies star- star-convexity. Note the small shaded regions, which represents the 95 % confidence computed over repetitions.
Table 6: Links for used datasets.
dataset
link
birdsong
extragalactic
oraaff/feeeeeaaaaaooooooooooaaar ga
metabolic
netflix ORL
a
satellite
http://
results we need. The proofs include considerable amounts of elementary algebraic calculations. For completeness and ease of reference, present these in Appendix
14

---

Under review as a conference paper at ICLR 2020
birds
extragalactic
goodbooks
0.9
0.904
codtne
0.980
0.6
5000 metabolic
10000
5000
10000
5000
10000
netflix
satellite
1.0
0.9
0.8
0.8
0.6
5000
10000
5000
10000
5000 10000
step
step
Figure 10: The cosine similarity between the negative gradient (U, V) and the straight line (Un, Vo) - (U*, V*), during training as in Figure 6 Note the small shaded regions, which represents the 95 confidence computed over 5 repetitions.
extragalactic
satellite
0.09
0.16
d std
0.12
0.03
0.08
#rows
#rows
Illustration of how the relative deviation o/p of the curvature equation 6 depend on the dataset size as Figure Unfortunately, computing these figures for the larger Netflix and Goodbooks datasets is computationally infeasible for us.
Figure 11:
D.2 NOTATION AND THE MAIN INEQUALITY
The proof will involve various constants co, that do not depend on n. For convenience, we will let exact values be context dependent and will reuse the symbols co, C1 C2 and so on. The proofs will not depend on the exact values of these constants. Constants in our main result can be improved slightly, but at the cost of more complicated expression. We present the non-optimized version. We will let boldface capital letters denote matrices, boldface lower-case letter vectors and non-boldface letters denote scalars. Let U1. U2, U be n--y-r matrices and VI, V2. V* r-by-m matrices sampled per Assumption I Without loss of generality, We will let pvar be the expectation, and o² be the variance of the entry-wise distributions. We will denote the centered variables by U1, V, and so and the mean matrix of U and V resp U + 1axr- By slight abuse of notation, we will use the convention (x, Y) Tr (XY") for matrices X, of the same shape. The loss function we wish to minimize, subject non-negativity constraints, is
assume nem where 0 < Cm & 1.
as 1 1,x, Trxm- Then
15

---

Under review as a conference paper at ICLR 2020
birdsong
extragalactic
goodbooks
metabolic
md matri
matni meentt
and mot
14
md morri
0.4
-2
-1.3
LL.
-05
9.3
-25
-20
-55
-LB
-35
0.0
-15
-10
-05
0.0
0.5
1.
movielens
netflix
ORL
satellite
md marri
manns
1.75
manrs
2.0
md marco
U meins
U mairi
U" metri
U meiie
15
0.75
1.0
10
0.50
0.5
0.25
-2.0
-1.
-3.5
-0.5
0.0
-3.5
-1.0
-0.5
0.0
0.00
-2
0.0
-10
-5
log
Jog
log
log
Taaax
dmaas
Figure 12: Histogram of singular value spectra for U found via gradient descent and random matrix of the same shape with entries drawn iid from half-normal distribution. For the datasets with larger ranks, the spectra typically agree significantly.
birdsong
extragalactic
goodbooks
metabolic
md
mabis V Vmmarrx
matric V V*
V mann
15.0
V"tratna
125
0.4
1.0
75
0
5.0
0.5
2.5
0.0
-0.5
0.0
-2.0
-1.0
-0.5
6.
0.0
movielans
netflix
ORL
satellite
md manrt
nnd matria mabti
md metits
mi matti mahro
V Virato
10
V Vmmtra
25
2.3
1.5
1.0
0.5
4.00
-1.5
+3.6
-0.5
0.0
-3.5
-3.0
-0.5
0.6
-2.0
+1.5
-1.0
+85
5.6
0.0
-1.5
-1.0
-5.5
0.0
5.5
log
di
log
log
01
Figure 13: Histogram of singular value spectra for V found via gradient descent and random matrix of the same shape with entries drawn iid from half-normal distribution. For the datasets with larger ranks, the spectra typically agree significantly.
16

---

Under review as a conference paper at ICLR 2020
(U. - 2
-U,V)-
- X
When we interpolate the solution UV between any fixed two points (U1, V1) and (U2, V2), we write
X(()= (AU1 +1 AJU2) + (1- (1-A)VV)
The loss is then
1
- ((A) - X
2
Proving Theorem in the case of two random points and completely observed data amounts to showing that the continuous function ((X) is convex in À on the interval [0, 1J with high probability. We will show that the second-derivate is non-negative. For fixed matrices U1, U2, U 1I. V2, V*, the loss ((A) is fourth-degree polynomial in X, so its second derivate w.r.t. À will be second- degree polynomial. For a general second-degree polynomial p(z) = ax? + bar + e. we have p(x) = _[(ax + 1)2² + (ac- ). By inspecting equation & one can conclude that a >> O. Showing that 8² the polynomial is non- non-negative can then be done by showing ac > 1 Let (A)(A) be element i.j of the matrix X ()). The derivates of E(A) are then
((A) 2
Σ -X),
17
((A) - Σ (2) - x,,)8,(())
19
((()) = Σ 8Y (2) (A) - -X,) + +A)
(2) 3 Σ (A),,,)
(A) = 3 Σ (2)
(8)
Where we have
x(()= 1AU,+(1
+(1 A)U2) (11-))U; + +(1-))V,)
X((A) = U1 - U2) 1V, (AVI+ + (1- --/ss)) + (A (1 ) (Vi V22
x²())= 2 2(U, -U2) V1 (Vi-Vz) V/2
Let us define
Wo= = U2= U
W, U, U
U2) -12
V2+
U2 Vi V2
W₂ - (U, Un Vi - V/))
17

---

Under review as a conference paper at ICLR 2020
By expanding (A) in a McLaurin series around O, see that proving non-negativity of L (A) can be done by proving (0 en" (0) > (0) Thus, proving Theorem 3 then amounts to showing that
W (IWil (I 2(W, W2)) 3( W2))
D.3 PROVING THE INEQUALITY BETWEEN RANDOM POINTS
Theorem 2. Let (U1, V1). (U2, V2) and the planted solution (U V*) be sampled as per As- The loss function equation is convex on straight line connecting (U1, V1) and
sumption !
(U2, V2) with probability > -- exp
c2n ) for positive constants c1, c1.
Proof.
As per section D.2 we only need to prove that equation holds with probability 1
C1 exp (23 Let exhange all terms in equation 9 with their means, which are given in
Facts
7 5
and 8
(errmno""(rrmo''" 4rmnp 0² + 2rmma*) > 3(- 4rmmno))
(10)
Clearly, equation 9 would hold if one naively exchanges the terms for their means. Just counting terms of order rmnod we have 64 on the LHS and 48 on the RHS. We need to show that deviations sufficiently large to violate the inequality are unlikely. Our strategy will be to show that the factors are exponentially unlikely to deviate substantially individually, and then use union bounds. The concentration results and their derivations are detailed in Section D.6
Consider the random variable || [22 As per equation 14 Wall can be rewritten into polynomi- als of centered random matrices where we have to pad the matrices with rows/columns of all zeros. We can then apply the concentration result of Fact |
to conclude that the probability that [|2l deviates from its mean by a factor (1 + E) is no more than 01 exp(-cze"n).
| W can be rewritten as the sum of expression equation I6 plus terms of centered variables. The latter expressions are polynomials in centered random matrices, after padding some columns/rows with zeros we can apply Fact [ to conclude that the probability that it deviates from its mean by factor (1 is no more than C1 exp(-c2(2n). Consider the expression equation 16 Clearly the expressions
Now, consider the random variable [ 12- As the proof of Fact 7
will be psd, and thus their trace will be nonnegative. We can thus lower bound the LHS of equation 10 by omitting the terms in equation [6. and will thus only consider terms scaling as rn?o4.
IT [U, U2) (U, U2) 1yxm and (V, V2) 1TTTT
EXT Inxr V1
V2)
Now, consider the random variable <Wo, W2). As per equation 19 the variable (Wo, W2) can also be separated into two parts. After padding with some zero rows/columns to obtain square matrices, the first is a polynomial in centered matrices for which Fact the probability of deviations by factor (1+ e) by C1 exp(-c2e"n) The second one is sum of the type 1X,X, modulo permutations, under which the trace is invariant. We can thus apply Fact 2 which bounds the probability for deviations of size e Wo, W2) by Ci exp (- (-Ecgn2/3)
which again bounds
At last, consider the random variable (W1, 2... By equation 18 can, just like (Wo, W2), be written the sum of polynomial in centered random matrices, and sums of variables of the type 1x, X3X3 modulo permutations. We can thus apply the same argument as for (Wo, W2) to bounds the probability for deviations of relative size e by exp ( EC3)
We can now apply union bound on the variables W.1 | modulu term equation [6] deviating from their respective mean by factor e. The probability that either of them does is more than Ci exp ( (- o2e 2/33 by union bounds. Now, neither variable deviates by a factor of more than 0.01, then equation [tjt holds if we only count terms scaling 4 since 0.992., 64 1.01 48. Thus, inequality is violated with probability most ej exp c2n4/33 for positive constants C1, C2.
(Wo. Wa) and (W1, W2).
0.01 If
18

---

Under review as a conference paper at ICLR 2020
D.4 PROVING THE INEQUALITY TOWARDS THE PLANTED SOLUTION
Theorem 3. Let (U1, Vi) and the planted solution (U*, V*) be sampled as per Assumption
The loss function of equation iss convex on straight line connecting (U1, V1) and (U*, V*) with
probability 01 exp ( c2n²/a) for constants C1 C2 >
Proof. To prove this, we can repeat the argument used in the proof of Theorem 2 The terms |W 22 Will and (Wi, W2) will have the same mean and concentration since Un and U are identically distributed. The only difference will be the term <Wo. W2), which now will have mean 2rmno per Fact[10] This will only make the LHS of equation [r]ler so the inequality will still hold and the concentration of measure properties will ensure that equation Wholds with high probability as in the proof of theorem
D.5 PROVING THE INEQUALITY BETWEEN RANDOM POINTS FOR UNOBSERVED DATA
As explained in the main text, we will assume that entries are observed with independent probability We formalize this in the following assumption
Assumption 2. For any n, let i e {0, 13 1 have entries iid drawn from Bernoulli distribution with probability p. which is constant w.r.
Given any set of observations 1, we define our loss function
(U,V) Eiao (LVV -x.)
(1I)
Theorem 4. Let (U,, V1). (U2, V2) and the planted solution (U*, V*) be sampled as per As-
sumption
[
Let the set of observations i be sampled per Assumption 2 The loss func- 17 is convex on a straight line connecting (U1, Vi) and (U2, V2) with probability
tion equation
2 1 -1-ch Ci exp
c2/2/3) for constants 0ı, 02 > O.
Proof. If no entries are observed, we can claim trivially that the function is convex. some entries are observed, then a > 0 since 1y (A)2 O for any (i,j) with probability 1. The second derivate of equation can be written as
(2) Σ Cia
X + (X -x,))
Using Lemma 1 with probability & cin² exp (20) Note that this estimate gives the exp -o2r1/3) scaling of the proof. Let assume that the entries are bounded like this, then no entry in X X" will have magnitude more than 4/3)) for any X. Standard Hoeffding bounds Hoeffding 1994) states that for variables (a:)) bounded [Ac, B.] we have
we can assume by union bound that no entry in X, X', X", X is larger than (1))/3)
X
2n222
P
& eexp
Σ" (b: - az))
Let us define
v(A)
Σ x (A) + X" (8, Xis)
Let us now consider fixed matrices U, U2 U V,, V2. V satisfying Lemma but i remain a random variable. We can then consider the product of any two variables out of X,, X, x"; X, fixed constants in the interval [-crr4/3 e 1/33 for some constant C1. We note that y (A) is the
19

---

Under review as a conference paper at ICLR 2020
sum of nm variables, each of size at most (1443)) Now y(A) is sum of independent variables and Hoeffdinger applies with (b, a,)² x (1 for all i. Taking cr gives
-(U E[U(A)] 3 2r2
2c 2m
& exp
& exp (-en 2/3)
cn2
n238/3
This will hold for any A. We can assume that this holds for let's say 3 evenly spaced À by union bound. Using union bounds, assume the following: v(A) > crrmn for all X, which follows from the derivation of Theorem 2 with probability > C1 exp(-c2n
2) |X,ز] & 22/3 for all E via Lemma I 3) (Y E[y(A)]I & 2/3 for 3 evenly spaced X by the above equation.
Now, since the (A) is second-degree polynomial, if it's close to its expectation at 3 places, it must be close it its expectation everywhere. Formally, we can define the second-degree polynomial ((A) = y(A) Ely(A)J- Now, our union bounds states that lύ(A:)] < cr2 for three evenly spaced A; Now, let the three coefficients of the second-degree polynomial be described by the vector p. its values at A; by the vector and let the matrix A describe the values of the monomials Now, A will have elements bounded by but will be full rank,
1, X at A₃. We then have Ap this implies that if is bounded by 2r2/3 must p be. The fact that the coefficents in have absolute value bounded by Orr2/3n n2n together with the fact that the mean scales as rn gives us the following
min ((A) min ((A) [[]( > min (A) + min F[y(X)]
X
3 min ((A) + ern? 3 2/2 + crn?
Here is positive as per assumptions, whereas e' might be negative. Now. for sufficiently large r, the above quality will be non-negative. We can thus find new constants, based upon and d', to complete the proof.
D.6 CONCENTRATION
This section contains the concentration results needed for the proof of Theorem ! results from random matrix theory, which has stronger results for matrices with independent entries that are concentrated (Ahlswede and Winter 2002 Tropp (2012, Guionnet et al., 20000.. We will use the concentration results of Meckes and Szarek (2012) which relies on the notation of CCP - convex concentration property which is regularity condition.
We will use
Definition 2. A random matrix X in normed vector space satisfies CCP iff there exists positive constants Cı C2 such that P([[(X) - MS(()) > 1) & c for all and all convex 1 1-Lipschitz functions f. Here M. is the median.
One can easily verify that independent Gaussian variables satisfies this (Ledoux 200T), and it then follows that I-Lipschitz functions of Gaussians also satisfies CCP. One important class here is the half-normal distribution which is just the absolute value of a Gaussuan variable, and absolute value a 1-Lipschitz function. Any vector of independent bounded variables will also satisfy CCP (Meckes) and Szarek 2012).
Fact 1. Let P be a polynomial of degree in centered matrices X,, Y, X, otherwise sampled per Assumption [ where we allow i j. j I and any other arbitrary index relationship. Let Tr P(X,, Xj, Xx, X,) and let μ be then mean of then P([= pl trn?) & ea exp 22 min(12,11/2)) n) for positive constants c1, 62.
Proof. Any vector CCP where some components are zero will still be CCP, this we can pad the matrices X;, X,, Xx, X, so that they are square. We then invoke Theorem of Meckes and Szarek 2012) which gives
P 11| > Tn? & e exp 02 min(72, 1(12)
20

---

Under review as a conference paper at ICLR 2020
Setting tr gives us
p(1=-1|>11 = & ei exp ( 0 min( 22,,, 2//2 n))
Using our assumption r On))) for some y e [1/2, 1] gives
P [|=-u|>tr>? & ci exp ( 02 min((, (012,111) (11))) n)
Fact 2. Let Tr (IX,X,Xs) for centered matrices X., X, otherwise sampled per As- sumption 7 and let be the mean of 2. is a matrix of all is of the appropriate shape. Then P(1= M 2 tr?) & exp c2n c/3 min(tt?? f?)) for positive constants C1 C2-
Proof. As before, we can pad the matrices to be square while retaining the CCP property. We note that the singular value of the matrix is at most n. This means that shatten-norm [E I|[x: is at most n for all k. Let us consider the matrix 2t7 2/3 For this matrix, Theorem 1 in Meckes and Szarek (2012) applies, that we have
1 which then has shatten-norm | a is at most
p[[m Tr IX,,XXX, -
!n?
& c1 exp 02 min (P, nt!
(12)
Let us take / lorn 10rm-1/3 11/3 so that In333 lorn?. We then have
Tr (ix,X,Xx 11] tn²
(IX,XX, - H) > 7/3
Tr (IX;X,X; w) torn?
By substituting 1orn-1/1 1/3 into equation 12 we then have
(TX, - -4] 2 torn?
(13)
ci exp (- 02 min (1/r2 2/33 , 2-1/))
Recall assumption cyn" for [1/2, 1]. We then have
min (2 to
2/3
1/2 1/2 min (t) {)) 1/3
Plugging this into equation completes the proof
With probability & cin² exp (222)//3) no entry in Xig, Xig. X'y, Xij has an absolute value larger than 2/3, for some positive constant
Lemma 1.
Proof. For a fixed i,j consider the terms Xij. X ijt ig Xij- Fact 9 says that each one can be
expressed as constant number of variables with zero mean of the form
(2)
Since the variables themselves sub- gau-gaussian, by Lemma 2.7.7 in Vershynin (2018) the product (1) (2) is sub-exponential. Thus, the variable a is a sum of iid sub-exponential variables, and Theorem 2.8.1 in Vershynin (2018) states that
t
P([a) > 1) & 2exp -emin
rk? K
21

---

Under review as a conference paper at ICLR 2020
Here K is the orlicz norm || - [[,, which is constant for fixed distributions. In the above expression, let us set t cr This gives
P P(
E[a]
> 2/3/3
< 2exp (- (-cr!/3) cr!/3)
We note that there a polynomial number of entries a, so we can a polynomial number (w.r.t n) of union bounds, which might change the constants, to show that no entry is further than c from its expectation for some positive 61.
E
ALGEBRACC CALCULATIONS
E. BASIC FACTS
Fact 3. E T[UUUUV
rmno 1
Proof. We have
TTU'Ov E
Σ
VaVV
Kik!
Taking the mean, and using linearity of expectations, we only have nonzero mean if = k. We get
E
Using linearity of expectation and independence, this becomes
Σ
For single matrix entry, E [ goes over the rows of of which there are n and goes over the columns of of which there are m, clearly get rrmn.
a2. goes over the columns of of which there are r.
Fact 4. E
Tr TUU rxm rxm
ramp 2
Proof. We can can first contract then want to find
1
1f rxm
Impbar where is a r-by-r matrix of all ones. We
E
U
Now since the variables are centered, the expectations becomes zero unless i k. The sum thus becomes
E
Σ
U
= nro
This gives us the result of 2mmp2 22
E.2 EXPECTATION
Fact 5. [[ W
4mmrgg
22

---

Under review as a conference paper at ICLR 2020
Proof. Let rewrite B[] W2ll
E'IT (u) Trace and expectations are linear operators, so we can reorder them. Let us consider the matrix
U2)
T Vi (vivv)> ( (vi-v))(ui.vv,
T (v,
U2
(v, (vi-V) V2)
We can easily add and subtract the mean μ of all matrices which gives
V1 Vi-va (U, (..)))(( (U,
UU
V.2
(14)
Expanding the parantheses gives us 16 matrices, however they will have zero mean unless both the U-matrices and V-matrices ar the same. For calculating the mean, we can thus only consider four matrices of the type VTU"UV. Permuting the indices cyclically and appealing to 3
W2 3 4mnro
Fact WW W2) rmno4
Proof. We can write W. W2)] as
T (v ((U,- V2)
Again, we want to add and subtract the matrix means Ixx, 1rxm to get
ETr (Ive "V,""U,"" T,," -V'+VV''' TT nxr
+1 +x,x U2 T + rxm nxr -
1
-+
U+ +
nxr rxm U+ T + + 1 nxr
+1
(15)
(.) -v)
As before, we can remove terms which are linear in any centered variable. This removes matrices with index 1, and leaves
ETr
( V₂
U2 V2"U,""
+ V2 1s
Txx + 1s rxm
U²²)
(UoV.)
Applying fact
3 to the only term that remain gives
WW, W2 =
ET
V T U, T
U.V.
rmno
Fact W 12 6 4rmm
Proof. We rewrite E|[W, 1. as
ET ( V ( (U) (V, V2) U3² (IV, U2 U2(V, V2))
We will again want to center the variables, which gives
T [v V -U2)" + pxm 11-U. - + (U, V,) " (V, V,) T nxr
23

---

Under review as a conference paper at ICLR 2020
x( (U,) (U, -01-U,) 12) U2 V2) Ixx (V, Va)
]=)
Let us first consider the terms involving constants. We remove any terms linear in centered variables. We are then left with
px (Ú, (U.
+ (V. V2)"
nxr Ixx (V -V)
(16)
As before, any expressions linear in centered variables vanish when we take expectations. this and Fact we get that the above expression is equal
Using
4rmmp 2 o²
We now return to the terms without constants These are
( - (V, - V2) U2 U2(V (V, U, Vz)
(17)
+ 2 UZ) UV U,, - V2) (V, V22) T U (U, U2
As before, we remove any expressions linear centered variables. As turns out, we are left with 6 terms of the type V2 U, U2 Applying Fact gives us
T
W | Grmno 4rmmpper
Fact W2, Wi> = -4rmno
Proof. Let rewrite E(W,, W1) as
vz) Vo (MN
U.) -Va)
T
As per usual, we center the variables
- [Vv..vo'" (U), ( (ū,-U,)) 1
1 (V1-Vz) (i-Va)
(18)
Any terms involving the constant will be linear in a centered variable, and thus disappear under expectations. Equating like terms and using Fact 3 we get
-E
TrV
TVV
T U
T
U.V,
Armno
E.3
OTHER ALGEBRAIC FACTS
Fact 9. For any fixed j the entries of X, X' and X" are mean.
Proof. We have
*(A) - - (XU, + (1- (AV (1-
A)V2) V
X((A) = (U--U:) U2) + -(1-
+ (AU, + (1 (1- (1-))U2)(M V2)
x(()) (U,-U)) -U) (v, -V2)
24

---

Under review as a conference paper at ICLR 2020
The fact that U1 and U2 are iid implies that (U1 U2) has zero mean, and the similar holds for Vi and V2. This implies that all terms of X' and X" zero-mean. Using the fact that U1, U2 and U are iid implies that
E +1 + (VV
E[U*V*
This, in turn, implies that [[X] 0. Fact 10. For U1 U and V1 = V we have W. W2)] = 2rmmo*
Proof. We can write BK 0. W2) as
E'Tr
V - (())())))))) (1U+-U>)
Again, we want to add and subtract the matrix means 1xr, lx to get
ETr (Iv "U="" +V," 1TT exr +1 U2 + +1,x Txr] - U+* +V+ 17
1xxx+ +1 U+
+1
1 nxr
rxm
(19)
Uv)
As before, we can remove terms which are linear any centered variable. The only term that remain gives
WW. W2)] = ET
V2
U2V2
T
+ ETr
V* T U U*V*
2rmno
25


Reviews:
[{"review_id": "rkg28BBhtB", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "1.\tTypos: \n(1)\t“We will consider slighly weaker notation of…” in page 3 should be “We will consider slightly weaker notation of…”.\n(2)\t“The same holds along the line line…” in page 3 should be “The same holds along the line…”.\n(3)\tA comma should be added between $U^*$ and $V_1$ in the Subsection ‘Proof sketch of unobserved Data’ in page 5.\n2.\tFigure 3 presents the loss surface of NMF on straight paths connecting two random points for 8 real-world datasets. From this figure, we can see that the minima is obtained around lambda equals to 0.5. Whether the authors can explain this phenomenon? Besides, the authors should annotate the differences among each curve in each subfigure in Figure 3 and Figure 4.\n3.\tExperiments utilize 8 datasets to demonstrate the good performance of the proposed planted model. The decomposition rank are given in the previously literature. However, in practice, the rank of a new dataset is unavilable. How to handel this situation?\n4.\tThere are unknow elements in Goodbooks, Movielens and Netflix datasets. These can be processed by the given sparsity. However, there is no items in the proposed planted model that can handle the sparsity.\n5.     Open codes about this paper.\n", "extra_scores": {"experience_assessment": "I have read many papers in this area.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory.", "review_assessment:_checking_correctness_of_experiments": "I did not assess the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper."}, "extra_text": {}}, {"review_id": "rkeCQ6JaKB", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper studies loss landscape of Non-negative matrix factorization (NMF) when the matrix is very large. It shows that with high probability, the landscape is quasi-convex under some conditions. This suggests that the optimization problem would become easier as the size of the matrix becomes very large. Implications on deep networks are also discussed. \n\nThe NMF problem is known to be NP-hard. In case that the matrix X to factorize is large, the author(s) uses concentration property of random matrix to show that along any random positive matrix U,V and U’,V’, the MSE loss of NMF is convex with high probability.  The extra assumption is that the rank of U and V should also be large enough. Section 3 is devoted to prove this. It seems to me there are some typos which are quite serious and make the equation (3) incorrect. However, the main result (Theorem 1) still seems to hold. The equation (3) should replace W_2 with 2 W_2. The reason is in the appendix D.2, the definition of W_2 has missed this constant 2, which is the hat X’’(lambda) at lambda=0. Therefore, all the constants in the equation (4) need to be modified accordingly. In D.2, to derive the equation (9), it seems to me the McLaurin series should give 2 l’’’’(0) l’’(0) >= (l’’’(0))^2, isn’t it? The whole proof is quite long to check. In Fact 1, is the mu the mean of z? In Lemma 1, what is lemma 9? Fact 10 has a constant 2 which seems to be forgotten. Therefore significant modification is needed to correct all the errors. \n\nRegarding experiments, some data-set in Table 1 does not seem to me relevant to the paper (Assumption 1), in particular those with r < 10. Figure 6 shows that the gradient flow is close to a straightly line, suggesting that the gradient descent algorithm follows a convex landscape. The Figure 6(b) seems to me have not converged yet, as at step 10,000, the cosine is not as flat as the others. This means that maybe the gradient flow does not converge to the local minima (U^*,V^*). Further explanation about this is needed in the paper. Regarding optimization efficiency, it is not that convincing since even in the over-parameterized regime: the landscape become more convex, but there can be a lot of local minima which are not as good as the global minima. Therefore from an optimization perspective, finding global minima still remain challenging. I think it would be better to mention this somewhere in the paper. \n\nMinor typo includes: \nequation (5), write ||W_2||_F^2. \nEquation (12), hat 1 should be 1\n", "extra_scores": {"experience_assessment": "I have read many papers in this area.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I carefully checked the derivations and theory."}, "extra_text": {}}, {"review_id": "S1gZu92OtS", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "The paper derives results for nonnegative-matrix factorization along the lines of recent results on SGD for DNNs, showing that the loss is star-convex towards randomized planted solutions. The star-convexity property is also shown to hold to some degree on real world datasets. The paper argues that these results explain the good performance that usual gradient descent procedures achieve in practice. The paper also puts forward a conjecture that more parameters make the loss function easier to optimize by making it more likely that star convexity holds, and that a similar conclusion could hold for DNNs.\n\nThe paper is rather well written, although there are many small typos or notation errors (of which I mention a few below). In addition, I have a few issues with the presentation of both the theoretical and experimental results. Although the results relating to star convexity seem compelling and interesting to understand the good practical performance of the usual simple NMF algorithms, I find the conjecture on concentration of measure a bit hand-wavy.\n\nIn particular, I have some questions regarding the main theorem:\n\n\t- \"r grows as $O(n^\\gamma)$ and m as $O(n)$\": Big-O means asymptotically bounded, i.e., that r is roughly smaller than n^\\gamma (which is a tautology for $\\gamma=1$ anyway), and that m is roughly smaller than n. Is that really what you mean? Or do you mean $\\Omega/\\Theta$ instead? Fact 2 uses \"recall our assumption that $r = c n^\\gamma$\" which seems to imply you mean \"r = \\Omega(n^\\gamma)\", which can also be informally stated as \"r grows as n^\\gamma\", without Big-O notation. Please clarify this notation.\n\n\t- Also, re $\\gamma \\geq 0.5$, I do not quite see why such a strong assumption is made. Wouldn't $r = \\Omega(n^{1/3 + \\varepsilon})$ be enough with respect to Fact 2 to get an asymptotically vanishing deviation probability? i.e., wouldn't the final result work with $\\gamma > 1/3`$, which is more general?\n\nGenerally, this begs the question of whether $r = \\Omega(n^0.5)$ is realistic. Can this be put in perspective with respect to other work?\n\n\t- What is Lemma 9 mentioned in the proof of Lemma 1? Is that in the paper? I could not find it. In particular, I am unclear on \"we can do a polynomial number of union bounds\": polynomial with respect to which variable?\n\nI also have the following additional questions on the experimental findings and the proposed conjecture.\n\n- Section 4.2 and Figure 5 uses the 'relative deviation', which is the standard deviation normalized by the mean. I am not sure what conclusion to draw from this, however. In particular:\n  - Why normalize by dividing by the mean?\n  - What is the evolution of the mean itself? If the mean is always greater than a few standard deviations, then the fact that curvature is getting more concentrated may not matter. How about showing instead the fraction of trials where the curvature was non-negative? (i.e., where we had convexity along the line)\n\n- I struggle a bit to make sense of the conjecture. In particular, 'concentration of measure' is related to randomness, but it isn't quite clear which 'measure' we're talking about here. Table 2 is also not very convincing: although the legend indicates 'increased width makes the loss surface increasingly locally convex', it only seems to hold for the fourth row (epoch=300). In addition, these means are reported without standard deviations, making it hard to judge whether to trust the ordering of these few numbers.\n\nTypos/unclear:\n\nintroduction: \"strictly non-negative factors\", what do you mean by strictly?\n\"randomly chosen or the global minimizer\" is a bit unclear - what is the 'or' over?\n\"Convex along straight paths towards the optima x*\": x* -> $x^*$ to be consistent with Definition 1.\n\"similar to Dvoretzky's\": I fail to see the similarity and how this is related to the present paper.\n\"we will assume that there is a planted optimal solution (U*, V*)\": U*, V* should be in bold to be consistent with further notation.\n\"how r and m depends on n\": depends -> depend\n\"as the size of the problem increaseS\"\n\"loss function *of* equation 2\"\nTheorem 1: \"at least \\geq\" is redundant\nTheorem 1: \"but with exponent -c r^{1/3}\" is unclear: which exponent is this? Write the statement in full instead.\n\"it's second derivative\": its?\n\"for unobserved Data\": why is 'data' capitalized?\nD3: \"clearly, equation 9 holds in this case\": not sure what is meant here - equation (10) does not imply (9) or reciprocally. Did you mean that equation 10 holds instead?\nD3: \"3 evenly spaceD \\lambda\"\nD6: Definition 2: \"iff there *exists* positive constants...\"\nD6: \"one can easily verify that independenT Gaussian variables\"\nD6: \"i=j, j=l, and so on\": what is 'and so on'? all indexes are completely arbitrary?\nD6: \"z = P(X_i, X_j, X_k, X_l)\": clarify notation $P$. In the main text, you've used the notation $p$ instead.\nD6: Equation (12) and (13): should the RHS be exp(-X) instead of exp(X)?\nD6: $- \\mu$ notation is a bit confusing: the text doesn't explain what it is, and lack of bold face hints that this is a scalar and not a matrix.\nD6: \"Lemma 9 says that each one can be expressED\"\nE1: End of proof of fact 3: do not include an equal sign if there is no left-hand side.\nE1: \"trace and linearity are linear operators\": linearity is linear?\n", "extra_scores": {"experience_assessment": "I have read many papers in this area.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper thoroughly."}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper derives results for nonnegative-matrix factorization along the lines of recent results on SGD for DNNs, showing that the loss is star-convex towards randomized planted solutions.

Overall, the paper is relatively well written and fairly clear.  The reviewers agree that the theoretical contribution of the paper could be improved (tighten bounds) and that the experiments can be improved as well. In the context of other papers submitted to ICLR I therefore recommend to reject the paper.


Decision: Reject