Title: STAR-CONVEXITY IN NON-NEGATIVE MATRIX FAC-TORIZATION

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.

1. INTRODUCTION:

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 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 x a , x b and the global minimizer x ˚. We consider a model of NMF with a planted solution, and as shown in b) the loss is typically convex on straight paths between points x a and a planted solution x ˚. Additionally, as illustrated in c), the loss is typically convex on straight paths between points x a and x b . 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.

2. NMF AND STAR-CONVEXITY:

The aim of NMF is to decompose some large measurement matrix X P R nˆm into two non-negative matrices U P R nˆr `and V P R rˆm `such that X « UV. The canonical formulation of NMF is min

U,Vě0

pU, Vq, where pU, Vq "

1 2 }UV ´X} 2 F (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 1pi,jq be an indicator variable that is 1 if entry pi, jq is "observed" and 0 otherwise. The loss function is then min

EQUATION

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 : R n Ñ R is star-convex towards x ˚if for all λ P r0, 1s and x P R n , we have f `λx `p1 ´λq x ˚˘ď λf pxq `p1 ´λqf px ˚q.

Figure 2 : The function p|x| p |y| p q 1{p is an example of a starconvex function for 0 ă p ă 1. It is non-convex in general, but convex towards p0, 0q.

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.

3. PROVING TYPICAL-CASE STAR-CONVEXITY:

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 ˚˘ď λf pxq `p1 ´λqf px ˚q holds not for all x, but for random x with high probability. This is in fact the best achievable, an NMF instance with u 1 " 1, u ˚" 0 and v 1 " 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 R nˆ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 U 1 , V 1 , U 2 , V 2 , U ˚, V

˚be sampled according to Assumption 1. Then there exists positive constants c 1 , c 2 , such that with probability ě 1 ´c1 expp´c 2 n 1{3 q, the loss function pU, Vq in equation 1 is convex on the straight line pU 1 , V 1 q Ñ pU 2 , V 2 q. The same holds along the line pU 1 , V 1 q Ñ pU ˚, V ˚q. It also holds if any entry pi, jq is observed independently with constant probability p, but with probability ě 1 ´c1 expp´c 2 r 1{3 q.

3.1. PROOF STRATEGY:

Let us parametrize the NMF solution one gets along the line pU 2 , V 2 q Ñ pU 1 , V 1 q as Xpλq " ˆλU 1 `p1 ´λqU 2 ˙ˆλV 1 `p1 ´λqV 2

Ṗroving:

Theorem 1 amounts to showing that the loss function pλq " 1 2 } Xpλ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 U 1 , U 2 , U ˚, V 1 , V 2 , 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 " ax 2 `bx `c we have ppxq " 1 a "`a

x `b 2 ˘2 ``ac ´b2 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}W 2 } 2 F `}W 1 } 2 F `2xW 0 , W 2 y ˘ě 3 `xW 1 , W 2 y ˘2 (3) Where the matrices W 0 , W 1 , W 2 are given as W 0 " U 2 V 2 ´U˚V˚, W 1 " `U1 ´U2 ˘V2 Ù2 `V1 ´V2 ˘, W 2 " `U1 ´U2 ˘`V 1 ´V2 ˘.

By slight abuse of notation, we have used xA, By to denote TrpAB T q for matrices A, B of the same shape. By exchanging terms in equation 3 by their means one gets

2p4rmnσ 4 q `6rmnσ 4 `4rmnµ 2 var σ 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σ 4 q 2 , we see that the LHS has 64 such terms while the RHS has only 48. Thus, if all matrices W 0 , W 1 and W 2 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 W 2 " `U1 ´U2 ˘`V 1 ´V2 ˘. Given that all matrices are iid we can center the variables such that

W 2 " `U1 ´U2 ˘`V 1 ´V2 ˘" `Ū 1 Ú2 ˘`V 1 ´V 2 ˘

, where the bar denotes the centered matrices. The term }W 2 } 2 F can then be written as

Tr `V 1 ´V 2 ˘T `Ū 1 ´Ū 2 ˘T `Ū 1 ´Ū 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. 5) where c 3 , c 4 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 n 1{3 instead of n, see Appendix D.

P `ˇ} W 2 } 2 F ´E" }W 2 } 2 F ‰ˇˇą t r n 2 ˘ď c 3 exp `´c 4 minpt 2 , t 1{2 q n ˘(

Proof sketch Given that E " }W 2 } 2 F " 4rmnσ 4 , equation 5 says that the probability that the term deviates from its mean by a relative factor is less than c 3 exp `´c 5 2 n ˘for some small . By applying similar arguments to terms xW 0 , W 2 y and xW 1 , W 2 y, one can show that the probability that they will deviate by a relative factor is less than c 6 expp´c 7

2 n 1{3 q. A problematic term is }W 1 } 2 F which contains a term of the type Tr `V 1 ´V 2 ˘T µ T 1 µ 1 `V 1

´V 2 ˘which has weak concentration properties. Matrices of type A T A 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 c 1 expp´c 8 2 n 1{3 q for positive constants c 1 , c 8 . Now, set " 0.01 If neither variable deviates by a factor of more than 0.01, then equation 10 still holds since 0.99 2 ˚64 ě 1.01 2 ˚48. Thus, inequality is violated with probability at most c 1 exp `´c 2 n 1{3 ˘for positive c 1 , c 2 . 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. (Li et al., 2001) . satellite p162, 94249, 4q (Erichson et al., 2018) .

Proof sketch for unobserved data If the entries in equation 2 are "observed" independently with probability p, for fixed matrices

U 1 , U 2 , U ˚, V 1 , V 2 , V ˚such that Theorem 1 hold, we have Er 2 pλqs " E " ÿ ij 1pi,jq ˆX 1 2 ij `X 2 ij p Xij ´Xij q ˙ " p ÿ ij ˆX 1 2 ij `X 2 ij p Xij ´Xij q ˙ě 0

Thus, the expectation of 2 pλq is convex. To show that it is convex with high probability, one first observes that with high probability, no entry pi, jq in 2 pλq is particularly large. Assuming this holds via union bound, for fix matrices U 1 , U 2 , U ˚, V 1 , V 2 , V ˚with elements that are "observed" independently with probability p, one gets that 2 pλq 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 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 < l a t e x i t s h a 1 _ b a s e 6 4 = " / J I 5 i y n The loss surface of NMF along the straight line from a random point w 0 to the local optima w ˚found via gradient descent from an independent starting point. We overlap 5 independent lines, zoom in for detail. For all datasets, this loss surface is convex, which is in line with what one would expect from Theorem 1. 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.

v N W O E K Z j L q 6 u j H W h d s H w = " > A A A B 7 n i c b V D L S s N A F L 2 p r 1 p f V Z d u B o v g q i Q i 1 G X R j c s K 9 g F t K J P J p B 0 6 m Y S Z G 6 G E f o Q b F 4 q 4 9 X v c + T d O 2 y y 0 9 c D A 4 Z x z m X t P k E p h 0 H W / n d L G 5 t b 2 T n m 3 s r d / c H h U P T 7 p m C T T j L d Z I h P d C 6 j h U i j e R o G S 9 1 L N a R x I 3 g 0 m d 3 O / + 8 S 1 E Y l 6 x G n K / Z i O l I g E o 2 i l 7 k D a a E i H 1 Z p b d x c g 6 8 Q r S A 0 K t I b V r 0 G Y s C z m C p m k x v Q 9 N 0 U / p x o F k 3 x W G W S G p 5 R N 6 I j 3 L V U 0 5 s b P F + v O y I V V Q h I l 2 j 6 F Z K H + n s h p b M w 0 D m w y p j g 2 q 9 5 c / M / r Z x j d + L l Q a Y Z c s e V H U S Y J J m R + O w m F 5 g z l 1 B L K t L C 7 E j a m m j K 0 D V V s C d 7 q y e u k c 1 X 3 3 L r 3 c F 1 r 3 h Z 1 l O E M z u E S P G h A E + 6 h B W 1 g M I F n e I U 3 J 3 V e n H f n Y x k t O c X M K f y B 8 / k D P M W P f Q = = < / l a t e x i t > < l a t e x i t s h a 1 _ b a s e 6 4 = " / J I 5 i y n v N W O E K Z j L q 6 u j H W h d s H w = " > A A A B 7 n i c b V D L S s N A F L 2 p r 1 p f V Z d u B o v g q i Q i 1 G X R j c s K 9 g F t K J P J p B 0 6 m Y S Z G 6 G E f o Q b F 4 q 4 9 X v c + T d O 2 y y 0 9 c D A 4 Z x z m X t P k E p h 0 H W / n d L G 5 t b 2 T n m 3 s r d / c H h U P T 7 p m C T T j L d Z I h P d C 6 j h U i j e R o G S 9 1 L N a R x I 3 g 0 m d 3 O / + 8 S 1 E Y l 6 x G n K / Z i O l I g E o 2 i l 7 k D a a E i H 1 Z p b d x c g 6 8 Q r S A 0 K t I b V r 0 G Y s C z m C p m k x v Q 9 N 0 U / p x o F k 3 x W G W S G p 5 R N 6 I j 3 L V U 0 5 s b P F + v O y I V V Q h I l 2 j 6 F Z K H + n s h p b M w 0 D m w y p j g 2 q 9 5 c / M / r Z x j d + L l Q a Y Z c s e V H U S Y J J m R + O w m F 5 g z l 1 B L K t L C 7 E j a m m j K 0 D V V s C d 7 q y e u k c 1 X 3 3 L r 3 c F 1 r 3 h Z 1 l O E M z u E S P G h A E + 6 h B W 1 g M I F n e I U 3 J 3 V e n H f n Y x k t O c X M K f y B 8 / k D P M W P f Q = = < / l a t e x i t > < l a t e x i t s h a 1 _ b a s e 6 4 = " / J I 5 i y n v N W O E K Z j L q 6 u j H W h d s H w = " > A A A B 7 n i c b V D L S s N A F L 2 p r 1 p f V Z d u B o v g q i Q i 1 G X R j c s K 9 g F t K J P J p B 0 6 m Y S Z G 6 G E f o Q b F 4 q 4 9 X v c + T d O 2 y y 0 9 c D A 4 Z x z m X t P k E p h 0 H W / n d L G 5 t b 2 T n m 3 s r d / c H h U P T 7 p m C T T j L d Z I h P d C 6 j h U i j e R o G S 9 1 L N a R x I 3 g 0 m d 3 O / + 8 S 1 E Y l 6 x G n K / Z i O l I g E o 2 i l 7 k D a a E i H 1 Z p b d x c g 6 8 Q r S A 0 K t I b V r 0 G Y s C z m C p m k x v Q 9 N 0 U / p x o F k 3 x W G W S G p 5 R N 6 I j 3 L V U 0 5 s b P F + v O y I V V Q h I l 2 j 6 F Z K H + n s h p b M w 0 D m w y p j g 2 q 9 5 c / M / r Z x j d + L l Q a Y Z c s e V H U S Y J J m R + O w m F 5 g z l 1 B L K t L C 7 E j a m m j K 0 D V V s C d 7 q y e u k c 1 X 3 3 L r 3 c F 1 r 3 h Z 1 l O E M z u E S P G h A E + 6 h B W 1 g M I F n e I U 3 J 3 V e n H f n Y x k t O c X M K f y B 8 / k D P M W P f Q = = < / l a t e x i t > < l a t e x i t s h a 1 _ b a s e 6 4 = " / J I 5 i y n v N W O E K Z j L q 6 u j H W h d s H w = " > A A A B 7 n i c b V D L S s N A F L 2 p r 1 p f V Z d u B o v g q i Q i 1 G X R j c s K 9 g F t K J P J p B 0 6 m Y S Z G 6 G E f o Q b F 4 q 4 9 X v c + T d O 2 y y 0 9 c D A 4 Z x z m X t P k E p h 0 H W / n d L G 5 t b 2 T n m 3 s r d / c H h U P T 7 p m C T T j L d Z I h P d C 6 j h U i j e R o G S 9 1 L N a R x I 3 g 0 m d 3 O / + 8 S 1 E Y l 6 x G n K / Z i O l I g E o 2 i l 7 k D a a E i H 1 Z p b d x c g 6 8 Q r S A 0 K t I b V r 0 G Y s C z m C p m k x v Q 9 N 0 U / p x o F k 3 x W G W S G p 5 R N 6 I j 3 L V U 0 5 s b P F + v O y I V V Q h I l 2 j 6 F Z K H + n s h p b M w 0 D m w y p j g 2 q 9 5 c / M / r Z x j d + L l Q a Y Z c s e V H U S Y J J m R + O w m F 5 g z l 1 B L K t L C 7 E j a m m j K 0 D V V s C d 7 q y e u k c 1 X 3 3 L r 3 c F 1 r 3 h Z 1 l O E M z u E S P G h A E + 6 h B W 1 g M I F n e I U 3 J 3 V e n H f n Y x k t O c X M K f y B 8 / k D P M W P f Q = = < / l a t e x i t > < l a t e x i t s h a 1 _ b a s e 6 4 = " / J I 5 i y n v N W O E K Z j L q 6 u j H W h d s H w = " > A A A B 7 n i c b V D L S s N A F L 2 p r 1 p f V Z d u B o v g q i Q i 1 G X R j c s K 9 g F t K J P J p B 0 6 m Y S Z G 6 G E f o Q b F 4 q 4 9 X v c + T d O 2 y y 0 9 c D A 4 Z x z m X t P k E p h 0 H W / n d L G 5 t b 2 T n m 3 s r d / c H h U P T 7 p m C T T j L d Z I h P d C 6 j h U i j e R o G S 9 1 L N a R x I 3 g 0 m d 3 O / + 8 S 1 E Y l 6 x G n K / Z i O l I g E o 2 i l 7 k D a a E i H 1 Z p b d x c g 6 8 Q r S A 0 K t I b V r 0 G Y s C z m C p m k x v Q 9 N 0 U / p x o F k 3 x W G W S G p 5 R N 6 I j 3 L V U 0 5 s b P F + v O y I V V Q h I l 2 j 6 F Z K H + n s h p b M w 0 D m w y p j g 2 q 9 5 c / M / r Z x j d + L l Q a Y Z c s e V H U S Y J J m R + O w m F 5 g z l 1 B L K t L C 7 E j a m m j K 0 D V V s C d 7 q y e u k c 1 X 3 3 L r 3 c F 1 r 3 h Z 1 l O E M z u E S P G h A E + 6 h B W 1 g M I F n e I U 3 J 3 V e n H f n Y x k t O c X M K f y B 8 / k D P M W P f Q = = < / l a t e x i t > < l a t e x i t s h a 1 _ b a s e 6 4 = " / J I 5 i y n v N W O E K Z j L q 6 u j H W h d s H w = " > A A A B 7 n i c b V D L S s N A F L 2 p r 1 p f V Z d u B o v g q i Q i 1 G X R j c s K 9 g F t K J P J p B 0 6 m Y S Z G 6 G E f o Q b F 4 q 4 9 X v c + T d O 2 y y 0 9 c D A 4 Z x z m X t P k E p h 0 H W / n d L G 5 t b 2 T n m 3 s r d / c H h U P T 7 p m C T T j L d Z I h P d C 6 j h U i j e R o G S 9 1 L N a R x I 3 g 0 m d 3 O / + 8 S 1 E Y l 6 x G n K / Z i O l I g E o 2 i l 7 k D a a E i H 1 Z p b d x c g 6 8 Q r S A 0 K t I b V r 0 G Y s C z m C p m k x v Q 9 N 0 U / p x o F k 3 x W G W S G p 5 R N 6 I j 3 L V U 0 5 s b P F + v O y I V V Q h I l 2 j 6 F Z K H + n s h p b M w 0 D m w y p j g 2 q 9 5 c / M / r Z x j d + L l Q a Y Z c s e V H U S Y J J m R + O w m F 5 g z l 1 B L K t L C 7 E j a m m j K 0 D V V s C d 7 q y e u k c 1 X 3 3 L r 3 c F 1 r 3 h Z 1 l O E M z u E S P G h A E + 6 h B W 1 g M I F n e I U 3 J 3 V e n H f n Y x k t O c X M K f y B 8 / k D P M W P f Q = = < / l a t e x i t > < l a t e x i t s h a 1 _ b a s e 6 4 = " / J I 5 i y n v N W O E K Z j L q 6 u j H W h d s H w = " > A A A B 7 n i c b V D L S s N A F L 2 p r 1 p f V Z d u B o v g q i Q i 1 G X R j c s K 9 g F t K J P J p B 0 6 m Y S Z G 6 G E f o Q b F 4 q 4 9 X v c + T d O 2 y y 0 9 c D A 4 Z x z m X t P k E p h 0 H W / n d L G 5 t b 2 T n m 3 s r d / c H h U P T 7 p m C T T j L d Z I h P d C 6 j h U i j e R o G S 9 1 L N a R x I 3 g 0 m d 3 O / + 8 S 1 E Y l 6 x G n K / Z i O l I g E o 2 i l 7 k D a a E i H 1 Z p b d x c g 6 8 Q r S A 0 K t I b V r 0 G Y s C z m C p m k x v Q 9 N 0 U / p x o F k 3 x W G W S G p 5 R N 6 I j 3 L V U 0 5 s b P F + v O y I V V Q h I l 2 j 6 F Z K H + n s h p b M w 0 D m w y p j g 2 q 9 5 c / M / r Z x j d + L l Q a Y Z c s e V H U S Y J J m R + O w m F 5 g z l 1 B L K t L C 7 E j a m m j K 0 D V V s C d 7 q y e u k c 1 X 3 3 L r 3 c F 1 r 3 h Z 1 l O E M z u E S P G h A E + 6 h B W 1 g M I F n e I U 3 J 3 V e n H f n Y x k t O c X M K f y B 8 / k D P M W P f Q = = < / l a t e x i t > < l a t e x i t s h a 1 _ b a s e 6 4 = " / J I 5 i y n v N W O E K Z j L q 6 u j H W h d s H w = " > A A A B 7 n i c b V D L S s N A F L 2 p r 1 p f V Z d u B o v g q i Q i 1 G X R j c s K 9 g F t K J P J p B 0 6 m Y S Z G 6 G E f o Q b F 4 q 4 9 X v c + T d O 2 y y 0 9 c D A 4 Z x z m X t P k E p h 0 H W / n d L G 5 t b 2 T n m 3 s r d / c H h U P T 7 p m C T T j L d Z I h P d C 6 j h U i j e R o G S 9 1 L N a R x I 3 g 0 m d 3 O / + 8 S 1 E Y l 6 x G n K / Z i O l I g E o 2 i l 7 k D a a E i H 1 Z p b d x c g 6 8 Q r S A 0 K t I b V r 0 G Y s C z m C p m k x v Q 9 N 0 U / p x o F k 3 x W G W S G p 5 R N 6 I j 3 L V U 0 5 s b P F + v O y I V V Q h I l 2 j 6 F Z K H + n s h p b M w 0 D m w y p j g 2 q 9 5 c / M / r Z x j d + L l Q a Y Z c s e V H U S Y J J m R + O w m F 5 g z l 1 B L K t L C 7 E j a m m j K 0 D V V s C d 7 q y e u k c 1 X 3 3 L r 3 c F 1 r 3 h Z 1 l O E M z u E S P G h A E + 6 h B W 1 g M I F n e I U 3 J 3 V e n H f n Y x k t O c X M K f y B 8 / k D P M W P f Q = = < / l a t e x i t > < l a t e x i t s h a 1 _ b a s e 6 4 = " / J I 5 i y n v N W O E K Z j L q 6 u j H W h d s H w = " > A A A B 7 n i c b V D L S s N A F L 2 p r 1 p f V Z d u B o v g q i Q i 1 G X R j c s K 9 g F t K J P J p B 0 6 m Y S Z G 6 G E f o Q b F 4 q 4 9 X v c + T d O 2 y y 0 9 c D A 4 Z x z m X t P k E p h 0 H W / n d L G 5 t b 2 T n m 3 s r d / c H h U P T 7 p m C T T j L d Z I h P d C 6 j h U i j e R o G S 9 1 L N a R x I 3 g 0 m d 3 O / + 8 S 1 E Y l 6 x G n K / Z i O l I g E o 2 i l 7 k D a a E i H 1 Z p b d x c g 6 8 Q r S A 0 K t I b V r 0 G Y s C z m C p m k x v Q 9 N 0 U / p x o F k 3 x W G W S G p 5 R N 6 I j 3 L V U 0 5 s b P F + v O y I V V Q h I l 2 j 6 F Z K H + n s h p b M w 0 D m w y p j g 2 q 9 5 c / M / r Z x j d + L l Q a Y Z c s e V H U S Y J J m R + O w m F 5 g z l 1 B L K t L C 7 E j a m m j K 0 D V V s C d 7 q y e u k c 1 X 3 3 L r 3 c F 1 r 3 h Z 1 l O E M z u E S P G h A E + 6 h B W 1 g M I F n e I U 3 J 3 V e n H f n Y x k t O c X M K f y B 8 / k D P M W P f Q = = < / l a t e x i t > < l a t e x i t s h a 1 _ b a s e 6 4 = " / J I 5 i y n v N W O E K Z j L q 6 u j H W h d s H w = " > A A A B 7 n i c b V D L S s N A F L 2 p r 1 p f V Z d u B o v g q i Q i 1 G X R j c s K 9 g F t K J P J p B 0 6 m Y S Z G 6 G E f o Q b F 4 q 4 9 X v c + T d O 2 y y 0 9 c D A 4 Z x z m X t P k E p h 0 H W / n d L G 5 t b 2 T n m 3 s r d / c H h U P T 7 p m C T T j L d Z I h P d C 6 j h U i j e R o G S 9 1 L N a R x I 3 g 0 m d 3 O / + 8 S 1 E Y l 6 x G n K / Z i O l I g E o 2 i l 7 k D a a E i H 1 Z p b d x c g 6 8 Q r S A 0 K t I b V r 0 G Y s C z m C p m k x v Q 9 N 0 U / p x o F k 3 x W G W S G p 5 R N 6 I j 3 L V U 0 5 s b P F + v O y I V V Q h I l 2 j 6 F Z K H + n s h p b M w 0 D m w y p j g 2 q 9 5 c / M / r Z x j d + L l Q a Y Z c s e V H U S Y J J m R + O w m F 5 g z l 1 B L K t L C 7 E j a m m j K 0 D V V s C d 7 q y e u k c 1 X 3 3 L r 3 c F 1 r 3 h Z 1 l O E M z u E S P G h A E + 6 h B W 1 g M I F n e I U 3 J 3 V e n H f n Y x k t O c X M K f y B 8 / k D P M W P f Q = = < / l a t e x i t > < l a t e x i t s h a 1 _ b a s e 6 4 = " / J I 5 i y n v N W O E K Z j L q 6 u j H W h d s H w = " > A A A B 7 n i c b V D L S s N A F L 2 p r 1 p f V Z d u B o v g q i Q i 1 G X R j c s K 9 g F t K J P J p B 0 6 m Y S Z G 6 G E f o Q b F 4 q 4 9 X v c + T d O 2 y y 0 9 c D A 4 Z x z m X t P k E p h 0 H W / n d L G 5 t b 2 T n m 3 s r d / c H h U P T 7 p m C T T j L d Z I h P d C 6 j h U i j e R o G S 9 1 L N a R x I 3 g 0 m d 3 O / + 8 S 1 E Y l 6 x G n K / Z i O l I g E o 2 i l 7 k D a a E i H 1 Z p b d x c g 6 8 Q r S A 0 K t I b V r 0 G Y s C z m C p m k x v Q 9 N 0 U / p x o F k 3 x W G W S G p 5 R N 6 I j 3 L V U 0 5 s b P F + v O y I V V Q h I l 2 j 6 F Z K H + n s h p b M w 0 D m w y p j g 2 q 9 5 c / M / r Z x j d + L l Q a Y Z c s e V H U S Y J J m R + O w m F 5 g z l 1 B L K t L C 7 E j a m m j K 0 D V V s C d 7 q y e u k c 1 X 3 3 L r 3 c F 1 r 3 h Z 1 l O E M z u E S P G h A E + 6 h B W 1 g M I F n e I U 3 J 3 V e n H f n Y x k t O c X M K f y B 8 / k D P M W P f Q = = < / l a t e x i t > < l a t e x i t s h a 1 _ b a s e 6 4 = " / J I 5 i y n v N W O E K Z j L q 6 u j H W h d s H w = " > A A A B 7 n i c b V D L S s N A F L 2 p r 1 p f V Z d u B o v g q i Q i 1 G X R j c s K 9 g F t K J P J p B 0 6 m Y S Z G 6 G E f o Q b F 4 q 4 9 X v c + T d O 2 y y 0 9 c D A 4 Z x z m X t P k E p h 0 H W / n d L G 5 t b 2 T n m 3 s r d / c H h U P T 7 p m C T T j L d Z I h P d C 6 j h U i j e R o G S 9 1 L N a R x I 3 g 0 m d 3 O / + 8 S 1 E Y l 6 x G n K / Z i O l I g E o 2 i l 7 k D a a E i H 1 Z p b d x c g 6 8 Q r S A 0 K t I b V r 0 G Y s C z m C p m k x v Q 9 N 0 U / p x o F k 3 x W G W S G p 5 R N 6 I j 3 L V U 0 5 s b P F + v O y I V V Q h I l 2 j 6 F Z K H + n s h p b M w 0 D m w y p j g 2 q 9 5 c / M / r Z x j d + L l Q a Y Z c s e V H U S Y J J m R + O w m F 5 g z l 1 B L K t L C 7 E j a m m j K 0 D V V s C d 7 q y e u k c 1 X 3 3 L r 3 c F 1 r 3 h Z 1 l O E M z u E S P G h A E + 6 h B W 1 g M I F n e I U 3 J 3 V e n H f n Y x k t O c X M K f y B 8 / k D P M W P f Q = = < / l a t e x i t > < l a t e x i t s h a 1 _ b a s e 6 4 = " / J I 5 i y n v N W O E K Z j L q 6 u j H W h d s H w = " > A A A B 7 n i c b V D L S s N A F L 2 p r 1 p f V Z d u B o v g q i Q i 1 G X R j c s K 9 g F t K J P J p B 0 6 m Y S Z G 6 G E f o Q b F 4 q 4 9 X v c + T d O 2 y y 0 9 c D A 4 Z x z m X t P k E p h 0 H W / n d L G 5 t b 2 T n m 3 s r d / c H h U P T 7 p m C T T j L d Z I h P d C 6 j h U i j e R o G S 9 1 L N a R x I 3 g 0 m d 3 O / + 8 S 1 E Y l 6 x G n K / Z i O l I g E o 2 i l 7 k D a a E i H 1 Z p b d x c g 6 8 Q r S A 0 K t I b V r 0 G Y s C z m C p m k x v Q 9 N 0 U / p x o F k 3 x W G W S G p 5 R N 6 I j 3 L V U 0 5 s b P F + v O y I V V Q h I l 2 j 6 F Z K H + n s h p b M w 0 D m w y p j g 2 q 9 5 c / M / r Z x j d + L l Q a Y Z c s e V H U S Y J J m R + O w m F 5 g z l 1 B L K t L C 7 E j a m m j K 0 D V V s C d 7 q y e u k c 1 X 3 3 L r 3 c F 1 r 3 h Z 1 l O E M z u E S P G h A E + 6 h B W 1 g M I F n e I U 3 J 3 V e n H f n Y x k t O c X M K f y B 8 / k D P M W P f Q = = < / l a t e x i t > < l a t e x i t s h a 1 _ b a s e 6 4 = " / J I 5 i y n v N W O E K Z j L q 6 u j H W h d s H w = " > A A A B 7 n i c b V D L S s N A F L 2 p r 1 p f V Z d u B o v g q i Q i 1 G X R j c s K 9 g F t K J P J p B 0 6 m Y S Z G 6 G E f o Q b F 4 q 4 9 X v c + T d O 2 y y 0 9 c D A 4 Z x z m X t P k E p h 0 H W / n d L G 5 t b 2 T n m 3 s r d / c H h U P T 7 p m C T T j L d Z I h P d C 6 j h U i j e R o G S 9 1 L N a R x I 3 g 0 m d 3 O / + 8 S 1 E Y l 6 x G n K / Z i O l I g E o 2 i l 7 k D a a E i H 1 Z p b d x c g 6 8 Q r S A 0 K t I b V r 0 G Y s C z m C p m k x v Q 9 N 0 U / p x o F k 3 x W G W S G p 5 R N 6 I j 3 L V U 0 5 s b P F + v O y I V V Q h I l 2 j 6 F Z K H + n s h p b M w 0 D m w y p j g 2 q 9 5 c / M / r Z x j d + L l Q a Y Z c s e V H U S Y J J m R + O w m F 5 g z l 1 B L K t L C 7 E j a m m j K 0 D V V s C d 7 q y e u k c 1 X 3 3 L r 3 c F 1 r 3 h Z 1 l O E M z u E S P G h A E + 6 h B W 1 g M I F n e I U 3 J 3 V e n H f n Y x k t O c X M K f y B 8 / k D P M W P f Q = = < / l a t e x i t > < l a t e x i t s h a 1 _ b a s e 6 4 = " / J I 5 i y n v N W O E K Z j L q 6 u j H W h d s H w = " > A A A B 7 n i c b V D L S s N A F L 2 p r 1 p f V Z d u B o v g q i Q i 1 G X R j c s K 9 g F t K J P J p B 0 6 m Y S Z G 6 G E f o Q b F 4 q 4 9 X v c + T d O 2 y y 0 9 c D A 4 Z x z m X t P k E p h 0 H W / n d L G 5 t b 2 T n m 3 s r d / c H h U P T 7 p m C T T j L d Z I h P d C 6 j h U i j e R o G S 9 1 L N a R x I 3 g 0 m d 3 O / + 8 S 1 E Y l 6 x G n K / Z i O l I g E o 2 i l 7 k D a a E i H 1 Z p b d x c g 6 8 Q r S A 0 K t I b V r 0 G Y s C z m C p m k x v Q 9 N 0 U / p x o F k 3 x W G W S G p 5 R N 6 I j 3 L V U 0 5 s b P F + v O y I V V Q h I l 2 j 6 F Z K H + n s h p b M w 0 D m w y p j g 2 q 9 5 c / M / r Z x j d + L l Q a Y Z c s e V H U S Y J J m R + O w m F 5 g z l 1 B L K t L C 7 E j a m m j K 0 D V V s C d 7 q y e u k c 1 X 3 3 L r 3 c F 1 r 3 h Z 1 l O E M z u E S P G h A E + 6 h B W 1 g M I F n e I U 3 J 3 V e n H f n Y x k t O c X M K f y B 8 / k D P M W P f Q = = < / l a t e x i t > < l a t e x i t s h a 1 _ b a s e 6 4 = " / J I 5 i y n v N W O E K Z j L q 6 u j H W h d s H w = " > A A A B 7 n i c b V D L S s N A F L 2 p r 1 p f V Z d u B o v g q i Q i 1 G X R j c s K 9 g F t K J P J p B 0 6 m Y S Z G 6 G E f o Q b F 4 q 4 9 X v c + T d O 2 y y 0 9 c D A 4 Z x z m X t P k E p h 0 H W / n d L G 5 t b 2 T n m 3 s r d / c H h U P T 7 p m C T T j L d Z I h P d C 6 j h U i j e R o G S 9 1 L N a R x I 3 g 0 m d 3 O / + 8 S 1 E Y l 6 x G n K / Z i O l I g E o 2 i l 7 k D a a E i H 1 Z p b d x c g 6 8 Q r S A 0 K t I b V r 0 G Y s C z m C p m k x v Q 9 N 0 U / p x o F k 3 x W G W S G p 5 R N 6 I j 3 L V U 0 5 s b P F + v O y I V V Q h I l 2 j 6 F Z K H + n s h p b M w 0 D m w y p j g 2 q 9 5 c / M / r Z x j d + L l Q a Y Z c s e V H U S Y J J m R + O w m F 5 g z l 1 B L K t L C 7 E j a m m j K 0 D V V s C d 7 q y e u k c 1 X 3 3 L r 3 c F 1 r 3 h Z 1 l O E M z u E S P G h A E + 6 h B W 1 g M I F n e I U 3 J 3 V e n H f n Y x k t O c X M K f y B 8 / k D P M W P f Q = = <

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.

4.2. ABLATION EXPERIMENTS:

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 x 0 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. For all datasets, the relative deviations decrease with more samples, suggesting that the (positive) curvature become increasingly concentreated around its mean for larger matrices. Figure 6 : aq and bq show the cosine similarity between the negative gradient ´∇ pU, Vq and the straight line pU 0 , V 0 q Ñ pU ˚, V ˚q, 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. cq and dq illustrate how the curvature equation 6 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 5 iterations.

4.3. IMPLICATIONS FOR NEURAL NETWORKS:

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.

U ⇤:

< l a t e x i t s h a 1 _ b a s e 6 4 = " b a I l G q P A C 9 r u 4 6 5 B V G E e P n K L 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 , λ 2 s 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.

A P E = " > A A A B 8 3 i c b V B N S w M x F H z x s 9 a v q k c v w S K I h 7 I r g h 6 L X j x W c N t C d y 3 Z N N u G Z r N L k h X K 0 r / h x Y M i X v 0 z 3 v w 3 Z t s 9 a O t A Y J h 5 j z e Z M B V c G 8 f 5 R i u r a + s b m 5 W t 6 v b O 7 t 5 + 7 e C w r Z N M U e b R R C S q G x L N B J f M M 9 w I 1 k 0 V I 3 E o W C c c 3 x Z + 5 4 k p z R P 5 Y C Y p C 2 I y l D z i l B g r + X 5 M z C i M c m / 6 e N 6 v 1 Z 2 G M w N e J m 5 J 6 l C i 1 a 9 9 + Y O E Z j G T h g q i d c 9 1 U h P k R B l O B Z t W / U y z l N A x G b K e p Z L E T A f 5 L P M U n 1 p l g K N E 2 S c N n q m / N 3 I S a z 2 J Q z t Z Z N S L X i H + 5 / U y E 1 0 H O Z d p Z p i k 8 0 N R J r B J c F E A H n D F q B E T S w h V 3 G b F d E Q U o c b W V L U l u I t f X i b t i 4 b r N N z 7 y 3 r z p q y j A s d w A m f g w h U 0 4 Q 5 a 4 A G F F J 7 h F d 5 Q h l 7 Q O / q Y j 6 6 g c u c I / g B 9 / g D o u 5 G V < / l a t e x i t > < l a t e x i t s h a 1 _ b a s e 6 4 = " b a I l G q P A C 9 r u 4 6 5 B V G E e P n K L A P E = " > A A A B 8 3 i c b V B N S w M x F H z x s 9 a v q k c v w S K I h 7 I r g h 6 L X j x W c N t C d y 3 Z N N u G Z r N L k h X K 0 r / h x Y M i X v 0 z 3 v w 3 Z t s 9 a O t A Y J h 5 j z e Z M B V c G 8 f 5 R i u r a + s b m 5 W t 6 v b O 7 t 5 + 7 e C w r Z N M U e b R R C S q G x L N B J f M M 9 w I 1 k 0 V I 3 E o W C c c 3 x Z + 5 4 k p z R P 5 Y C Y p C 2 I y l D z i l B g r + X 5 M z C i M c m / 6 e N 6 v 1 Z 2 G M w N e J m 5 J 6 l C i 1 a 9 9 + Y O E Z j G T h g q i d c 9 1 U h P k R B l O B Z t W / U y z l N A x G b K e p Z L E T A f 5 L P M U n 1 p l g K N E 2 S c N n q m / N 3 I S a z 2 J Q z t Z Z N S L X i H + 5 / U y E 1 0 H O Z d p Z p i k 8 0 N R J r B J c F E A H n D F q B E T S w h V 3 G b F d E Q U o c b W V L U l u I t f X i b t i 4 b r N N z 7 y 3 r z p q y j A s d w A m f g w h U 0 4 Q 5 a 4 A G F F J 7 h F d 5 Q h l 7 Q O / q Y j 6 6 g c u c I / g B 9 / g D o u 5 G V < / l a t e x i t > < l a t e x i t s h a 1 _ b a s e 6 4 = " b a I l G q P A C 9 r u 4 6 5 B V G E e P n K L A P E = " > A A A B 8 3 i c b V B N S w M x F H z x s 9 a v q k c v w S K I h 7 I r g h 6 L X j x W c N t C d y 3 Z N N u G Z r N L k h X K 0 r / h x Y M i X v 0 z 3 v w 3 Z t s 9 a O t A Y J h 5 j z e Z M B V c G 8 f 5 R i u r a + s b m 5 W t 6 v b O 7 t 5 + 7 e C w r Z N M U e b R R C S q G x L N B J f M M 9 w I 1 k 0 V I 3 E o W C c c 3 x Z + 5 4 k p z R P 5 Y C Y p C 2 I y l D z i l B g r + X 5 M z C i M c m / 6 e N 6 v 1 Z 2 G M w N e J m 5 J 6 l C i 1 a 9 9 + Y O E Z j G T h g q i d c 9 1 U h P k R B l O B Z t W / U y z l N A x G b K e p Z L E T A f 5 L P M U n 1 p l g K N E 2 S c N n q m / N 3 I S a z 2 J Q z t Z Z N S L X i H + 5 / U y E 1 0 H O Z d p Z p i k 8 0 N R J r B J c F E A H n D F q B E T S w h V 3 G b F d E Q U o c b W V L U l u I t f X i b t i 4 b r N N z 7 y 3 r z p q y j A s d w A m f g w h U 0 4 Q 5 a 4 A G F F J 7 h F d 5 Q h l 7 Q O / q Y j 6 6 g c u c I / g B 9 / g D o u 5 G V < / l a t e x i t > < l a t e x i t s h a 1 _ b a s e 6 4 = " b a I l G q P A C 9 r u 4 6 5 B V G E e P n K L A P E = " > A A A B 8 3 i c b V B N S w M x F H z x s 9 a v q k c v w S K I h 7 I r g h 6 L X j x W c N t C d y 3 Z N N u G Z r N L k h X K 0 r / h x Y M i X v 0 z 3 v w 3 Z t s 9 a O t A Y J h 5 j z e Z M B V c G 8 f 5 R i u r a + s b m 5 W t 6 v b O 7 t 5 + 7 e C w r Z N M U e b R R C S q G x L N B J f M M 9 w I 1 k 0 V I 3 E o W C c c 3 x Z + 5 4 k p z R P 5 Y C Y p C 2 I y l D z i l B g r + X 5 M z C i M c m / 6 e N 6 v 1 Z 2 G M w N e J m 5 J 6 l C i 1 a 9 9 + Y O E Z j G T h g q i d c 9 1 U h P k R B l O B Z t W / U y z l N A x G b K e p Z L E T A f 5 L P M U n 1 p l g K N E 2 S c N n q m / N 3 I S a z 2 J Q z t Z Z N S L X i H + 5 / U y E 1 0 H O Z d p Z p i k 8 0 N R J r B J c F E A H n D F q B E T S w h V 3 G b F d E Q U o c b W V L U l u I t f X i b t i 4 b r N N z 7 y 3 r z p q y j A s d w A m f g w h U 0 4 Q 5 a 4 A G F F J 7 h F d 5 Q h l 7 Q O / q Y j 6 6 g c u c I / g B 9 / g D o u 5 G V < / l a t e x i t > log i max < l a t e x i t s h a 1 _ b a s e 6 4 = " M 4 M f / l 4 l Q u t x f x P 2 N b H D L f N j V h E = " > A A A C D H i c b V D L S g M x F M 3 4 r P V V d e k m W A R X Z U Y E X R b d u K x g H 9 A p 5 U 6 a m Y Y m k y H J i G W Y D 3 D j r 7 h x o Y h b P 8 C d f 2 P a j q C t B w K H c 8 7 l 5 p 4 g 4 U w b 1 / 1 y l p Z X V t f W S x v l z a 3 t n d 3 K 3 n 5 L y 1 Q R 2 i S S S 9 U J Q F P O Y t o 0 z H D a S R Q F E X D a D k Z X E 7 9 9 R 5 V m M r 4 1 4 4 T 2 B E Q x C x k B Y 6 V + p e p z G W E / V E A y X 7 N I Q J / l P y z z B d z n u U 2 5 N X c K v E i 8 g l R R g U a / 8 u k P J E k F j Q 3 h o H X X c x P T y 0 A Z R j j N y 3 6 q a Q J k B B H t W h q D o L q X T Y / J 8 b F V B j i U y r 7 Y 4 K n 6 e y I D o f V Y B D Y p w A z 1 v D c R / / O 6 q Q k v e h m L k 9 T Q m M w W h S n H R u J J M 3 j A F C W G j y 0 B o p j 9 K y Z D s M U Y 2 1 / Z l u D N n 7 x I W q c 1 z 6 1 5 N 2 f V + m V R R w k d o i N 0 g j x 0 j u r o G j V Q E x H 0 g J 7 Q C 3 p 1 H p 1 n 5 8 1 5 n 0 W X n G L m A P 2 B 8 / E N G 9 W c S g = = < / l a t e x i t > < l a t e x i t s h a 1 _ b a s e 6 4 = " M 4 M f / l 4 l Q u t x f x P 2 N b H D L f N j V h E = " > A A A C D H i c b V D L S g M x F M 3 4 r P V V d e k m W A R X Z U Y E X R b d u K x g H 9 A p 5 U 6 a m Y Y m k y H J i G W Y D 3 D j r 7 h x o Y h b P 8 C d f 2 P a j q C t B w K H c 8 7 l 5 p 4 g 4 U w b 1 / 1 y l p Z X V t f W S x v l z a 3 t n d 3 K 3 n 5 L y 1 Q R 2 i S S S 9 U J Q F P O Y t o 0 z H D a S R Q F E X D a D k Z X E 7 9 9 R 5 V m M r 4 1 4 4 T 2 B E Q x C x k B Y 6 V + p e p z G W E / V E A y X 7 N I Q J / l P y z z B d z n u U 2 5 N X c K v E i 8 g l R R g U a / 8 u k P J E k F j Q 3 h o H X X c x P T y 0 A Z R j j N y 3 6 q a Q J k B B H t W h q D o L q X T Y / J 8 b F V B j i U y r 7 Y 4 K n 6 e y I D o f V Y B D Y p w A z 1 v D c R / / O 6 q Q k v e h m L k 9 T Q m M w W h S n H R u J J M 3 j A F C W G j y 0 B o p j 9 K y Z D s M U Y 2 1 / Z l u D N n 7 x I W q c 1 z 6 1 5 N 2 f V + m V R R w k d o i N 0 g j x 0 j u r o G j V Q E x H 0 g J 7 Q C 3 p 1 H p 1 n 5 8 1 5 n 0 W X n G L m A P 2 B 8 / E N G 9 W c S g = = < / l a t e x i t > < l a t e x i t s h a 1 _ b a s e 6 4 = " M 4 M f / l 4 l Q u t x f x P 2 N b H D L f N j V h E = " > A A A C D H i c b V D L S g M x F M 3 4 r P V V d e k m W A R X Z U Y E X R b d u K x g H 9 A p 5 U 6 a m Y Y m k y H J i G W Y D 3 D j r 7 h x o Y h b P 8 C d f 2 P a j q C t B w K H c 8 7 l 5 p 4 g 4 U w b 1 / 1 y l p Z X V t f W S x v l z a 3 t n d 3 K 3 n 5 L y 1 Q R 2 i S S S 9 U J Q F P O Y t o 0 z H D a S R Q F E X D a D k Z X E 7 9 9 R 5 V m M r 4 1 4 4 T 2 B E Q x C x k B Y 6 V + p e p z G W E / V E A y X 7 N I Q J / l P y z z B d z n u U 2 5 N X c K v E i 8 g l R R g U a / 8 u k P J E k F j Q 3 h o H X X c x P T y 0 A Z R j j N y 3 6 q a Q J k B B H t W h q D o L q X T Y / J 8 b F V B j i U y r 7 Y 4 K n 6 e y I D o f V Y B D Y p w A z 1 v D c R / / O 6 q Q k v e h m L k 9 T Q m M w W h S n H R u J J M 3 j A F C W G j y 0 B o p j 9 K y Z D s M U Y 2 1 / Z l u D N n 7 x I W q c 1 z 6 1 5 N 2 f V + m V R R w k d o i N 0 g j x 0 j u r o G j V Q E x H 0 g J 7 Q C 3 p 1 H p 1 n 5 8 1 5 n 0 W X n G L m A P 2 B 8 / E N G 9 W c S g = = < / l a t e x i t > < l a t e x i t s h a 1 _ b a s e 6 4 = " M 4 M f / l 4 l Q u t x f x P 2 N b H D L f N j V h E = " > A A A C D H i c b V D L S g M x F M 3 4 r P V V d e k m W A R X Z U Y E X R b d u K x g H 9 A p 5 U 6 a m Y Y m k y H J i G W Y D 3 D j r 7 h x o Y h b P 8 C d f 2 P a j q C t B w K H c 8 7 l 5 p 4 g 4 U w b 1 / 1 y l p Z X V t f W S x v l z a 3 t n d 3 K 3 n 5 L y 1 Q R 2 i S S S 9 U J Q F P O Y t o 0 z H D a S R Q F E X D a D k Z X E 7 9 9 R 5 V m M r 4 1 4 4 T 2 B E Q x C x k B Y 6 V + p e p z G W E / V E A y X 7 N I Q J / l P y z z B d z n u U 2 5 N X c K v E i 8 g l R R g U a / 8 u k P J E k F j Q 3 h o H X X c x P T y 0 A Z R j j N y 3 6 q a Q J k B B H t W h q D o L q X T Y / J 8 b F V B j i U y r 7 Y 4 K n 6 e y I D o f V Y B D Y p w A z 1 v D c R / / O 6 q Q k v e h m L k 9 T Q m M w W h S n H R u J J M 3 j A F C W G j y 0 B o p j 9 K y Z D s M U Y 2 1 / Z l u D N n 7 x I W q c 1 z 6 1 5 N 2 f V + m V R R w k d o i N 0 g j x 0 j u r o G j V Q E x H 0 g J 7 Q C 3 p 1 H p 1 n 5 8 1 5 n 0 W X n G L m A P 2 B 8 / E N G 9 W c S g = = < / l a t e x i t >

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

5. RELATED WORK:

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

6. CONCLUSIONS:

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.

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

B DNN PARAMETERS:

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) . 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 6 , for various datasets. Note that it is always positive, and thus that the function satisfies star-convexity. Note the small shaded regions, which represents the 95 % confidence computed over 5 repetitions. Figure 10 : The cosine similarity between the negative gradient ´∇ pU, Vq and the straight line pU 0 , V 0 q Ñ pU ˚, V ˚q, during training as in Figure 6 . Note the small shaded regions, which represents the 95 % confidence computed over 5 repetitions. 

D.2 NOTATION AND THE MAIN INEQUALITY:

The proof will involve various constants c 0 , c 1 , c 2 that do not depend on n. For convenience, we will let exact values be context dependent and will reuse the symbols c 0 , c 1 , c 2 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 U 1 , U 2 , U ˚be n-by-r matrices and V 1 , V 2 , V ˚r-by-m matrices sampled as per Assumption 1. Without loss of generality, we assume m " nc m where 0 ă c m ď 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 Ū1 , V1 and so on, and the mean matrix of U and V resp as 1 nˆr , 1 rˆm . Then U " Ū `1nˆr . By slight abuse of notation, we will use the convention xX, Yy " Tr `XY T ˘for matrices X, Y of the same shape. The loss function we wish to minimize, subject to non-negativity constraints, is By expanding 2 pλq in a McLaurin series around 0, we see that proving non-negativity of 2 pλq can be done by proving 2 p0q 2 4 p0q ě 3 p0q 2 . Thus, proving Theorem 3 then amounts to showing that

EQUATION

D.3 PROVING THE INEQUALITY BETWEEN RANDOM POINTS Theorem 2. Let pU 1 , V 1 q, pU 2 , V 2 q 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 pU 1 , V 1 q and pU 2 , V 2 q with probability ě 1 ´c1 exp `´c 2 n 1{3 ˘for positive constants c 1 , c 2 .

Proof. As per section D.2, we only need to prove that equation 9 holds with probability ě 1 ć1 exp `´c 2 n 1{3 ˘. Let us exhange all terms in equation 9 with their means, which are given in Facts 7, 5, 6 and 8

EQUATION

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 }W 2 } 2 F . As per equation 14, }W 2 } 2 F 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 }W 2 } 2 F deviates from its mean by a factor p1 ` q is no more than c 1 expp´c 2 2 n ˘.

Now, consider the random variable }W 1 } 2 F . As in the proof of Fact 7, }W 1 } 2 F 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 c 1 expp´c 2 2 n ˘. Consider the expression equation 16. Clearly the expressions

1 T rˆm `Ū 1 ´Ū 2 ˘T `Ū 1 ´Ū 2 ˘1rˆm and `V 1 ´V 2 ˘T 1 T nˆr 1 nˆ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 rn 2 σ 4 . Now, consider the random variable xW 0 , W 2 y. As per equation 19, the variable xW 0 , W 2 y 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 c 1 expp´c 2 2 n ˘. The second one is a sum of the type 1X 1 X 2 X 3 modulo permutations, under which the trace is invariant. We can thus apply Fact 2 which bounds the probability for deviations of size xW 0 , W 2 y by c 1 exp `´ c 2 n 1{3 ˘.

At last, consider the random variable xW 1 , W 2 y. By equation 18 can, just like xW 0 , W 2 y, be written as the sum of a polynomial in centered random matrices, and sums of variables of the type 1X 1 X 2 X 3 modulo permutations. We can thus apply the same argument as for xW 0 , W 2 y to bounds the probability for deviations of relative size by c 1 exp `´ c 2 n 1{3 ˘.

We can now apply union bound on the variables }W 1 }2 F , }W 2 } 2 F , xW 0 , W 2 y and xW 1 , W 2 y, modulu term equation 16, deviating from their respective mean by a factor . The probability that either of them does is no more than c 1 exp `´c 2 2 n 1{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.99 2 ˚64 ě 1.01 2 ˚48. Thus, inequality is violated with probability at most c 1 exp `´c 2 n 1{3 ˘for positive constants c 1 , c 2 . sum of c m n 2 variables, each of size at most Opr 4{3 q. Now ypλq is a sum of independent variables and Hoeffdinger applies with pb i ´ai q 2 ď Opr 8{3 q for all i. Taking t " cr 2{3 gives us P ˆˇˇˇy pλq ´Erypλqs ˇˇˇě cr 2{3 n 2 ˙ď exp ˆ´2c 2 c m n 4 r 4{3 n 2 r 8{3 ˙ď exp `´cn 2{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 ą c 1 rmn for all λ, which follows from the derivation of Theorem 2 with probability ě 1 ´c1 expp´c 2 n 1{3 q. 2) | Xij | ď r 2{3 for all i, j via Lemma 1. 3) |Y pλq ´Erypλqs| ď cr 2{3 n 2 for 3 evenly spaced λ i by the above equation. Now, since the 2 pλ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 ŷpλq " ypλq ´Erypλqs. Now, our union bounds states that |ŷpλ i q| ă cr 2{3 n 2 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 cr 2{3 n 2 so must p be. The fact that the coefficents in ŷ have absolute value bounded by Opr 2{3 n 2 q, together with the fact that the mean scales as rn 2 gives us the following

min λ ypλq " min λ ŷpλq `Erypλqs ě min λ ŷpλq `min λ 1 Erypλ 1 qs ě min λ ŷpλq `crn 2 ě c 1 r 2{3 n 2 `crn 2

Here c is positive as per our assumptions, whereas c 1 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 c 1 , to complete the proof.

D.6 CONCENTRATION:

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 c 1 , c 2 such that P `ˇf pXq ´Mf pXq ˇˇě t ˘ď c 1 e ´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 X i , X j , X k , X l otherwise sampled as per Assumption 1, where we allow i " j, j " l and any other arbitrary index relationship. Let z " Tr P pX i , X j , X k , X l q and let µ be then mean of z, then P `|z ´µ| ą t r n 2 ˘ď c 1 exp `ć

Here K is the orlicz norm } ¨}Ψ1 which is a constant for our fixed distributions. In the above expression, let us set t " cr 2{3 . This gives P ˆˇˇˇa ´Eras ˇˇˇě cr 2{3 ˙ď 2 exp `´cr 1{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 c 1 r 2{3 from its expectation for some positive c 1 . For a single matrix entry, E " Ūji Ūji ‰ " σ 2 . i goes over the columns of U of which there are r, j goes over the rows of Ū of which there are n and l goes over the columns of V of which there are m, so we clearly get σ 4 rmn. Proof. We can can first contract 1 rˆm 1 T rˆm " 1mµ 2 var , where 1 is a r-by-r matrix of all ones. We then want to find This gives us the result of rmnµ 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 V T U T UV. Permuting the indices cyclically and appealing to Fact 3 gives us Er}W 2 } 2 s " 4mnrσ 4 Fact 6. ErxW 0 , W 2 ys " rmnσ 4

E ALGEBRAIC CALCULATIONS:

Proof. We can write ErxW 0 , W 2 ys as

E Tr "ˆV T 2 U T 2 ´pV ˚qT pU ˚qT ˙ˆ`U 1 ´U2 ˘`V 1 ´V2

˘˙ Again, we want to add and subtract the matrix means 1 nˆr , 1 rˆm to get Proof. We rewrite E}W 1 } 2 F as

E Tr "ˆV T 2 `U1 ´U2 ˘T ``V 1 ´V2 ˘T U T 2 ˙ˆ`U 1 ´U2 ˘V2 `U2 `V1 ´V2

˘˙:

We will again want to center the variables, which gives

E Tr "ˆV 2 T `Ū 1 ´Ū 2 ˘T `1T rˆm `Ū 1 ´Ū 2 ˘T ``Ū 1 ´V 2 ˘T Ū2 T ``V 1 ´V 2 ˘T 1 T nˆr ˆˆ`Ū 1 ´Ū 2 ˘V 2 ``Ū 1 ´Ū 2 ˘1rˆm `Ū 2 `V 1 ´V 2 ˘`1 nˆ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 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µ2 var σ 2 We now return to the terms without constants These are

1 T rˆm `Ū 1 ´Ū 2 ˘T `Ū 1 ´Ū 2 ˘1rˆm ``V 1 ´V 2 ˘T 1 T nˆr 1 nˆr `V 1 ´V 2 ˘(

V2 T `Ū 1 ´Ū 2 ˘T `Ū 1 ´Ū 2 ˘V 2 ``V 1 ´V 2 ˘T Ū2 T Ū2 `V 1 ´V 2 ˘(17) `V 2 T `Ū 1 ´Ū 2 ˘T Ū2 `V 1 ´V 2 ˘``V 1 ´V 2 ˘T Ū2 T `Ū 1 ´Ū 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 V2 

As per usual, we center the variables

" "ˆ`V 1 ´V 2 ˘T `Ū 1 ´Ū 2 ˘T ˙ˆ`Ū 1 ´Ū 2 ˘V 2 ``Ū 1 ´Ū 2 ˘1rˆm `Ū 2 `V 1 ´V 2 ˘`1 nˆ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 V1 T Ū1 T Ū1 V1  " ´4rmnσ 4

E.3 OTHER ALGEBRAIC FACTS:

Fact 9. For any fixed i, j the entries of X, X1 and X2 are zero mean.

Proof. We have Xpλq ´X " `λU 1 `p1 ´λqU 2 ˘`λV 1 `p1 ´λqV 2 ˘´U ˚VX

The fact that U 1 and U 2 are iid implies that pU 1 ´U2 q has zero mean, and the similar holds for V 1 and V 2 . This implies that all terms of X1 and X2 are zero-mean. Using the fact that U 1 , U 2 and U ˚are iid implies that E " `λU 1 `p1 ´λqU 2 ˘`λV 1 `p1 ´λqV 2 ˘ " ErU ˚V˚s This, in turn, implies that Er Xs " 0. Fact 10. For U 1 " U ˚and V 1 " V ˚, we have ErxW 0 , W 2 ys " 2rmnσ 4

Proof. We can write ErxW 0 , W 2 ys as 

:

minpt 2 , t 1{2 q n ˘for positive constants c 1 , c 2 .Proof. Any vector CCP where some components are zero will still be CCP, this we can pad the matrices X i , X j , X k , X l so that they are square. We then invoke Theorem 1 ofMeckes and Szarek (2012) which gives P ˆ|z ´µ| ą τ n 2 ˙ď c 1 exp `´c 2 minpτ 2 , n τ 1{2 q

pλq " `U1 ´U2 ˘`λV 1 `p1 ´λqV

˘``λ U 1 `p1 ´λqU 2 ˘`V 1 ´V2 X2 pλq " `U1 ´U2 ˘`V 1 ´V2

Figures and Tables:

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

Figure4: The loss surface of NMF along the straight line from a random point w 0 to the local optima w ˚found via gradient descent from an independent starting point. We overlap 5 independent lines, zoom in for detail. For all datasets, this loss surface is convex, which is in line with what one would expect from Theorem 1.

Figure5: Illustration of how the relative deviation σ{µ of the curvature equation 6 depend on 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.

Figure 7: Histogram of singular values σ i for found U ˚and a random matrix. Note the similarity of the spectrum. Best viewed in color.

Figure 8: The loss landscape of a 110-layer Resnet architecture at epoch 200 along two random directions, visualized as inLi et al. (2018). The network in the right image is four times as wide, and its loss landscape is increasingly convex. In Table2we generalize this idea, showing that the length scale of local convexity increases with network width.

Figure11: Illustration of how the relative deviation σ{µ of the curvature equation 6 depend on the dataset size as in Figure6. Unfortunately, computing these figures for the larger Netflix and Goodbooks datasets is computationally infeasible for us.



Now since the variables are centered, the expectations becomes zero unless i " k. The sum thus becomes

Dataset details. References contain suggested rank r. See Appendix A for details.

Table content: <table><tr><td>name</td><td>shape pn, m, rq</td><td colspan="2">sparsity reference</td></tr><tr><td>birdsong</td><td>p5120, 1246, 88q</td><td/><td>(Flenner and Hunter, 2017)</td></tr><tr><td colspan="2">extragalactic p2760, 2820, 10q</td><td/><td>(Zhu, 2016)</td></tr><tr><td>goodbooks</td><td colspan="2">p10000, 43461, 50q 0.0022</td><td>(Kula, 2017)</td></tr><tr><td>metabolic</td><td>p9335, 36, 3q</td><td/><td>(Li and Ngom, 2013)</td></tr><tr><td>movielens</td><td>p3953, 6041, 20q</td><td>0.0419</td><td>(Harper and Konstan, 2016)</td></tr><tr><td>netflix</td><td>p47928, 8963, 20q</td><td>0.0121</td><td>(Zhou et al., 2008)</td></tr><tr><td>ORL faces</td><td>p400, 10304, 49q</td><td/><td/></tr></table>

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

Table content: <table><tr><td/><td>20-layers</td><td/><td/><td>44-layers</td><td/><td/><td>68-layers</td><td>110-layers</td></tr><tr><td colspan="9">epoch k=1 k=2 k=4 k=1 k=2 k=4 k=1 k=2 k=4 k=1 k=2 k=4</td></tr><tr><td>0</td><td>0.96 1.0</td><td>1.0</td><td>1.0</td><td>1.0</td><td>1.0</td><td>1.0</td><td>1.0</td><td>1.0 0.94 0.94 0.94</td></tr><tr><td>100</td><td colspan="8">0.87 0.84 0.87 0.72 0.79 0.83 0.71 0.76 0.87 0.79 0.75 0.91</td></tr><tr><td>200</td><td colspan="8">0.81 0.74 0.73 0.66 0.68 0.76 0.6 0.71 0.8 0.71 0.71 0.82</td></tr><tr><td>300</td><td colspan="8">0.71 0.72 0.75 0.57 0.68 0.78 0.58 0.67 0.81 0.63 0.68 0.82</td></tr></table>

Hyper-parameters used for training.

Table content: <table><tr><td>Parameter</td><td>Value</td></tr><tr><td colspan="2">init. learning rate 0.1</td></tr><tr><td colspan="2">SGD momentum 0.9</td></tr><tr><td>batch size</td><td>128</td></tr><tr><td>weight decay</td><td>0.0005</td></tr><tr><td>initialization</td><td>Kaiming</td></tr><tr><td>loss</td><td>cross-entropy</td></tr><tr><td>C EXTENDED NMF FIGURES</td><td/></tr><tr><td>D PROOFS</td><td/></tr><tr><td>D.1 OVERVIEW</td><td/></tr></table>

Continuation of Table 2.

Table content: <table><tr><td/><td/><td>32-layers</td><td/><td/><td>56-layers</td><td/><td/><td>80-layers</td><td/></tr><tr><td colspan="10">epoch k=1 k=2 k=4 k=1 k=2 k=4 k=1 k=2 k=4</td></tr><tr><td>0</td><td>1.0</td><td>1.0</td><td>1.0</td><td>1.0</td><td>1.0</td><td>1.0</td><td>1.0</td><td>1.0</td><td>1.0</td></tr><tr><td>100</td><td colspan="9">0.77 0.8 0.84 0.7 0.81 0.84 0.72 0.85 0.81</td></tr><tr><td>200</td><td colspan="9">0.61 0.68 0.8 0.63 0.67 0.8 0.59 0.7 0.77</td></tr><tr><td>300</td><td colspan="9">0.55 0.68 0.82 0.57 0.66 0.79 0.63 0.71 0.79</td></tr></table>

Links for used datasets. The proofs include considerable amounts of elementary algebraic calculations. For completeness and ease of reference, we present these in Appendix E.

Table content: <table><tr><td>dataset</td><td>link</td></tr><tr><td>birdsong</td><td>https://www.kaggle.com/rtatman/british-birdsong-dataset/data</td></tr><tr><td colspan="2">extragalactic https://s3.us-east-2.amazonaws.com/setcoverproblem/Extra...</td></tr><tr><td/><td>...galacticTest/Extragalatic_Archetype_testsample_spec.fits</td></tr><tr><td>goodbooks</td><td>https://www.kaggle.com/zygmunt/goodbooks-10k</td></tr><tr><td>metabolic</td><td>ftp://ftp.ncbi.nlm.nih.gov/geo/series/GSE3nnn</td></tr><tr><td/><td>/GSE3431/matrix/GSE3431_series_matrix.txt.gz</td></tr><tr><td>movielens</td><td>https://www.kaggle.com/prajitdatta/movielens-100k-dataset</td></tr><tr><td>netflix</td><td>https://www.kaggle.com/netflix-inc/netflix-prize-data</td></tr><tr><td>ORL</td><td>https://github.com/chibuta</td></tr><tr><td/><td>/2Layer_convolution/blob/master/ORL_faces.npz.zip</td></tr><tr><td>satellite</td><td>http://www.escience.cn/system/file?fileId=69117</td></tr><tr><td>results we need.</td><td/></tr></table>

Taking the mean, and using linearity of expectations, we only have nonzero mean if i " k. We get

Table content: <table><tr><td colspan="2">E.1 BASIC FACTS</td><td/><td/><td/></tr><tr><td>Fact 3. E "</td><td>Tr ŪT Ū V VT</td><td>‰</td><td colspan="2">" rmnσ 4</td></tr><tr><td colspan="2">Proof. We have</td><td/><td/><td/></tr><tr><td/><td/><td/><td/><td/><td>"</td><td></td></tr><tr><td/><td/><td colspan="2">E "</td><td colspan="2">Tr ŪT Ū V VT ‰</td><td>" E</td><td>ÿ</td><td>Ūji Ūjk Vkl Vil</td></tr><tr><td/><td/><td/><td/><td/><td>ijkl</td></tr><tr><td/><td/><td/><td/><td/><td>"</td><td></td></tr><tr><td/><td/><td/><td/><td colspan="2">" E</td><td>ÿ</td><td>Ūji Ūji Vil Vil</td></tr><tr><td/><td/><td/><td/><td/><td>ijl</td></tr><tr><td colspan="6">Using linearity of expectation and independence, this becomes</td></tr><tr><td/><td/><td/><td/><td>ÿ</td><td>E " Ūji Ūji</td><td>‰</td><td>E " Vil Vil</td><td>‰</td></tr><tr><td/><td/><td/><td/><td>ijl</td></tr></table>

2 var σ 2 . Er}W 2 } 2 s " 4mnrσ 4 Proof. Let us rewrite Er}W 2 } 2 s as Trace and expectations are linear operators, so we can reorder them. Let us consider the matrix ´V2 Ẇe can easily add and subtract the mean µ of all matrices which gives ˆV 1 ´V 2 ˙T ˆŪ 1 ´Ū 2 ˙T ˆŪ 1 ´Ū 2 ˙ˆV 1 ´V 2 ˙(14)

Table content: <table><tr><td>E Tr</td><td colspan="2">"ˆV 1 ´V2</td><td colspan="2">˙T ˆU1 ´U2</td><td>˙T ˆU1 ´U2 ˙ˆV 1 ´V2</td><td>˙</td></tr><tr><td colspan="2">ˆV1 ´V2</td><td colspan="2">˙T ˆU1 ´U2</td><td colspan="2">˙T ˆU1 ´U2 ˙ˆV 1</td></tr></table>

˘˙As before, we can remove terms which are linear in any centered variable. This removes matrices with index 1, 3 and leaves

Table content: <table><tr><td>"ˆ"</td><td/><td/><td/><td/><td/><td/><td/><td/><td/><td/><td/><td>(15)</td></tr><tr><td>E Tr</td><td>V2</td><td>T Ū2</td><td>T `V 2</td><td colspan="2">T 1 T nˆr</td><td colspan="4">`1T rˆm Ū2</td><td colspan="3">T `1T rˆm 1 T nˆr</td><td>‰</td><td>´" V˚T Ū˚T `V ˚T 1 T nˆr</td><td>`1T rˆm</td><td>Ū˚T `1T rˆm 1 T nˆr</td><td>‰</td></tr><tr><td/><td/><td/><td/><td/><td/><td/><td colspan="2">ˆˆ`Ū</td><td colspan="4">1 ´Ū 2 ˘`V 1 ´V 2</td></tr><tr><td/><td/><td/><td colspan="2">E Tr</td><td>"ˆV</td><td>2</td><td>T Ū2</td><td colspan="3">T `V 2</td><td colspan="2">T 1 T nˆr</td><td>`1T rˆm Ū2</td><td>T ˙ˆŪ 2 V2</td><td>˙</td></tr><tr><td colspan="13">Applying fact 3 to the only term that remain gives</td></tr><tr><td/><td/><td/><td/><td/><td/><td/><td/><td/><td/><td>"</td><td/><td></td></tr><tr><td/><td/><td/><td colspan="8">ErxW 0 , W 2 ys " E Tr</td><td>V2</td><td>T Ū2</td><td>T Ū2 V2</td><td>" rmnσ 4</td></tr><tr><td colspan="12">Fact 7. E}W 1 } 2 F " 6rmnσ 4 `4rmnµ 2 var σ 2</td></tr></table>

Fact 8. ExW 2 , W 1 y " ´4rmnσ 4Proof. Let us rewrite ExW 2 , W 1 y as

Table content: <table><tr><td/><td colspan="2">T Ū2</td><td colspan="4">T Ū2 V2 . Applying Fact 3 gives us</td></tr><tr><td/><td/><td colspan="2">E "</td><td colspan="2">}W 1 } 2 F</td><td>‰</td><td>" 6rmnσ 4 `4rmnµ 2 var σ 2</td></tr><tr><td>E Tr</td><td>"ˆ`V</td><td colspan="3">1 ´V2</td><td colspan="2">˘T `U1 ´U2</td><td>˘T ˙ˆ`U</td><td>1 ´U2 ˘V2 `U2 `V1 ´V2</td></tr></table>

T 2 ´pV ˚qT pU ˚qT ˙ˆ`U ˚´U 2 ˘`V ˚´V 2˘˙ Again, we want to add and subtract the matrix means 1 nˆr , 1 rˆm to getˆˆ`Ū ˚´Ū 2 ˘`V˚´V 2 ˘˙As before, we can remove terms which are linear in any centered variable. The only term that remain gives ErxW 0 , W 2 ys " E Tr

Table content: <table><tr><td>"ˆV</td><td/><td/><td/><td/><td/><td/></tr><tr><td colspan="3">E Tr T `V 2 2 U E Tr T V2 T Ū2 T 1 T nˆr `1T rˆm Ū2 "ˆ"</td><td colspan="2">T `1T rˆm 1 T nˆr</td><td>‰</td><td>´" V˚T Ū˚T `V ˚T 1 T nˆr</td><td>`1T rˆm</td><td>Ū˚T `1T rˆm 1 T nˆr</td><td>‰ (19)</td></tr><tr><td>"</td><td/><td/><td></td><td colspan="2">"</td><td/></tr><tr><td>V2</td><td>T Ū2</td><td colspan="2">T Ū2 V2</td><td>`E Tr</td><td/><td colspan="2">V˚T Ū˚T Ū˚V˚ " 2rmnσ 4</td></tr></table>

Peer review (iclr2020):
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. The 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. In particular, I have some questions regarding the main theorem: - *r grows as and m as *: Big-O means asymptotically bounded, i.e., that r is roughly smaller than n^gamma (which is a tautology for anyway), and that m is roughly smaller than n. Is that really what you mean? Or do you mean instead? Fact 2 uses *recall our assumption that * 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. - Also, re , I do not quite see why such a strong assumption is made. Wouldn*t be enough with respect to Fact 2 to get an asymptotically vanishing deviation probability? i.e., wouldn*t the final result work with , which is more general? Generally, this begs the question of whether is realistic. Can this be put in perspective with respect to other work? - 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? I also have the following additional questions on the experimental findings and the proposed conjecture. - 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: - Why normalize by dividing by the mean? - 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) - 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. Typos/unclear: introduction: *strictly non-negative factors*, what do you mean by strictly? *randomly chosen or the global minimizer* is a bit unclear - what is the *or* over? *Convex along straight paths towards the optima x**: x* -> to be consistent with Definition 1. *similar to Dvoretzky*s*: I fail to see the similarity and how this is related to the present paper. *we will assume that there is a planted optimal solution (U*, V*)*: U*, V* should be in bold to be consistent with further notation. *how r and m depends on n*: depends -> depend *as the size of the problem increaseS* *loss function *of* equation 2* Theorem 1: *at least geq* is redundant Theorem 1: *but with exponent -c r^{1/3}* is unclear: which exponent is this? Write the statement in full instead. *it*s second derivative*: its? *for unobserved Data*: why is *data* capitalized? D3: *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? D3: *3 evenly spaceD lambda* D6: Definition 2: *iff there *exists* positive constants...* D6: *one can easily verify that independenT Gaussian variables* D6: *i=j, j=l, and so on*: what is *and so on*? all indexes are completely arbitrary? D6: *z = P(X_i, X_j, X_k, X_l)*: clarify notation . In the main text, you*ve used the notation instead. D6: Equation (12) and (13): should the RHS be exp(-X) instead of exp(X)? D6: 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. D6: *Lemma 9 says that each one can be expressED* E1: End of proof of fact 3: do not include an equal sign if there is no left-hand side. E1: *trace and linearity are linear operators*: linearity is linear?