Year: 2019

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 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.

heading: 1 INTRODUCTION
text: Non-negative matrix factorization (NMF) is a ubiquitous technique for data analysis where one attempts to factorize a 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 et al., 2014), scientific analysis (Berne et al., 2007; Trindade et al., 2017), computer vision (Gillis, 2012), internet distance prediction (Mao et al., 2006), audio processing (Schmidt et al., 2007) and many more domains. Often, the non-negativity is crucial for interpretability, for example, in the context of crystallography, the light sources, which are represented as matrix factors, have non-negative intensity (Suram et al., 2016).
Like many other non-convex optimization problems, finding the exact solution to NMF is 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 formulations such as SVMs (Cortes and Vapnik, 1995), but owing to the success of neural networks, non-convex optimization has experienced a 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 a similar property called star-convexity holds in 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 in sum-of-squares literature (Barak et al., 2016). 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 if the loss is computed over unobserved data. From an empirical perspective, we verify that our theoretical results hold for an extensive collection
<latexit sha1_base64="/JI5iynvNWOEKZjLq6ujHWhdsHw=">AAAB7nicbVDLSsNAFL2pr1pfVZduBovgqiQi1GXRjcsK9gFtKJPJpB06mYSZG6GEfoQbF4q49Xvc+TdO2yy09cDA4ZxzmXtPkEph0HW/ndLG5tb2Tnm3srd/cHhUPT7pmCTTjLdZIhPdC6jhUijeRoGS91LNaRxI3g0md3O/+8S1EYl6xGnK/ZiOlIgEo2il7kDaaEiH1Zpbdxcg68QrSA0KtIbVr0GYsCzmCpmkxvQ9N0U/pxoFk3xWGWSGp5RN6Ij3LVU05sbPF+vOyIVVQhIl2j6FZKH+nshpbMw0Dmwypjg2q95c/M/rZxjd+LlQaYZcseVHUSYJJmR+OwmF5gzl1BLKtLC7EjammjK0DVVsCd7qyeukc1X33Lr3cF1r3hZ1lOEMzuESPGhAE+6hBW1gMIFneIU3J3VenHfnYxktOcXMKfyB8/kDPMWPfQ==</latexit><latexit sha1_base64="/JI5iynvNWOEKZjLq6ujHWhdsHw=">AAAB7nicbVDLSsNAFL2pr1pfVZduBovgqiQi1GXRjcsK9gFtKJPJpB06mYSZG6GEfoQbF4q49Xvc+TdO2yy09cDA4ZxzmXtPkEph0HW/ndLG5tb2Tnm3srd/cHhUPT7pmCTTjLdZIhPdC6jhUijeRoGS91LNaRxI3g0md3O/+8S1EYl6xGnK/ZiOlIgEo2il7kDaaEiH1Zpbdxcg68QrSA0KtIbVr0GYsCzmCpmkxvQ9N0U/pxoFk3xWGWSGp5RN6Ij3LVU05sbPF+vOyIVVQhIl2j6FZKH+nshpbMw0Dmwypjg2q95c/M/rZxjd+LlQaYZcseVHUSYJJmR+OwmF5gzl1BLKtLC7EjammjK0DVVsCd7qyeukc1X33Lr3cF1r3hZ1lOEMzuESPGhAE+6hBW1gMIFneIU3J3VenHfnYxktOcXMKfyB8/kDPMWPfQ==</latexit><latexit sha1_base64="/JI5iynvNWOEKZjLq6ujHWhdsHw=">AAAB7nicbVDLSsNAFL2pr1pfVZduBovgqiQi1GXRjcsK9gFtKJPJpB06mYSZG6GEfoQbF4q49Xvc+TdO2yy09cDA4ZxzmXtPkEph0HW/ndLG5tb2Tnm3srd/cHhUPT7pmCTTjLdZIhPdC6jhUijeRoGS91LNaRxI3g0md3O/+8S1EYl6xGnK/ZiOlIgEo2il7kDaaEiH1Zpbdxcg68QrSA0KtIbVr0GYsCzmCpmkxvQ9N0U/pxoFk3xWGWSGp5RN6Ij3LVU05sbPF+vOyIVVQhIl2j6FZKH+nshpbMw0Dmwypjg2q95c/M/rZxjd+LlQaYZcseVHUSYJJmR+OwmF5gzl1BLKtLC7EjammjK0DVVsCd7qyeukc1X33Lr3cF1r3hZ1lOEMzuESPGhAE+6hBW1gMIFneIU3J3VenHfnYxktOcXMKfyB8/kDPMWPfQ==</latexit><latexit sha1_base64="/JI5iynvNWOEKZjLq6ujHWhdsHw=">AAAB7nicbVDLSsNAFL2pr1pfVZduBovgqiQi1GXRjcsK9gFtKJPJpB06mYSZG6GEfoQbF4q49Xvc+TdO2yy09cDA4ZxzmXtPkEph0HW/ndLG5tb2Tnm3srd/cHhUPT7pmCTTjLdZIhPdC6jhUijeRoGS91LNaRxI3g0md3O/+8S1EYl6xGnK/ZiOlIgEo2il7kDaaEiH1Zpbdxcg68QrSA0KtIbVr0GYsCzmCpmkxvQ9N0U/pxoFk3xWGWSGp5RN6Ij3LVU05sbPF+vOyIVVQhIl2j6FZKH+nshpbMw0Dmwypjg2q95c/M/rZxjd+LlQaYZcseVHUSYJJmR+OwmF5gzl1BLKtLC7EjammjK0DVVsCd7qyeukc1X33Lr3cF1r3hZ1lOEMzuESPGhAE+6hBW1gMIFneIU3J3VenHfnYxktOcXMKfyB8/kDPMWPfQ==</latexit>
<latexit sha1_base64="/JI5iynvNWOEKZjLq6ujHWhdsHw=">AAAB7nicbVDLSsNAFL2pr1pfVZduBovgqiQi1GXRjcsK9gFtKJPJpB06mYSZG6GEfoQbF4q49Xvc+TdO2yy09cDA4ZxzmXtPkEph0HW/ndLG5tb2Tnm3srd/cHhUPT7pmCTTjLdZIhPdC6jhUijeRoGS91LNaRxI3g0md3O/+8S1EYl6xGnK/ZiOlIgEo2il7kDaaEiH1Zpbdxcg68QrSA0KtIbVr0GYsCzmCpmkxvQ9N0U/pxoFk3xWGWSGp5RN6Ij3LVU05sbPF+vOyIVVQhIl2j6FZKH+nshpbMw0Dmwypjg2q95c/M/rZxjd+LlQaYZcseVHUSYJJmR+OwmF5gzl1BLKtLC7EjammjK0DVVsCd7qyeukc1X33Lr3cF1r3hZ1lOEMzuESPGhAE+6hBW1gMIFneIU3J3VenHfnYxktOcXMKfyB8/kDPMWPfQ==</latexit><latexit sha1_base64="/JI5iynvNWOEKZjLq6ujHWhdsHw=">AAAB7nicbVDLSsNAFL2pr1pfVZduBovgqiQi1GXRjcsK9gFtKJPJpB06mYSZG6GEfoQbF4q49Xvc+TdO2yy09cDA4ZxzmXtPkEph0HW/ndLG5tb2Tnm3srd/cHhUPT7pmCTTjLdZIhPdC6jhUijeRoGS91LNaRxI3g0md3O/+8S1EYl6xGnK/ZiOlIgEo2il7kDaaEiH1Zpbdxcg68QrSA0KtIbVr0GYsCzmCpmkxvQ9N0U/pxoFk3xWGWSGp5RN6Ij3LVU05sbPF+vOyIVVQhIl2j6FZKH+nshpbMw0Dmwypjg2q95c/M/rZxjd+LlQaYZcseVHUSYJJmR+OwmF5gzl1BLKtLC7EjammjK0DVVsCd7qyeukc1X33Lr3cF1r3hZ1lOEMzuESPGhAE+6hBW1gMIFneIU3J3VenHfnYxktOcXMKfyB8/kDPMWPfQ==</latexit><latexit sha1_base64="/JI5iynvNWOEKZjLq6ujHWhdsHw=">AAAB7nicbVDLSsNAFL2pr1pfVZduBovgqiQi1GXRjcsK9gFtKJPJpB06mYSZG6GEfoQbF4q49Xvc+TdO2yy09cDA4ZxzmXtPkEph0HW/ndLG5tb2Tnm3srd/cHhUPT7pmCTTjLdZIhPdC6jhUijeRoGS91LNaRxI3g0md3O/+8S1EYl6xGnK/ZiOlIgEo2il7kDaaEiH1Zpbdxcg68QrSA0KtIbVr0GYsCzmCpmkxvQ9N0U/pxoFk3xWGWSGp5RN6Ij3LVU05sbPF+vOyIVVQhIl2j6FZKH+nshpbMw0Dmwypjg2q95c/M/rZxjd+LlQaYZcseVHUSYJJmR+OwmF5gzl1BLKtLC7EjammjK0DVVsCd7qyeukc1X33Lr3cF1r3hZ1lOEMzuESPGhAE+6hBW1gMIFneIU3J3VenHfnYxktOcXMKfyB8/kDPMWPfQ==</latexit><latexit sha1_base64="/JI5iynvNWOEKZjLq6ujHWhdsHw=">AAAB7nicbVDLSsNAFL2pr1pfVZduBovgqiQi1GXRjcsK9gFtKJPJpB06mYSZG6GEfoQbF4q49Xvc+TdO2yy09cDA4ZxzmXtPkEph0HW/ndLG5tb2Tnm3srd/cHhUPT7pmCTTjLdZIhPdC6jhUijeRoGS91LNaRxI3g0md3O/+8S1EYl6xGnK/ZiOlIgEo2il7kDaaEiH1Zpbdxcg68QrSA0KtIbVr0GYsCzmCpmkxvQ9N0U/pxoFk3xWGWSGp5RN6Ij3LVU05sbPF+vOyIVVQhIl2j6FZKH+nshpbMw0Dmwypjg2q95c/M/rZxjd+LlQaYZcseVHUSYJJmR+OwmF5gzl1BLKtLC7EjammjK0DVVsCd7qyeukc1X33Lr3cF1r3hZ1lOEMzuESPGhAE+6hBW1gMIFneIU3J3VenHfnYxktOcXMKfyB8/kDPMWPfQ==</latexit>
of real-world datasets spanning collaborative filtering (Zhou et al., 2008; Kula, 2017; Harper and Konstan, 2016), signal decomposition (Zhu, 2016; Li and Ngom, 2013; Li et al., 2001; Erichson et al., 2018) and audio processing (Flenner and Hunter, 2017; canto Foundation), and demonstrate that the star-convex behavior results in efficient optimization. Finally, we show that star-convex behavior becomes more likely with growing number of parameters, suggesting that a similar result may hold as neural networks become wider. We provide supporting empirical evidence for this hypothesis on modern network architectures.

heading: 2 NMF AND STAR-CONVEXITY
text: The aim of NMF is to decompose some large measurement matrix X P Rnˆm into two non-negative matrices U P Rnˆr` and V P Rrˆm` such that X « UV. The canonical formulation of NMF is
min U,Vě0 `pU,Vq, where `pU,Vq “ 1 2 }UV ´X}2F (1)
NMF is commonly used in recommender systems where entries pi, jq of X for example correspond to the rating user i has given to movie j (Luo et al., 2014). In such settings, data might be missing as all users have not rated all movies. In those cases, it is common to only consider the loss over observed data (Zhang et al., 2006; Candès and Recht, 2009). We let 1̂pi,jq be an indicator variable that is 1 if entry pi, jq is "observed" and 0 otherwise. The loss function is then
min U,Vě0 `pU,Vq “ 1 2 ÿ
i,j
1̂pi,jq
ˆ
“ UV ‰ ij ´Xij
˙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 r 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, 2001), are popular and are known to work reliably (Koren et al., 2009). This gap between theoretical hardness and practical performance is also found in deep learning. Optimizing neural networks is NP-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-games (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 Izmailov et al. (2018) shows that the loss surface is convex around the local optimum, while Zhou et al. (2019) and Kleinberg et al. (2018) 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 is a property of a function f that guarantees that it is convex along straight paths towards the optima x˚. See Figure 2 for an example. Formally, it is defined as follows.
Definition 1. A function f : Rn Ñ R is star-convex towards x˚ if for all λ P r0, 1s and x P Rn, we have f ` λx` p1´ λq x˚ ˘ ď λfpxq ` p1´ λqfpx˚q.
Optimizing star-convex functions can be done in polynomial time (Lee and Valiant, 2016), in Kleinberg et al. (2018) it is shown how the function only needs to be star-convex under a natural noise model. NMF is not star-convex in general as it is NP-hard, however, it is natural to conjecture that NMF is starconvex in the typical case. Such a 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 1. Indeed, one can verify numerically that NMF is typically star-convex for natural distributions and realistically sized matrices, see Figure 1 where we consider a rank 10 decomposition of p100, 100qmatrices with iid half-normal entries and a planted solution, sampled as per Assumption 1 given in the next section. Following sections will be dedicated to proving that NMF is starconvex with high probability in a planted model, and to confirm that this phenomenon generalizes to datasets from the real world, which are far from worst-case.

heading: 3 PROVING TYPICAL-CASE STAR-CONVEXITY
text: Our aim now is to prove that the NMF loss-function is typically star-convex for natural non-worstcase distribution of NMF instances. We will consider a slighly weaker notation of star-convexity where f ` λx ` p1 ´ λq x˚ ˘
ď λfpxq ` p1 ´ λqfpx˚q holds not for all x, but for random x with high probability. This is in fact the best achievable, an NMF instance with u1 “ 1, u˚ “ 0 and v1 “ 0, v˚ “ 1 is not star-convex. Our results hold with high probability in high dimensions, similar to Dvoretzky’s theorem in convex geometry (Dvoredsky, 1961; Davis).
Inspired by the stochastic block model of social networks (Holland et al., 1983; Decelle et al., 2011) and the planted clique problem (Barak et 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 pU˚,V˚q, where entries of these matrices are sampled iid from a class of distributions with good concentration properties that include the halfnormal 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 pn, rq and pr,mq become large. For this reason, we will need to specify how r and m depend on n.
Assumption 1. For pU,Vq P Rnˆr ˆ Rrˆm we assume that the entries of the matrices U,V are sampled iid from a continuous distribution with non-negative support that either piq is bounded or piiq can be expressed as a 1-Lipschitz function of a Gaussian distribution. As n Ñ 8, we assume that r grows as nγ up to a constant factor for γ P r1{2, 1s, and m as n up to a constant factor.
We are now ready to state our main results, that the loss function equation 1 is convex on a straight line between points samples as per Assumption 1, and thus satisfy our slightly weaker notion of star-convexity, with high probability. The probability increases as 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 U1,V1,U2,V2,U˚,V˚ be sampled according to Assumption 1. Then there exists positive constants c1, c2, such that with probability ě 1 ´ c1 expp´c2n1{3q, the loss function `pU,Vq in equation 1 is convex on the straight line pU1,V1q Ñ pU2,V2q. The same holds along the line pU1,V1q Ñ pU˚,V˚q. It also holds if any entry pi, jq is observed independently with constant probability p, but with probability ě 1´ c1 expp´c2r1{3q.

heading: 3.1 PROOF STRATEGY
text: Let us parametrize the NMF solution one gets along the line pU2,V2q Ñ pU1,V1q as
X̂pλq “ ˆ λU1 ` p1´ λqU2 ˙ˆ λV1 ` p1´ λqV2 ˙
Proving Theorem 1 amounts to showing that the loss function `pλq “ 12}X̂pλq ´ X} 2 F is convex in λ with high probability, our strategy is to show that its second-derivate is non-negative. For fixed matrices U1,U2,U˚,V1,V2,V˚, the function `pλq is a fourth-degree polynomial in λ, so its second derivate w.r.t. λ will be a second-degree polynomial in λ. For a general second-degree polynomial ppxq “ ax2 ` bx ` c we have ppxq “ 1a “` ax ` b2 ˘2 ` ` ac ´ b 2 4 ˘‰
. If a ą 0, which in the case here (see Appendix D), showing that it’s positive could be done by showing ac ě b 2
4 . This is equivalent to showing that
2}W2}2F ` }W1}2F ` 2xW0,W2y ˘ ě 3 ` xW1,W2y ˘2
(3) Where the matrices W0,W1,W2 are given as W0 “ U2V2 ´U˚V˚, W1 “ ` U1 ´U2 ˘
V2 ` U2 ` V1´V2 ˘ , W2 “ ` U1´U2 ˘` V1´V2 ˘
. By slight abuse of notation, we have used xA,By to denote TrpABT q for matrices A,B of the same shape. By exchanging terms in equation 3 by their means one gets
2p4rmnσ4q ` 6rmnσ4 ` 4rmnµ2varσ2 ` 2rmnσ4 ˘ ě 3 ` ´ 4rmnσ4 ˘2
(4)
Here, σ2 is the variance of the distribution of the entries in the matrices, while µ is the mean. By just counting terms of order prmnσ4q2, we see that the LHS has 64 such terms while the RHS has only 48. Thus, if all matrices W0,W1 and W2 would exactly be equal to 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 W2 “ ` U1 ´U2 ˘` V1 ´ V2 ˘
. Given that all matrices are iid we can center the variables such that W2 “ ` U1 ´ U2 ˘` V1 ´ V2 ˘ “ `
Ū1 ´ Ū2 ˘` V̄1´ V̄2 ˘
, where the bar denotes the centered matrices. The term }W2}2F can then be written as Tr ` V̄1´V̄2 ˘T ` Ū1´Ū2 ˘T ` Ū1´Ū2 ˘` V̄1´V̄2 ˘
. Given that all matrix entries are independent as per Assumption 1, 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; Meckes and Szarek, 2012). Via such results one can achieve the following concentration result, see Appendix D.
P ` ˇ ˇ}W2}2F ´ E “ }W2}2F ‰ ˇ ˇ ą t r n2 ˘ ď c3 exp ` ´ c4 minpt2, t1{2qn ˘
(5) where c3, 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 as n1{3 instead of n, see Appendix D.
Proof sketch Given that E “ }W2}2F “ 4rmnσ4, equation 5 says that the probability that the term deviates from its mean by a relative factor is less than c3 exp ` ´ c5 2n ˘
for some small . By applying similar arguments to terms xW0,W2y and xW1,W2y, one can show that the probability that they will deviate by a relative factor is less than c6 expp´c7 2n1{3q. A problematic term is }W1}2F which contains a term of the type Tr ` V̄1 ´ V̄2 ˘T µT1 µ1 ` V̄1 ´ V̄2 ˘
which has weak concentration properties. Matrices of type ATA are 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 c1 expp´c8 2n1{3q for positive constants c1, c8. Now, set “ 0.01 If neither variable deviates by a factor of more than 0.01, then equation 10 still holds since 0.992 ˚ 64 ě 1.012 ˚ 48. Thus, inequality is violated with probability at most c1 exp ` ´ c2n1{3 ˘
for positive c1, c2.
<latexit sha1_base64="/JI5iynvNWOEKZjLq6ujHWhdsHw=">AAAB7nicbVDLSsNAFL2pr1pfVZduBovgqiQi1GXRjcsK9gFtKJPJpB06mYSZG6GEfoQbF4q49Xvc+TdO2yy09cDA4ZxzmXtPkEph0HW/ndLG5tb2Tnm3srd/cHhUPT7pmCTTjLdZIhPdC6jhUijeRoGS91LNaRxI3g0md3O/+8S1EYl6xGnK/ZiOlIgEo2il7kDaaEiH1Zpbdxcg68QrSA0KtIbVr0GYsCzmCpmkxvQ9N0U/pxoFk3xWGWSGp5RN6Ij3LVU05sbPF+vOyIVVQhIl2j6FZKH+nshpbMw0Dmwypjg2q95c/M/rZxjd+LlQaYZcseVHUSYJJmR+OwmF5gzl1BLKtLC7EjammjK0DVVsCd7qyeukc1X33Lr3cF1r3hZ1lOEMzuESPGhAE+6hBW1gMIFneIU3J3VenHfnYxktOcXMKfyB8/kDPMWPfQ==</latexit><latexit sha1_base64="/JI5iynvNWOEKZjLq6ujHWhdsHw=">AAAB7nicbVDLSsNAFL2pr1pfVZduBovgqiQi1GXRjcsK9gFtKJPJpB06mYSZG6GEfoQbF4q49Xvc+TdO2yy09cDA4ZxzmXtPkEph0HW/ndLG5tb2Tnm3srd/cHhUPT7pmCTTjLdZIhPdC6jhUijeRoGS91LNaRxI3g0md3O/+8S1EYl6xGnK/ZiOlIgEo2il7kDaaEiH1Zpbdxcg68QrSA0KtIbVr0GYsCzmCpmkxvQ9N0U/pxoFk3xWGWSGp5RN6Ij3LVU05sbPF+vOyIVVQhIl2j6FZKH+nshpbMw0Dmwypjg2q95c/M/rZxjd+LlQaYZcseVHUSYJJmR+OwmF5gzl1BLKtLC7EjammjK0DVVsCd7qyeukc1X33Lr3cF1r3hZ1lOEMzuESPGhAE+6hBW1gMIFneIU3J3VenHfnYxktOcXMKfyB8/kDPMWPfQ==</latexit><latexit sha1_base64="/JI5iynvNWOEKZjLq6ujHWhdsHw=">AAAB7nicbVDLSsNAFL2pr1pfVZduBovgqiQi1GXRjcsK9gFtKJPJpB06mYSZG6GEfoQbF4q49Xvc+TdO2yy09cDA4ZxzmXtPkEph0HW/ndLG5tb2Tnm3srd/cHhUPT7pmCTTjLdZIhPdC6jhUijeRoGS91LNaRxI3g0md3O/+8S1EYl6xGnK/ZiOlIgEo2il7kDaaEiH1Zpbdxcg68QrSA0KtIbVr0GYsCzmCpmkxvQ9N0U/pxoFk3xWGWSGp5RN6Ij3LVU05sbPF+vOyIVVQhIl2j6FZKH+nshpbMw0Dmwypjg2q95c/M/rZxjd+LlQaYZcseVHUSYJJmR+OwmF5gzl1BLKtLC7EjammjK0DVVsCd7qyeukc1X33Lr3cF1r3hZ1lOEMzuESPGhAE+6hBW1gMIFneIU3J3VenHfnYxktOcXMKfyB8/kDPMWPfQ==</latexit><latexit sha1_base64="/JI5iynvNWOEKZjLq6ujHWhdsHw=">AAAB7nicbVDLSsNAFL2pr1pfVZduBovgqiQi1GXRjcsK9gFtKJPJpB06mYSZG6GEfoQbF4q49Xvc+TdO2yy09cDA4ZxzmXtPkEph0HW/ndLG5tb2Tnm3srd/cHhUPT7pmCTTjLdZIhPdC6jhUijeRoGS91LNaRxI3g0md3O/+8S1EYl6xGnK/ZiOlIgEo2il7kDaaEiH1Zpbdxcg68QrSA0KtIbVr0GYsCzmCpmkxvQ9N0U/pxoFk3xWGWSGp5RN6Ij3LVU05sbPF+vOyIVVQhIl2j6FZKH+nshpbMw0Dmwypjg2q95c/M/rZxjd+LlQaYZcseVHUSYJJmR+OwmF5gzl1BLKtLC7EjammjK0DVVsCd7qyeukc1X33Lr3cF1r3hZ1lOEMzuESPGhAE+6hBW1gMIFneIU3J3VenHfnYxktOcXMKfyB8/kDPMWPfQ==</latexit>
<latexit sha1_base64="/JI5iynvNWOEKZjLq6ujHWhdsHw=">AAAB7nicbVDLSsNAFL2pr1pfVZduBovgqiQi1GXRjcsK9gFtKJPJpB06mYSZG6GEfoQbF4q49Xvc+TdO2yy09cDA4ZxzmXtPkEph0HW/ndLG5tb2Tnm3srd/cHhUPT7pmCTTjLdZIhPdC6jhUijeRoGS91LNaRxI3g0md3O/+8S1EYl6xGnK/ZiOlIgEo2il7kDaaEiH1Zpbdxcg68QrSA0KtIbVr0GYsCzmCpmkxvQ9N0U/pxoFk3xWGWSGp5RN6Ij3LVU05sbPF+vOyIVVQhIl2j6FZKH+nshpbMw0Dmwypjg2q95c/M/rZxjd+LlQaYZcseVHUSYJJmR+OwmF5gzl1BLKtLC7EjammjK0DVVsCd7qyeukc1X33Lr3cF1r3hZ1lOEMzuESPGhAE+6hBW1gMIFneIU3J3VenHfnYxktOcXMKfyB8/kDPMWPfQ==</latexit><latexit sha1_base64="/JI5iynvNWOEKZjLq6ujHWhdsHw=">AAAB7nicbVDLSsNAFL2pr1pfVZduBovgqiQi1GXRjcsK9gFtKJPJpB06mYSZG6GEfoQbF4q49Xvc+TdO2yy09cDA4ZxzmXtPkEph0HW/ndLG5tb2Tnm3srd/cHhUPT7pmCTTjLdZIhPdC6jhUijeRoGS91LNaRxI3g0md3O/+8S1EYl6xGnK/ZiOlIgEo2il7kDaaEiH1Zpbdxcg68QrSA0KtIbVr0GYsCzmCpmkxvQ9N0U/pxoFk3xWGWSGp5RN6Ij3LVU05sbPF+vOyIVVQhIl2j6FZKH+nshpbMw0Dmwypjg2q95c/M/rZxjd+LlQaYZcseVHUSYJJmR+OwmF5gzl1BLKtLC7EjammjK0DVVsCd7qyeukc1X33Lr3cF1r3hZ1lOEMzuESPGhAE+6hBW1gMIFneIU3J3VenHfnYxktOcXMKfyB8/kDPMWPfQ==</latexit><latexit sha1_base64="/JI5iynvNWOEKZjLq6ujHWhdsHw=">AAAB7nicbVDLSsNAFL2pr1pfVZduBovgqiQi1GXRjcsK9gFtKJPJpB06mYSZG6GEfoQbF4q49Xvc+TdO2yy09cDA4ZxzmXtPkEph0HW/ndLG5tb2Tnm3srd/cHhUPT7pmCTTjLdZIhPdC6jhUijeRoGS91LNaRxI3g0md3O/+8S1EYl6xGnK/ZiOlIgEo2il7kDaaEiH1Zpbdxcg68QrSA0KtIbVr0GYsCzmCpmkxvQ9N0U/pxoFk3xWGWSGp5RN6Ij3LVU05sbPF+vOyIVVQhIl2j6FZKH+nshpbMw0Dmwypjg2q95c/M/rZxjd+LlQaYZcseVHUSYJJmR+OwmF5gzl1BLKtLC7EjammjK0DVVsCd7qyeukc1X33Lr3cF1r3hZ1lOEMzuESPGhAE+6hBW1gMIFneIU3J3VenHfnYxktOcXMKfyB8/kDPMWPfQ==</latexit><latexit sha1_base64="/JI5iynvNWOEKZjLq6ujHWhdsHw=">AAAB7nicbVDLSsNAFL2pr1pfVZduBovgqiQi1GXRjcsK9gFtKJPJpB06mYSZG6GEfoQbF4q49Xvc+TdO2yy09cDA4ZxzmXtPkEph0HW/ndLG5tb2Tnm3srd/cHhUPT7pmCTTjLdZIhPdC6jhUijeRoGS91LNaRxI3g0md3O/+8S1EYl6xGnK/ZiOlIgEo2il7kDaaEiH1Zpbdxcg68QrSA0KtIbVr0GYsCzmCpmkxvQ9N0U/pxoFk3xWGWSGp5RN6Ij3LVU05sbPF+vOyIVVQhIl2j6FZKH+nshpbMw0Dmwypjg2q95c/M/rZxjd+LlQaYZcseVHUSYJJmR+OwmF5gzl1BLKtLC7EjammjK0DVVsCd7qyeukc1X33Lr3cF1r3hZ1lOEMzuESPGhAE+6hBW1gMIFneIU3J3VenHfnYxktOcXMKfyB8/kDPMWPfQ==</latexit>
<latexit sha1_base64="/JI5iynvNWOEKZjLq6ujHWhdsHw=">AAAB7nicbVDLSsNAFL2pr1pfVZduBovgqiQi1GXRjcsK9gFtKJPJpB06mYSZG6GEfoQbF4q49Xvc+TdO2yy09cDA4ZxzmXtPkEph0HW/ndLG5tb2Tnm3srd/cHhUPT7pmCTTjLdZIhPdC6jhUijeRoGS91LNaRxI3g0md3O/+8S1EYl6xGnK/ZiOlIgEo2il7kDaaEiH1Zpbdxcg68QrSA0KtIbVr0GYsCzmCpmkxvQ9N0U/pxoFk3xWGWSGp5RN6Ij3LVU05sbPF+vOyIVVQhIl2j6FZKH+nshpbMw0Dmwypjg2q95c/M/rZxjd+LlQaYZcseVHUSYJJmR+OwmF5gzl1BLKtLC7EjammjK0DVVsCd7qyeukc1X33Lr3cF1r3hZ1lOEMzuESPGhAE+6hBW1gMIFneIU3J3VenHfnYxktOcXMKfyB8/kDPMWPfQ==</latexit><latexit sha1_base64="/JI5iynvNWOEKZjLq6ujHWhdsHw=">AAAB7nicbVDLSsNAFL2pr1pfVZduBovgqiQi1GXRjcsK9gFtKJPJpB06mYSZG6GEfoQbF4q49Xvc+TdO2yy09cDA4ZxzmXtPkEph0HW/ndLG5tb2Tnm3srd/cHhUPT7pmCTTjLdZIhPdC6jhUijeRoGS91LNaRxI3g0md3O/+8S1EYl6xGnK/ZiOlIgEo2il7kDaaEiH1Zpbdxcg68QrSA0KtIbVr0GYsCzmCpmkxvQ9N0U/pxoFk3xWGWSGp5RN6Ij3LVU05sbPF+vOyIVVQhIl2j6FZKH+nshpbMw0Dmwypjg2q95c/M/rZxjd+LlQaYZcseVHUSYJJmR+OwmF5gzl1BLKtLC7EjammjK0DVVsCd7qyeukc1X33Lr3cF1r3hZ1lOEMzuESPGhAE+6hBW1gMIFneIU3J3VenHfnYxktOcXMKfyB8/kDPMWPfQ==</latexit><latexit sha1_base64="/JI5iynvNWOEKZjLq6ujHWhdsHw=">AAAB7nicbVDLSsNAFL2pr1pfVZduBovgqiQi1GXRjcsK9gFtKJPJpB06mYSZG6GEfoQbF4q49Xvc+TdO2yy09cDA4ZxzmXtPkEph0HW/ndLG5tb2Tnm3srd/cHhUPT7pmCTTjLdZIhPdC6jhUijeRoGS91LNaRxI3g0md3O/+8S1EYl6xGnK/ZiOlIgEo2il7kDaaEiH1Zpbdxcg68QrSA0KtIbVr0GYsCzmCpmkxvQ9N0U/pxoFk3xWGWSGp5RN6Ij3LVU05sbPF+vOyIVVQhIl2j6FZKH+nshpbMw0Dmwypjg2q95c/M/rZxjd+LlQaYZcseVHUSYJJmR+OwmF5gzl1BLKtLC7EjammjK0DVVsCd7qyeukc1X33Lr3cF1r3hZ1lOEMzuESPGhAE+6hBW1gMIFneIU3J3VenHfnYxktOcXMKfyB8/kDPMWPfQ==</latexit><latexit sha1_base64="/JI5iynvNWOEKZjLq6ujHWhdsHw=">AAAB7nicbVDLSsNAFL2pr1pfVZduBovgqiQi1GXRjcsK9gFtKJPJpB06mYSZG6GEfoQbF4q49Xvc+TdO2yy09cDA4ZxzmXtPkEph0HW/ndLG5tb2Tnm3srd/cHhUPT7pmCTTjLdZIhPdC6jhUijeRoGS91LNaRxI3g0md3O/+8S1EYl6xGnK/ZiOlIgEo2il7kDaaEiH1Zpbdxcg68QrSA0KtIbVr0GYsCzmCpmkxvQ9N0U/pxoFk3xWGWSGp5RN6Ij3LVU05sbPF+vOyIVVQhIl2j6FZKH+nshpbMw0Dmwypjg2q95c/M/rZxjd+LlQaYZcseVHUSYJJmR+OwmF5gzl1BLKtLC7EjammjK0DVVsCd7qyeukc1X33Lr3cF1r3hZ1lOEMzuESPGhAE+6hBW1gMIFneIU3J3VenHfnYxktOcXMKfyB8/kDPMWPfQ==</latexit>
<latexit sha1_base64="/JI5iynvNWOEKZjLq6ujHWhdsHw=">AAAB7nicbVDLSsNAFL2pr1pfVZduBovgqiQi1GXRjcsK9gFtKJPJpB06mYSZG6GEfoQbF4q49Xvc+TdO2yy09cDA4ZxzmXtPkEph0HW/ndLG5tb2Tnm3srd/cHhUPT7pmCTTjLdZIhPdC6jhUijeRoGS91LNaRxI3g0md3O/+8S1EYl6xGnK/ZiOlIgEo2il7kDaaEiH1Zpbdxcg68QrSA0KtIbVr0GYsCzmCpmkxvQ9N0U/pxoFk3xWGWSGp5RN6Ij3LVU05sbPF+vOyIVVQhIl2j6FZKH+nshpbMw0Dmwypjg2q95c/M/rZxjd+LlQaYZcseVHUSYJJmR+OwmF5gzl1BLKtLC7EjammjK0DVVsCd7qyeukc1X33Lr3cF1r3hZ1lOEMzuESPGhAE+6hBW1gMIFneIU3J3VenHfnYxktOcXMKfyB8/kDPMWPfQ==</latexit><latexit sha1_base64="/JI5iynvNWOEKZjLq6ujHWhdsHw=">AAAB7nicbVDLSsNAFL2pr1pfVZduBovgqiQi1GXRjcsK9gFtKJPJpB06mYSZG6GEfoQbF4q49Xvc+TdO2yy09cDA4ZxzmXtPkEph0HW/ndLG5tb2Tnm3srd/cHhUPT7pmCTTjLdZIhPdC6jhUijeRoGS91LNaRxI3g0md3O/+8S1EYl6xGnK/ZiOlIgEo2il7kDaaEiH1Zpbdxcg68QrSA0KtIbVr0GYsCzmCpmkxvQ9N0U/pxoFk3xWGWSGp5RN6Ij3LVU05sbPF+vOyIVVQhIl2j6FZKH+nshpbMw0Dmwypjg2q95c/M/rZxjd+LlQaYZcseVHUSYJJmR+OwmF5gzl1BLKtLC7EjammjK0DVVsCd7qyeukc1X33Lr3cF1r3hZ1lOEMzuESPGhAE+6hBW1gMIFneIU3J3VenHfnYxktOcXMKfyB8/kDPMWPfQ==</latexit><latexit sha1_base64="/JI5iynvNWOEKZjLq6ujHWhdsHw=">AAAB7nicbVDLSsNAFL2pr1pfVZduBovgqiQi1GXRjcsK9gFtKJPJpB06mYSZG6GEfoQbF4q49Xvc+TdO2yy09cDA4ZxzmXtPkEph0HW/ndLG5tb2Tnm3srd/cHhUPT7pmCTTjLdZIhPdC6jhUijeRoGS91LNaRxI3g0md3O/+8S1EYl6xGnK/ZiOlIgEo2il7kDaaEiH1Zpbdxcg68QrSA0KtIbVr0GYsCzmCpmkxvQ9N0U/pxoFk3xWGWSGp5RN6Ij3LVU05sbPF+vOyIVVQhIl2j6FZKH+nshpbMw0Dmwypjg2q95c/M/rZxjd+LlQaYZcseVHUSYJJmR+OwmF5gzl1BLKtLC7EjammjK0DVVsCd7qyeukc1X33Lr3cF1r3hZ1lOEMzuESPGhAE+6hBW1gMIFneIU3J3VenHfnYxktOcXMKfyB8/kDPMWPfQ==</latexit><latexit sha1_base64="/JI5iynvNWOEKZjLq6ujHWhdsHw=">AAAB7nicbVDLSsNAFL2pr1pfVZduBovgqiQi1GXRjcsK9gFtKJPJpB06mYSZG6GEfoQbF4q49Xvc+TdO2yy09cDA4ZxzmXtPkEph0HW/ndLG5tb2Tnm3srd/cHhUPT7pmCTTjLdZIhPdC6jhUijeRoGS91LNaRxI3g0md3O/+8S1EYl6xGnK/ZiOlIgEo2il7kDaaEiH1Zpbdxcg68QrSA0KtIbVr0GYsCzmCpmkxvQ9N0U/pxoFk3xWGWSGp5RN6Ij3LVU05sbPF+vOyIVVQhIl2j6FZKH+nshpbMw0Dmwypjg2q95c/M/rZxjd+LlQaYZcseVHUSYJJmR+OwmF5gzl1BLKtLC7EjammjK0DVVsCd7qyeukc1X33Lr3cF1r3hZ1lOEMzuESPGhAE+6hBW1gMIFneIU3J3VenHfnYxktOcXMKfyB8/kDPMWPfQ==</latexit>
Proof sketch for unobserved data If the entries in equation 2 are "observed" independently with probability p, for fixed matrices U1,U2,U˚,V1,V2,V˚ such that Theorem 1 hold, we have
Er`2pλqs “ E „ ÿ
ij
1̂pi,jq
ˆ
X̂1 2 ij ` X̂2ijpX̂ij ´Xijq ˙ “ p ÿ
ij
ˆ
X̂1 2 ij ` X̂2ijpX̂ij ´Xijq ˙ ě 0
Thus, the expectation of `2pλq is convex. To show that it is convex with high probability, one first observes that with high probability, no entry pi, jq in `2pλq is particularly large. Assuming this holds via union bound, for fix matrices U1,U2,U˚,V1,V2,V˚ with elements that are "observed" independently with probability p, one gets that `2pλq is concentrated around its convex mean via Hoeffding bounds (Hoeffding, 1994).

heading: 4 EXPERIMENTS

heading: 4.1 VERIFYING THEORETICAL PREDICTIONS
text: To verify that the conclusions from our planted model hold more broadly, we now consider realworld 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 on a handful of representative datasets spanning image analysis, scientific applications and collaborative filtering. In Table 1, we list these datasets together with references and sparsity, the decomposition rank we use is based upon values previously used in the literature.
We perform a non-negative matrix factorization via gradient descent, starting with randomly initialized data. To enable comparison between datasets, we scale all data matrices so that the variance of
<latexit sha1_base64="/JI5iynvNWOEKZjLq6ujHWhdsHw=">AAAB7nicbVDLSsNAFL2pr1pfVZduBovgqiQi1GXRjcsK9gFtKJPJpB06mYSZG6GEfoQbF4q49Xvc+TdO2yy09cDA4ZxzmXtPkEph0HW/ndLG5tb2Tnm3srd/cHhUPT7pmCTTjLdZIhPdC6jhUijeRoGS91LNaRxI3g0md3O/+8S1EYl6xGnK/ZiOlIgEo2il7kDaaEiH1Zpbdxcg68QrSA0KtIbVr0GYsCzmCpmkxvQ9N0U/pxoFk3xWGWSGp5RN6Ij3LVU05sbPF+vOyIVVQhIl2j6FZKH+nshpbMw0Dmwypjg2q95c/M/rZxjd+LlQaYZcseVHUSYJJmR+OwmF5gzl1BLKtLC7EjammjK0DVVsCd7qyeukc1X33Lr3cF1r3hZ1lOEMzuESPGhAE+6hBW1gMIFneIU3J3VenHfnYxktOcXMKfyB8/kDPMWPfQ==</latexit><latexit sha1_base64="/JI5iynvNWOEKZjLq6ujHWhdsHw=">AAAB7nicbVDLSsNAFL2pr1pfVZduBovgqiQi1GXRjcsK9gFtKJPJpB06mYSZG6GEfoQbF4q49Xvc+TdO2yy09cDA4ZxzmXtPkEph0HW/ndLG5tb2Tnm3srd/cHhUPT7pmCTTjLdZIhPdC6jhUijeRoGS91LNaRxI3g0md3O/+8S1EYl6xGnK/ZiOlIgEo2il7kDaaEiH1Zpbdxcg68QrSA0KtIbVr0GYsCzmCpmkxvQ9N0U/pxoFk3xWGWSGp5RN6Ij3LVU05sbPF+vOyIVVQhIl2j6FZKH+nshpbMw0Dmwypjg2q95c/M/rZxjd+LlQaYZcseVHUSYJJmR+OwmF5gzl1BLKtLC7EjammjK0DVVsCd7qyeukc1X33Lr3cF1r3hZ1lOEMzuESPGhAE+6hBW1gMIFneIU3J3VenHfnYxktOcXMKfyB8/kDPMWPfQ==</latexit><latexit sha1_base64="/JI5iynvNWOEKZjLq6ujHWhdsHw=">AAAB7nicbVDLSsNAFL2pr1pfVZduBovgqiQi1GXRjcsK9gFtKJPJpB06mYSZG6GEfoQbF4q49Xvc+TdO2yy09cDA4ZxzmXtPkEph0HW/ndLG5tb2Tnm3srd/cHhUPT7pmCTTjLdZIhPdC6jhUijeRoGS91LNaRxI3g0md3O/+8S1EYl6xGnK/ZiOlIgEo2il7kDaaEiH1Zpbdxcg68QrSA0KtIbVr0GYsCzmCpmkxvQ9N0U/pxoFk3xWGWSGp5RN6Ij3LVU05sbPF+vOyIVVQhIl2j6FZKH+nshpbMw0Dmwypjg2q95c/M/rZxjd+LlQaYZcseVHUSYJJmR+OwmF5gzl1BLKtLC7EjammjK0DVVsCd7qyeukc1X33Lr3cF1r3hZ1lOEMzuESPGhAE+6hBW1gMIFneIU3J3VenHfnYxktOcXMKfyB8/kDPMWPfQ==</latexit><latexit sha1_base64="/JI5iynvNWOEKZjLq6ujHWhdsHw=">AAAB7nicbVDLSsNAFL2pr1pfVZduBovgqiQi1GXRjcsK9gFtKJPJpB06mYSZG6GEfoQbF4q49Xvc+TdO2yy09cDA4ZxzmXtPkEph0HW/ndLG5tb2Tnm3srd/cHhUPT7pmCTTjLdZIhPdC6jhUijeRoGS91LNaRxI3g0md3O/+8S1EYl6xGnK/ZiOlIgEo2il7kDaaEiH1Zpbdxcg68QrSA0KtIbVr0GYsCzmCpmkxvQ9N0U/pxoFk3xWGWSGp5RN6Ij3LVU05sbPF+vOyIVVQhIl2j6FZKH+nshpbMw0Dmwypjg2q95c/M/rZxjd+LlQaYZcseVHUSYJJmR+OwmF5gzl1BLKtLC7EjammjK0DVVsCd7qyeukc1X33Lr3cF1r3hZ1lOEMzuESPGhAE+6hBW1gMIFneIU3J3VenHfnYxktOcXMKfyB8/kDPMWPfQ==</latexit>
<latexit sha1_base64="/JI5iynvNWOEKZjLq6ujHWhdsHw=">AAAB7nicbVDLSsNAFL2pr1pfVZduBovgqiQi1GXRjcsK9gFtKJPJpB06mYSZG6GEfoQbF4q49Xvc+TdO2yy09cDA4ZxzmXtPkEph0HW/ndLG5tb2Tnm3srd/cHhUPT7pmCTTjLdZIhPdC6jhUijeRoGS91LNaRxI3g0md3O/+8S1EYl6xGnK/ZiOlIgEo2il7kDaaEiH1Zpbdxcg68QrSA0KtIbVr0GYsCzmCpmkxvQ9N0U/pxoFk3xWGWSGp5RN6Ij3LVU05sbPF+vOyIVVQhIl2j6FZKH+nshpbMw0Dmwypjg2q95c/M/rZxjd+LlQaYZcseVHUSYJJmR+OwmF5gzl1BLKtLC7EjammjK0DVVsCd7qyeukc1X33Lr3cF1r3hZ1lOEMzuESPGhAE+6hBW1gMIFneIU3J3VenHfnYxktOcXMKfyB8/kDPMWPfQ==</latexit><latexit sha1_base64="/JI5iynvNWOEKZjLq6ujHWhdsHw=">AAAB7nicbVDLSsNAFL2pr1pfVZduBovgqiQi1GXRjcsK9gFtKJPJpB06mYSZG6GEfoQbF4q49Xvc+TdO2yy09cDA4ZxzmXtPkEph0HW/ndLG5tb2Tnm3srd/cHhUPT7pmCTTjLdZIhPdC6jhUijeRoGS91LNaRxI3g0md3O/+8S1EYl6xGnK/ZiOlIgEo2il7kDaaEiH1Zpbdxcg68QrSA0KtIbVr0GYsCzmCpmkxvQ9N0U/pxoFk3xWGWSGp5RN6Ij3LVU05sbPF+vOyIVVQhIl2j6FZKH+nshpbMw0Dmwypjg2q95c/M/rZxjd+LlQaYZcseVHUSYJJmR+OwmF5gzl1BLKtLC7EjammjK0DVVsCd7qyeukc1X33Lr3cF1r3hZ1lOEMzuESPGhAE+6hBW1gMIFneIU3J3VenHfnYxktOcXMKfyB8/kDPMWPfQ==</latexit><latexit sha1_base64="/JI5iynvNWOEKZjLq6ujHWhdsHw=">AAAB7nicbVDLSsNAFL2pr1pfVZduBovgqiQi1GXRjcsK9gFtKJPJpB06mYSZG6GEfoQbF4q49Xvc+TdO2yy09cDA4ZxzmXtPkEph0HW/ndLG5tb2Tnm3srd/cHhUPT7pmCTTjLdZIhPdC6jhUijeRoGS91LNaRxI3g0md3O/+8S1EYl6xGnK/ZiOlIgEo2il7kDaaEiH1Zpbdxcg68QrSA0KtIbVr0GYsCzmCpmkxvQ9N0U/pxoFk3xWGWSGp5RN6Ij3LVU05sbPF+vOyIVVQhIl2j6FZKH+nshpbMw0Dmwypjg2q95c/M/rZxjd+LlQaYZcseVHUSYJJmR+OwmF5gzl1BLKtLC7EjammjK0DVVsCd7qyeukc1X33Lr3cF1r3hZ1lOEMzuESPGhAE+6hBW1gMIFneIU3J3VenHfnYxktOcXMKfyB8/kDPMWPfQ==</latexit><latexit sha1_base64="/JI5iynvNWOEKZjLq6ujHWhdsHw=">AAAB7nicbVDLSsNAFL2pr1pfVZduBovgqiQi1GXRjcsK9gFtKJPJpB06mYSZG6GEfoQbF4q49Xvc+TdO2yy09cDA4ZxzmXtPkEph0HW/ndLG5tb2Tnm3srd/cHhUPT7pmCTTjLdZIhPdC6jhUijeRoGS91LNaRxI3g0md3O/+8S1EYl6xGnK/ZiOlIgEo2il7kDaaEiH1Zpbdxcg68QrSA0KtIbVr0GYsCzmCpmkxvQ9N0U/pxoFk3xWGWSGp5RN6Ij3LVU05sbPF+vOyIVVQhIl2j6FZKH+nshpbMw0Dmwypjg2q95c/M/rZxjd+LlQaYZcseVHUSYJJmR+OwmF5gzl1BLKtLC7EjammjK0DVVsCd7qyeukc1X33Lr3cF1r3hZ1lOEMzuESPGhAE+6hBW1gMIFneIU3J3VenHfnYxktOcXMKfyB8/kDPMWPfQ==</latexit>
<latexit sha1_base64="/JI5iynvNWOEKZjLq6ujHWhdsHw=">AAAB7nicbVDLSsNAFL2pr1pfVZduBovgqiQi1GXRjcsK9gFtKJPJpB06mYSZG6GEfoQbF4q49Xvc+TdO2yy09cDA4ZxzmXtPkEph0HW/ndLG5tb2Tnm3srd/cHhUPT7pmCTTjLdZIhPdC6jhUijeRoGS91LNaRxI3g0md3O/+8S1EYl6xGnK/ZiOlIgEo2il7kDaaEiH1Zpbdxcg68QrSA0KtIbVr0GYsCzmCpmkxvQ9N0U/pxoFk3xWGWSGp5RN6Ij3LVU05sbPF+vOyIVVQhIl2j6FZKH+nshpbMw0Dmwypjg2q95c/M/rZxjd+LlQaYZcseVHUSYJJmR+OwmF5gzl1BLKtLC7EjammjK0DVVsCd7qyeukc1X33Lr3cF1r3hZ1lOEMzuESPGhAE+6hBW1gMIFneIU3J3VenHfnYxktOcXMKfyB8/kDPMWPfQ==</latexit><latexit sha1_base64="/JI5iynvNWOEKZjLq6ujHWhdsHw=">AAAB7nicbVDLSsNAFL2pr1pfVZduBovgqiQi1GXRjcsK9gFtKJPJpB06mYSZG6GEfoQbF4q49Xvc+TdO2yy09cDA4ZxzmXtPkEph0HW/ndLG5tb2Tnm3srd/cHhUPT7pmCTTjLdZIhPdC6jhUijeRoGS91LNaRxI3g0md3O/+8S1EYl6xGnK/ZiOlIgEo2il7kDaaEiH1Zpbdxcg68QrSA0KtIbVr0GYsCzmCpmkxvQ9N0U/pxoFk3xWGWSGp5RN6Ij3LVU05sbPF+vOyIVVQhIl2j6FZKH+nshpbMw0Dmwypjg2q95c/M/rZxjd+LlQaYZcseVHUSYJJmR+OwmF5gzl1BLKtLC7EjammjK0DVVsCd7qyeukc1X33Lr3cF1r3hZ1lOEMzuESPGhAE+6hBW1gMIFneIU3J3VenHfnYxktOcXMKfyB8/kDPMWPfQ==</latexit><latexit sha1_base64="/JI5iynvNWOEKZjLq6ujHWhdsHw=">AAAB7nicbVDLSsNAFL2pr1pfVZduBovgqiQi1GXRjcsK9gFtKJPJpB06mYSZG6GEfoQbF4q49Xvc+TdO2yy09cDA4ZxzmXtPkEph0HW/ndLG5tb2Tnm3srd/cHhUPT7pmCTTjLdZIhPdC6jhUijeRoGS91LNaRxI3g0md3O/+8S1EYl6xGnK/ZiOlIgEo2il7kDaaEiH1Zpbdxcg68QrSA0KtIbVr0GYsCzmCpmkxvQ9N0U/pxoFk3xWGWSGp5RN6Ij3LVU05sbPF+vOyIVVQhIl2j6FZKH+nshpbMw0Dmwypjg2q95c/M/rZxjd+LlQaYZcseVHUSYJJmR+OwmF5gzl1BLKtLC7EjammjK0DVVsCd7qyeukc1X33Lr3cF1r3hZ1lOEMzuESPGhAE+6hBW1gMIFneIU3J3VenHfnYxktOcXMKfyB8/kDPMWPfQ==</latexit><latexit sha1_base64="/JI5iynvNWOEKZjLq6ujHWhdsHw=">AAAB7nicbVDLSsNAFL2pr1pfVZduBovgqiQi1GXRjcsK9gFtKJPJpB06mYSZG6GEfoQbF4q49Xvc+TdO2yy09cDA4ZxzmXtPkEph0HW/ndLG5tb2Tnm3srd/cHhUPT7pmCTTjLdZIhPdC6jhUijeRoGS91LNaRxI3g0md3O/+8S1EYl6xGnK/ZiOlIgEo2il7kDaaEiH1Zpbdxcg68QrSA0KtIbVr0GYsCzmCpmkxvQ9N0U/pxoFk3xWGWSGp5RN6Ij3LVU05sbPF+vOyIVVQhIl2j6FZKH+nshpbMw0Dmwypjg2q95c/M/rZxjd+LlQaYZcseVHUSYJJmR+OwmF5gzl1BLKtLC7EjammjK0DVVsCd7qyeukc1X33Lr3cF1r3hZ1lOEMzuESPGhAE+6hBW1gMIFneIU3J3VenHfnYxktOcXMKfyB8/kDPMWPfQ==</latexit>
<latexit sha1_base64="/JI5iynvNWOEKZjLq6ujHWhdsHw=">AAAB7nicbVDLSsNAFL2pr1pfVZduBovgqiQi1GXRjcsK9gFtKJPJpB06mYSZG6GEfoQbF4q49Xvc+TdO2yy09cDA4ZxzmXtPkEph0HW/ndLG5tb2Tnm3srd/cHhUPT7pmCTTjLdZIhPdC6jhUijeRoGS91LNaRxI3g0md3O/+8S1EYl6xGnK/ZiOlIgEo2il7kDaaEiH1Zpbdxcg68QrSA0KtIbVr0GYsCzmCpmkxvQ9N0U/pxoFk3xWGWSGp5RN6Ij3LVU05sbPF+vOyIVVQhIl2j6FZKH+nshpbMw0Dmwypjg2q95c/M/rZxjd+LlQaYZcseVHUSYJJmR+OwmF5gzl1BLKtLC7EjammjK0DVVsCd7qyeukc1X33Lr3cF1r3hZ1lOEMzuESPGhAE+6hBW1gMIFneIU3J3VenHfnYxktOcXMKfyB8/kDPMWPfQ==</latexit><latexit sha1_base64="/JI5iynvNWOEKZjLq6ujHWhdsHw=">AAAB7nicbVDLSsNAFL2pr1pfVZduBovgqiQi1GXRjcsK9gFtKJPJpB06mYSZG6GEfoQbF4q49Xvc+TdO2yy09cDA4ZxzmXtPkEph0HW/ndLG5tb2Tnm3srd/cHhUPT7pmCTTjLdZIhPdC6jhUijeRoGS91LNaRxI3g0md3O/+8S1EYl6xGnK/ZiOlIgEo2il7kDaaEiH1Zpbdxcg68QrSA0KtIbVr0GYsCzmCpmkxvQ9N0U/pxoFk3xWGWSGp5RN6Ij3LVU05sbPF+vOyIVVQhIl2j6FZKH+nshpbMw0Dmwypjg2q95c/M/rZxjd+LlQaYZcseVHUSYJJmR+OwmF5gzl1BLKtLC7EjammjK0DVVsCd7qyeukc1X33Lr3cF1r3hZ1lOEMzuESPGhAE+6hBW1gMIFneIU3J3VenHfnYxktOcXMKfyB8/kDPMWPfQ==</latexit><latexit sha1_base64="/JI5iynvNWOEKZjLq6ujHWhdsHw=">AAAB7nicbVDLSsNAFL2pr1pfVZduBovgqiQi1GXRjcsK9gFtKJPJpB06mYSZG6GEfoQbF4q49Xvc+TdO2yy09cDA4ZxzmXtPkEph0HW/ndLG5tb2Tnm3srd/cHhUPT7pmCTTjLdZIhPdC6jhUijeRoGS91LNaRxI3g0md3O/+8S1EYl6xGnK/ZiOlIgEo2il7kDaaEiH1Zpbdxcg68QrSA0KtIbVr0GYsCzmCpmkxvQ9N0U/pxoFk3xWGWSGp5RN6Ij3LVU05sbPF+vOyIVVQhIl2j6FZKH+nshpbMw0Dmwypjg2q95c/M/rZxjd+LlQaYZcseVHUSYJJmR+OwmF5gzl1BLKtLC7EjammjK0DVVsCd7qyeukc1X33Lr3cF1r3hZ1lOEMzuESPGhAE+6hBW1gMIFneIU3J3VenHfnYxktOcXMKfyB8/kDPMWPfQ==</latexit><latexit sha1_base64="/JI5iynvNWOEKZjLq6ujHWhdsHw=">AAAB7nicbVDLSsNAFL2pr1pfVZduBovgqiQi1GXRjcsK9gFtKJPJpB06mYSZG6GEfoQbF4q49Xvc+TdO2yy09cDA4ZxzmXtPkEph0HW/ndLG5tb2Tnm3srd/cHhUPT7pmCTTjLdZIhPdC6jhUijeRoGS91LNaRxI3g0md3O/+8S1EYl6xGnK/ZiOlIgEo2il7kDaaEiH1Zpbdxcg68QrSA0KtIbVr0GYsCzmCpmkxvQ9N0U/pxoFk3xWGWSGp5RN6Ij3LVU05sbPF+vOyIVVQhIl2j6FZKH+nshpbMw0Dmwypjg2q95c/M/rZxjd+LlQaYZcseVHUSYJJmR+OwmF5gzl1BLKtLC7EjammjK0DVVsCd7qyeukc1X33Lr3cF1r3hZ1lOEMzuESPGhAE+6hBW1gMIFneIU3J3VenHfnYxktOcXMKfyB8/kDPMWPfQ==</latexit>
observed entries is 1 and divide the loss function by the number of (observed) entries. The initialization 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 in NMF we only compute the loss over observed ratings (Zhang et 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 4 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 a challenge.

heading: 4.2 ABLATION EXPERIMENTS
text: Theorem 1 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 a point x, given some optimal solution x˚, is
αpxq “ min λPr0,1s
`2 ` λx˚ ` p1´ λqx ˘
(6)
Note that α ě 0 implies star-convexity. In practice, x and x˚ are 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 α. Figure 5 show how the relative deviation, σµ , of α 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 6, we show that the cosine similarity between the negative gradients ´∇`pU,Vq and the straight line from x0 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 a random matrix of the same shape with iid entries from a halfnormal distribution. The spectra are similar, and while U˚ is not random, it seems to share structural qualities with the random matrices used in our proofs. See Appendix C for figures on more datasets.

heading: 4.3 IMPLICATIONS FOR NEURAL NETWORKS
text: We have seen how increasing the number of parameters makes NMF problems more likely to be starconvex, and Figure 5 shows how more parameters make the curvature tend towards its positive mean. Theorem 1 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. It has previously been observed how neural networks are locally convex (Izmailov et al., 2018; Kleinberg et al., 2018), and also how overparameterization is important in deep learning (Arora et al., 2018; Frankle and Carbin, 2018). Based upon our observations in NMF, we hypothesise that a major benefit of overparameterization is in making the loss surface more convex via concentration of measure w.r.t. the weights.
To verify this hypothesis, we consider image classification on CIFAR10 (Krizhevsky et al., 2014) with Resnet networks (He et al., 2016) trained with standard parameters (see Appendix B). Networks are typically only locally convex, a property we quantify as the length of subsets of random "lines" in parameter space, along which the loss is convex. We sample a random direction r and then consider a 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 maximal sub-interval rλ1, λ2s containing 0 on which `pw` λrq 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 locally convex for all but the most shallow networks, results that support our hypothesis. See Appendix B for extended tables.

heading: 5 RELATED WORK
text: Our work was initially motivated by findings in Kleinberg et al. (2018) and Zhou et al. (2019) regarding star-convexity in neural networks. As the success of deep learning has become apparent, researchers have empirically investigated neural network trained on real-world datasets (Li and Yuan, 2017; Keskar et al., 2016). In the context of sharp vs flat local minima (Keskar et al., 2016), Li et al. (2018) illustrate how width improved flatness in a Resnet network, an observation Table 2 quantifies. In general, real-world datasets seem to be far more well-behaved than the worst case, given that training neural networks are NP-hard (Blum and Rivest, 1989). There is extensive work on nonworst-case analysis of algorithms and machine learning models, and on what problem distributions can guarantee tractability which addresses such gaps (Bilu and Linial, 2012; Afshani et al., 2017). On the positive side Arora et al. (2012) has shown an exact algorithm for NMF that runs in polynomial time for small constant r, and there are positive results for ’separable’ NMF (Donoho and Stodden, 2004). Compressive sensing (Candes et al., 2004), smoothed analysis (Spielman 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 in theoretical convergence properties of shallow and linear networks (Lu and Kawaguchi, 2017), where a common theme is that functions with only saddle points and global minima can be effectively optimized (Ge et al., 2015). In analysis of neural networks, random matrix theory often plays a role, directly or indirectly (Choromanska et al., 2015; Glorot and Bengio, 2010; Pennington and Bahri, 2017; Xiao et al., 2018).

heading: 6 CONCLUSIONS
text: This paper revisits NMF, a non-convex optimization problem in machine learning. We have shown that NMF is typically star-convex, provably for a natural average-case model and empirically on an extensive set of real-world datasets. Our results support the counter-intuitive observation that optimization might sometimes be easier in higher dimensions due to concentration of measure effects.

heading: A DATASETS
text: Here we describe the datasets we used to evaluate our results on and provide references for them.
Birdsong: time series for bird calls, see (Flenner and Hunter, 2017; canto Foundation). Extragalactic: dataset for extragalactic light sources, see (Zhu, 2016). Goodbooks: user ratings for books, see (Kula, 2017; Bourgin, 2018). Metabolic: Yest metabolic activity time series, see (Li and Ngom, 2013). Movielens: user ratings for movies , see (Harper and Konstan, 2016; Li et al., 2012; Zhang et al., 2006). Netflix: User ratings for movies, see (Zhou et al., 2008; Ampazis, 2008; Li et al., 2012). ORL faces: black and white facial images, see (Li et al., 2001; Hoyer, 2004). Satellite: satellite urban spectral-image, see (Erichson et al., 2018; Gillis, 2014).

heading: B DNN PARAMETERS
text: Table 3 presents the hyper-parameters 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 10 after epochs p150, 225, 275q. We use the standard Resnet architecture for CIFAR10 with three segments with p16, 32, 64q channels each, and use the standard blocks (i.e. not bottleneck blocks) (He et al., 2016).

heading: C EXTENDED NMF FIGURES

heading: D PROOFS

heading: D.1 OVERVIEW
text: We here provide the proof of Theorem 1. In section D.2 we present the notation and derive the main inequality. In Section D.3, we prove that the loss function is convex between any two 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 is convex between any two random points with high probability in Section 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 1 as stated in the main text. Section D.6 presents the concentration
results we need. The proofs include considerable amounts of elementary algebraic calculations. For completeness and ease of reference, we present these in Appendix E.

heading: D.2 NOTATION AND THE MAIN INEQUALITY
text: The proof will involve various constants c0, c1, c2 that do not depend on n. For convenience, we will let exact values be context dependent and will reuse the symbols c0, 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 a 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-by-r matrices and V1, V2, V˚ r-by-m matrices sampled as per Assumption 1. Without loss of generality, we assume m “ ncm where 0 ă cm ď 1. We will let µvar be the expectation, and σ2 be the variance of the entry-wise distributions. We will denote the centered variables by Ū1, V̄1 and so on, and the mean matrix of U and V resp as 1nˆr, 1rˆm. Then U “ Ū ` 1nˆr. By slight abuse of notation, we will use the convention xX,Yy “ Tr ` XYT ˘
for matrices X,Y of the same shape. The loss function we wish to minimize, subject to non-negativity constraints, is
`pU,Vq “ 1 2 }UV ´X}2F (7)
When we interpolate the solution UV between any fixed two points pU1,V1q and pU2,V2q, we write
X̂pλq “ ` λU1 ` p1´ λqU2 ˘` λV1 ` p1´ λqV2 ˘
The loss is then
`pλq “ 1 2 }X̂pλq ´X}2F
Proving Theorem 1 in the case of two random points and completely observed data amounts to showing that the continuous function `pλq is convex in λ on the interval r0, 1s with high probability. We will show that the second-derivate is non-negative. For fixed matrices U1,U2,U˚,V1,V2,V˚, the loss `pλq is a fourth-degree polynomial in λ, so its second derivate w.r.t. λ will be a seconddegree polynomial. For a general second-degree polynomial ppxq “ ax2 ` bx` c we have ppxq “ 1 a “` ax ` b2 ˘2 ` ` ac ´ b 2 4 ˘‰
. By inspecting equation 8 one can conclude that a ą 0. Showing that the polynomial is non-negative can then be done by showing ac ě b 2
4 . Let X̂ijpλq be element i, j of the matrix X̂pλq. The derivates of `pλq are then
`pλq “ 1 2 ÿ
ij
` X̂ijpλq ´Xij ˘2
`1pλq “ ÿ
ij
` X̂ijpλq ´Xij ˘ X̂1ijpλq
`2pλq “ ÿ
ij
X̂2ijpλq ` X̂ijpλq ´Xij ˘ ` X̂1ijpλq2
`3pλq “ 3 ÿ
ij
X̂2ijpλqX̂1ijpλq
`4pλq “ 3 ÿ
ij
X̂2ijpλq2 (8)
Where we have
X̂pλq “ ` λU1 ` p1´ λqU2 ˘` λV1 ` p1´ λqV2 ˘
X̂1pλq “ ˆ U1 ´U2 ˙ˆ λV1 ` p1´ λqV2 ˙ ` ˆ λU1 ` p1´ λqU2 ˙ˆ V1 ´V2 ˙
X̂2pλq “ 2 ˆ U1 ´U2 ˙ˆ V1 ´V2 ˙
Let us define
W0 “ U2V2 ´U˚V˚
W1 “ ˆ U1 ´U2 ˙ V2 `U2 ˆ V1 ´V2 ˙
W2 “ ˆ U1 ´U2 ˙ˆ V1 ´V2 ˙
By expanding `2pλq in a McLaurin series around 0, we see that proving non-negativity of `2pλq can be done by proving 2`p0q2`4p0q ě `3p0q2. Thus, proving Theorem 3 then amounts to showing that
2}W2}2F ` }W1}2F ` 2xW0,W2y ˘ ě 3 ` xW1,W2y ˘2
(9)

heading: D.3 PROVING THE INEQUALITY BETWEEN RANDOM POINTS
text: Theorem 2. Let pU1,V1q, pU2,V2q and the planted solution pU˚,V˚q be sampled as per Assumption 1. The loss function equation 7 is convex on a straight line connecting pU1,V1q and pU2,V2q with probability ě 1´ c1 exp ` ´ c2n1{3 ˘ for positive constants c1, c2.
Proof. As per section D.2, we only need to prove that equation 9 holds with probability ě 1 ´ c1 exp ` ´ c2n1{3 ˘
. Let us exhange all terms in equation 9 with their means, which are given in Facts 7, 5, 6 and 8
2p4rmnσ4q ` 6rmnσ4 ` 4rmnµ2varσ2 ` 2rmnσ4 ˘ ě 3 ` ´ 4rmnσ4 ˘2
(10)
Clearly, equation 9 would hold if one naively exchanges the terms for their means. Just counting terms of order rmnσ4 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 }W2}2F . As per equation 14, }W2}2F can be rewritten into polynomials 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 1 to conclude that the probability that }W2}2F deviates from its mean by a factor p1` q is no more than c1 expp´c2 2n ˘ .
Now, consider the random variable }W1}2F . As in the proof of Fact 7, }W1}2F can be rewritten as the sum of expression equation 16 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 1 to conclude that the probability that it deviates from its mean by a factor p1 ` q is no more than c1 expp´c2 2n ˘ . Consider the expression equation 16. Clearly the expressions 1Trˆm ` Ū1 ´ Ū2 ˘T ` Ū1 ´ Ū2 ˘ 1rˆm and ` V̄1 ´ V̄2 ˘T 1Tnˆr1nˆr ` V̄1 ´ V̄2 ˘
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 16, and will thus only consider terms scaling as rn2σ4.
Now, consider the random variable xW0,W2y. As per equation 19, the variable xW0,W2y 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 1 applies which again bounds the probability of deviations by a factor p1` q by c1 expp´c2 2n ˘
. The second one is a sum of the type 1X1X2X3 modulo permutations, under which the trace is invariant. We can thus apply Fact 2 which bounds the probability for deviations of size xW0,W2y by c1 exp ` ´ c2n1{3 ˘ .
At last, consider the random variable xW1,W2y. By equation 18 can, just like xW0,W2y, be written as the sum of a polynomial in centered random matrices, and sums of variables of the type 1X1X2X3 modulo permutations. We can thus apply the same argument as for xW0,W2y to bounds the probability for deviations of relative size by c1 exp ` ´ c2n1{3 ˘ .
We can now apply union bound on the variables }W1}2F , }W2}2F , xW0,W2y and xW1,W2y, modulu term equation 16, deviating from their respective mean by a factor . The probability that either of them does is no more than c1 exp ` ´ c2 2n1{3 ˘
by union bounds. Now, set “ 0.01 If neither variable deviates by a factor of more than 0.01, then equation 10 still holds if we only count terms scaling as rmrσ4 since 0.992 ˚ 64 ě 1.012 ˚ 48. Thus, inequality is violated with probability at most c1 exp ` ´ c2n1{3 ˘ for positive constants c1, c2.

heading: D.4 PROVING THE INEQUALITY TOWARDS THE PLANTED SOLUTION
text: Theorem 3. Let pU1,V1q and the planted solution pU˚,V˚q be sampled as per Assumption 1. The loss function of equation 7 is convex on a straight line connecting pU1,V1q and pU˚,V˚q with probability ě 1´ c1 exp ` ´ c2n1{3 ˘ for constants c1, c2 ą 0.
Proof. To prove this, we can repeat the argument used in the proof of Theorem 2. The terms }W2}2, }W1}2 and xW1,W2y will have the same mean and concentration since U1 and U˚ are identically distributed. The only difference will be the term xW0,W2y, which now will have mean 2rmnσ4 per Fact 10. This will only make the LHS of equation 10 larger, so the inequality will still hold and the concentration of measure properties will ensure that equation 9 holds with high probability as in the proof of theorem 2.

heading: D.5 PROVING THE INEQUALITY BETWEEN RANDOM POINTS FOR UNOBSERVED DATA
text: As explained in the main text, we will assume that entries are observed with independent probability p. We formalize this in the following assumption
Assumption 2. For any n, let 1̂ P t0, 1unˆm have entries iid drawn from a Bernoulli distribution with probability p, which is constant w.r.t n.
Given any set of observations 1̂, we define our loss function as
`pU,Vq “ ÿ
i,j
1̂pi,jq
ˆ
“ UV ‰ ij ´Xij
˙2
(11)
Theorem 4. Let pU1,V1q, pU2,V2q and the planted solution pU˚,V˚q be sampled as per Assumption 1. Let the set of observations 1̂ be sampled as per Assumption 2. The loss function equation 11 is convex on a straight line connecting pU1,V1q and pU2,V2q with probability ě 1´ c1 exp ` ´ c2r1{3 ˘ for constants c1, c2 ą 0.
Proof. If no entries are observed, we can claim trivially that the function is convex. If some entries are observed, then a ą 0 since X̂2ijpλq2 ą 0 for any pi, jq with probability 1. The second derivate of equation 11 can be written as
`2pλq “ ÿ
ij
1̂pi,jq
ˆ
X̂1 2 ij ` X̂2ijpX̂ij ´Xijq ˙
Using Lemma 1, we can assume by union bound that no entry in X̂, X̂1, X̂2,X is larger than Opr2{3q with probabilityď c1n2 exp ` ´ c2r1{3 ˘ . Note that this estimate gives the exp ` ´ c2r1{3 ˘ scaling of the proof. Let assume that the entries are bounded like this, then no entry in X̂1 2
ij`X̂2ijpX̂ij´Xijq will have magnitude more than Opr4{3q for any λ. Standard Hoeffding bounds (Hoeffding, 1994) states that for variables txiu bounded in rAi, Bis we have
P
ˆ ˇ
ˇ
ˇ
ˇ
1
n
n ÿ
i
xi
ˇ
ˇ
ˇ
ˇ
ě t ˙ ď exp ˆ ´ 2n 2t2
řn i pbi ´ aiq2
˙
Let us define
ypλq “ ÿ
ij
X̂1 2
ijpλq ` X̂2ijpX̂ijpλq ´Xijq
Let us now consider fixed matrices U1,U2,U˚,V1,V2,V˚ satisfying Lemma 1, but let 1̂ remain a random variable. We can then consider the product of any two variables out of X̂ij , X̂1ij , X̂ 2
ij ,Xij as fixed constants in the interval r´c1r4{3, c1r4{3s for some constant c1. We note that ypλq is the
sum of cmn2 variables, each of size at most Opr4{3q. Now ypλq is a sum of independent variables and Hoeffdinger applies with pbi ´ aiq2 ď Opr8{3q for all i. Taking t “ cr2{3 gives us
P
ˆ ˇ
ˇ
ˇ
ˇ
ypλq ´ Erypλqs ˇ ˇ ˇ
ˇ
ě cr2{3n2 ˙ ď exp ˆ ´ 2c 2cmn 4r4{3
n2r8{3
˙
ď exp ` ´ cn2{3 ˘
This will hold for any λ. We can assume that this holds for let’s say 3 evenly spaced λ by union bound. Using union bounds, we assume the following: 1) ypλq ą c1rmn for all λ, which follows from the derivation of Theorem 2 with probability ě 1 ´ c1 expp´c2n1{3q. 2) |X̂ij | ď r2{3 for all i, j via Lemma 1. 3) |Y pλq ´ Erypλqs| ď cr2{3n2 for 3 evenly spaced λi by the above equation. Now, since the `2pλq is a 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 ŷpλq “ ypλq ´ Erypλqs. Now, our union bounds states that |ŷpλiq| ă cr2{3n2 for three evenly spaced λi. Now, let the three coefficients of the second-degree polynomial be described by the vector p, its values at λi by the vector v and let the matrix A describe the values of the monomials 1, λ, λ2 at λi. We then have Ap “ v. Now, A will have elements bounded by 1 but will be full rank, this implies that if v is bounded by cr2{3n2 so must p be. The fact that the coefficents in ŷ have absolute value bounded by Opr2{3n2q, together with the fact that the mean scales as rn2 gives us the following
min λ ypλq “ min λ ŷpλq ` Erypλqs ě min λ ŷpλq `min λ1 Erypλ1qs
ě min λ ŷpλq ` crn2 ě c1r2{3n2 ` crn2
Here c is positive as per our assumptions, whereas c1 might be negative. Now, for sufficiently large r, the above quality will be non-negative. We can thus find new constants, based upon c and c1, to complete the proof.

heading: D.6 CONCENTRATION
text: This section contains the concentration results needed for the proof of Theorem 1. We will use 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., 2000). We will use the concentration results of Meckes and Szarek (2012) which relies on the notation of CCP – convex concentration property – which is a regularity condition. Definition 2. A random matrix X in a normed vector space satisfies CCP iff there exists positive constants c1, c2 such that P `ˇ ˇfpXq ´MfpXq ˇ ˇ ě t ˘ ď c1e´c2t 2
for all t and all convex 1-Lipschitz functions f . Here M is the median.
One can easily verify that independent Gaussian variables satisfies this (Ledoux, 2001), and it then follows that 1-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 is 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 4 in centered matrices Xi,Xj ,Xk,Xl otherwise sampled as per Assumption 1, where we allow i “ j, j “ l and any other arbitrary index relationship. Let z “ Tr P̂ pXi,Xj ,Xk,Xlq and let µ be then mean of z, then P ` |z ´ µ| ą t r n2 ˘ ď c1 exp `
´ c2 minpt2, t1{2qn ˘ for positive constants c1, c2.
Proof. Any vector CCP where some components are zero will still be CCP, this we can pad the matrices Xi,Xj ,Xk,Xl so that they are square. We then invoke Theorem 1 of Meckes and Szarek (2012) which gives
P
ˆ |z ´ µ| ą τn2 ˙ ď c1 exp ` ´ c2 minpτ2, n τ1{2q ˘
Setting τ “ tr gives us
P
ˆ |z ´ µ| ą t r n2 ˙ ď c1 exp ` ´ c2 minp t2 r2, t1{2 r1{2 nq ˘
Using our assumption r “ Opnγq for some γ P r1{2, 1s gives
P
ˆ |z ´ µ| ą t r n2 ˙ ď c1 exp ` ´ c2 minpt2, t1{2qn ˘
Fact 2. Let z “ Tr ` 1XiXjXk ˘
for centered matrices Xi,Xj ,Xk otherwise sampled as per Assumption 1, and let µ be the mean of z. 1 is a matrix of all 1s of the appropriate shape. Then P ` |z ´ µ| ě t rn2 ˘ ď c1 exp ` ´ c2n1{3 minpt1{2, t2q ˘ 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 1 is at most n. This means that the shatten-norm }E 1}k is at most n for all k. Let us consider the matrix 1̂ “ 1
n1{3 which then has shatten-norm }E 1̂}d is at most
n2{3. For this matrix, Theorem 1 in Meckes and Szarek (2012) applies, so that we have
P
„ ˇ
ˇ
ˇ
ˇ
Tr
ˆ 1XiXjXk ´ µ ˙ ˇ ˇ ˇ
ˇ
ě tn2  ď c1 exp ` ´ c2 min ` t2, nt1{2 ˘˘
(12)
Let us take t “ t0rn´1{3 so that tn7{3 “ t0rn2. We then have
ˇ ˇTr ` 1̂XiXjXk ´ µ ˘ ˇ ˇ ě tn2 ðñ ˇ ˇTr ` 1XiXjXk ´ µ ˘ ˇ ˇ ě tn7{3
ðñ ˇ ˇTr ` 1XiXjXk ´ µ ˘ ˇ ˇ ě t0rn2
By substituting t “ t0rn´1{3 into equation 12 we then have
P
ˆ
ˇ ˇTr ` 1XiXjXk ´ µ ˘ ˇ ˇ ě t0rn2 ˙
(13)
ď c1 exp ` ´ c2 min ` t20r 2n´2{3, t 1{2 0 r 1{2n1´1{6 ˘˘
Recall our assumption r “ c3nγ for γ P r1{2, 1s. We then have
min ` t20r 2n´2{3, t 1{2 0 r 1{2n1´1{6 ˘ ě min ` t 1{2 0 , t 2 0 ˘ n1{3
Plugging this into equation 13 completes the proof
Lemma 1. With probabilityď c1n2 exp ` ´c2r1{3 ˘ , no entry in X̂ij , X̂1ij , X̂ 2
ij ,Xij has an absolute value larger than cr2{3, for some positive constant c.
Proof. For a fixed i, j consider the terms X̂ij , X̂1ij , X̂ 2
ij ,Xij . Fact 9 says that each one can be expressed as a constant number of variables a with zero mean of the form
a “ r ÿ
i“1 vp1qi v p2q i
Since the variables themselves are sub-gaussian, by Lemma 2.7.7 in Vershynin (2018) the product vp1qi v p2q i 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
P ` ˇ ˇa ˇ ˇ ě t ˘ ď 2 exp ˆ ´ cmin „ t2 rK2 , t K ˙
Here K is the orlicz norm } ¨ }Ψ1 which is a constant for our fixed distributions. In the above expression, let us set t “ cr2{3. This gives
P
ˆ ˇ
ˇ
ˇ
ˇ
a´ Eras ˇ ˇ ˇ
ˇ
ě cr2{3 ˙ ď 2 exp ` ´ cr1{3 ˘
We note that there is a polynomial number of entries a, so we can do a polynomial number (w.r.t. n) of union bounds, which might change the constants, to show that no entry is further than c1r2{3 from its expectation for some positive c1.

heading: E ALGEBRAIC CALCULATIONS

heading: E.1 BASIC FACTS
text: Fact 3. E “ Tr ŪT ŪV̄V̄T ‰ “ rmnσ4
Proof. We have
E “ Tr ŪT ŪV̄V̄T ‰ “ E „ ÿ
ijkl
ŪjiŪjkV̄klV̄il

Taking the mean, and using linearity of expectations, we only have nonzero mean if i “ k. We get
“ E „ ÿ
ijl
ŪjiŪjiV̄ilV̄il

Using linearity of expectation and independence, this becomes
ÿ
ijl
E “ ŪjiŪji ‰ E “ V̄ilV̄il ‰
For a single matrix entry, E “ ŪjiŪji ‰ “ σ2. i goes over the columns of U of which there are r, j goes over the rows of Ū of which there are n and l goes over the columns of V̄ of which there are m, so we clearly get σ4rmn.
Fact 4. E „
Tr ŪT Ū1rˆm1Trˆm

“ rmnµ2varσ2
Proof. We can can first contract 1rˆm1Trˆm “ 1mµ2var, where 1 is a r-by-r matrix of all ones. We then want to find
E „ ÿ
ijk
ŪjiŪjk1ki 
Now since the variables are centered, the expectations becomes zero unless i “ k. The sum thus becomes
E „ ÿ
ij
ŪjiŪji1ii  “ nrσ2
This gives us the result of rmnµ2varσ 2.

heading: E.2 EXPECTATION
text: Fact 5. Er}W2}2s “ 4mnrσ4
Proof. Let us rewrite Er}W2}2s as
ETr „ˆ V1 ´V2 ˙Tˆ U1 ´U2 ˙Tˆ U1 ´U2 ˙ˆ V1 ´V2 ˙
Trace and expectations are linear operators, so we can reorder them. Let us consider the matrix
ˆ V1 ´V2 ˙Tˆ U1 ´U2 ˙Tˆ U1 ´U2 ˙ˆ V1 ´V2 ˙
We can easily add and subtract the mean µ of all matrices which gives
ˆ V̄1 ´ V̄2 ˙Tˆ Ū1 ´ Ū2 ˙Tˆ Ū1 ´ Ū2 ˙ˆ V̄1 ´ 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 VTUTUV. Permuting the indices cyclically and appealing to Fact 3 gives us
Er}W2}2s “ 4mnrσ4 Fact 6. ErxW0,W2ys “ rmnσ4
Proof. We can write ErxW0,W2ys as
ETr „ˆ
VT2 U T 2 ´ pV˚qT pU˚qT
˙ˆ
` U1 ´U2 ˘` V1 ´V2 ˘
˙
Again, we want to add and subtract the matrix means 1nˆr, 1rˆm to get
ETr „ˆ “ V̄2 T Ū2 T`V̄2 T 1Tnˆr`1TrˆmŪ2 T`1Trˆm1Tnˆr ‰ ´ “ V̄˚ T Ū˚ T`V̄˚T 1Tnˆr`1TrˆmŪ˚ T`1Trˆm1Tnˆr ‰ ˙
(15)
ˆ ˆ ` Ū1 ´ Ū2 ˘` V̄1 ´ V̄2 ˘ ˙
As before, we can remove terms which are linear in any centered variable. This removes matrices with index 1, 3 and leaves
ETr „ˆ V̄2 T Ū2 T ` V̄2 T 1Tnˆr ` 1TrˆmŪ2 T ˙ˆ Ū2V̄2 ˙
Applying fact 3 to the only term that remain gives
ErxW0,W2ys “ ETr „ V̄2 T Ū2 T Ū2V̄2  “ rmnσ4
Fact 7. E}W1}2F “ 6rmnσ4 ` 4rmnµ2varσ2
Proof. We rewrite E}W1}2F as
ETr „ˆ
VT2 ` U1 ´U2 ˘T ` ` V1 ´V2 ˘T UT2
˙ˆ
` U1 ´U2 ˘ V2 `U2 ` V1 ´V2 ˘
˙
We will again want to center the variables, which gives
ETr „ˆ V̄2 T ` Ū1 ´ Ū2 ˘T ` 1Trˆm ` Ū1 ´ Ū2 ˘T ` ` Ū1 ´ V̄2 ˘T Ū2 T ` ` V̄1 ´ V̄2 ˘T 1Tnˆr ˙
ˆ ˆ ` Ū1 ´ Ū2 ˘ V̄2 ` ` Ū1 ´ Ū2 ˘ 1rˆm ` Ū2 ` V̄1 ´ V̄2 ˘ ` 1nˆr ` V̄1 ´ V̄2 ˘ ˙
Let us first consider the terms involving constants. We remove any terms linear in centered variables. We are then left with
1Trˆm ` Ū1 ´ Ū2 ˘T ` Ū1 ´ Ū2 ˘ 1rˆm ` ` V̄1 ´ V̄2 ˘T 1Tnˆr1nˆr ` V̄1 ´ V̄2 ˘
(16)
As before, any expressions linear in centered variables vanish when we take expectations. Using this and Fact 4 we get that the above expression is equal to
“ 4rmnµ2varσ2
We now return to the terms without constants These are
V̄2 T ` Ū1 ´ Ū2 ˘T ` Ū1 ´ Ū2 ˘ V̄2 ` ` V̄1 ´ V̄2 ˘T Ū2 T Ū2 ` V̄1 ´ V̄2 ˘
(17)
`V̄2 T ` Ū1 ´ Ū2 ˘T Ū2 ` V̄1 ´ V̄2 ˘ ` ` V̄1 ´ V̄2 ˘T Ū2 T ` Ū1 ´ Ū2 ˘ V̄2
As before, we remove any expressions linear in centered variables. As it turns out, we are left with 6 terms of the type V̄2 T Ū2 T Ū2V̄2. Applying Fact 3 gives us
E “ }W1}2F ‰ “ 6rmnσ4 ` 4rmnµ2varσ2 Fact 8. ExW2,W1y “ ´4rmnσ4
Proof. Let us rewrite ExW2,W1y as
ETr „ˆ ` V1 ´V2 ˘T ` U1 ´U2 ˘T ˙ˆ ` U1 ´U2 ˘ V2 `U2 ` V1 ´V2 ˘ ˙
As per usual, we center the variables
“ „ˆ ` V̄1´V̄2 ˘T ` Ū1´Ū2 ˘T ˙ˆ ` Ū1´Ū2 ˘ V̄2` ` Ū1´Ū2 ˘ 1rˆm`Ū2 ` V̄1´V̄2 ˘ `1nˆr ` V̄1´V̄2 ˘ ˙
(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
“ ´4E „ Tr V̄1 T Ū1 T Ū1V̄1  “ ´4rmnσ4

heading: E.3 OTHER ALGEBRAIC FACTS
text: Fact 9. For any fixed i, j the entries of X̂, X̂1 and X̂2 are zero mean.
Proof. We have
X̂pλq ´X “ ` λU1 ` p1´ λqU2 ˘` λV1 ` p1´ λqV2 ˘ ´U˚V˚
X̂1pλq “ ` U1 ´U2 ˘` λV1 ` p1´ λqV2 ˘ ` ` λU1 ` p1´ λqU2 ˘` V1 ´V2 ˘
X̂2pλq “ ` U1 ´U2 ˘` V1 ´V2 ˘
The fact that U1 and U2 are iid implies that pU1 ´U2q has zero mean, and the similar holds for V1 and V2. This implies that all terms of X̂1 and X̂2 are zero-mean. Using the fact that U1,U2 and U˚ are iid implies that
E „ ` λU1 ` p1´ λqU2 ˘` λV1 ` p1´ λqV2 ˘  “ ErU˚V˚s
This, in turn, implies that ErX̂s “ 0. Fact 10. For U1 “ U˚ and V1 “ V˚, we have ErxW0,W2ys “ 2rmnσ4
Proof. We can write ErxW0,W2ys as
ETr „ˆ
VT2 U T 2 ´ pV˚qT pU˚qT
˙ˆ
` U˚ ´U2 ˘` V˚ ´V2 ˘
˙
Again, we want to add and subtract the matrix means 1nˆr, 1rˆm to get
ETr „ˆ “ V̄2 T Ū2 T`V̄2 T 1Tnˆr`1TrˆmŪ2 T`1Trˆm1Tnˆr ‰ ´ “ V̄˚ T Ū˚ T`V̄˚T 1Tnˆr`1TrˆmŪ˚ T`1Trˆm1Tnˆr ‰ ˙
(19)
ˆ ˆ ` Ū˚ ´ Ū2 ˘` V̄˚ ´ V̄2 ˘ ˙
As before, we can remove terms which are linear in any centered variable. The only term that remain gives
ErxW0,W2ys “ ETr „ V̄2 T Ū2 T Ū2V̄2  ` ETr „ V̄˚ T Ū˚ T Ū˚V̄˚  “ 2rmnσ4

Review summaries:
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.

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.