Small random initialization is akin to spectral learning: Optimization and generalization guarantees for overparameterized low-rank matrix reconstruction
Authors: Dominik Stöger
Mahdi Soltanolkotabi
Venue: NeurIPS 2021 Poster (2021)
Keywords: low-rank matrix recovery
overparameterized learning
non-convex optimization

Abstract: Recently there has been significant theoretical progress on understanding the convergence and generalization of gradient-based methods on nonconvex losses with overparameterized models. Nevertheless, many aspects of optimization and generalization and in particular the critical role of small random initialization are not fully understood. In this paper, we take a step towards demystifying this role by proving that small random initialization followed by a few iterations of gradient descent behaves akin to popular spectral methods. We also show that this implicit spectral bias from small random initialization, which is provably more prominent for overparameterized models, also puts the gradient descent iterations on a particular trajectory towards solutions that are not only globally optimal but also generalize well. Concretely, we focus on the problem of reconstructing a low-rank matrix from a few measurements via a natural nonconvex formulation. In this setting, we show that the trajectory of the gradient descent iterations from small random initialization can be approximately decomposed into three phases: (I) a spectral or alignment phase where we show that that the iterates have an implicit spectral bias akin to spectral initialization allowing us to show that at the end of this phase the column space of the iterates and the underlying low-rank matrix are sufficiently aligned, (II) a saddle avoidance/refinement phase where we show that the trajectory of the gradient iterates moves away from certain degenerate saddle points, and (III) a local refinement phase where we show that after avoiding the saddles the iterates converge quickly to the underlying low-rank matrix. Underlying our analysis are insights for the analysis of overparameterized nonconvex optimization schemes that may have implications for computational problems beyond low-rank reconstruction.

Small random initialization is akin to spectral learning: Optimization and generalization guarantees for overparameterized low-rank matrix reconstruction
Dominik Stöger
Mahdi Soltanolkotabi University of Southern California Los Angeles, CA 90089 toltanoluusc. edu
Katholische Universität Eichstät-Ingolstadd 85072 Eichstätt, Germany
Dominik. Stoekkrku.og
Abstract
Recently there has been significant thcoretical progress on understanding the convergence and generalization of gradient-based methods on nonconvex losses with overparameterized models. Nevertheless, many aspects of optimization and generalization and in particular the critical role of small random initialization are not fully understood. In this paper, we take a step towards demystifying this role by proving that small random initialization followed by few iterations of gradient descent behaves akin to popular spectral methods. We also show that this implicil spectral bias from small random initialization, which is provably more prominent for overparameterized models, also puts the gradient descent iterations particular trajectory towards solutions that are not only globally optimal but also generalize well. Concretely, we focus on the problem of reconstructing a low-rank matrix from a few measurements via natural nonconvex formulation. In this setting, we show that the trajectory of the gradient descent iterations from small random initialization (I) a spectral or alignment phase where we show that that the iterates have an implicit spectral bias akin spectral initialization allowing us show that at the end of this phase the column space of the iterates and the underlying low-rank matrix sufficiently aligned, (II) saddle avoidunce/refinement phase where we show that the trajectory of the gradient iterates moves away from certain degenerate saddle points, and (III) local refinement phase where show that after avoiding the saddles the iterates converge quickly to the underlying low-rank matrix. Underlying our analysis are insights for the analysis of overparameterized nonconvex optimization schemes that may have implications for computational problems beyond low-rank reconstruction.
be approximately decomposed into three phases:
Introduction
Many contemporary problems machine learning and signal estimation spanning deep learning to low-rank matrix reconstruction involve fitting nonlinear models to training data. Despite tremendous empirical progress, theoretical understanding of these problems poses two fundamental challenges. First, from optimization perspective, fitting these models often requires solving highly nonconvex optimization problems and except for few special cases, it is not known how to provably find globally approximately optimal solutions. Yet simple heuristics such running (stochastic) gradient descent from (typically) small random initialization is surprisingly effective at finding globally optimal solutions. A second generalization challenge is that many modern learning models including neural network architectures are trained in an overparameterized regime where the parameters of the model exceed the size of the training dataset. It is well understood that in this overparameterized
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

regime, these large models are highly expressive and have the capacity to (over)fit arbitrary training datasets including pure noise. Mysteriously however overparameterized models trained via simple algorithms such as (stochastic) gradient descent when initialized at random continue to predict well or generalize on yet unseen test data. In particular, it has been noted in a number of works that for many modern machine learning architectures, the scale of initialization is important for the generalization/test behavior [1, 2]. It has been noted that stronger generalization performance is typically observed for a smaller scale initialization. Indeed, small random initialization followed by (stochastic) gradient descent iterative updates is arguably the most widely used learning algorithm in modern machine learning and signal estimation.
There has been large number of exciting results aimed at demystifying both the optimization and generalization aspects over the past few years. We will elaborate on these results in detail in the supplementary, however, we would like to briefly mention the common techniques and their existing limitations. On the optimization front a large body of work has emerged on providing guarantees for nonconvex optimization which can roughly be put into two categories: (I) smart initialization+loaal convergence and (II) landscape analysistsaddle escaping algorithms. Approaches in (I) focus on showing local convergence of local search techniques from carefully designed spectral initializations [3, 4, 5, 6. 7, 8, 9, 10]. Approaches in (II) focus on showing that in some cases the optimization landscape is benign in the sense that all local minima are global (no spurious local minima) and the saddle points have direction of strict negative curvature (strict saddle) [11]. Then specialized truncation or saddle escaping algorithms such as trust region, cubic regularization [12, 13), or noisy (stochastic) gradient-based methods [14, 15, 16, 17] are deployed to provably find global optimum. Both approaches fail to fully explain the typical behavior of local search techniques in practice. Indeed, for many nonconvex problems local search techniques or simple variants, when initialized at random, quickly converge to globally optimal solutions without getting stuck in local optima/saddles without the need for sophisticated initialization or saddle escaping heuristics. We note that while for differentiable losses eventual convergence to local minimizers is known from a random initialization [18] on problems of the form (II), these results cannot rule out exponentially slow cases in the worst-case [19]. Indeed, it has been argued that in general more granular analysis of the trajectory of gradient descent beyond the landscape may be necessary [20]. For example, some recent advances has been made by analysing the trajectory of gradient descent using a leave-one-ous analysis for the phase retrieval problem [21].
Similarly, there has been a lot of exciting progress on the generalization front, especially for neural networks. Specific generalization capabilities of gradient-based approaches these results broadly fall into two categories: (a) the first category is based on a linearization principle which characterizes the performance of nonlinear models such as neural networks by comparing it linearized kernel problem around the initialization (a.k.a. Neural Tangent Kernels) [22, 23, 24, 25, 26, 27, 28). This has often been referred to as "lazy training". (b) the second category is based on a continuous limit analysis in the limit of width going to infinity and learning rate going to zero (mean-fice field analysis) [29, 30, 31, 32, 33]. However, these existing analyses contain many idcalized and non- realistic assumptions (c.g. requiring large, random initialization in (a), which typically leads to worse generalization than what is observed in practice, or unrealistically large widths in (b)) and therefore cannot fully explain the success of overparameterized models or serve as a guiding principle for practitioners [34].
Despite the aforementioned exciting recent theoretical progress many aspects of optimization and generalization and in particular the role of random initialization remains mysterious. This leads to the main challenge of this paper
Why is small random initialization combined with gradient descent updates so ef- fective at finding globally optimal models that generalize well despite the nonconvex nature of the optimization landscape model overparametericatton??
In this paper we wish to take step towards addressing the above challenge by demystifying the critical role of small random initialization in gradient- based approaches. Specifically we show that
Small random initialization followed by a few iterations of gradient descent behaves akin to spectral initialization.
By that, we mean more precisely, that if the initialization is chosen small enough, then in the initial stage of the training, gradient descent implicitly behaves like spectral initialization techniques such as
2

---

8p
0cp
0.8
0.6
0.4
0.2
0.5
3.6 0g
60
number of iterations
Figure 1: Gradient descent from small random initialization is akin to spectral initialization. The left figure depicts the empirical landscape of low-rank matrix reconstruction problem with the two green circles depicting the two global minima and the white circle the saddle point at the origin. In this figure, we also depict the trajectory of the gradient descent iterations (magenta) together with the power method based on popular spectral initialization technique (blue). Both gradient descent and power method use the same small initialization near the origin. We see that in the early stage, the two trajectories are almost the same. The figure on the right depicts the angle between the gradient descent (magenta)/power method (blue) iterates and a popular spectral initialization technique, denoted by lGD and Op respectively. This figure clearly demonstrates that for the first iterations these angles are practically the same further confirming that the initial trajectory of gradient descent and power methods are similar. See Section for further detail on the experimental setup. (In this figure we have used r rr, 1.)
those commonly used in techniques based on the method of moments. This implicit spectral bias of gradient descent from random initialization puts the gradient descent iterations on a particular trajectory towards solutions that are not only globally optimal but also generalize well for overpa- rameterized models. We also show that with small random initialization this implicit spectral bias phenomenon is more prominent for more overparameterized models in the sense that it materializes after fewer iterations. This intriguing phenomenon is depicted Figure in the context of low-rank reconstruction problem. This figure clearly demonstrates that the first few iterations of gradient descent starting from a small random initialization are virtually identical to that of running power iterations (a popular algorithm to find the spectral initialization, see, e.g. [35]).
Concretely focus on the problem of low-rank matrix recovery, which appears in many different application areas such as recommendation systems, phase retrieval, and quantum tomography [36]. Here, our goal is recover a low-rank matrix of the form XX" from a few linear measurements. We consider natural, non-convex approach based on matrix factorization, where we minimize the loss function via gradient descent. In this paper, we show that, regardless of the amount of overparameterizztion used, for small random initialization vanilla gradient descent will always converge towards the low-rank solution. This holds as long as the measurement operator obeys popular restricted isometry property [37].
Our analysis consists of three phases. The first phase is the aforementioned spectral or alignment phase where we show gradient descent from small random initialization behaves akin to spectral initialization, which is key insight of this paper. Indeed, we show that the first few gradient descent iterates can be accurately approximated by power method iterates. Next, we show that after this first spectral or alignment phase, gradient descent enters a second phase, which we refer to saddle avoidance phase. In this phase, we show that the trajectory of the gradient iterates moves away from degenerate saddle points, while the iterates maintain almost the same effective rank as X XT In the third phase, the local refinement phase, we show that the iterates approximately converge towards the underlying low-rank matrix X X with a geometric rate up to a certain error floor which depends on the initialization scale. In particular, by decreasing the scale of initialization this error threshold can

---

be made arbitrarily small. While in this paper our main focus is on low-rank matrix reconstruction, we believe that our analysis holds more generally for variety of contemporary machine learning and signal estimation tasks including neural networks.
Finally we that while similar setting has already been studied in [38], our analysis goes beyond it in many important ways. For example, our result holds for any amount of overparameterriztion and allows for arbitrarily small initialization. Maybe most importantly, we study the spectral phase phenomenon at initialization.
Low-rank matrix recovery via non-convex optimization
As mentioned earlier in this paper focus reconstructing (possibly overparameterized Positive Semidefinite (PSD) low rank matrix from a few measurements. In this problem, given m observations of the form
(1) we wish reconstruct the unknown matrix X XXx.. Here, RRax, with 1 sr. n is factor the unknown matrix and {A; i-1, are known symmetric measurement matrices. A common approach to solving this problem is via minimizing the loss function
V/ (A,,X*) Tr (A,X²²
i=1....,m.
min S(0) UeR
:= min (v. Roke 4m
with r 2 T.. More compactly one can rewrite the optimization problem above in the form
min f(0) min UeRaxr
A(UO"
(2)
DeRmaer
where A: |Ruxn RT is the measurement operator defined by [A [A())];= 7.m. (A,, Z).
In order solve the minimization problem (2) we run gradient descent iterations starting from (often small) random initialization. More specifically.
U U, uVf (Vf( U, MA
+ ( = U.+ +U+ () U.U?"]]
where we have set Un = aU is the initialization matrix, A' denotes the adjoint operator of AA and y = (y:), e RRm denotes the measurement vector. Here, U [Ra*r is typically random matrix which represents the form of the initialization and > 0 is a scaling parameter.
There are two challenges associated with analyzing such randomly initialized gradient descent updates. The first is an optimization challenge. Since f is non-comvex it a priori not clear whether gradient global optimum whether it gets stuck in local minima and/or saddle. The second challenge is that of generalization. This is particularly pronounced in the overparameterized scenario where the number of parameters this case, there are infinitely many U such that f(Ū) = O, but |U XX" Ir is arbitrarily large (see, e.g., [39, Proposition i]). That is, even if gradient descent converges to global optimum, iee. (8) O, it is priori not clear whether it has found the low-rank solution X (see also Figure 5).
descent converges
larger than the number of data points i.e.
In
3
Main results
In this section, we present our main results. Stating these results requires a couple of simple definitions. The first definition concerns the measurement operator A.
Definition 3.1 (Restricted Isometry Property (RIP).. The measurement operator A |R
RT
satisfies RIP of rank r with constant > 0, if it holds for all matrices Z of rank at most
(1 8) | [A(Z) (11+8) 12
(3)
We note that for a Gaussian measurement operator A 1 RIP of rank r and constant > + holds with high probability, if the number of observations satisfies nr/82 [37, 40].
By that, we that all the entries of the (symmetric) measurement matrices (A:),, drawn i..d. with distribution / (0, 1) on the off diagona and distribution '' (0, 1/v2) on the diagonal.

---

The second definition concerns the condition number of the factor X.
Definition 3.2 (condition number). We denote the condition number of X e Ruxx, by k ov, (X)) where o, (X) denotes r.-th largest singular value of X.
[X]
With these definitions in place we are now ready to state our main results. Due to space limitations in the main paper we focus on the case of r 2r.. With refer the reader to the supplementary for results covering all r 2 r, including two special cases: (1) the fully overparameterized case, i.e., along with comparisons with existing work, in this case [38], and (2) the scenario that U has the same number of parameters as X, i.c., T
Theorem 3.3. Let X E RRAX.. and assume we have m measurements of the low rank matrix XXT of the form y = A (XX") with A the measurement operator. We assume A satisfies the restricted isometry property for all matrices of rank at most 2r, 11 with constant ô S rx" To reconstruct X from the measurements we fit model of the form Ú + A (UT"") with U RuxT via running gradient descent iterations of the form UL-1 U, (U)) on the objective (2) with a step size obeying μ S cK +|x|| Here, the initialization is given by Uo al, where U Raxr has i.i.d entries distributed as N (0, (0.1/ Furthermore, we assume r 2r. and that the scale of initialization fulfills
(min (r; (r;
a min
2n:²
π2
|X||.
(4)
n//2
min (13n)
k7 m
Then, after
Cinu
|X|
is min
(x)² In
-mxx 1; minn {r;m] r.
min {r;n}
a
iterations we have that
UUUU XX
2 81/16, 1/8
a 21/16
$
(5)
|X|2
(min (r:n)) 15/16
|
holds with probability at least Ce- Here, c, C, > are fixed numerical constants.
Note that the test error ||UGU? X 12 can made arbitrarily small by choosing the scale of initialization small enough. In particular, the dependence of the test error on is polynomial and the dependence of the number of iterations on a is logarithmic, which means that reducing the test error by scaling down introduces only modest additional computational cost. Hence, as long as the rank at most 2r, + RIP with constant 8 s "r, 1/2 holds, gradient descent converges to point in the proximity of the low-rank solution, whenever the initialization is chosen small enough regardless of the choice of This holds even when the model is overparameterizze i.e. rn >> and the optimization problem has many global optima many of which do not obey UU XXT. This result thus further demonstrates that when initialized with small random initialization gradient descent has an implicit bias towards solutions of low-rank or small nuclear norm. This is in sharp contrast Neural Tangent Kernel (NTK)-based theory for low-ram matrix recovery (see [23, Section 4.2l) which will not approximately recover the ground truth matrix Xx" due to the larger scale of initialization required when using that technique.
As discussed in Section 2, the restricted isometry property holds with high probability for a sample complexity m 2t 2r for Gaussian measurement matrices. Up to constants, this sample complexity optimal n, while it is sub-optimal in r. and x compared to approaches based on nuclear-norn minimization (see, e.g., [37]). While there is numerical evidence that the true scaling of m in should also be linear in the non-convex case [41], we note that the optimal dependence of the sample complexity r. is major open problem in the field, as the sample complexities in all theoretical results for non-convex approaches the literature scale at least quadratically in r..
Interpretation: Recall from Section I that our convergence analysis can be divided into three phases: the spectral phase, the saddle avoidance phase, and the local refinement phase. As it will become clear from the proofs in the supplementary when 2r, the bound on the number of iterations can
5

---

be decomposed as follows
8 m0 (X)²
In 2x
min (r;n)
72
In
Omin (X)
In
max
min
(r:
|
Pluse I: specttalaaligmmmm phuse
Phose Tl: subile avoillncce plaase
Phuse [II: local refinement pluse
(6)
First, note that the duration of all three phases scales inversely with minn (x)². This is due the fact that in all three phases the dynamics associated the smallest singular value of X is the slowest one and hence needs the most time complete.
In the spectral phase, the cigenvectors corresponding to the leading r. cigenvalues of U,U?" become aligned with the eigenvectors corresponding to the leading r. eigenvalues of A' A'AA (XX"). We observe in (6) that in the spectral phase increasing r, i.e. the amount of parameters, decreases the number of iterations in this phase. As we will explain in the supplementary, the reason is that increasing decreases the angle between the column space of the initialization Un and the span of the eigenvectors corresponding to the leading т, cigenvalues of AA" "A (XX²) used in spectral initialization. As a consequence, gradient descent needs fewer iterations to align these two subspaces.
In the saddle avoidance phase (Phase II), or, (U)) the r.th largest singular value of Us, grows geometrically until it is on the order of T (X). Hence, this duration depends on the ratio between the min (X) and the the scale of initialization a. This is clearly reflected in the upper bound on the number of needed iterations equation (6).
In Phase III, the local refinement phase, the matrix U,U? converges towards X XX". In particular, at iteration & the test error obeys (5). We observe that a smaller a allows for a smaller test error in (5) but per (6) this higher accuracy is achieved with modest increase in the required iterations.
4 A glimpse of our analysis
In our proofs, we show that the trajectory of the gradient descent iterations can be approximately decomposed into three phases: (I) spectral or alignment phase where we show that gradient descent from random initialization behaves akin to spectral initialization allowing us to show that at the end of this phase the column spaces of the iterates U, and the ground truth matrix X are sufficiently aligned, (II) a saddle avoidance phase, where we show that the trajectory of the gradient iterates move away from certain degenerate saddle points, and (III) refinement phase, where the product of the gradient descent iterates U,U? converges quickly to the underlying low-rank matrix X XXT. The latter result holds up to small eтror that is commensurate with the scale of the initialization and tends to zero as the scale of the initialization goes to zero.
To formalize the above, we use I, and I, to denote the subspaces spanned by the eigenvectors corresponding to the r. largest eigenvalues of the matrix A' A'A **xxxx") and U,U?", respectively. Moreover, for a subspace L of dimension r. we use Vy, e Raax. to denote an orthonormal matrix whose columns span the subspace L. Note that the subspace. which obtained by commonly used spectral methods. Using this notation, Figure 2a depicts the three phases described above.
In the spectral phase will prove that
approximate the iterate U, by U. x (Id pA AXx"((Xx")) ZuU := Ü..
=:Z+
We note that the matrix Z, Id + A is the basis for the commonly used spectral initialization, where typically factorization of the rank r, approximation of this matrix is used as the initialization [6, 5, 42]. Therefore, the approximation (7) suggests that gradient descent iterates modulo the normalization are akin to running power method Z,. Hence, we expect that at the end of the spectral phase the subspace L, to be closely aligned with the subspace L, i.e. the subspace obtained by commonly used spectral initialization techniques. In particular, this also implies that L, is also aligned with the subspace X. Figure 2b clearly illustrates that the first few iterations of gradient descent behave essentially identical the power method, confirming our intuition.
The description of the second and third phase is more elaborate and technical in nature and we defer to the supplementary for more detailed and intuitive explanation. However, to give brief

---

Paoe
0.5
0.6
0.2
20
100
rumbber Ineaaions
sambbes of Itecciions
(b)
Figure 2: (a) Depiction of the three phases of convergence. This figure demonstrates that the convergence analysis can be divided into three phases: (I) spectral/alignment phase; (II) saddle avoidance phase and (III) the refinement phase. We see that in the first phase the first r. eigenvectors of U,U? rapidly learn the subspace corresponding to the first r. eigenvectors of A A (XX")) i.e. the angle VL. becomes small. The th largest singular value of U, is still small in this phase and the (normalized) test error |U, XxX || [XXIXX"" 7 has not decreased yet. In Phase (II), however, we see that or, (Ut) is growing, whereas the loss begins to decrease in this phase and the subspaces stay aligned. In Phase (III) meaning that U,U," converges to X xx" Consequently, or (Ut)/a,, (X) converges to (red curve). We also see that in this phase the angle [V Vz. grows again, until reaches a certain threshold. This is because in this phase the top r. cigenvalues of U,U? become aligned with the eigenvectors of XXT. (b) Depiction of the spectral alignment phase: in the first few iterations, gradient descent with small initialization behaves like a power method. Denote by L, the subspace spanned by
that the test error is converging towards 0 rapidly,
the eigenvectors corresponding the largest eigenvalues of the matrix U, Analogously as before denote by Ví, orthonormal matrix, whose columns span the subspace L, In this figure, observe that in the first iterations U, and U, learn the subspace L at almost exactly the same rate.
description, in these two phases we will decompose the iterates Ug into the sum of two matrices, a "signal" matrix of rank and a "noise" matrix of rank at most r- T.. In Phase (II) will prove that the smallest singular value of the signal term, which approximately the same as o,, (U)) grows, whereas the spectral norm of the noise matrix grows at much slower rate. We will also show that in this phase the columns of the signal term stay approximately aligned with the span of the matrix X. As the smallest singular value of the signal term of U is approximately at the same order than the smallest singular value of we enter Phase (III). In that Phase we provide a local convergence argument, which shows that the signal term of U, converges towards X (up rotation), whereas the noise term stays small.
5 Numerical experiments
In this section, we perform several numerical experiments to corroborate our theoretical results.
Experimental setup. For the experiments we set the ground truth matrix X E gaxr, to be a random orthogonal matrix with = 200 and r. Moreover, we use m 10nr, 50n random Gaussian measurements. The initialization U is chosen as in Theorem 3.3 and we use step size of 1/4 which is consistent with these theorems. We note that while all experimental depictions are based on single trial, in line with the NeurIPS guidelines we have drawn these curves multiple times (not depicted) and the behavior of the plots do not change.
Depiction of the three phases and the role of overparameterization. In first experiment, want to examine how increasing the number of parameters via increasing the number of the columns r of the matrix U, e RRa affects the spectral phase. To this aim we set the scale of initialization to 1/ (70m²). Let L denote the subspace spanned by the eigenvectors corresponding to the leading r. singular values of A (*A(XX)) XT) and T., denotes the subspace spanned by the left-singular vectors corresponding to the largest singular values of U..
7

---

5=
10
10
0.8
0.8
F= 00
40
0.6
200
8, (02)
0.6
200
F= 400
0.4
0.4
0.2
0.2
20
40
60
80
100
120
20
40
60
80
100
120
namber of itorations
namber iterations
(a)
(b)
r=
10
[0,07 -XX" 1xxxXx/"xx [
20
100
0.6
400
0.4
0.2
number iteracionns
(c)
Figure 3: Impact of different levels of overparameterization on (a) the angle |V V2, and (b) the r.th
largest singular value, (c) the trajectory of the (normalized) test error |U,U? - XX" 2x1 |x/|
Spectral phase and alignment under different levels of overparamettriizatin. First, we examine how the angle between these two subspaces (i.e. VV VL, 1) changes in the first few iterations. We depict the results for different r in Figure 3a. We see that in the first few iterations, i.e. in the spectral phase, this angle converges towards zero. This confirms the main conclusion of this paper that the first few iterations of gradient descent from small random initialization indeed behaves akin to running power method for spectral initialization. This experiment also shows that changing the number of columns r of U, has an interesting effect on the spectral phase. In particular, increasing allows the gradient descent algorithm to learn the subspace L with fewer iterations, i.c. |V[ VL, becomes small with fewer iterations. This is in accordance with our theory for т. S r S (see, for example, the first summand on the right-hand side of equation (6)), where we show that more overparameterrizatoo allows gradient descent to leave the spectral phase earlier. Interestingly, this improvement continues to hold even when increasing beyond allowing for even faster convergence of |/V VL, This holds even though in this case the rank of Uo is still not larger than n. One potential explanation for this phenomenon might be that for such a choice of r the matrix Un is better conditioned.
Growth of or, (U+) and saddle avoidance. In Figure 3b we depict how a,, (Ut) grows during the training for different choices of r. We see that the curves look similar, although for smaller r the growth phase in at a slightly later time. This is due the fact that for smaller r, have seen in Figure 3a, Phase I, the spectral phase takes longer to complete.
Evolution of the test error and the refinement phase. Similarly, in Figure 3c depict how the (normalized) test error |U x | evolves during the training for different choices of r. We observe that for smaller the third phase sets in slightly later. Again, this is due to the fact that for smaller r the spectral phase takes slightly longer to complete (see inequality (6)).
Test error under different scales of initialization. In the next experiment, we focus on understanding how the scale of initialization affects the generalization error |U,U," -x-xXx"X 12.
8

---

train test ceror
10-1
Canbo lest cITD
10"3
10"
10"
10"
10:3
10
| -XX" for different scales of initialization a
Figure 4: Relative test error
1XXT|r
10
10-5 test error 10 train
0.5
O 0.5 train arpor
10-4
toxt post//rsiio error
tot/ttrinn CITOr
10-7
10.4
10:23
10-9
10-10
10:31
1-10P
2- 10P
3- 100
4-
0
1: 10'
2: 307
3- 10"
4-10
Iteratioo
(a) 10
(b) 0.5
Figure 5: Change of test error JUU? X 13 and train error (U.) for (a) small and (b) large during training.
For that, we set r = 180 and run gradient descent with for different choices of a. stop as soon as the training error becomes small (f (U,) s 0.5 10-9), We depict the results in Figure 4. We see that the test error decreases as a decreases. In particular, this figure indicates that the test error depends This is in line with our theory, where also show that
polynomially the scale of initialization the test error decreases at least with the rate a 21/16 (see inequality (5) in Theorem 3.3).
Change of test and train error during training. In the next experiment, we set r 180 and examine how the test error |U,U?" xx= 1/ and the train error f (U,) changes throughout training and, in particular, how this depends on the scale of initialization. To this aim, we run gradient descent with 10 iterations. We see that for small scale of initialization, a 10-3 which the scenario studied in this paper, both test error and train error decrease throughout training.
We observe that in the beginning, described After that the decrease of both test and train error slows down significantly. Moreover, the train error converges towards zero, in contrast to the test error. One reason for the slow convergence in this phase might be that U, is ill-conditioned in the sense that σ,, (U,W) is much larger than [UW,,, is an interesting future research direction to extend our theory this part of the training.
theory, both test and train error decrease rapidly.
For large scale initialization a = 0.3, we observe a very different behaviour. We see that the train error converges with linear rate until machine precision is reached. However, the test error barely changes throughout the training. This scale of initialization corresponds to the lazy training regime [34], where the parameters stay close to the initialization during the training. We depict the results in Figure 5.
Number of iterations until convergence: In the last experiment, many iterations are needed until the test error !U X falls below a certain threshold of 10- for different values of obeying S $ 30. For each choice we run the experiment ten times and then average the number of iterations for each choice of The results are depicted in Figure 6. We observe that increasing the number of columns r from 5 to 10, i.e., a small amount of overparameteriiation,, decreases the number of iterations needed. After that the number of iterations
10-3 and examine how

---

Blimber licratione
60
50
45
20
30
mimber of coblunss
Figure 6: Number of iterations required for the test error to fall below 10-4 for different levels of overparameterization.
needed stays roughly constant. This observation is in line with Figure 3, where we have seen that overparameterizatioo leads to fast decrease of the test error in the spectral phase (with diminishing speedup as r becomes larger and larger) without affecting the other two phases.
6 Conclusion and Broader Impact
In this paper we focused demystifying the role of initialization when training overparameterized models by showing that small random initialization followed by a few iterations of gradient descent behaves akin to popular spectral methods. We also show that this implicit spectral bias from small random initialization, which provably more prominent for overparameterized models, also puts the gradient descent iterations particular trajectory towards solutions that are not only globally optimal but also generalize well.
We think that our results give rise to a number of interesting future research directions. For example, one could extend our results to scenarios where the measurement matrices are more structured such as in matrix completion [43] or in blind deconvolution [44]. Moreover, while our main results, e.g. Theorem 3.3 do require early stopping, our simulations (e.g. Figure 5a) indicate that early stopping is not needed. It would be interesting to examine whether we can remove the early stopping requirement. also an interesting future avenue to examine whether quadratic dependence of the sample complexity
in results is really needed.
Moreover, while in this paper our main focus was on low-rank matrix reconstruction, we believe that our analysis holds more generally for variety of contemporary overparameterized machine learning and signal estimation tasks including neural network training. This is tantalizing future research direction.
Despite being theoretical/foundatinaal in nature our results have potential for broader practical impact. In particular, low rank reconstruction problems are an important component of many recommender engines and our insights may guide better algorithm and systems designs for such engines. More broadly, training overparameterized models using stochastic GD starting from small random initialization the work-horse of modemn learning neluding deep learning and our insights may in the long term help enable more effficient/reiablle training with smaller carbon footprint and improved accuracy. As with other technologies such insights may potentially also be used nefariously.
Acknowledgments and Disclosure of Funding
M.S. is supported by the Packard Fellowship in Science and Engineering, a Sloan Research Fellowship in Mathematics, an NSF-CAREER under award #1 8143669,, the Air Force Office of Scientific Research Young Investigator Program (AFOSR-YE YIP) under award #FA9550-15 18-1-0078. DARPA Learning with Less Labels (LwLL) and FastNICS programs, and NSF-CIF awards #1813877 and #2008443.
10

---

References
[1] Blake Woodworth, Suriya Gunasekar, Jason D. Lee, Edward Moroshko, Pedro Savarese, Itay Golan, Daniel Soudry, and Nathan Srebro. Kernel and rich regimes in overparametrizee models. In Jacob Abernethy and Shivani Agarwal, editors, Proceedings of Thirty Third Conference on Learning Theory, volume 125 of Proceedings of Machine Learning Research, pages 3635-3673. PMLR, 09-12 Jul 2020.
[2] Behrooz Ghorbani, Song Mei, Theodor Misiakiewicz, and Andrea Montanari. When do neural networks outperform kernel methods? arXiv preprini arXiv:2006. 2020.
[3] Emmanuel Candès, Xiaodong Li, and Mahdi Soltanolkotabi, Phase retrieval via Wirtinger flow: theory and algorithms. IEEE Trans. Inf. Theory, 61(4): 2015.
[4] Yuxin Chen and Emmanuel J. Candès. Solving random quadratic systems of equations is nearly easy solving linear systems. Commun. Pure Appl. Math., 70(5):822-88) -83, 2017.
[5] Cong Ma, Kaizheng Wang, Yuejie Chi, and Yuxin Chen. Implicit regularization in nonconvex statistical estimation: gradient descent converges linearly for phase retrieval, matrix completion, and blind deconvolution. Found. Comput. Math., 20(3):451-633 2020.
[6] Tu, R. Boczar, M. Simchowitz, M. Soltanolkotabi, and B. Recht. Low-rank solutions of linear matrix equations via procrustes flow. In Proceedings of the 33rd International Conference on International Conference on Machine Learning (ICML), volume 48, pages 964-973. Journal of Machine Learning Research, 2016.
[7] Xiaodong Li, Shuyang Ling, Thomas Strohmer, and Ke Wei. Rapid, robust, and reliable blind deconvolution via nonconvex optimization. Appl. Comput. Harmon. Anal., 47(3):893-934, 2019.
[8] Shuyang Ling and Thomas Strohmer. Regularized gradient descent: non-convex recipe for fast joint blind deconvolution and demixing. Inf. Inference, 8(1):1 2019.
[9] Praneeth Netrapalli, Prateek Jain, and Sujay Sanghavi. Phase retrieval using alternating mini- mization. IEEE Trans. Signal Process., (1(18)):48448888 2015.
[10] Irêne Waldspurger. Phase retrieval with random Gaussian sensing vectors by alternating projections. IEEE Trans. Inf. Theory, 6465):3301-3312 2018.
[11] Ju Sun, Qing Qu, and John Wright. When are nonconvex problems not scary? arXiv preprint arXiv:1510.0609 2015.
[12] Yurii Nesterov and Boris T. Polyak. Cubic regularization of Newton method and its global performance. Math. Program., 108(1 (A)):177-205, 2006.
[13] Jorge Nocedal and Stephen Wright. Trust-region methods. Numerical Optimization, pages 66-100, 2006.
[14] Chi Jin, Rong Ge, Praneeth Netrapalli, Sham M. Kakade, and Michael I. Jordan. How to escape saddle points efficiently. page 1724- 1732, 2017.
[15] Rong Ge, Furong Huang, Chi Jin, and Yang. Yuan. Escaping from saddle points: online stochastic gradient for tensor decomposition. In Proceedings of The 28th Conference on Learning Theory, pages 797-842, 2015.
[16] Maxim Raginsky, Alexander Rakhlin, and Matus Telgarsky. Non-convex learning via stochastic gradient langevin dynamics: nonasymptotic analysis. pages 1674-1703, 2017.
[17] Yuchen Zhang, Percy Liang, and Moses Charikar. A hitting time analysis of stochastic gradient langevin dynamics. In Satyen Kale and Ohad Shamir, editors, Proceedings of the 2017 Con- ference on Learning Theory, volume 65 of Proceedings of Machine Learning Research, pages 2922. PMLR, 07-10 Jul 2017.
11

---

[18] Jason D. Lee. Max Simchowitz, Michael I. Jordan, and Benjamin Recht. Gradient descent only converges minimizers. In Vitaly Feldman, Alexander Rakhlin, and Ohad Shamir, editors, 29th Annual Conference on Learning Theory, volume 49 of Proceedings of Machine Learning Research, pages 1246-1257, Columbia University, New York, New York, USA, 23-26 Jun 2016. PMLR.
[19] Simon S Du, Chi Jin, Jason D Lee, Michael Jordan, Aarti Singh, and Barnabas Poczos. Gradient descent can take exponential time to escape saddle points. In I. Guyon, U. V. Luxburg, S. Bengio, H. Wallach, R. Fergus, S. Vishwanathan, and R. Garnett, editors, Advances in Neural Information Processing Systems, volume 30. Curran Associates, Inc., 2017.
[20] Sanjeev Arora, Nadav Cohen, Wei Hu, and Yuping Luo. Implicit regularization in deep matrix factorization. In Advances in Neural Information Processing Systems, pages 7413-7424, 2019.
[21] Yuxin Chen, Yuejie Chi, Jianqing Fan, and Cong Ma. Gradient descent with random initializa- tion: fast global convergence for nonconvex phase retrieval. Math. Program., 176(1-2 (B)):5-37, 2019.
[22] Arthur Jacot, Franck Gabriel, and Clément Hongler. Neural tangent kemne:: Convergence and generalization in neural networks. In Advances in neural information processing systems, pages 8571-8580, 2018.
[23] Samet Oymak and Mahdi Soltanolkotabi. Overparameterrized nonlinear learning: Gradient descent takes the shortest path? In International Conference on Machine Learning, pages 4951-4960. PMLR, 2019.
[24] Samet Oymak and Mahdi Soltanolkotabi. Towards moderate overparameterization: global convergence guarantees for training shallow neural networks. IEEE Journal on Selected Areas in Information Theory, 2020.
[25] Simon Du, Jason Lee, Haochuan Li, Liwei Wang, and Xiyu Zhai. Gradient descent finds global minima of deep neural networks. In International Conference on Machine Learning, pages 1675-1685. PMLR, 2019.
[26] Sanjeev Arora, Simon S Du, Wei Hu, Zhiyuan Li, and Ruosong Wang. Fine-grained analysis of optimization and generalization for overparameterized two-layer neural networks. In 36th International Conference on Machine Learning, ICML 2019, pages 477-502. International Machine Learning Society (IMLS), 2019.
[27] Sam Buchanan, Dar Gilboa, and John Wright, Deep networks and the multiple manifold problem. In International Conference on Learning Representations, 2021.
[28] Zixiang Chen, Yuan Cao, Difan Zou, and Quanquan Gu. How much over per-paramtterizaiionn is suf- ficient to learn deep re [lu} networks? In International Conference on Learning Representations, 2021.
[29] Song Mei. Andrea Montanari, and Phan-Minh Nguyen. A mean field view of the landscape of two-layer neural networks. Proceedings of the National Academy of Sciences, 115(33):E7665- E7671, 2018
[30] Lénaïc Chizat and Francis Bach. On the global convergence of gradient descent for over- parameterized models using optimal transport. In S. Bengio, H. Wallach, H. Larochelle, K. Grauman, N. Cesa-Bianchi, and R. Garnett, editors, Advunces in Neural Information Pro- cessing Systems, volume 31, pages 3036-3046. Curran Associates, Inc., 2018.
[31] Song Mei, Theodor Misiakiewicz, and Andrea Montanari. Mean-field theory of two-layers neural networks: dimension-free bounds and kernel limit. In Conference on Learning Theory, pages 2388-2464. PMLR, 2019.
[32] Adel Javanmard, Marco Mondelli, Andrea Montanari, et al. Analysis of a two-layer neural network via displacement convexity, Ann. Statist., 48(6):361933422 2020.
[33] Justin Sirignano and Konstantinos Spiliopoulos. Mean field analysis of neural networks: a central limit theorem. Stochastic Processes Appl., 13003): 2020.
12

---

[34] Lénaïc Chizat, Edouard Oyallon, and Francis Bach. On lazy training in differentiable program ming. Advances Neural Information Processing Systems, 32:2937-2947, 2019.
[35] Gene Golub and Charles F. Van Loan. Matrix computations. Baltimore, MD: The Johns Hopkins Univ. Press, 1996.
[36] Mark A Davenport and Justin Romberg. An overview of low-rank matrix recovery from incomplete observations. IEEE Journal of Selected Topics in Signal Processing. 10(4):608-62) 2016.
[37] Emmanuel Candès and Yaniv Plan. Tight oracle inequalities for low-rank matrix recovery from a minimal number of noisy random measurements. IEEE Trans. Inf. Theory, 57(4):2342-2359, 2011.
[38] Yuanzhi Li, Tengyu Ma, and Hongyang Zhang. Algorithmic regularization in over-ovvennnnee over-parameterized matrix sensing and neural networks with quadratic activations. volume 75 of Proceedings of Machine Learning Research, pages 2-47. PMLR, 06-09 Jul 2018.
[39] Martin Slawski, Ping Li, and Matthias Hein. Regularization free estimation in trace regression with symmetric positive semidefinite matrices. Advances in Neural Information Processing Systems, 28:2782-2790, 2015.
[40] Roman Vershynin. Fligh-dimensional probabilit: An introduction with applications in data science, volume 47. Cambridge university press, 2018.
[41] Srinadh Bhojanapalli, Behnam Neyshabur, and Nati Srebro. Global optimality of local search for low rank matrix recovery. 29, 2016.
[42] Ji Chen, Dekai Liu, and Xiaodong Li. Nonconvex rectangular matrix completion via gradient descent without f,, oo regularization. IEEE Trans. Inf. Theory, 6669),5806-584,, 2020.
[43] Emmanuel J. Candès and Benjamin Recht. Exact matrix complction via convex optimization. Found. Comput. Math., 966)717-777 2009.
[44] Ali Ahmed, Benjamin Recht, and Justin Romberg. Blind deconvolution using convex program- ming. IEEE Trans. Inf. Theory, 6013):17 2014.
13


Reviews:
[{"review_id": "x-ofHxgU88r", "reviewer": "Reviewer_pNVA", "summary": "This paper takes an initial step to explain why small random initialization followed by a few iterations gradient descent on non-convex optimization can often converge to a global minimum point with also good generalization ability. Specifically, this paper focuses on low-rank matrix recovery, a highly non-convex optimization problem with spurious local optimal points, and shows that: (1) This method has similar behavior to the popular spectral methods with three phases—a spectral or alignment phase, a saddle avoidance/refinement phase, and a local refinement phase. (2) Larger parameter space tends to have a larger spectral bias which helps convergence to a global optimal point with also smaller generalization error. ", "questions": "", "limitations": "", "rating": 7, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Originality: This work is original as it explains a phenomenon that is not explained well before. \n\nQuality: The submission is technically sound. The claims are well supported by theoretical analysis and experimental results. Appropriate methods are used. This is a complete work. Both the strengths and weaknesses of their work are explained.\n\nClarity: The submission is generally clear and well organized, but some points need explanation as pointed out in advice and questions below. \n\nSignificance: This paper takes an initial and important step to explain why small random initialization followed by a few iterations gradient descent on non-convex optimization can often converge to a global minimum point with also good generalization ability. This work only focuses on the low-rank matrix reconstruction problem and an important future direction is to extend to other non-convex optimization problems, so I think this work will perhaps be cited. \n\nAdvice and questions: \n(1) What is the power method? You may give more explanation or citations. \n\n(2) Typo in the last paragraph of Section 1: Use “as long as” in “This holds as long the measurement operator obeys a popular restricted isometry property”. \n\n(3) In Section 2, you might add application examples of (1) and explain the meanings of $y_i$, $A_i$, $XX^{\\top}$ in the examples. You may also list some applications in the introduction. \n\n(4) What does $\\mathcal{A}^*$ mean in the gradient descent equation below eq. (2)? Also, since $X$ is unknown while $y_i$ is known, why not using $y_i$ instead of $X$ in the update rule? \n\n(5) You put the case of $r\\ge 2r_*$ to the main text and $r\\ge r_*$ including two special cases into the appendix. Why is the former more important? \n\n(6) In Theorem 3.3, can the probability $1-Ce^{-\\widetilde{c}r}$ get arbitrarily close to 1? Does it rely on $\\alpha$? \n\n(7) How does eq. (6) relate to the equation between eqs. (4) and (5)? For example, does eq. (6) imply that equation? You might well explain that around eq. (6). \n\n(8) In Phase II, the $r_*$-th eigenvalues will align. How does that relate to saddle avoidance? Also, $\\alpha\\propto \\sigma_{r_*}(U_0) \\ll \\mathcal{O}[\\sigma_{\\min}(X)]$ yes? If so, I did not see something like $\\alpha\\le \\mathcal{O}[\\sigma_{\\min}(X)]$ in eq. (4). Could you explain? \n\n(9) What’s the value of r for Figure 2? \n\n(10) You said “We note that while all experimental depictions are based on a single trial, in line with the NeuRIPS guidelines we have drawn these curves multiple times (not depicted) and the behavior of the plots do not change. ” Have you tried multiple initializations of U? Do they have almost overlapping curves? \n\n(11) In your paragraph beginning with “Evolution of the test error and the refinement phase”, eq. (6) might also be used to explain the result. \n\n(12) In Figure 3, you might also add the plot of computation complexity (iteration number $\\times$ number of flops or involved entries per iteration) VS r. This may help us select proper r in practice I think.  \n\n(13) In Figure 4, you may also add the plot of the number of iterations/computation complexity VS alpha. Hopefully the iteration number is proportional to $\\ln(1/\\alpha)$. Also, there is a typo in the caption—“relative”. \n\n(14) You could add a sentence like “We depict the results in Figure 5.” to the final paragraph.\n\n(15) For Figure 5b, is the initial point already close to a local minimum point? (computing gradient norm might be helpful) How about trying more initial points with alpha=1? ", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "This work points out its limitation that the sample complexity has sub-optimal dependence on $r_*$. Also, I think this work could be generalized into more non-convex optimization problems in the future. This work simply points out that “As with other technologies such insights may potentially also be used nefariously. ”", "review_text": "", "extra_scores": {"ethical_concerns": "I did not see any ethical concerns arising from this theoretical work. ", "needs_ethics_review": "No", "ethics_review_area": ["I don’t know"], "time_spent_reviewing": "About 4 hours"}, "extra_text": {}}, {"review_id": "nKd9zfxGVB2", "reviewer": "Reviewer_SPzT", "summary": "This paper studies both the optimization and the generalization of the non-convex overparameterized low-rank matrix reconstruction problem, showing that the small (random) initialization plays an important role. In detail, they divided the dynamic into three phases, in the first phase the eigenspace gradually aligns with the ground truth; the second phase is the saddle avoidance/refinement phase; and the last phase is the local convergence period.", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "This paper is very solid, extending previous Li et al. [1]'s result in the case that the overparameterized model U is $d*r'$ instead of $d*d$. However, this result is not interesting now. The small initialization has been well studied in different areas (e.g. low rank matrix recovery, tensor decomposition, linear neural network and so on). Also, compared to Li et al. [1]'s result, their result seems to be only a marginal improvement. The detailed comments are provided as following:\n1. Why we need to have the first two phases? Is it because some technical reason? For me there is only one phase: the eigenspace aligns to the ground truth and the minimum eigenvalue converges to the ground truth. Also, it is quite confusing for me that why the second phase named \"saddle avoidance/refinement phase\". I cannot see any intuition why and how GD avoid this from the main body.\n2. From Figure 2, the distance measure between the two eigenspaces will decrease first and then increase again. This is very strange to me. My guess is that this comes from the \"ground truth\" you chosen, $A^*A(XX')$ instead of $XX'$. Will this re-increasing phenomenon effect the proof? Or what if directly measure the distance compared to $XX'$.\n3. As you mentioned in line 236-237, the behavior of the plots do not change. Do you running different initialization or choose different Gaussian (symmetric) measurement matrices? For me, it is quite strange that the behaviors with different random seed are exactly the same.\n4. It seems this result also needs early stopping. Is there any way to show that the generalization won't blow up again like in [2]?\n\n[1] Yuanzhi Li, Tengyu Ma, and Hongyang Zhang. Algorithmic regularization in over-parameterized matrix sensing and neural networks with quadratic activations. In Conference On Learning Theory, pages 2–47. PMLR, 2018.\n[2] Jiacheng Zhuo, Jeongyeol Kwon, Nhat Ho, and Constantine Caramanis. On the computational and statistical complexity of over-parameterized matrix sensing. arXiv preprint arXiv:2102.02756, 2021.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes", "review_text": "", "extra_scores": {"ethical_concerns": "No", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "24 hours"}, "extra_text": {}}, {"review_id": "LuLGd6g36S", "reviewer": "Reviewer_UAzE", "summary": "The authors study the nonconvex approach to the positive semidefinite (PSD)\nmatrix sensing problem, a much-studied model problem for tractable nonconvex\noptimization in the literature. Specifically, they consider the\n\"overparameterized\" version of this problem: there is an unknown ground truth\nfactor matrix $X \\in \\mathbb{R}^{n \\times r_{\\star}}$ which one observes through\nlinear measurements $\\mathcal{A}(X X^T) \\in \\mathbb{R}^m$; one seeks to find\n$X$ by minimizing the nonconvex objective $U \\mapsto (1/4) \\\\| \\mathcal{A} (\nUU^T - XX^T) \\\\|^2$ ($\\ell^2$ norm) using randomly-initialized gradient descent\nfrom initialization $\\alpha U \\in \\mathbb{R}^{n \\times r}$ with $r \\geq\nr_{\\star}$,  where $\\alpha > 0$ is a small scale parameter (e.g. inverse\npolynomial in $n$) and $U$ is an i.i.d. gaussian matrix with entries of\nsuitable variance. The authors analyze this problem in the setting where the\nmeasurement operator $\\mathcal{A}$ has the RIP (e.g. enough gaussian\nmeasurements) and the general setting of $r \\geq r_{\\star}$; they prove that\ngradient descent recovers the true factor matrix $X$ up to symmetry to any\ndesired accuracy (measured in frobenius norm), where the precision is improved\nby decreasing the magnitude of $\\alpha$ (at the cost of a logarithmic gain in\nthe number of gradient descent iterations required) and with constants that\ndepend on the condition number of $X$ (Theorem 3.3). The approach to the proof\nis claimed as novel, with a connection made between overparameterization in\nthis model and the common spectral initialization schemes in use, and synthetic\nexperiments are presented that support the authors' separation of their\napproach to the convergence proof into distinct phases, and the predictions of\ntheir main theorem. \n\n", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "## Summary wrt rating\n\nThe paper provides new results on nonconvex gradient descent for PSD matrix\nsensing under an RIP property in the setting where the problem is\noverparameterized, and the proof techniques seem to reveal novel qualitative\ninsights into the behavior of the gradient descent algorithm in this\noverparameterized setting. Here, I found the simple experiments in Figures 4\nand 5 to be quite helpful illustrations. In a similar way, these results also\nseem to constitute a valuable contribution to the literature on provable\nguarantees for generic optimization methods (randomly initialized gradient\ndescent) on nonconvex problems. My rating reflects some issues with the paper,\nmostly around context wrt the literature and organization. Specifically,\nthe authors have submitted the \"full version\" of the paper as the supplementary\nmaterial -- I don't see anything wrong with this from a policy perspective, but\nthey seem to have not prepared the \"9 page\" version of this work very\ncarefully, to the extent that there are a number of omissions of highly related\nwork in both the introduction/motivation and in the presentation of the results\non overparameterized matrix sensing. This has the effect of making it seem like\nthe authors are unaware of these works, and seems to make it near-impossible to\nunderstand the precise contributions of the authors (wrt generality of their\nresult; sharpness of the rates; and insights in the proofs) relative to prior\nart as someone not actively working on matrix sensing/matrix completion problems. I will discuss these issues in detail below; I would expect to be able to\nraise my rating given their satisfactory resolution.\n\n## Context and contributions\n\nIt seems to me that the concrete contributions of the authors are: new results\nfor overparameterized PSD matrix sensing with RIP (global convergence; large\n$r$ allowed; possibly new rates); new qualitative insights into the behavior of\nrandomly-initialized gradient descent on this problem (with small\ninitialization); a novel contribution to the literature on guarantees for\nrandomly-initialized gradient methods (i.e. saddle-avoidance-free) on\nnonconvex problems. I find it somewhat unclear how most of the motivation in\nthe introduction connects to these contributions. I also find it challenging to\nappreciate these contributions from the current version of the submission due\nto omissions of comparisons to relevant prior works. I will give more details\nbelow.\n\n- The paper seems to be motivated from the idea that in *general ML theory\n  settings* with overparameterized models, there is a need to understand the\n  issues of \"small random initialization\" and generalization. I find this claim\n  incompletely justified here -- for example, there are a number of inverse\n  problems in the nonconvex optimization literature in which it is natural to\n  formulate the problem with a compact constraint set, where there is no natural\n  notion of \"small initialization\" (e.g. [2-5] below), and one instead uses a\n  random initialization or a data-driven initialization; similarly in practical\n  deep learning settings it seems like the standard initialization strategies\n  (e.g. \"He initialization\", etc.) lead to matrices with $\\Theta(1)$\n  operator norms, so it is not clear to me how these are \"small\". If the\n  authors want to motivate their work in this way (e.g. sentence at line 39),\n  it would seem appropriate to provide additional justification here.\n- The dichotomy outlined in the paragraph from lines 42-61 omits a significant\n  body of work on understanding structures in practical problems that enable\n  randomly-initialized gradient descent to succeed: for example, [1, 6-8] below\n  are relevant here. One could also argue that NTK analyses of deep learning\n  problems where generalization is established fall into this category, e.g.\n  [9-10] below, although these approaches do not proceed by a geometric\n  analysis. \n- In a similar vein, I do not understand why the authors have neglected to\n  discuss prior art on overparameterized PSD matrix sensing (including [1, 6,\n  8] below) in the introduction and related work, given its importance in\n  establishing the novelty of the authors' contributions. Footnote 1 seems\n  dubious to me in this connection.\n- The paragraph from lines 62-71 seems to be only tenuously related to the\n  paper's PSD matrix sensing setting. In particular, I had the impression that\n  \"beyond-NTK\" analyses of neural network training in the teacher-student setting were\n  more similar to high-order tensor decomposition problems than matrix sensing\n  under RIP (e.g. [11]), in particular requiring a specialized initialization\n  to work with sharp rates; and in general, these approaches seem to be\n  unsuitable for extension to non-shallow neural networks of the kind used in\n  practice (relevant to a \"guiding principle for practitioners\" in line 71). \n- In section 3, outside of a discussion of the sample complexity, the authors compare their result only to the cited reference\n  [20], which applies to a completely different initialization scheme. The\n  authors should compare here to relevant prior works in order to demonstrate\n  the novelty of their contributions: i.e. [1] below (this work seems extremely\n  relevant, and even offers a precedent for the authors' ideas about \"small\n  random initialization\" with $\\alpha$) and [6] below, plus other relevant\n  results. I would also think it appropriate, where possible, to compare to the\n  proof techniques employed in these works and point out any novelties of the\n  authors' approach in this context (e.g. specifically with regards to the\n  \"small initialization is akin to spectral learning\" claim, to demonstrate its\n  novelty in the authors' work -- naively, it seems to me that an idea similar to this is employed in [6], and boils down to gradient descent bringing the iterates into the 'basin of attraction' of good solutions without the need for targeted initialization. The same principle is at play in [5, 7] below).\n\nBecause of the amount of omitted discussion of relevant works in the PSD matrix\nsensing / nonconvex optimization literature, and the lack of convincing\nconnections between the overparameterized PSD matrix sensing problem and\ngeneral ML theory problems (e.g. deep learning theory, \"small random\ninitialization\" ubiquity), it would seem to me to be most appropriate to\nreplace the discussion of these latter issues in the intro with a more detailed\ndiscussion of the former. I also note that there seems to be a lot of\nadditional space available by reducing figures later in the paper to fit all\npanels onto one line, instead of two.  \n\n\n## References mentioned above\n\n[1] https://arxiv.org/abs/1712.09203\n\n[2] http://arxiv.org/abs/1206.5882\n\n[3] https://arxiv.org/abs/1511.03607\n\n[4] https://arxiv.org/abs/1906.02435\n\n[5] https://arxiv.org/abs/1901.00256\n\n[6] https://link.springer.com/article/10.1007/s10107-019-01363-6\n\n[7] https://arxiv.org/abs/1809.10313\n\n[8] https://arxiv.org/abs/2012.15467\n\n[9] https://openreview.net/forum?id=O-6Pm_d_Q-\n\n[10] https://openreview.net/forum?id=fgd7we_uZa6\n\n[11] https://arxiv.org/abs/2102.02410\n\n[12] https://arxiv.org/abs/2006.08857\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "5"}, "extra_text": {}}, {"review_id": "FFPpWey69uQ", "reviewer": "Reviewer_TBNY", "summary": "This paper studies the role of small random initialization followed by gradient descent in the setting of low-rank matrix sensing. Authors show that the trajectory of the gradient descent from small random initialization behaves similarly as spectral initialization in the initial stage, and then moves from degenerate saddle points and converges to the ground truth. Numerical experiments are provided to validate the theory.", "questions": "", "limitations": "", "rating": 7, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The paper is well-written and easy to read. It considers a basic problem, and shows interesting results about the role of random initialization followed by gradient descent. The literature review is comprehensive. Therefore, I'd like to see it accepted.\n\nBelow are some minor suggestions/questions:\n1. It would be better to provide more detailed informal high-level sketches for the last two stages in Section 4.\n2. For the over-parameterized case, it seems that the iterate need to be singular in order for the matrix estimator to be close to the ground truth. Does this affect the convergence rate of vanilla gradient descent? It might be better to add a few discussions.\n\nTypo:\nA transpose seems to be missing in equation (1)", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4"}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper provides and analyzes a setting where small random initialization has a certain implicit spectral bias.  Reviewers are positive and I recommend acceptance.  That said, the reviewers had many detailed concerns, which led to extensive feedback discussions as below; I request the authors address these points carefully in their revisions.
Decision: Accept (Poster)