Gradient Descent for Deep Matrix Factorization: Dynamics and Implicit Bias towards Low Rank

Introduction

Deep learning has become the standard machine learning technology in recent years, celebrating breakthroughs in many areas ranging from face recognition over medical imaging to autonomous driving. Despite all its successes it is still mysterious why deep learning works so well. Often deep neural networks have significantly more parameters than the number of examples used in training. As studied systematically via numerical experiments, for instance in , (stochastic) gradient descent usually results in zero training error so that the resulting neural networks interpolate the training samples exactly. Nevertheless and somewhat surprisingly, the trained deep networks generalize very well, although classical statistics would suggest that one is in a regime of overfitting. It was remarked already in that the employed optimization algorithms induce an implicit bias towards certain solutions. Apparently, those solutions often behave very nicely in realistic situations. Providing an understanding of the nature of such implicit bias seems to be a key task for the development and understanding of deep learning in general. While a general theory for the implicit bias in deep learning seems presently out of reach, first theoretical works concentrate on linear networks and suggest that (stochastic) gradient descent converges to a linear network, i.e., a linear function described by a matrix, which is of low rank. Nevertheless, even for the linear case, the settings considered in these works are rather restrictive and many open questions remain.

The optimization problem (2) is normally solved via variants of (stochastic) gradient descent (using back propagation). As already described above, this often leads to decent solutions, even in the overparametrized setting and a recent research hypothesis claims an implicit bias of gradient descent towards low-complexity solutions – although no regularization term is added to (2). It was observed in that early stopping may produce beneficial solutions while omitting unfavorable local and global minima. Since (2) is hard to analyze in general due to the non-linear structure of (1), recent theoretical works concentrate on the simplified case of linear neural networks , where $\sigma(x)=x$ and $b_{k}=0$, i.e., (1) becomes

Choosing $\mathcal{L}$ to be the quadratic loss, equation (2) then takes the more accessible shape

Hence, we are interested in analyzing the discrete dynamics defined by

for $j\in[N]:=\left\{1,\dots,N\right\}$, where

$\eta>0$ is the step-size, $W_{0}$ is some initialization matrix, and $\alpha>0$ is assumed to be small. Note that the gradient of $\mathcal{L}$ with respect to a single factor $W_{j}$ is given by

We derive a sharp upper bound on the step size $\eta$ ensuring convergence, for all choices of $\alpha$ and $N$.

We only assume symmetry of the ground-truth, which is considerably weaker than the often used assumption of positive semidefiniteness (PSD).

We prove that negative eigenvalues can only be recovered under a suitable perturbation of the initialization. This has not yet been discussed in the standard setting of identity initialization since the prior works only consider positive semi-definite ground-truths, cf. Table 2.

Our main results consist of three central observations (note that we always use explicit constants in the statements).

I. Recovery of positive eigenvalues: Initializing with $W_{0}=I$, as done in in a matrix sensing framework, the dynamics in (6)-(7) can solely recover non-negative eigenvalues of $\widehat{W}$. In addition, the following theorem provides a quantitative analysis that shows how fast eigenvalues of $\widehat{W}$ are approximated depending on their magnitude and other model parameters like $N$, $\eta$, and $\alpha$.

for all $k\geq T^{\operatorname{Id}}_{N}(\lambda_{i},\varepsilon,\alpha,\eta)$, where $T^{\operatorname{Id}}_{N}$ is defined in (24) below.

The proof of Theorem 1.1 is given in Section 2.1.

The exact form of $T_{N}^{\text{Id}}$ involves some additional notation, which will be introduced later, see (24). Let us nevertheless give some simplified approximate expressions in the relevant case that $N\geq 3$, $0<\varepsilon^{N}\ll\lambda_{i}\leq\lambda_{1}$ and $0<\alpha^{N}\ll\lambda_{i}$, so that the initial matrix $W(0)=\alpha^{N}{\operatorname{Id}}$ has small enough spectral norm compared to the $i$-th eigenvalue of the ground truth, which in turn is larger than the desired accuracy $\varepsilon^{N}$. In this case $M=\|\widehat{W}\|^{\frac{1}{N}}=\lambda_{1}^{\frac{1}{N}}$ and we assume that

for some $\kappa\leq\frac{1}{3}$ so that (10) is satisfied. The quantity $T^{\operatorname{Id}}_{N}$ then takes the form (the interested reader is referred to the more detailed derivation and discussion in Appendix A)

where we ignore the additional term $s_{N}(\lambda_{i},\alpha)$ appearing in (24) since it is neglectable for small $\kappa$ and large $N$ (and probably resembles a proof artefact). As (12) shows, $T^{\text{Id}}_{N}$ consists of two main terms. One depends on the ratio between $\lambda_{i}$ and $\lambda_{1}$ and one on the desired accuracy $\varepsilon$. $T^{\text{Id}}_{N}$ increases for smaller $\lambda_{i}$ and $\varepsilon$.

II. Recovery of arbitrary eigenvalues: Perturbing the initialization slightly, i.e., setting

allows the dynamics in (6) to recover the whole spectrum of $\widehat{W}$, cf. Figure 1(b). This suggests that the spectral cut-off observed in Theorem 1.1 is a pathological case and thus hardly observed in practice. As before, the following theorem also quantifies the approximation rates of eigenvalues of $\widehat{W}$ in terms of their magnitude, their sign, $N$, $\eta$, $\alpha$, and $\beta$.

then $W({k})$ converges to $\widehat{W}$. Moreover, the error $E({k})=(V^{\top}W({k})V-\Lambda)$ is a diagonal matrix, whose entries satisfy

for all $\varepsilon\in(0,|\lambda_{i}|^{\frac{1}{N}})$, and

where $T^{{\operatorname{Id}}}_{N}$ is defined in (24).

The proof of Theorem 1.3 is given in Section 2.2.

such that $c^{2N-2}\leq c^{2N}\leq(N+1)^{2}$. Consequently, we obtain for $\alpha<1$ that

Let us finally mention that the condition $0<\frac{\beta}{c-1}<\alpha$ is used to simplify parts of the argument. Numerical simulations suggest that it is an artifact of the proof ; $0<\beta<\alpha$ is empirically sufficient.

III. Implicit bias towards low-rank: Theorems 1.1 and 1.3 suggest an implicit rank regularization of the gradient descent iterates $W({k})$ if we stop at some appropriate finite $k$, since dominant eigenvalues will be approximated faster than the rest of the spectrum. The discussion in Section 3 — in particular, Theorems 3.1 (gradient flow, $N=2$) and 3.5 (gradient descent, $N\geq 2$) — makes this precise by showing that the effective rank (a generalized notion of rank) of the iterates $W({k})$ first drops to one and then monotonously increases, plateauing on the effective rank levels of various low-rank approximations of $\widehat{W}$, cf. Figure 3. Theorems 3.1 and 3.5 explicitly characterize the time intervals during which the effective rank of $W({k})$ remains approximately constant.

In addition to those highlights, we provide numerical evidence supporting the theory and simulations in more general settings suggesting that our observations are not restricted to matrix factorization with symmetric ground truths. The organization of the paper is as follows: Section 2 contains the core analysis including a quantitative description of the dynamics in (6)-(7), both for the identical and the perturbed initialization. Building upon those results, Section 3 then deduces an implicit low-rank bias of gradient descent and compares theoretical predictions to actual numerical outcomes. Finally, we present in Section 4 additional numerical simulations in more general settings and discuss future work in Section 5.

2 Related Work

Linear multilayer neural networks and related optimization problems have been investigated in several works . In particular, it has been shown in (extending ) that the gradient flow minimizing $L(W_{1},\ldots,W_{N})=\frac{1}{2}\|Y-W_{N}\cdots W_{1}X\|_{F}^{2}$, i.e., learning deep linear networks, converges to a global minimizer for almost all initializations.

In the authors consider the problem of recovering a symmetric, positive matrix $X$ of low rank from incomplete linear measurements $y=\mathcal{A}(X)$. They are able to show that gradient descent on the factorized problem $L(W_{1})=\frac{1}{2}\|y-\mathcal{A}(W_{1}W^{T}_{1})\|_{2}^{2}$ converges to the ground truth if a restricted isometry assumption holds for $\mathcal{A}$. While this seems to suggest a bias of gradient descent towards low-rank solutions, the conclusion is questionable because restricting the linear system $y=\mathcal{A}(W)$ to positive semidefinite matrices $W$ often means that $X$ is the unique solution if $y=\mathcal{A}(X)$ for a low rank matrix $X$ .

Early stopping of gradient descent in deep learning has been investigated in a number of contributions, see e.g. . It may be interpreted as bias-variance trade-off . In the context of neural tangent kernels, shows that when the width of network becomes infinite, the convergence rate of gradient flow is faster for eigenspaces with larger eigenvalues. Hence, early stopping may seem appealing for applications where only few major features are required. In fact, early stopping is intertwined with the idea of implicit bias, as we will discuss later in our paper.

3 Notation

We abbreviate $[n]:=\left\{1,...n\right\}$. We denote matrices by uppercase letters and scalars by lowercase letters. Norms that frequently appear are the operator norm (spectral norm) $\|A\|=\sup_{\|x\|_{2}=1}\|Ax\|_{2}$, the Frobenius norm $\|A\|_{F}=(\sum_{j,k}|A_{j,k}|^{2})^{1/2}=\sqrt{\text{tr}(A^{T}A)}$, and the nuclear norm $\|\cdot\|_{*}=\sum_{j}\sigma(A)_{j}$, where $\sigma(A)_{j}$ are the singular values of $A$. Throughout the paper, $\alpha$ represents the initialization, $\eta$ the step size, and $N$ the depth of the matrix factorization. For a real number $a$, we denote $a_{+}=\max\{0,a\}$.

The Dynamics of Gradient Descent

The goal of this section is to derive precise bounds on the full trajectory of the gradient descent iterations $W({k})$ defined in (6) for the quadratic loss function (8) where $\widehat{W}$ is assumed to be a symmetric ground truth matrix. We first choose a small positive multiple of the identity as initialization of all factor matrices. However, we will see that we cannot recover negative eigenvalues of $\widehat{W}$ with such initialization. To mend this, we will consider then a slightly modified initialization, which guarantees recovery of the ground truth $\widehat{W}$ in the limit as ${k}\to\infty$, and characterize also the dynamics in this case.

We start by observing that the dynamics of the different eigenvalues decouple when initializing with the same multiple of the identity matrix. A similar result and proof has already appeared for the underlying gradient flow in [9, Section E.1].

Let $(W_{j}({k}))_{j=1}^{N}$ be the solution to the gradient descent (6) with identical initialization (7) and let $\widehat{W}=V\Lambda V^{T}$ be an eigenvalue decomposition of the symmetric ground truth matrix (where $V$ is orthogonal). Then the matrices $D_{j}({k}):=V^{\top}W_{j}({k})V$ are real, diagonal and identical, i.e., $D_{j}({k})=D({k})$ for all $j$ for some $D({k})$, and follow the dynamics

By orthogonality of $V$ this shows that $D_{j}(k+1)=D(k+1)$ so that the induction step is completed. ∎

Due to the previous decoupling lemma it suffices to analyze the dynamics of each diagonal entry of $D({k})$ separately. Denoting by $\lambda$ an eigenvalue of the ground truth matrix $\widehat{W}$ the corresponding diagonal element $d({k})$ of $D({k})$ evolves according to the equation

The following lemma describes the convergence of $d$ in (18). It extends [9, Lemma 1] to negative choices of $\lambda$ and to the case $\lambda\leq\alpha$. Note that the proof is fundamentally different from the one presented in .

If $N=1$ and $\eta\in(0,1)$, then $d$ converges to $\lambda$ linearly, i.e.,

then $\lim_{{k}\to\infty}d({k})=\lambda_{+}^{\frac{1}{N}}=\max\{\lambda,0\}^{\frac{1}{N}}$. Moreover, the error $|d({k})^{N}-\lambda_{+}|$ is monotonically decreasing and, for all ${k}\geq 0$, one has that $d({k})\in[\alpha,\lambda^{\frac{1}{N}}]$ if $\lambda\geq\alpha^{N}$, and $d({k})\in[\lambda_{+}^{\frac{1}{N}},\alpha]$ if $\lambda<\alpha^{N}$.

Note that the proof of Lemma 2.2 shows that the sequence $d({k})$ is monotonically increasing for $\lambda>\alpha$ and monotonically decreasing for $\lambda<\alpha$. We will repeatedly make use of this observation in the following.

For $N=1$ the computation is straight-forward and follows by induction. For $N\geq 2$ we need to make a case distinction with four cases that depend on the sign and the magnitude of $\lambda$. This is due to the fact that the sign of $\lambda$ determines the limit of $d$, while the magnitude of $\lambda$ determines whether $d$ is increasing or decreasing in time.

Let $N\geq 2$. Before diving into the case distinction, let us define, for $|\lambda|^{\frac{1}{N}}>\alpha$, the function

and observe that $d({k}+1)=g(d({k}))$. For $x\in[0,|\lambda|^{\frac{1}{N}}]$, $z=x/|\lambda|^{1/N}\in$ and $\sigma=\operatorname{sign}(\lambda)$ its derivative satisfies

where we used that $z\in$. By the assumption on $\eta$ it follows that $g^{\prime}(x)\geq 0$ for all $x\in[0,|\lambda|^{\frac{1}{N}}]$ and, hence, $g$ is monotonically increasing on that interval. We can now distinguish the four cases defined by $\lambda\geq 0$/$\lambda<0$ and $|\lambda|^{\frac{1}{N}}>\alpha$/$|\lambda|^{\frac{1}{N}}\leq\alpha$.

For $\lambda\geq 0$ and $|\lambda|^{\frac{1}{N}}\leq\alpha$, we show by induction that $d({k})$ remains in the interval $[\lambda^{\frac{1}{N}},\alpha]$ and is monotonically decreasing in ${k}$, which implies that the error $|d({k})^{N}-\lambda|$ is monotonically decreasing. For ${k}=0$, the claim is trivially fulfilled. If $d({k})\in[\lambda^{\frac{1}{N}},\alpha]$, then $d({k})^{N}-\lambda\geq 0$ so that $d({k}+1)\leq d({k})\leq\alpha$. Moreover, if $\lambda>0$

since $d({k})\geq\lambda^{\frac{1}{N}}$ and by assumption on $\eta$. If $\lambda=0$, then

since $d({k})\geq 0$ and by assumption on $\eta$. Hence $d({k}+1)\in[\lambda^{\frac{1}{N}},\alpha]$. Here we have a bounded decreasing sequence, and hence it must converges to the only fixed point in the domain, which is $\lambda^{\frac{1}{N}}$.

Finally, consider $\lambda<0$ with $|\lambda|^{\frac{1}{N}}\leq\alpha$. If $d({k})\in[0,\alpha]$, then $d({k}+1)\leq d({k})\leq\alpha$. Moreover,

by the assumption on $\eta$. Hence $d({k}+1)\in[0,\alpha]$. This means that the error $|d({k})^{N}-0|$ is monotonically decreasing. Here we have a bounded decreasing sequence, and hence it must converges to the only fixed point in the domain, which is . ∎

Lemma 2.2 shows that in the presence of matrix factorization, i.e., $N\geq 2$, gradient descent with identical initialization loses its ability to recover negative eigenvalues and the condition on the constant $\alpha$ in the initialization becomes more restrictive. (The condition on $\eta$ becomes either more or less restrictive depending on $|\lambda|$.) Note that Lemma 2.2 only provides a sufficient condition on the stepsize $\eta$ for convergence. However, this condition is basically necessary up to the constant, see Lemma B.1 in Appendix B.

Having settled convergence, we will now analyze the number of iterations that are needed in order to reach an $\varepsilon$-neighborhood of $\lambda$. By Lemma 2.1, this forms the basis for analyzing the implicit bias of gradient descent (6) on the matrix factorized problem with $N\geq 2$. In order to state our theorem, we need to introduce a few quantities corresponding to certain numbers of iterations that are important in our subsequent analysis. For $\lambda>0$ and $\mu>0$ we define

The quantity $T^{{\operatorname{Id}}}_{N}(\lambda,\varepsilon,\alpha,\eta)$ estimates the required number of gradient descent iterations to reach a certain accuracy $\varepsilon\in(0,|\lambda_{+}^{\frac{1}{N}}-\alpha|)$ when starting with identical initialization with parameter $\alpha>0$ and using step size $\eta$. In particular, it illustrates that fine approximation of positive eigenvalues dominating $\alpha$ (fourth case) happens in two stages: to obtain a rough approximation a fixed number of iterations is necessary ($T_{N}^{+}$ does not depend on $\varepsilon$) while to obtain approximation of accuracy $\varepsilon\ll 1$ one needs an additional number of iterations depending on $\varepsilon$, cf. Figure 4. Note that Remark 1.2 already commented on the behaviour of $T^{\operatorname{Id}}_{N}$ in the most relevant fourth case, see also Lemma E.1.

With these definitions at hand we are ready to state the first core result. Note that the third case $c_{N}\lambda<\alpha^{N}\leq\lambda$ together with the general assumption $\varepsilon\in(0,|\lambda_{+}^{\frac{1}{N}}-\alpha|)$ implies that $\varepsilon<(1-c_{N}^{\frac{1}{N}})\lambda^{\frac{1}{N}}$.

Further, let $\varepsilon\in(0,|\alpha-\lambda_{+}^{\frac{1}{N}}|)$ be the desired error and $T=\min\{{k}:|d({k})-\lambda_{+}^{\frac{1}{N}}|\leq\varepsilon\}$ be the minimal number of iterations to achieve such error bound. Then

Moreover, in the case $\lambda>\alpha^{N}$ we have the lower bound

The proof of Theorem 2.4 uses the following two lemmas. The first analyzes the continuous analog of (18), namely the gradient flow following the differential equation obtained by letting the step size $\eta$ tend to zero, i.e.,

The gradient flow defined by (28) has the following solution. If $\lambda=0$ then

If $\lambda>0$ then the solution is given implicitly by

For $N=1,2$ and $\lambda\neq 0$ we can also give the solution of (28) in explicit form,

The solution for $N=2$ has been derived already in . Let us also mention that, for $N\geq 3$, the solution can be expressed in an alternative way avoiding the use of complex logarithms. For details, see Appendix C.

If $\lambda=0$, or $\lambda\neq 0$ and $N=1$, it is easy to verify the stated solutions.

Let now $\lambda>0$ and $N\geq 2$. The differential equation (28) is separable, hence its solution $y(t)$ satisfies

the complex roots of $\lambda$. A partial fraction decomposition gives

Hence, for $N\geq 3$ the solution $y(t)$ satisfies

If $N=2$ then the roots $r_{2,1}=-\lambda^{1/2}$, $r_{2,2}=\lambda^{1/2}$ are real and the solution $y(t)$ satisfies

By the definition of $U^{+}_{N}$ this completes the proof. ∎

The second lemma required for the proof of Theorem 2.4 links the continuous dynamics in (28) to the discrete dynamics in (18). Although a result of this form might exist already, we include the full proof for the reader’s convenience.

We first show by induction that $d({k})\leq d^{*}({k})$ for $0\leq{k}\leq T/\eta$. The claim clearly holds for ${k}=0$. Now assume that it holds for some ${k}$ such that $\eta({k}+1)\leq T$. We aim at proving the claim for ${k}+1$. Since $f(x)f^{\prime}(x)\geq 0$ for $x\in I$ and $y({t})\in I$ for ${t}\in[0,T]$ we have

Hence, $y$ is convex on $[0,T]$ and therefore, $y(\eta(k+1))\geq y(\eta k)+\eta y^{\prime}(\eta k)=y(\eta k)+\eta f(y(\eta k))$ and $y(\eta k)\geq y(\eta(k+1))-\eta f(y(\eta(k+1)))$ so that by definition of $d^{*}$

The definition of $d$ and the mean-value theorem together with (32) and $|f^{\prime}(x)|\leq K_{2}$ for all $x\in I$ imply that, for some $\xi$ between $d({k})$ and $d^{*}({k})$,

In the second inequality we have used the induction hypothesis that $d^{*}({k})-d({k})\geq 0$. This proves the first part of the lemma.

via induction. Note that $f$ is monotonously increasing on $I$ because $f(x)>0$ and $f^{\prime}(x)f(x)\geq 0$ by assumption. Since $d(s)\geq d(0)+s\eta f(\alpha)\geq d(0)+\eta K_{1}$ (by the monotonicity of $f$ as well as the definition of $d$ and $s$), we have

Let us now assume the claim (33) holds for ${k}$ with $d({k}+s)\in I$ and $d^{*}({k})\in I$. If $d^{*}({k}+1),d({k}+s+1)\in I$, the right hand inequality in (32) implies that

which implies $d^{*}({k})+\eta K_{1}\in I$. Hence, by the monotonicity of $f$ on $I$ we obtain

This completes the induction step and, hence, proves the inequality $d^{*}({k})\leq d({k}+s)$ whenever $d({k}+s)\in I$.

We first consider the case that $\lambda<0$. By our assumption (25) on the stepsize $\eta$ the conditions in Lemma 2.2 are satisfied so that $d({k})$ is monotonically decreasing and $d({k})\in[0,\alpha]$, for all ${k}\geq 0$. Let $g_{-}(x)=x+\eta\lambda x^{N-1}$ and define $d_{-}({k})$ as

Note that for $x\geq 0$ and $\lambda<0$ it holds $g(x):=x-\eta x^{N-1}(x^{N}-\lambda)\leq g_{-}(x)$. Recalling that $d({k}+1)=g(d({k}))$, we inductively conclude that $d({k})\leq d_{-}({k})$, for all ${k}\geq 0$. Let $y_{-}$ be the continuous analog of $d_{-}$, i.e., the solution of the differential equation

Define the discrete variable $d_{-}^{*}({k}):=y_{-}(\eta{k})$. We intend to apply Lemma 2.7 for $I=[0,\alpha]$, $f(x)=\lambda x^{N-1}$. Note that $f(x)f^{\prime}(x)=\lambda^{2}(N-1)x^{2N-1}\geq 0$, $|f(x)|\leq|\lambda|\alpha^{N-1}=:K_{1}$ and $|f^{\prime}(x)|\leq|\lambda|(N-1)\alpha^{N-2}=:K_{2}$ for $x\in I$. The assumption (25) on the stepsize implies that $\eta<1/K_{2}$ so that Lemma 2.7 yields $d_{-}({k})\leq d_{-}^{*}({k})$, for all ${k}\geq 1$. Hence, $d_{-}({k})\leq d_{-}^{*}({k})=y_{-}(\eta{k})\leq\varepsilon$ for ${k}\geq\frac{1}{\eta|\lambda|}T_{N}^{-}(\varepsilon,\alpha)$ by the definition of $T_{N}^{-}(\varepsilon,\alpha)$ and a short calculation using (34). We conclude that $T\leq\frac{1}{\eta|\lambda|}T_{N}^{-}(\varepsilon,\alpha)$.

We now consider the case $0\leq\lambda<\alpha^{N}$. By Lemma 2.2, $d({k})$ is monotonically decreasing and $d({k})\in[\lambda^{\frac{1}{N}},\alpha]$, for all ${k}\geq 0$. For $x\in[\lambda^{\frac{1}{N}},\alpha]$, the function $f(x)=-x^{N-1}(x^{N}-\lambda)$ satisfies $f(x)f^{\prime}(x)=(N-1)x^{2N-3}(x^{N}-\lambda)^{2}+Nx^{3N-3}(x^{N}-\lambda)\geq 0$ and $|f^{\prime}(x)|=(N-1)x^{N-2}(x^{N}-\lambda)+Nx^{2N-2}\leq(2N-1)\alpha^{2N-2}=:K_{2}$. By assumption (25), the stepsize satisfies $\eta<1/K_{2}$. Hence, we can apply Lemma 2.7 which gives $d({k})\leq d^{*}({k})=y(\eta{k})$, for all ${k}\geq 0$, where $y$ is defined by (28). By Lemma 2.5 and the observation that $y$ is monotonically decreasing for $\lambda\geq 0$ and $\lambda<\alpha^{N}$, we obtain that $y({t})\leq\lambda^{\frac{1}{N}}+\varepsilon$ for all ${t}\geq T_{N}^{+}(\lambda,\lambda^{\frac{1}{N}}+\varepsilon,\alpha)$ since $T_{N}^{+}(\lambda,\lambda^{\frac{1}{N}}+\varepsilon,\alpha)=U_{N}^{+}(\lambda,\lambda^{\frac{1}{N}}+\varepsilon)-U_{N}^{+}(\lambda,\alpha)$ and $y$ satisfies (28). Consequently, $d^{*}({k})\leq\lambda^{\frac{1}{N}}+\varepsilon$ for all ${k}\leq\frac{1}{\eta}T_{N}^{+}(\lambda,\lambda^{\frac{1}{N}}+\varepsilon,\alpha)$, which proves the claim for the case $0\leq\lambda<\alpha^{N}$.

Finally, consider $\lambda>\alpha^{N}$. The proof distinguishes two phases of the dynamics. In the first phase we use the associated continuous flow $y$ in (28) for the time where it is convex. For the following second phase, we directly work with the discrete dynamics. In order to make this distinction we use again the function $f(x)=-x^{N-1}(x^{N}-\lambda)$ so that $y^{\prime}({t})=f(y(t))$ and $d({k}+1)=d({k})+\eta f({k})$. Note that the function

satisfies $h(x)\geq 0$ for $x\in[0,\zeta]$ and $h(x)\leq 0$ for $x\in[\zeta,\lambda^{\frac{1}{N}}]$, where

This implies that $y$ is convex as long as $y({t})\in[0,\zeta]$ and concave when $y({t})\in[\zeta,\lambda^{\frac{1}{N}}]$. If $\varepsilon>\lambda^{\frac{1}{N}}-\zeta$ then $\alpha<\zeta$ by the assumption $\varepsilon\in(0,|\alpha-\lambda_{+}^{1/N}|)$ and the desired accuracy $\varepsilon$ is reached while the dynamics is still in the convex phase, i.e., $y({t})\in[\alpha,\zeta]\subset[0,\zeta]$. In this case, we define

Now assume $\varepsilon\leq\lambda^{\frac{1}{N}}-\zeta$. If $\alpha<\zeta$ then the dynamics starts in the convex phase, while it starts in the concave phase if $\alpha\geq\zeta$. Accordingly, we define

We start with bounding $T_{1}$. If $\alpha\geq\zeta$, then $T_{1}=0$ and we are done. In the case $\alpha<\zeta$, we intend to apply Lemma 2.7 for $I=[\alpha,\zeta]$, and $f(x)=-x^{N-1}(x^{N}-\lambda)$. Then $f(x)f^{\prime}(x)\geq 0$ for $x\in I$ as already noted above and $|f^{\prime}(x)|=|(N-1)x^{N-2}(\lambda-x^{N})-Nx^{2N-1}|\leq\lambda^{2-\frac{2}{N}}N=:K_{2}$, for all $x\in[0,\lambda^{\frac{1}{N}}]\supset I$, where the inequality follows similarly as in (21). By the assumption (25) on the stepsize we have $\eta<1/K_{2}$. Hence, by Lemma 2.7 we have $d({k})\leq d^{*}({k})\leq d({k}+s)$, where

Since $y$ is monotonically increasing for $\lambda>\alpha^{N}$, Lemma 2.5 implies that $T_{1}$ is lower bounded by $T_{N}^{+}(\lambda,\min\{\zeta,\lambda^{\frac{1}{N}}-\varepsilon\},\alpha)$ and upper bounded by $T_{N}^{+}(\lambda,\min\{\zeta,\lambda^{\frac{1}{N}}-\varepsilon\},\alpha)+s_{N}(\lambda,\alpha)$.

Now we consider the second phase where $d({k})\in[\zeta,\lambda^{\frac{1}{N}}]$ and define $\Delta({k})=\lambda^{\frac{1}{N}}-d({k})$ to be the difference to the limit $\lambda^{\frac{1}{N}}$. If $\varepsilon\geq\lambda^{\frac{1}{N}}(1-c_{N}^{1/N})=\lambda^{\frac{1}{N}}-\zeta$ then $T_{2}=0$. Therefore, we assume $\varepsilon\geq\lambda^{\frac{1}{N}}(1-c_{N}^{1/N})$ from now on. By Lemma 2.2, $d({k})$ is increasing and remains inside the interval $[\zeta,\lambda^{\frac{1}{N}}]$ for all ${k}\geq T_{1}$. A direct computation gives

The last equality follows from a straightforward calculation. Note that

In particular, $g$ is increasing on $[\zeta,\lambda^{\frac{1}{N}}]$. Note that, since $c_{N}<1$,

Note that $1-\eta N(c_{N}\lambda)^{2-\frac{2}{N}}\geq 1-\eta N\lambda^{2-\frac{2}{N}}>0$ by the assumption on $\eta$. Hence, $\Delta({k}+T_{1})\leq\varepsilon$ if

so that $T_{2}$ is bounded from above by the right hand side. In the case that $\alpha>\zeta$, we have $T_{1}=0$ and the inequality (37) can be improved to

For the lower bound, assume first that $\alpha<\zeta$. Then $T_{1}\geq 1$. and since $\alpha<\zeta$ it follows that $d(T_{1}-1)<\zeta$ so that by the assumption (25) on the stepsize $\eta$,

Observe that by (35) and (36), for all ${k}\geq 0$,

Hence, $\Delta({k}+T_{1})\geq\varepsilon$ for all

This implies that $T_{2}$ is lower bounded by the right hand side above if if $\alpha<\zeta$.

If $\alpha>\zeta$ then $T_{1}=0$ and $\Delta({k})\geq(1-\eta r_{2})^{k}\Delta(0)=(1-\eta r_{2})^{k}(\lambda^{\frac{1}{N}}-\alpha).$ Hence, $\Delta({k})\geq\varepsilon$ for all

Hence, $T_{2}$ is bounded from below by the right hand side of the above inequality.

Noting that $T=T_{1}+T_{2}$, collecting all the cases and comparing with the definition of $T^{\operatorname{Id}}_{N}(\lambda,\varepsilon,\alpha,\eta)$ and $s_{N}(\lambda,\alpha)$ completes the proof. ∎

The statement is an immediate consequence of Lemma 2.1 and Theorem 2.4 in Section 2.1, also noting that $\|\widehat{W}\|=\max_{i\in[n]}|\lambda_{i}|$. In particular, Theorem 2.4 yields that, for $\varepsilon\in(0,|\lambda_{i}|^{\frac{1}{N}})$,

The case $\lambda_{i}>0$ in (11) follows from the mean-value theorem applied to the function $h(\varepsilon)=(\lambda_{i}^{\frac{1}{N}}-\varepsilon)^{N}$. To be precise, there exists $\xi\in(0,\varepsilon)$ such that

2 Perturbed Identical Initialization

For $N\geq 2$, we have seen in the previous section that we cannot recover negative eigenvalues $\lambda$ of the ground truth matrix with gradient descent when identically initializing all matrices as $W_{1}(0)=\cdots=W_{N}(0)=\alpha I$. As already mentioned before, this problem can be overcome by slightly perturbing the constant $\alpha$ at one of the $N$ matrices. Instead of (7) we thus consider the mildly perturbed initialization

for some $0<\beta<\alpha$ (where one could think of $\beta$ much smaller than $\alpha$). We will call (13) perturbed identical initialization. The choice of $j=1$ for perturbing the constant $\alpha$ to $(\alpha-\beta)$ is generic. In light of the fact that slightly perturbing a single factor $W_{j}(0)$ suffices to recover the full spectrum, the spectral cut-off phenomenon in Theorem 1.1 appears to be a pathological case.

We can now turn to the proof of Theorem 1.3. Before stating the formal argument, let us provide a rough intuition on why a slight perturbation like in (38) makes such a difference: all squared singular values of all factors $W_{j}$ converge to the $N$-th root of the squares of the respective ground-truth eigenvalues, i.e., their limits coincide in absolute value. At the same time the gradient descent dynamics induce a repelling effect between the eigenvalues of differently initialized factors if the corresponding ground-truth eigenvalue is negative. The only way all factors can converge in this situation is that the perturbed factor converges to the negative $N$-th root of the ground-truth eigenvalue while the eigenvalues of all remaining factors stay positive. We begin by stating a modified version of the decoupling in Lemma 2.1.

The proof of Lemma 2.8 follows the lines of Lemma 2.1 and is thus omitted. Similar to (but not quite the same as) the case of identical initialization, the system can be reduced to the scalar dynamics

To further analyze the perturbed setting, we concentrate on three quantities: the difference $\Delta_{1}({k})$, the difference of squares $\Delta_{2}({k})$, and the rate factor $\kappa({k})$, defined as

Let $\eta>0$, $d_{1}({k}),d_{2}({k})$ be defined by (40) with the perturbed identical initialization (41), and let $\Delta_{1},\Delta_{2}$, and $\kappa$ be the quantities defined in (42). Then

and similarly $\Delta_{2}({k}+1)=[1-\eta^{2}\kappa^{2}({k})]\Delta_{2}({k}).$ This completes the proof. ∎

Due to the coupling of $d_{1}$ and $d_{2}$, we are not able to derive limits as previously done in Lemma 2.2. However, we can show in Lemma 2.12 below that the product $d_{1}({k})d_{2}({k})^{N-1}$ converges to $\lambda$ regardless of its sign. In order to keep the presentation concise, parts of the proof (treating positive $\lambda$) are deferred to Appendix D in form of Lemma D.2 and D.3.

For $\lambda<0$, which cannot be recovered with identical initialization, the key is the “phase transition” time ${k}_{0}$, defined by

where we use the convention that $\inf\emptyset=\infty$.

Let $N\geq 2$ and $\lambda<0$. Let $d_{1},d_{2}$ be defined by (40) with the perturbed identical initialization (41) and define $M=\max(\alpha,|\lambda|^{\frac{1}{N}})$. If

then ${k}_{0}$ defined in (46) is finite.

Let the difference $\Delta_{1}$ and the factor $\kappa$ be defined as in (42). We define the two auxiliary sequences

whose behavior is well-understood by Section 2.1, and we make the auxiliary claim that

Assume that ${k}<{k}_{0}$ for the moment. By the definition of ${k}_{0}$, we have $0\leq d_{1}({k})$. Furthermore, Lemma 2.2 implies that $a({k})\leq\alpha-\beta$ and $0<b({k})$. Note that due to $\lambda<0$ and $d_{1}({k})\geq 0$, $\kappa({k})\geq 0$ as long as $d_{2}({k})>0$. Since $d_{2}(0)=\alpha>0$, $\Delta_{1}(0)=\beta>0$ and $d_{2}({k})=d_{1}({k})+\Delta_{1}({k})$ it follows by induction from (45) in Lemma 2.9 that $\Delta_{1}({k})>0$, $d_{2}({k})>d_{1}({k})\geq 0$ and $\kappa({k})>0$ for all ${k}<{k}_{0}$. Therefore, $d_{1}({k})$ and $d_{2}({k})$ are monotonically decreasing in ${k}$ for ${k}<{k}_{0}$ by (40). Hence, $d_{1}({k})\leq d_{1}(0)=\alpha-\beta$ and $d_{2}({k})\leq d_{2}(0)=\alpha$, for ${k}<{k}_{0}$. In order to fully prove (50), we will show next that $d_{1}({k})\leq a({k})$ and $b({k})\leq d_{2}({k})$ by induction.

By construction $d_{1}(0)=\alpha-\beta=a(0)$ and $d_{2}(0)=\alpha=b(0)$. Assume that $d_{1}({k})\leq a({k})$ and $b({k})\leq d_{2}({k})$ for some ${k}<{k}_{0}-1$. Define $g(x)=x-\eta x^{N-1}(x^{N}-\lambda)$ as in the proof of Lemma 2.2. By a direct computation as in (21), $g^{\prime}(x)\geq 0$ for $x\in(0,M)$ because $\eta$ satisfies (47). Thus $g$ is monotonically increasing on $(0,M)$ and since $d_{1}({k}),d_{2}({k}),a({k}),b({k})\in(0,M)$

This completes the induction step and shows (50).

by assumption on $\eta$. By Lemma 2.9, $\Delta_{1}({k})=d_{2}({k})-d_{1}({k})$ is monotonically increasing while $\Delta_{2}({k})=d_{2}({k})^{2}-d_{1}({k})^{2}$ is monotonically decreasing. Consequently, we have

Since $d_{1}({k}),d_{2}({k})\geq 0$ and $\lambda<0$ this gives

then $\lim_{{k}\to\infty}d_{1}({k})d_{2}({k})^{N-1}=\lambda$.

Setting $\alpha_{0}:=d_{2}({k}_{0})$ and $\gamma_{0}:=d_{0}({k}_{0})=-d_{1}({k}_{0})>0$, and interpreting $\alpha_{0},\gamma_{0}$ as new initial conditions, the above system has the same form as (40) with $\lambda$ replaced by $|\lambda|>0$. According to Lemmas D.2 and D.3,

if $0<\gamma_{0}<\alpha_{0}\leq M$. It remains to verify the latter condition. Since $d_{1}({k}_{0}-1)$ and $d_{2}({k}_{0}-1)$ are positive, we have $d_{2}({k}_{0})\leq d_{2}({k}_{0}-1)$ according to the dynamics in (53). Together with the fact that $d_{2}$ is monotonically decreasing before this time, we deduce that $\alpha_{0}\leq\alpha\leq M$. Let the difference sequence $\Delta_{1}$ and the factor $\kappa$ be defined as in (42). Since $0<\eta\kappa({k})<1$, for ${k}<{k}_{0}$, cf. Equation (51), Lemma 2.9 states that $\Delta_{1}({k})>0$ is monotonically increasing, for ${k}<{k}_{0}$. In particular, $d_{2}({k}_{0}-1)-d_{1}({k}_{0}-1)=\Delta_{1}({k}_{0}-1)>0$ and we obtain

Hence the condition $0<\gamma_{0}<\alpha_{0}\leq M$ is satisfied. ∎

From a less technical point of view, Lemma 2.12 and its proof show that if $\lambda>0$, the dynamics is similar to the case of identical initialization. If $\lambda<0$, the dynamics is only similar up to the point where one of the components changes sign. Then, they start to behave as if $\lambda=|\lambda|$ and follow a mirrored trajectory of the identical initialization setting. We have all tools at hand to finally prove Theorem 1.3.

The convergence of $W({k})$ to $\widehat{W}$ directly follows from Lemma 2.8 and 2.12. For the rate of convergence, we will use Theorem 2.4 and Lemmas 2.9, 2.11, 2.12, D.2, D.3.

With $\lambda=\lambda_{i}$, let $d_{1},d_{2}$ be defined as in (40) and $a,b,p,p_{a},p_{b}$ as in (48), (49) and (69). Note that by Lemma 2.8, $E_{ii}({k})=p({k})-\lambda_{i}$. We distinguish the following cases.

Assume that $\lambda_{i}\leq-(\alpha-\beta)\alpha^{N-1}$. Let $\Delta_{1}({k})$, $\Delta_{2}({k})$ and $\kappa({k})$ be defined as in (42) with $\lambda=\lambda_{i}$. Let ${k}_{0}$ be the phase transition time defined in (46) at which $d_{1}$ becomes negative. We start with some useful observations.

For ${k}<{k}_{0}$, the sequences $d_{1},d_{2}$ are positive and decreasing by induction, i.e.,

Since $d_{1}(0)<d_{2}(0)<|\lambda_{i}|^{\frac{1}{N}}$, we have $d_{1}({k}),d_{2}({k})<|\lambda_{i}|^{\frac{1}{N}}$. Therefore

Note that $M=\max\{\alpha,\|\widehat{W}\|^{\frac{1}{N}}\}\geq|\lambda_{i}|^{\frac{1}{N}}$ together with Condition (14) on the stepsize implies that

for ${k}<{k}_{0}$. By Lemma 2.9, $\Delta_{1}$ is positive and increasing, while $\Delta_{2}$ is positive and decreasing in ${k}$. Thus $d_{2}({k})-d_{1}({k})>d_{2}(0)-d_{1}(0)=\beta$ and $d_{2}({k})^{2}-d_{1}({k})^{2}>0$ for ${k}<{k}_{0}$.

At the phase transition point ${k}_{0}$, since $d_{1}({k}_{0})<0\leq d_{1}({k}_{0}-1)$ and $d_{2}({k}_{0}-1)>d_{1}({k}_{0}-1)+\beta>\beta$, relation (56) yields

Now consider ${k}\geq{k}_{0}$ and recall from case (c) and the proof of Lemma 2.12, that the dynamics effectively becomes the one with $\lambda_{i}$ replaced by $|\lambda_{i}|$ by considering $(d_{0},d_{2}):=(-d_{1},d_{2})$ and with initializations $|d_{1}({k}_{0})|$ and $d_{2}({k}_{0})$.

To show our claim, it remains to characterize a time $T_{0}$ for which $d_{1}(T_{0})<-\beta$ and apply Theorem 2.4 as for the case (a) with $d_{0}(T_{0})>\beta$ as initial condition. This will give

Together with the lower bound in (58) this gives

Since $d_{1}(0)=\alpha-\beta$ it follows by induction that

Implicit Bias of Gradient Descent

The explicit characterization of gradient flow and gradient descent dynamics derived in Section 2 may be used to shed some light on the phenomenon of implicit bias resp. implicit regularization of gradient descent. In fact, different convergence rates for different eigenvalues (depending on their respective signs and magnitudes) result in matrix iterates of low effective rank and accurately explain the implicit regularization observed when applying gradient descent to matrix factorization of symmetric matrices. We expect that a similar reasoning to be valid in more general contexts beyond matrix estimation.

and $C>1$ may be chosen arbitrarily. Note, however, that $C$ influences Theorem 3.1 since it controls the trade-off between the size of $I_{3}$ and tightness of the bound.

for all ${t}\in I_{1}\cap I_{2}\cap I_{3}$.

where $g_{\lambda,\alpha}$ is defined in (60), we obtain, for ${t}\in I_{1}$, that

2 Gradient Descent

After the simpler analysis of gradient flow, we now deduce a corresponding statement for gradient descent from the results in Section 2. In contrast to Theorem 3.1, it holds for a general number of layers $N\geq 2$. As before, we remark that the statement can be extended in a straight-forward but tedious way to handle general symmetric ground truths and additive noise.

In order to obtain a simplified estimate, we can choose $\varepsilon^{\prime}$ and $\alpha$ depending on $\varepsilon$ and some of the eigenvalues of $\widehat{W}$ such that all three terms in (64) are bounded by $\varepsilon r(\widehat{W}_{L})$. Additionally, replacing $L^{\prime}-L$ by its upper bound $n-L$ and $n-L^{\prime}$ by its upper bound $n-L$ (so that $L^{\prime}$ and $L^{\prime\prime}$ are not needed for the estimate), this gives the choices

Of course, we may additionally set $\varepsilon=\delta/3$ for some desired accuracy $\delta\in(0,1)$ to obtain

Note in particular that (65) gives an indication on how to choose $\alpha$ (smaller values of $\alpha$ may also be fine). In particular, we require small enough initialization in comparison with the spectral norm $\|\widehat{W}\|=\lambda_{1}$.

Let us also remark that the lower bound (time needed to approximate the leading $L$ eigenvalues) in (63) may become larger than the upper bound (time in which the remaining eigenvalues of $W({k})$ stay small) for certain parameter choices, i.e., the time interval of values ${k}$ for which the theorem can make a statement becomes empty. This is to be expected if there is no gap between $\lambda_{L}$ and $\lambda_{L+1}$ since then $r(W({k}))$ never comes arbitrarily close to $r(\widehat{W}_{L})$ and the time interval is indeed empty, for small $\varepsilon$. Figure 3, however, shows that the theorem does provide non-empty time-intervals in relevant situations.

The estimate (63) in Theorem 3.5 for the time interval where the effective rank of $W({k})$ is close to the one of $\widehat{W}_{L}$ is slightly weaker than the ones in Theorem 3.1 and depends in terms of quality on the step-size $\eta$. Since gradient flow is at the core of the gradient descent analysis, the bounds on gradient descent are more accurate if gradient descent stays close to its continuous flow, which is rather the case for small choices of $\eta$ than for large ones. To make this more precise, for $\eta$ small, the gap between necessary and sufficient iteration bounds in Theorem 2.4 shrinks and the prediction accuracy improves. Figure 7(b) shows that Theorem 3.5 yields an accurate description of the effective rank behavior as long as the step-size is chosen sufficiently small and the eigenvalue gap between $\lambda_{L}$ and $\lambda_{L+1}$ is sufficiently large to guarantee that the feasible region in (63) is non-empty.

To prove Theorem 3.5, we need the following lemma which is a direct consequence of the considerations in Theorem 2.4. Recall $\zeta_{\lambda}=(c_{N}\lambda)^{\frac{1}{N}}=\sqrt[N]{\lambda\frac{N-1}{2N-1}}$ appearing in the proof of Theorem 2.4 (inflection point of eigenvalue dynamics) and define $d_{\lambda}$ as the discrete dynamic following (18), i.e.,

The proof mainly relies on Theorem 2.4 characterizing the evolution of eigenvalues of $W({k})=W_{N}({k})\cdots W_{1}({k})$ by $d_{\lambda}$ in (66). As in the proof of Theorem 3.1, we decompose the difference as

Let us now consider $A_{2}$. For $T_{N}^{\text{Id}}(\lambda_{1},\lambda_{1}/2,\alpha,\eta)\leq{k}\leq\frac{1}{\eta}T_{N}^{+}(\lambda_{L+1},(\varepsilon^{\prime}\lambda_{L+1})^{\frac{1}{N}},\alpha)$ Lemma 3.8 yields

3 Our work in light of [9]

Theorems 3.1 and 3.5 only make a non-trivial claim if $\alpha$, $\varepsilon$, and $\eta$ are chosen in a way such that $I_{1}\cap I_{2}\cap I_{3}\neq\emptyset$ (resp. the set of valid choices for ${k}$ in (63) is non-empty). In [9, Theorems 2 & 3] the authors characterize, for any pair of eigenvalues $\lambda_{i},\lambda_{j}$ of a positive semi-definite $\widehat{W}$ with $i,j\in[n]$, the maximal choice of $\alpha$ such that $\lambda_{i}$ and $\lambda_{j}$ are well-approximated at distinguishable times. Applying these results to $\lambda_{L}$ and $\lambda_{L+1}$, we thus can get a priori a necessary condition on $\alpha$ for the existence of the $L$-th effective rank plateau. Note, however, that the result on gradient descent [9, Theorem 3] only holds for the case $N=2$. Although there is a partial overlap of theory between and our work, the main difference of [9, Theorems 2 & 3] and our Theorems 3.1 & 3.5 is that the former answer the question whether a plateau exists, whereas the latter characterize the time at which the plateaus occur if they exist.