Implicit Regularization in Deep Learning May Not Be Explainable by Norms

Introduction

A standard test-bed for studying implicit regularization in deep learning is matrix completion (cf. ): given a randomly chosen subset of entries from an unknown matrix $W^{*}$, the task is to recover the unseen entries. This may be viewed as a prediction problem, where each entry in $W^{*}$ stands for a data point: observed entries constitute the training set, and the average reconstruction error over the unobserved entries is the test error, quantifying generalization. Fitting the observed entries is obviously an underdetermined problem with multiple solutions. However, an extensive body of work (see for a survey) has shown that if $W^{*}$ is low-rank, certain technical assumptions (e.g. “incoherence”) are satisfied and sufficiently many entries are observed, then various algorithms can achieve approximate or even exact recovery. Of these, a well-known method based upon convex optimization finds the minimal nuclear norm The nuclear norm (also known as trace norm) of a matrix is the sum of its singular values, regarded as a convex relaxation of rank. matrix among those fitting observations (see ).

One may try to solve matrix completion using shallow neural networks. A natural approach, matrix factorization, boils down to parameterizing the solution as a product of two matrices — $W=W_{2}W_{1}$ — and optimizing the resulting (non-convex) objective for fitting observations. Formally, this can be viewed as training a depth $2$ linear neural network. It is possible to explicitly constrain the rank of the produced solution by limiting the shared dimension of $W_{1}$ and $W_{2}$. However, Gunasekar et al. have shown in that in practice, even when the rank is unconstrained, running gradient descent with small learning rate (step size) and initialization close to the origin (zero) tends to produce low-rank solutions, and thus allows accurate recovery if $W^{*}$ is low-rank. Accordingly, they conjectured that the implicit regularization in matrix factorization boils down to minimization of nuclear norm:

With small enough learning rate and initialization close enough to the origin, gradient descent on a full-dimensional matrix factorization converges to a minimal nuclear norm solution.

Given a (shallow or deep) matrix factorization, for any norm (or quasi-norm) $\left\|\cdot\right\|$, there exists a set of observed entries with which small learning rate and initialization close to the origin can not ensure convergence of gradient descent to a minimal (in terms of $\left\|\cdot\right\|$) solution.

Conjectures 1 and 2 contrast each other, and more broadly, represent opposing perspectives on the question of whether norms may be able to explain implicit regularization in deep learning. In this paper, we resolve the tension between the two conjectures by affirming the latter. In particular, we prove that there exist natural matrix completion problems where fitting observations via gradient descent on a depth $L\geq 2$ matrix factorization leads — with probability $0.5$ or more over (arbitrarily small) random initialization — all norms (and quasi-norms) to grow towards infinity, while the rank essentially decreases towards its minimum. This result is in fact stronger than the one suggested by Conjecture 2, in the sense that: (i) not only is each norm (or quasi-norm) disqualified by some setting, but there are actually settings that jointly disqualify all norms (and quasi-norms); and (ii) not only are norms (and quasi-norms) not necessarily minimized, but they can grow towards infinity. We corroborate the analysis with empirical demonstrations.

The remainder of the paper is organized as follows. Section 2 reviews related work. Section 3 presents the deep matrix factorization model. Section 4 delivers our analysis, showing that its implicit regularization can drive all norms to infinity. Experiments, with both the analyzed setting and tensor factorization, are given in Section 5. Finally, Section 6 summarizes.

Related work

Theoretical analysis of implicit regularization in deep learning is a highly active area of research. Our work extends the bulk of literature concerning mathematical characterization of the implicit regularization induced by gradient-based optimization. As opposed to works studying the relation between implicit regularization and generalization (cf. ), or ones analyzing other sources of implicit regularization such as dropout (e.g. ). Existing characterizations focus on different aspects of learning, for example: dynamics of optimization (); curvature (“flatness”) of obtained minima (); frequency spectrum of learned input-output mappings (); invariant quantities throughout training (); and statistical properties imported from data (). A ubiquitous approach, arguably more prevalent than the aforementioned, is to demonstrate that learned input-output mappings minimize some notion of norm, or analogously, maximize some notion of margin. Works along this line have treated various models, Limiting such treatments to particular models is necessary, as in general one can not expect a gradient-based optimizer to yield minimal norm solutions over all possible objectives. Indeed, and have shown that there exist (carefully crafted) objectives over which variants of gradient descent do not produce minimal norm solutions. This accords with the conventional wisdom by which implicit regularization does not stem from an optimizer alone, but from its combination with a model (class of objectives). including: linear (single-layer) predictors (); normalized linear models (); certain polynomially parameterized linear models (); homogeneous (and sum of homogeneous) models (); ultra-wide neural networks (); linear neural networks with a single output (); and matrix factorization — the subject of our inquiry.

Matrix factorization is perhaps the most extensively studied model in the context of implicit regularization induced by non-convex gradient-based optimization. It corresponds to linear neural networks with multiple inputs and outputs, typically trained to recover low-rank linear mappings. The literature on matrix factorization for low-rank matrix recovery is far too broad to cover here — we refer to for a recent survey, while mentioning that the technique is often attributed to . Notable works proving successful recovery of a low-rank matrix via matrix factorization trained by gradient descent with no explicit regularization are . Of these, can be viewed as affirming Conjecture 1 (from ) for a certain special case. For a case related to (yet different from) that of , it was shown in that the set of matrices fitting observations is in fact a singleton, meaning Conjecture 1 holds trivially. has affirmed Conjecture 1 under different assumptions, but nonetheless argued empirically that it does not hold true in general, resonating with Conjecture 2 (from ). To the best of our knowledge, no theoretical support for the latter was provided prior to its proof in this paper. We note that the proof relies on technical results derived in and (restated in Subappendix D.2.1 for completeness).

Extending the research on matrix factorization, the use of tensor factorization for recovering low-rank tensors is a frequent topic of investigation (cf. ). Nevertheless, the experiments reported in this paper provide the first evidence we are aware of for such use to be successful under gradient-based optimization with no explicit regularization (in particular without imposing low-rank on the tensor factorization).

Deep matrix factorization

referred to as the product matrix of the factorization. Our interest lies on the implicit regularization of gradient descent, i.e. on the type of product matrices (Equation (3)) it will find when applied to the overparameterized objective (Equation (2)). Accordingly, and in line with prior work (cf. ), we focus on the case in which the search space is unconstrained, meaning $\min\{d_{l}\}_{l=0}^{L}=\min\{d_{0},d_{L}\}$ (rank is not limited by the parameterization).

As a theoretical surrogate for gradient descent with small learning rate and near-zero initialization, similarly to and (as well as other works analyzing linear neural networks, e.g. ), we study gradient flow (gradient descent with infinitesimally small learning rate): A technical subtlety of optimization in continuous time is that in principle, it is possible to asymptote (diverge to infinity) after finite time. In such a case, the asymptote is regarded as the end of optimization, and time tending to infinity ($t\to\infty$) is to be interpreted as tending towards that point.

and assume balancedness at initialization, i.e.:

In particular, when considering random initialization, we assume that $\{W_{l}(0)\}_{l=1}^{L}$ are drawn from a joint probability distribution by which Equation (5) holds almost surely. This is an idealization of standard random near-zero initializations, e.g. Xavier () and He (), by which Equation (5) holds approximately with high probability (note that the equation holds exactly in the standard “residual” setting of identity initialization — cf. ). The condition of balanced initialization (Equation (5)) played an important role in the analysis of , facilitating derivation of a differential equation governing the product matrix of a linear neural network (see Lemma 4 in Subappendix D.2.1). It was shown in empirically (and will be demonstrated again in Section 5) that there is an excellent match between the theoretical predictions of gradient flow with balanced initialization, and its practical realization via gradient descent with small learning rate and near-zero initialization. Other works (e.g. ) have supported this match theoretically, and we provide additional support in Appendix A by extending our theory to the case of unbalanced initialization (Equation (5) holding approximately).

Implicit regularization can drive all norms to infinity

In this section we prove that for matrix factorization of depth $L\geq 2$, there exist observations $\{b_{i,j}\}_{(i,j)\in\Omega}$ with which optimizing the overparameterized objective (Equation (2)) via gradient flow (Equations (4) and (5)) leads — with probability $0.5$ or more over random (“symmetric”) initialization — all norms and quasi-norms of the product matrix (Equation (3)) to grow towards infinity, while its rank essentially decreases towards minimum. By this we not only affirm Conjecture 2, but in fact go beyond it in the following sense: (i) the conjecture allows chosen observations to depend on the norm or quasi-norm under consideration, while we show that the same set of observations can apply jointly to all norms and quasi-norms; and (ii) the conjecture requires norms and quasi-norms to be larger than minimal, while we establish growth towards infinity.

For simplicity of presentation, the current section delivers our construction and analysis in the setting $d=d^{\prime}=2$ (i.e. $2$-by-$2$ matrix completion) — extension to different dimensions is straightforward (see Appendix B). We begin (Subsection 4.1) by introducing our chosen observations $\{b_{i,j}\}_{(i,j)\in\Omega}$ and discussing their properties. Subsequently (Subsection 4.2), we show that with these observations, decreasing loss often increases all norms and quasi-norms while lowering rank. Minimization of loss is treated thereafter (Subsection 4.3). Finally (Subsection 4.4), robustness of our construction to perturbations is established.

Consider the problem of completing a $2$-by-$2$ matrix based on the following observations:

The solution set for this problem (i.e. the set of matrices obtaining zero loss) is:

The (weakened) triangle inequality allows us to lower bound $\left\|\cdot\right\|$ by $\left\lvert(W)_{1,1}\right\rvert$ (up to multiplicative and additive constants). Thus, the set of $(W)_{1,1}$ values corresponding to $\epsilon$-minimizers must be bounded. If $\left\|\cdot\right\|$ is a Schatten-$p$ (quasi-)norm, a straightforward analysis shows it is monotonically increasing with respect to $\left\lvert(W)_{1,1}\right\rvert$, implying it is minimized if and only if $(W)_{1,1}=0$. ∎

In addition to norms and quasi-norms, we are also interested in the evolution of rank throughout optimization of a deep matrix factorization. More specifically, we are interested in the prospect of rank being implicitly minimized, as demonstrated empirically in . The discrete nature of rank renders its direct analysis unfavorable from a dynamical perspective (the rank of a matrix implies little about its proximity to low-rank), thus we consider the following surrogate measures: (i) effective rank (Definition 1 below; from ) — a continuous extension of rank used for numerical analyses; and (ii) distance from infimal rank (Definition 2 below) — (Frobenius) distance from the minimal rank that a given set of matrices may approach. According to Proposition 2 below, these measures independently imply that, although all solutions to our matrix completion problem — i.e. all $W\in{\mathcal{S}}$ (see Equation (7)) — have rank $2$, it is possible to essentially minimize the rank to $1$ by taking $\left\lvert(W)_{1,1}\right\rvert\to\infty$. Recalling Proposition 1, we conclude that in our setting, there is a direct contradiction between minimizing norms or quasi-norms and minimizing rank — the former requires confinement to some bounded interval, whereas the latter demands divergence towards infinity. This is the critical feature of our construction, allowing us to deem whether the implicit regularization in deep matrix factorization favors norms (or quasi-norms) over rank or vice versa.

The effective rank (Definition 1) takes the values $(1,2]$ along ${\mathcal{S}}$ (Equation (7)). For $W\in{\mathcal{S}}$, it is maximized when $(W)_{1,1}=0$, and monotonically decreases to $1$ as $\left\lvert(W)_{1,1}\right\rvert$ grows. Correspondingly, the infimal rank (Definition 2) of ${\mathcal{S}}$ is $1$, and the distance of $W\in{\mathcal{S}}$ from this infimal rank is maximized when $(W)_{1,1}=0$, monotonically decreasing to as $\left\lvert(W)_{1,1}\right\rvert$ grows.

Analyzing the singular values of $W\in{\mathcal{S}}$ — $\sigma_{1}(W)\geq\sigma_{2}(W)\geq 0$ — reveals that: (i) $\sigma_{1}(W)$ attains a minimal value of $1$ when $(W)_{1,1}=0$, monotonically increasing to $\infty$ as $\left\lvert(W)_{1,1}\right\rvert$ grows; and (ii) $\sigma_{2}(W)$ attains a maximal value of $1$ when $(W)_{1,1}=0$, monotonically decreasing to as $\left\lvert(W)_{1,1}\right\rvert$ grows. The results for effective rank, infimal rank and distance from infimal rank readily follow from this characterization. ∎

2 Decreasing loss increases norms

Consider the process of solving our matrix completion problem (Subsection 4.1) with gradient flow over a depth $L\geq 2$ matrix factorization (Section 3). Theorem 1 below states that if the product matrix (Equation (3)) has positive determinant at initialization, lowering the loss leads norms and quasi-norms to increase, while the rank essentially decreases.

An immediate consequence of Theorem 1 is that, if the product matrix (Equation (3)) has positive determinant at initialization, convergence to zero loss leads all norms and quasi-norms to grow to infinity, while the rank is essentially minimized. This is formalized in Corollary 1 below.

where $W_{L:1}(t)$ is the product matrix of the deep factorization (Equation (3)) at time $t$ of optimization. On the other hand:

Theorem 1 and Corollary 1 imply that in our setting (Subsection 4.1), where minimizing norms (or quasi-norms) and minimizing rank contradict each other, the implicit regularization of deep matrix factorization is willing to completely give up on the former in favor of the latter, at least on the condition that the product matrix (Equation (3)) has positive determinant at initialization. How probable is this condition? By Proposition 3 below, it holds with probability $0.5$ if the product matrix is initialized by any one of a wide array of common distributions, including matrix Gaussian distribution with zero mean and independent entries, and a product of such. We note that rescaling (multiplying by $\alpha>0$) initialization does not change the sign of product matrix’s determinant, therefore as postulated by Conjecture 2, initialization close to the origin (along with small learning rate Recall that gradient flow corresponds to gradient descent with infinitesimally small learning rate. ) can not ensure convergence to solution with minimal norm or quasi-norm.

Multiplying a row of $W$ by $-1$ keeps its distribution intact while flipping the sign of its determinant. This implies $\Pr(\det(W)>0)=\Pr(\det(W)<0)$. The first result then follows from the fact that a matrix drawn from a continuous distribution is almost surely non-singular. The second result is an outcome of the same fact, as well as the multiplicativity of determinant and the law of total probability. ∎

3 Convergence to zero loss

It is customary in the theory of deep learning (cf. ) to distinguish between implicit regularization — which concerns the type of solutions found in training — and the complementary question of whether training loss is globally optimized. We supplement our implicit regularization analysis (Subsection 4.2) by addressing this complementary question in two ways: (i) in Section 5 we empirically demonstrate that on the matrix completion problem we analyze (Subsection 4.1), gradient descent over deep matrix factorizations (Section 3) indeed drives training loss towards global optimum, i.e. towards zero; and (ii) in Proposition 4 below we theoretically establish convergence to zero loss for the special case of depth $2$ and scaled identity initialization (treatment of additional depths and initialization schemes is left for future work). We note that when combined with Corollary 1, Proposition 4 affirms that in the latter special case, all norms and quasi-norms indeed grow to infinity while rank is essentially minimized. Notice that under (positively) scaled identity initialization the determinant of the product matrix (Equation (3)) is positive, as required by Corollary 1.

We first establish that the product matrix is positive definite for all $t$. This simplifies a dynamical characterization from (restated as Lemma 4 in Subappendix D.2), yielding lucid differential equations governing the entries of the product matrix. Careful analysis of these equations then completes the proof. ∎

4 Robustness to perturbations

Our analysis (Subsection 4.2) has shown that when applying a deep matrix factorization (Section 3) to the matrix completion problem defined in Subsection 4.1, if the product matrix (Equation (3)) has positive determinant at initialization — a condition that holds with probability $0.5$ under the wide variety of random distributions specified by Proposition 3 — then the implicit regularization drives all norms and quasi-norms towards infinity, while rank is essentially driven towards its minimum. A natural question is how common this phenomenon is, and in particular, to what extent does it persist if the observed entries we defined (Equation (6)) are perturbed. Theorem 2 below generalizes Theorem 1 (from Subsection 4.2) to the case of arbitrary non-zero values for the off-diagonal observations $b_{1,2},b_{2,1}$, and an arbitrary value for the diagonal observation $b_{2,2}$. In this generalization, the assumption (from Theorem 1) of the product matrix’s determinant at initialization being positive is modified to an assumption of it having the same sign as $b_{1,2}\cdot b_{2,1}$ (the probability of which is also $0.5$ under the random distributions covered by Proposition 3). Conditioned on the modified assumption, the smaller $\left\lvert b_{2,2}\right\rvert$ is compared to $\left\lvert b_{1,2}\cdot b_{2,1}\right\rvert$, the higher the implicit regularization is guaranteed to drive norms and quasi-norms, and the lower it is guaranteed to essentially drive the rank. Two immediate implications of Theorem 2 are: (i) if the diagonal observation is unperturbed ($b_{2,2}=0$), the off-diagonal ones ($b_{1,2},b_{2,1}$) can take on any non-zero values, and the phenomenon of implicit regularization driving norms and quasi-norms towards infinity (while essentially driving rank towards its minimum) will persist; and (ii) this phenomenon gracefully recedes as the diagonal observation is perturbed away from zero. We note that Theorem 2 applies even if the unobserved entry is repositioned, thus our construction is robust not only to perturbations in observed values, but also to an arbitrary change in the observed locations. See Subappendix C.1 for empirical demonstrations.

Consider the setting of Theorem 1 subject to the following changes: (i) the observations from Equation (6) are generalized to:

leading to the following solution set in place of that from Equation (7):

The proof follows a line similar to that of Theorem 1, with slightly more involved derivations. ∎

Experiments

This section presents our empirical evaluations. We begin in Subsection 5.1 with deep matrix factorization (Section 3) applied to the settings we analyzed (Section 4). Then, we turn to Subsection 5.2 and experiment with an extension to tensor (multi-dimensional array) factorization. For brevity, many details behind our implementation, as well as some experiments, are deferred to Appendix C.

In , Gunasekar et al. experimented with matrix factorization, arriving at Conjecture 1. In the following work , Arora et al. empirically evaluated additional settings, ultimately arguing against Conjecture 1, and raising Conjecture 2. Our analysis (Section 4) affirmed Conjecture 2, by providing a setting in which gradient descent (with infinitesimally small learning rate and initialization arbitrarily close to the origin) over (shallow or deep) matrix factorization provably drives all norms (and quasi-norms) towards infinity. Specifically, we established that running gradient descent on the overparameterized matrix completion objective in Equation (2), where the observed entries are those defined in Equation (6), leads the unobserved entry to diverge to infinity as loss converges to zero. Figure 1 demonstrates this phenomenon empirically. Figures 4 and 5 in Subappendix C.1 extend the experiment by considering, respectively: different matrix dimensions (see Appendix B); and perturbations and repositionings applied to observations (cf. Subsection 4.4). The figures confirm that the inability of norms (and quasi-norms) to explain implicit regularization in matrix factorization translates from theory to practice.

2 From matrix to tensor factorization

At the heart of our analysis (Section 4) lies a matrix completion problem whose solution set (Equation (7)) entails a direct contradiction between minimizing norms (or quasi-norms) and minimizing rank. We have shown that on this problem, gradient descent over (shallow or deep) matrix factorization is willing to completely give up on the former in favor of the latter. This suggests that, rather than viewing implicit regularization in matrix factorization through the lens of norms (or quasi-norms), a potentially more useful interpretation is minimization of rank. Indeed, while global minimization of rank is in the worst case computationally hard (cf. ), it has been shown in (theoretically as well as empirically) that the dynamics of gradient descent over matrix factorization promote sparsity of singular values, and thus they may be interpreted as searching for low rank locally. As a step towards assessing the generality of this interpretation, we empirically explore an extension of matrix factorization to tensor factorization. The reader is referred to and for an introduction to tensor factorizations.

Figure 2 displays results of tensor completion experiments, in which tensor factorization (optimization of loss in Equation (16) via gradient descent over parameterization in Equation (17)) is applied to observations (i.e. $\{b_{i_{1},i_{2},\ldots,i_{N}}\}_{(i_{1},i_{2},\ldots,i_{N})\in\Omega}$) drawn from a low-rank ground truth tensor. As can be seen in terms of both reconstruction error (distance from ground truth tensor) and (tensor) rank of the produced solutions, tensor factorizations indeed exhibit an implicit regularization towards low rank. The phenomenon thus goes beyond the special case of matrix (order $2$ tensor) factorization. Theoretically supporting this finding is regarded as a promising direction for future research.

As discussed in Section 1, matrix completion can be seen as a prediction problem, Observed entries in the matrix to recover stand for training examples, and unobserved entries for test set. and matrix factorization as its solution with a linear neural network. In a similar vein, tensor completion may be viewed as a prediction problem, and tensor factorization as its solution with a convolutional arithmetic circuit — see Figure 3. Convolutional arithmetic circuits form a class of non-linear neural networks that has been studied extensively in theory (cf. ), and has also demonstrated promising results in practice (see ). Analogously to how the input-output mapping of a linear neural network is naturally represented by a matrix, that of a convolutional arithmetic circuit admits a natural representation as a tensor. Our experiments (Figure 2 and Figure 6 in Subappendix C.1) show that (at least in some settings) when learned via gradient descent, this tensor tends to have low rank. We thus obtain a second exemplar of a neural network architecture whose implicit regularization strives to lower a notion of rank for its input-output mapping. This leads us to believe that the phenomenon may be general, and formalizing notions of rank for input-output mappings of contemporary models may be key to explaining generalization in deep learning.

Summary

The extent to which norms (and quasi-norms) can explain the implicit regularization induced by gradient-based optimization is a central question in the theory of deep learning. A standard test-bed for its study is matrix factorization — matrix completion via linear neural networks trained by gradient descent — which in practice tends to produce low-rank solutions. It is an open problem whether the implicit regularization in matrix factorization can be characterized as minimization of a norm (or quasi-norm) — Conjecture 1 from supports this supposition, whereas Conjecture 2 from opposes it. We presented a simple (and robust to perturbations) matrix completion setting for which, with probability $0.5$ or more over random initialization of gradient descent, the implicit regularization in matrix factorization provably drives all norms (and quasi-norms) to grow towards infinity, while rank is essentially minimized. This affirms Conjecture 2, and although it does not formally refute Conjecture 1 (the latter’s technical assumptions are not necessarily satisfied by our setting), we believe that in essence our result implies that norm (or quasi-norm) minimization cannot explain implicit regularization in matrix factorization, let alone in deep learning altogether.

The crux behind the matrix completion setting we defined is that its solution set entails a direct contradiction between minimizing norms (or quasi-norms) and minimizing rank. The fact that the former is given up on in favor of the latter suggests that, rather than viewing implicit regularization in matrix factorization through the lens of norms (or quasi-norms), a potentially more useful interpretation is minimization of rank. As a step towards assessing the generality of this interpretation, we experimented with an extension of matrix factorization to tensor factorization, and found that it too exhibits an implicit regularization towards low rank, where rank is defined in the context of tensors. Similarly to how matrix factorization corresponds to a linear neural network whose input-output mapping is represented by a matrix, tensor factorization corresponds to a convolutional arithmetic circuit (certain type of non-linear neural network) whose input-output mapping is represented by a tensor. We thus obtain a second exemplar of a neural network architecture whose implicit regularization strives to lower a notion of rank for its input-output mapping. Theoretical investigation of the implicit regularization in tensor factorization is regarded as a promising direction for future research. More broadly, we believe that neural networks minimizing notions of rank for their input-output mappings may be a general phenomenon, and hypothesize that formalizing such notions in the context of contemporary models may be key to explaining generalization in deep learning.

Broader Impact

The application of deep learning in practice is based primarily on trial and error, conventional wisdom and intuition, often leading to suboptimal performance, as well as compromise in important aspects such as safety, privacy and fairness. Developing rigorous theoretical foundations behind deep learning may facilitate a more principled use of the technology, alleviating aforementioned shortcomings. The current paper takes a step along this vein, by addressing the central question of implicit regularization induced by gradient-based optimization. While theoretical advances — particularly those concerned with explaining widely observed empirical phenomena — oftentimes do not pose apparent societal threats, a potential risk they introduce is misinterpretation by scientific readership. We have therefore made utmost efforts to present our results as transparently as possible.

Acknowledgments and Disclosure of Funding

This work was supported by Len Blavatnik and the Blavatnik Family foundation, as well as the Yandex Initiative in Machine Learning. The authors thank Nathan Srebro and Jason D. Lee for their illuminating comments which helped improve the manuscript.

References

References

Appendix A Extension to unbalanced initialization

The following definition quantifies unbalancedness.

We will present two approaches for showing that approximate versions of our main theoretical results (Theorems 1 and 2) hold if unbalancedness magnitude at initialization is small: (i) using continuity of optimizer trajectory with respect to its initialization (Subappendix A.1); and (ii) employing conservation of unbalancedness magnitude throughout optimization (Subappendix A.2). Both approaches rely on the fact that small unbalancedness magnitude implies proximity to perfect balancedness, as stated formally in the following lemma.

Based on singular value decompositions of $W_{1},W_{2},\ldots,W_{L}$, the proof provides an explicit construction for $W^{\prime}_{1},W^{\prime}_{2},\ldots,W^{\prime}_{L}$. Starting with $W^{\prime}_{1}:=W_{1}$, for $l=2,3,\ldots,L$ the matrices $W^{\prime}_{l}$ are defined such that: (i) $W_{l}^{\prime\top}W^{\prime}_{l}=W^{\prime}_{l-1}W_{l-1}^{\prime\top}$; and (ii) $\left\|W_{l}-W^{\prime}_{l}\right\|_{Fro}\leq\left\|W_{l-1}-W^{\prime}_{l-1}\right\|_{Fro}+\sqrt{\epsilon}$. The former ensures that $W^{\prime}_{1},W^{\prime}_{2},\ldots,W^{\prime}_{L}$ are balanced, whereas the latter implies $\left\|W_{l}-W^{\prime}_{l}\right\|_{Fro}\leq(l-1)\cdot\sqrt{\epsilon}$ for all $l=1,2,\ldots,L$. ∎

Trajectories of gradient flow over a smooth objective are Lipschitz continuous with respect to their initialization, in the sense that for any $T>0$, the location at time $T$ of optimization is a Lipschitz continuous function of the initial point. This fact is established by Lemma 2 below.

Then, for any $\bar{t}\in[0,T]$ it holds that:

Specializing Lemma 2 to deep matrix factorization (Section 3) yields the following result.

Consider the overparameterized objective corresponding to a depth $L$ matrix factorization applied to an arbitrary matrix completion task (see Equations (2) and (3)). Let $\theta(t):=(W_{1}(t),W_{2}(t),\ldots,W_{L}(t))$ and $\theta^{\prime}(t):=(W^{\prime}_{1}(t),W^{\prime}_{2}(t),\ldots,W^{\prime}_{L}(t))$ be two (arbitrary) curves born from gradient flow over this objective (cf. Equation (4)). Given $T>0$, denote $R:=\sup_{t\in[0,T]}\max\{\left\|\theta(t)\right\|_{Fro},\left\|\theta^{\prime}(t)\right\|_{Fro}\}$. The Frobenius norm of a matrix tuple is defined as the Euclidean norm of their concatenation as a vector, so for example $\left\|\theta(t)\right\|_{Fro}=(\sum_{l=1}^{L}\left\|W_{l}(t)\right\|_{Fro}^{2})^{0.5}$. Then, for any $\bar{t}\in[0,T]$ it holds that:

where $B:=(\sum\nolimits_{(i,j)\in\Omega}b_{i,j}^{2})^{0.5}$, with $\{b_{i,j}\}_{(i,j)\in\Omega}$ standing for the observed matrix entries.

The proof follows from Lemma 2, and the fact that for any $R^{\prime}>0$ the overparameterized objective is $LR^{\prime L-2}\left(2R^{\prime L}+B\right)$-smooth over ${\mathcal{D}}_{R^{\prime}}:=\{(W_{1},W_{2},\ldots,W_{L}):\left\|(W_{1},W_{2},\ldots,W_{L})\right\|_{Fro}<R^{\prime}\}$. ∎

Combining Proposition 5 with Lemma 1 makes it possible to derive extensions of Theorems 1 and 2 in which the assumption of initialization being perfectly balanced (Equation (5)) is relaxed to a requirement for small unbalancedness magnitude (Definition 3). The underlying idea is as follows. An initialization with small unbalancedness magnitude is close to one which is balanced (Lemma 1), and for the latter Theorems 1 and 2 may be applied. The distance between gradient flow trajectories emanating from the two initializations is controlled (Proposition 5), therefore results of Theorems 1 and 2 (bounds on norms, quasi-norms, effective rank and distance from infimal rank) carry over — with additional error terms — to the trajectory originating from the unbalanced initialization. A drawback of this approach is that the bounds on distance between trajectories, and accordingly the error terms incurred, grow exponentially with time (see Equation (20)). In the next subappendix we present a different approach that takes into account specific properties of gradient flow over deep matrix factorization, allowing one to overcome this exponential growth (for depth $L\geq 3$).

A.2 Second approach: conservation of unbalancedness magnitude

Lemma 3 below shows that unbalancedness magnitude (Definition 3) is a conserved quantity of gradient flow over deep matrix factorization (Section 3).

Consider the overparameterized objective corresponding to a depth $L$ matrix factorization applied to an arbitrary matrix completion task (see Equations (2) and (3)). Let $(W_{1}(t),W_{2}(t),\ldots,W_{L}(t))$ be a curve born from gradient flow over this objective (cf. Equation (4)), and for any $t\geq 0$, denote by $\epsilon(t)$ the associated unbalancedness magnitude (Equation (18)). Then, $\epsilon(t)$ is constant through time, i.e. $\epsilon(t)=\epsilon(0)$ for all $t\geq 0$.

For $l=1,2,\ldots,L-1$, using the dynamics of $W_{l}(t)$ and $W_{l+1}(t)$ under gradient flow, we show that:

This implies $W_{l+1}(t)^{\top}W_{l+1}(t)-W_{l}(t)W_{l}(t)^{\top}=W_{l+1}(0)^{\top}W_{l+1}(0)-W_{l}(0)W_{l}(0)^{\top}$ for all $t\geq 0$. The proof concludes by taking nuclear norm of both sides of the latter equality, followed by maximization over $l\in\{1,2,\ldots,L-1\}$. ∎

Combining Lemma 3 with Lemma 1 implies that if unbalancedness magnitude is small at initialization, it remains that way throughout, and thus for every point along the optimization trajectory there exists some nearby point which is balanced (i.e. has unbalancedness magnitude zero). We may imagine a gradient flow trajectory emanating from such balanced point, and import certain characteristics from this imaginary trajectory to the original one. The idea of using imaginary balancedly-initialized trajectories for analyzing the unbalanced case also appears in the approach laid out in Subappendix A.1. However, whereas there only one such trajectory was employed, here there are infinitely many — one for each point in time. This allows us to maintain small distance from an imaginary trajectory (as opposed to a distance that grows exponentially with time — see Proposition 5), facilitating import of characteristics during which incurred error terms are small.

In the context of Theorems 1 and 2, the critical characteristic of trajectories originating from balanced initializations is that they do not allow the product matrix’s (Equation (3)) determinant to change sign, or more specifically, its smallest singular value to cross zero. Using the aforementioned technique (proximity to imaginary balancedly-initialized trajectories), we may import an approximate version of this characteristic into trajectories whose initializations have small unbalancedness magnitude. This amounts to a bound on the rate at which the smallest singular value of the product matrix can approach zero, yielding a guaranteed time throughout which the results of Theorems 1 and 2 hold.

Theorem 3 below formalizes the logic outlined above, extending Theorem 1 to the case of unbalanced initialization (we omit here the formal extension of Theorem 2, as it is essentially the same).

(Quasi-)norms, effective rank and distance from infimal rank are jointly bounded as follows:

By the proof of Theorem 1 (given in Subappendix D.5), its results (Equations (8), (9) and (10)) hold for any $t\geq 0$ with $\det(W_{L:1}(t))>0$. Bearing in mind that by assumption $\det(W_{L:1}(0))>0$, we let $T{\,\in\,}(0,\infty)$ be the initial time at which $\det(W_{L:1}(T))=0$ (if no such $T$ exists, the proof concludes). Fixing an arbitrary time $\bar{t}\in[0,T]$, Lemmas 3 and 1 imply that there exists a point $(W^{\prime}_{1},W^{\prime}_{2},\ldots,W^{\prime}_{L})$ which meets the balancedness condition (i.e. has unbalancedness magnitude zero), and is within (Frobenius) distance ${\mathcal{O}}(L^{2}\cdot\sqrt{\epsilon})$ from $(W_{1}(\bar{t}),W_{2}(\bar{t}),\ldots,W_{L}(\bar{t}))$. Imagining a gradient flow path that emanates from $(W^{\prime}_{1},W^{\prime}_{2},\ldots,W^{\prime}_{L})$, one may employ Lemma 5 from Subappendix D.2.1, to characterize the movement of the singular values of $W^{\prime}_{L:1}:=W^{\prime}_{L}W^{\prime}_{L-1}\cdots W^{\prime}_{1}$. Continuity arguments then imply that the singular values of $W_{L:1}(\bar{t})$ move similarly (at time $\bar{t}$), allowing us to obtain an upper bound on the rate at which the minimal singular value of $W_{L:1}(\bar{t})$ can decay. Integrating this upper bound yields a lower bound on $T$, specified in Equation (21) as one of the possible outcomes. The continuity arguments employed require $\left\|(W_{1}(t),W_{2}(t),\ldots,W_{L}(t))\right\|_{Fro}$, $t\in[0,T]$, to be bounded by a certain constant. If this is not the case then necessarily at some time $t\leq T$ the unobserved entry of $W_{L:1}(t)$ is large, leading to the bounds on (quasi-)norms, effective rank and distance from infimal rank in the alternative outcome (Equations (22), (23) and (24) respectively). ∎

Theorem 3 states that if initialization has unbalancedness magnitude $\epsilon>0$ (Definition 3), then the results of Theorem 1 — bounds on (quasi-)norms, effective rank and distance from infimal rank (Equations (8), (9) and (10) respectively) — are guaranteed to hold for a certain period of time (Equation (21)), or until certain terminal bounds (Equations (22), (23) and (24)) are jointly satisfied. Taking $\epsilon\to 0^{+}$, the aforementioned period of time tends to infinity, and the terminal bounds tend to the limits (as loss goes to zero) of the bounds in Theorem 1, meaning we effectively converge to the latter. The rate of this convergence highly depends on the depth of the matrix factorization — roughly speaking, it is proportional to a fractional power of $\ln(1/\epsilon)$ for depth $2$, and to a fractional power of $1/\epsilon$ for depth $3$ or more. Disregarding constants (terms that do not depend on $\epsilon$), We did not attempt to optimize those; doing so is regarded as a potential direction for future work. this implies that in order to get comparable guarantees, the unbalancedness magnitude of initialization needs to be exponentially smaller with depth $2$ than with depth $3$ or more. We thus have a theoretical reasoning that resonates with the empirical phenomenon reported in Figure 1, by which in practical settings (gradient descent with small learning rate and near-zero initialization), the prediction of Theorem 1 — unobserved entry increasing (and therefore norms and quasi-norms increasing, with effective rank and distance from infimal rank decreasing) as loss decreases — sustains for much longer with depth $3$ or more than it does with depth $2$. Note that this phenomenon takes place even when initializations are perfectly balanced (i.e. have unbalancedness magnitude zero), the reason being the discrepancy between gradient descent with small learning rate and gradient flow. Specifically, while the latter would have conserved the balancedness throughout (Lemma 3), the former will (generically) lead to positive unbalancedness magnitude immediately after its commencement.

Appendix B Extension to different matrix dimensions

In this appendix we outline an extension of the construction and analysis given in Subsections 4.1 and 4.2 respectively, to completion of matrices with dimensions beyond $2$-by-$2$. The extension presented here is not unique, but rather one simple option out of many. It is demonstrated empirically in Subappendix C.1 (Figure 4).

Observing ${\mathcal{S}}_{d}$, while comparing to the solution set ${\mathcal{S}}$ in our original construction (Equation (7)), we see that the former has a $2$-by-$2$ block diagonal structure, with the top-left block holding the latter, and the bottom-right block set to identity. This implies that $d-2$ of the singular values along ${\mathcal{S}}_{d}$ are fixed to one, and the remaining two are identical to the singular values along ${\mathcal{S}}$. Results analogous to Propositions 1 and 2 can therefore easily be proven. Since the determinant along ${\mathcal{S}}_{d}$ is bounded below and away from zero (it is equal to $-1$), approaching ${\mathcal{S}}_{d}$ while having positive determinant necessarily means that absolute value of unobserved entry (i.e. of the entry in location $(1,1)$) grows towards infinity. Combining this with the fact that the product matrix (Equation (3)) of a depth $L\geq 2$ matrix factorization maintains the sign of its determinant (see Lemma 6 in Subappendix D.2.1), results analogous to Theorem 1 and Corollary 1 may readily be established. That is, one may show that, with probability $0.5$ or more over random near-zero initialization, gradient descent with small learning rate drives all norms (and quasi-norms) towards infinity, while essentially driving rank towards its minimum.

Appendix C Further experiments and implementation details

Figures 4 and 5 supplement Figure 1 from Subsection 5.1, by demonstrating empirically that the phenomenon of implicit regularization in matrix factorization driving all norms (and quasi-norms) towards infinity is, respectively: (i) applicable to arbitrary matrix dimensions, as outlined in Appendix B; and (ii) robust to perturbations, as proven in Subsection 4.4. Figure 6 supplements Figure 2 from Subsection 5.2, further demonstrating that gradient descent over tensor factorization exhibits an implicit regularization towards low (tensor) rank.

C.2 Implementation details

Below we provide a full description of implementation details omitted from our experimental reports (Section 5 and Subappendix C.1). Source code for reproducing our results and figures, based on the PyTorch framework (), can be found at https://github.com/noamrazin/imp_reg_dl_not_norms.

In all experiments with deep matrix factorization, hidden dimensions were set to the minimal value ensuring unconstrained search space, i.e. to the minimum between the number of rows and the number of columns in the matrix to complete. Gradient descent was run with fixed learning rate until loss (Equation (1)) reached a value lower than $10^{-4}$ or $5\cdot 10^{6}$ iterations elapsed. Both balanced (Equation (5)) and unbalanced (layer-wise independent) random initializations were calibrated according to a desired standard deviation $\alpha>0$ for the entries of the initial product matrix (Equation (3)). Namely: (i) under unbalanced initialization, entries of all weight matrices were sampled independently from a Gaussian distribution with zero mean and standard deviation $(\alpha^{2}/\bar{d}^{L-1})^{1/2L}$, where $L$ stands for the depth of the factorization, and $\bar{d}$ for the size of its hidden dimensions; and (ii) under balanced initialization, we used Procedure 1 from , based on a Gaussian distribution with independent entries, zero mean and standard deviation $\alpha$. In accordance with the description in Appendix B, if the matrix to complete was rectangular, we ensured that excess rows or columns of the initial product matrix held zeros, by clearing (setting to zero) corresponding rows or columns of the initial leftmost or rightmost (respectively) matrix in the factorization. That is, if the matrix to complete had size $d$-by-$d^{\prime}$ with $d\neq d^{\prime}$, we cleared rows $d^{\prime}+1$ to $d$ of $W_{L}(0)$ if $d>d^{\prime}$, and columns $d+1$ to $d^{\prime}$ of $W_{1}(0)$ if $d^{\prime}>d$. Random initializations were repeated until the determinant of the initial product matrix (or of its top-left $\min\{d,d^{\prime}\}$-by-$\min\{d,d^{\prime}\}$ submatrix if its size was $d$-by-$d^{\prime}$ with $d\neq d^{\prime}$) was of the necessary sign, Positive for the experiments reported by Figures 1 and 4, and negative for those reported by Figure 5. taking two attempts on average. In the experiment reported by Figure 1, runs with matrix factorization depths $2$ and $3$ were carried out with learning rates $\{6\cdot 10^{-2},3\cdot 10^{-2},9\cdot 10^{-3},6\cdot 10^{-3},3\cdot 10^{-3},9\cdot 10^{-4}\}$ and corresponding standard deviations for initialization $\{10^{-2},10^{-3},10^{-4},10^{-5},10^{-6},10^{-7}\}$. Factorizations of depth $4$ were slightly more sensitive to changes in learning rate, thus we refined attempted values to $\{6\cdot 10^{-3},4.5\cdot 10^{-3},3\cdot 10^{-3},1.5\cdot 10^{-3},10^{-3}\}$, with corresponding standard deviations for initialization $\{10^{-1},10^{-2},10^{-3},10^{-4},10^{-5}\}$.

C.2.2 Tensor factorization (Figures 2 and 6)

with $\{{\mathbf{w}}^{*(n)}_{r}\}_{r=1}^{R^{*}}{}_{n=1}^{N}$ drawn independently from the standard normal distribution. After every such generation, we estimated the rank of the obtained tensor (its construction only ensures a rank of at most $R^{*}$), and repeated the process if it was smaller than $R^{*}$. For convenience, we subsequently normalized the ground truth tensor to be of unit Frobenius norm.

Appendix D Deferred proofs

D.2 Useful lemmas

For completeness, we include the following result from , which characterizes the evolution of the product matrix under gradient flow on a deep matrix factorization:

Suppose we run gradient flow over the factorization:

Then, the product matrix $W_{L:1}(t)=W_{L}(t)\cdots W_{1}(t)$ obeys the following dynamics:

Additionally, recall from the following characterization for the singular values of $W_{L:1}(t)$:

i.e. $\sigma_{r}(t)$ are the singular values of $W_{L:1}(t)$, and ${\mathbf{u}}_{r}(t),{\mathbf{v}}_{r}(t)$ are corresponding left and right (respectively) singular vectors. Furthermore, the singular values $\sigma_{r}(t)$ evolve by:

We rely on this result to establish that for square product matrices the sign of $\det(W_{L:1}(t))$ does not change throughout time.

We prove an analogous claim for the singular values of $W_{L:1}(t)$, from which the lemma readily follows. That is, for $r\in[d]$, the singular value $\sigma_{r}(t)$ is identically zero if $\sigma_{r}(0)=0$, and is positive if $\sigma_{r}(0)>0$.

As before, if $\sigma_{r}(0)=0$, then $\sigma_{r}(t)=0$ for all $t\geq 0$. If $\sigma_{r}(0)>0$, divergence in finite time of $\sigma_{r}(t)$ is possible, however, its positivity is preserved until that occurs nonetheless.

Turning our attention to the determinant of $W_{L:1}(t)$, suppose $\det(W_{L:1}(0))=0$. Then, $W_{L:1}(0)$ has a singular value which is , and for all $t$ that singular value and the determinant remain . If $\det(W_{L:1}(0))\neq 0$, the product matrix remains full rank for all $t$. The proof then immediately follows from the continuity of $\det(W_{L:1}(t))$. ∎

We will also make use of the following lemmas:

That is, $U_{L}\cdot\prod_{1}^{l=L}\Sigma_{l}\cdot V_{1}^{\top}$ is a singular value decomposition of $W_{L:1}$, and $\sigma_{i}(W_{L:1})=(\prod_{l=1}^{L}\Sigma_{l})_{i,i}$ for all $i\in[\min\{d_{L},d_{0}\}]$.

Fix $l\in[L]$ and $i\in[\min\{d_{L},d_{0}\}]$. If $i>\min\{d_{l^{\prime}}\}_{l^{\prime}=0}^{L}$, for any $l^{\prime}\in[L]$ with $\min\{d_{l^{\prime}},d_{l^{\prime}-1}\}\geq i$, by our construction it holds that $(\Sigma_{l^{\prime}})_{i,i}=0$. Hence, recalling that by convention $\sigma_{i}(W_{l})=0$ if $i>\min\{d_{l},d_{l-1}\}$, we may conclude that $\sigma_{i}(W_{L:1})=\sigma_{i}(W_{l})^{L}=0$. Otherwise, if $i\leq\min\{d_{l^{\prime}}\}_{l^{\prime}=0}^{L}$, the fact that $\sigma_{i}(W_{l^{\prime}})=(\Sigma_{l^{\prime}})_{i,i}=(\Sigma_{l^{\prime}-1})_{i,i}=\sigma_{i}(W_{l^{\prime}-1})$ for all $l^{\prime}=2,3,\ldots,L$ implies that $\sigma_{i}(W_{L:1})=\sigma_{i}(W_{l})^{L}$. ∎

D.2.2 Technical

Included below are a few technical lemmas used in our analyses.

We present a tighter inequality, $h(p)\leq 2\sqrt{p(1-p)}$, from which the proof immediately follows since $2\sqrt{p(1-p)}\leq 2\sqrt{p}$ for $p\in$.

Define the function $f(p):=\frac{h(p)^{2}}{p(1-p)}$ over the open interval $(0,1)$. Differentiating it with respect to $p$ we have:

Introducing $g(p):=-p\cdot\ln(p)$, we show that $g(p)^{2}>g(1-p)^{2}$ for all $p\in(0,\frac{1}{2})$. It is easily verified that $g(p)-g(1-p)$ is concave on the interval $(0,\frac{1}{2})$ (second derivative is negative). Since for $p=0$ and $p=1/2$ we have exactly $g(p)-g(1-p)=0$, it holds that $g(p)-g(1-p)\geq 0$ and $g(p)^{2}\geq g(1-p)^{2}$ for all $p\in(0,\frac{1}{2})$. Noticing $\frac{d}{dp}f(p)=\left(g(p)^{2}-g(1-p)^{2}\right)/p^{2}(1-p)^{2}$, it follows that $f(\cdot)$ is monotonically non-decreasing on $(0,\frac{1}{2})$. Due to the fact that $f(p)=f(1-p)$, it is non-increasing on $(\frac{1}{2},1)$, and attains its maximal value over $(0,1)$ at $p=\frac{1}{2}$. Putting it all together, for $p\in(0,1)$ we have:

and for $p=0,1$ there is exact equality, completing the proof. ∎

Replacing $A$ with its singular value decomposition and choosing ${\mathbf{y}}=VU^{\top}{\mathbf{o}}_{1}$:

Recalling that for any unit vector the quadratic form of a symmetric matrix is bounded by the maximal and minimal eigenvalues completes the proof:

The proof concludes by applying the inductive assumption for $L-1$. ∎

$(\Sigma_{B})_{i,i}=(\Sigma_{A})_{i,i}$ for any $i\in[\min\{d,k,d^{\prime}\}]$, with the remaining diagonal entries of $\Sigma_{A}$ and $\Sigma_{B}$ being ; and

$B=U_{B}\Sigma_{B}U_{A}^{\top}$, i.e. $U_{B}\Sigma_{B}U_{A}^{\top}$ is a singular value decomposition of $B$.

Therefore, we may conclude $B=B\sum_{i=1}^{r}{\mathbf{u}}_{A}^{(i)}\left({\mathbf{u}}_{A}^{(i)}\right)^{\top}=U_{B}\Sigma_{B}U_{A}^{\top}$. ∎

Let $t>0$ be such that $g(t)<g(0)$, and fix some $a\in(g(t),g(0)]$. Define $t_{a}:=\max\{t^{\prime}:t^{\prime}~{}\leq~{}t\text{ and }g(t^{\prime})=a\}$. Continuity of $g(\cdot)$, along with the intermediate value theorem, imply that $t_{a}$ is well defined (maximum of a closed non-empty set bounded from above). Assume by contradiction that $\dot{g}(t_{a})>0$. Then, $g(\cdot)$ is monotonically increasing on some neighborhood of $t_{a}$. Thus, by the intermediate value theorem, there exists $t^{\prime}\in(t_{a},t)$ such that $g(t^{\prime})=a$, in contradiction to the definition of $t_{a}$. An identical argument establishes the analogous result for the case $g(t)>g(0)$. ∎

By way of contradiction let us assume that $g(t)$ does not converge to . Let $\epsilon>0$ be such that for all $M>0$ there exists $t>M$ with $g(t)>\epsilon$.

We claim that for all $M,\epsilon^{\prime}>0$ there exists $t>M$ such that $g(t)<\epsilon^{\prime}$. Otherwise, we have a contradiction to the bound on the integral of $g(\cdot)$. Combined with our assumption, this means that for all $M>0$ we can find an interval $[t_{1},t_{2}]$, with $t_{1}>M$, where $g(t)$ transitions from $\frac{\epsilon}{2}$ to $\epsilon$. We now examine one such interval. Formally, for $t_{0}$ with $g(t_{0})<\frac{\epsilon}{2}$, we define:

Due to the fact that $g(\cdot)$ is continuous, $t_{2}$ and $t_{1}$ are well defined as they are the minimum and maximum, respectively, of closed non-empty sets bounded from below and above, respectively. Furthermore, notice that $t_{0}<t_{1}<t_{2}$. From the mean value theorem and the bound on the derivative of $g(\cdot)$ we have $t_{2}-t_{1}\geq\epsilon/2b$. Since $g(t)\geq\epsilon/2$ over the interval $[t_{1},t_{2}]$, this gives us $\int\nolimits_{t^{\prime}=t_{1}}^{t_{2}}g(t^{\prime})dt^{\prime}\geq\epsilon^{2}/4b$. Recall there are infinitely many such occurrences, implying that $\int\nolimits_{t^{\prime}=0}^{\infty}g(t^{\prime})dt^{\prime}=\infty$, in contradiction to the bound on the integral. ∎

Since $g(\cdot)$ is continuous over $[t_{0},\infty)$, and positive over $[t_{0},T)$, it is non-negative at $T$. In the case where $\gamma=1$, we have that $\dot{g}(t)\geq-a-b\cdot g(t)$. Dividing both sides by $a+b\cdot g(t)$ (positive since $a,b>0$ and $g(t)\geq 0$), and integrating over $t\in[t_{0},T]$, we have that:

The lower bound on $g(T)$ readily follows by rearranging the inequality above.

Dividing by $(a^{1/\gamma}+b^{1/\gamma}\cdot g(t))^{\gamma}$ (positive since $a,b>0$ and $g(t)\geq 0$), and integrating over $t\in[t_{0},T]$:

Rearranging the inequality above establishes the desired result. ∎

Then, $f(\theta(t))$ is monotonically non-increasing with respect to $t$.

The proof immediately follows from the fact that for any $t\in[0,\infty)$:

D.3 Proof of Proposition 1

For a quasi-norm $\left\|\cdot\right\|$, the weakened triangle inequality (see Footnote 2) implies that there exists a constant $c_{\left\|\cdot\right\|}\geq 1$ for which

Starting with $p=\infty$, the corresponding norm is the spectral norm $\left\|W_{x}\right\|_{S_{\infty}}:=\sigma_{1}(W_{x})$. When $x=0$, we have that $\sigma_{1}(W_{0})=1$. If $x>0$, then $\sigma_{1}(W_{x})=(x+\sqrt{x^{2}+4})~{}/~{}2>1$. Similarly, if $x<0$, then $\sigma_{1}(W_{x})=(-x+\sqrt{x^{2}+4})~{}/~{}2>1$. Therefore, $\left\|W_{x}\right\|_{S_{\infty}}$ attains its minimal value of $1$ if and only if $x=0$.

Moving to the case of $p\in(0,\infty)$, the corresponding quasi-norm is $\left\|W_{x}\right\|_{S_{p}}:=(\sigma_{1}(W_{x})^{p}+\sigma_{2}(W_{x})^{p})^{\frac{1}{p}}$. We now examine $\left\|W_{x}\right\|_{S_{p}}^{p}$ for $x>0$:

Differentiating with respect to $x$, we arrive at:

where in the first transition we used the fact that both $\left(x+\sqrt{x^{2}+4}\right)^{p-1}$ and $\left(-x+\sqrt{x^{2}+4}\right)^{p-1}$ are positive (as well as $x$). It then directly follows that $\left\|W_{x}\right\|_{S_{p}}^{p}$ and thus $\left\|W_{x}\right\|_{S_{p}}$ are monotonically increasing with respect to $x$ on $(0,\infty)$.

Similar arguments show that when $x<0$ the Schatten-$p$ quasi-norm of $W_{x}$ is monotonically decreasing with respect to $x$, implying that $\left\|W_{x}\right\|_{S_{p}}$ is minimized if and only if $x=0$. The claim relies on the fact that the Schatten-$p$ quasi-norm of $W_{x}$ is continuous with respect to $x$ for all $p\in(0,\infty)$. We note, however, that quasi-norms in general may be discontinuous. ∎

D.4 Proof of Proposition 2

As in the proof of Proposition 1 (Subappendix D.3), we denote by $W_{x}\in{\mathcal{S}}$ the solution matrix with $(W_{x})_{1,1}=x$. We begin by analyzing the behavior of $\sigma_{1}(W_{x})$ and $\sigma_{2}(W_{x})$ with respect to $x$. When $x=0$ the singular values are simply $\sigma_{1}(W_{0})=\sigma_{2}(W_{0})=1$. When $x$ is positive, the singular values may be written as:

Taking the derivative with respect to $x$, we arrive at:

Since $x>0$, we have that $d/dx~{}\sigma_{1}(W_{x})>0$ and $d/dx~{}\sigma_{2}(W_{x})<0$. In other words, $\sigma_{1}(W_{x})$ is monotonically increasing, while $\sigma_{2}(W_{x})$ is monotonically decreasing, when $x>0$. It can easily be verified that $\sigma_{1}(W_{x})$ and $\sigma_{2}(W_{x})$ are even functions of $x$, i.e. $\sigma_{1}(W_{x})=\sigma_{1}(W_{-x})$ and $\sigma_{2}(W_{x})=\sigma_{2}(W_{-x})$. It then follows that $\sigma_{1}(W_{x})$ is monotonically decreasing (conversely $\sigma_{2}(W_{x})$ is monotonically increasing) when $x<0$. Noticing that $\lim_{x\rightarrow\infty}\sigma_{1}(W_{x})=\infty$ and $\lim_{x\rightarrow\infty}\sigma_{2}(W_{x})=0$ (accordingly $\lim_{x\rightarrow-\infty}\sigma_{1}(W_{x})=\infty$ and $\lim_{x\rightarrow-\infty}\sigma_{2}(W_{x})=0$ ), we have a characterization of the behavior of $\sigma_{1}(W_{x})$ and $\sigma_{2}(W_{x})$.

We are now in a position to obtain the desired results for effective and infimal ranks. The effective rank (Definition 1) of $W_{x}$ can be written as

The binary entropy function is bounded by $\ln(2)$, hence, the effective rank over ${\mathcal{S}}$ is bounded by $2$. This upper bound is attained at $x=0$. According to the singular values analysis, when $\left\lvert x\right\rvert\rightarrow\infty$ we have that $\rho_{1}(W_{x})$ monotonically increases towards $1$, starting from the value $\rho_{1}(W_{0})=\frac{1}{2}$. Noticing that this implies the entropy function and effective rank monotonically decrease towards and $1$, respectively, completes the effective rank analysis.

Next, we analyze the infimal rank of ${\mathcal{S}}$ and the distance of $W_{x}$ from that infimal rank. The distance of $W_{x}$ from ${\mathcal{M}}_{1}$ is $D(W_{x},{\mathcal{M}}_{1})=\sigma_{2}(W_{x})$. Since $\lim_{x\rightarrow\infty}\sigma_{2}(W_{x})=0$, we have $D({\mathcal{S}},{\mathcal{M}}_{1})=0$. Clearly $D({\mathcal{S}},{\mathcal{M}}_{0})>0$, leading to the conclusion that the infimal rank of ${\mathcal{S}}$ is $1$. Finally, the analysis of $\sigma_{2}(W_{x})$ directly implies that the distance of $W_{x}$ from the infimal rank of ${\mathcal{S}}$ is maximized when $x=0$, monotonically tending to as $\left\lvert x\right\rvert\rightarrow\infty$. ∎

D.5 Proof of Theorem 1

In the following, as stated in Subappendix D.1, for results that hold for all $t\geq 0$ or when clear from the context, we omit the time index $t$. Furthermore, we denote the entries of the product matrix $W_{L:1}$ by $\{w_{i,j}\}_{i,j\in}$.

We begin by deriving loss-dependent bounds for $\left\lvert w_{1,1}\right\rvert,\sigma_{1}(W_{L:1})$ and $\sigma_{2}(W_{L:1})$. Writing the loss explicitly:

we can upper bound each of the non-negative terms separately. Multiplying by $2$ and taking the square root of both sides yields:

The following lemma characterizes the relation between $|w_{1,1}|$ and the loss.

From Lemma 6, the determinant of $W_{L:1}$ does not change signs and remains positive, i.e.:

An immediate consequence of the lemma above is that decreasing the loss towards zero drives $|w_{1,1}|$ towards infinity.

With this bound in hand, Lemma 19 below establishes bounds on the singular values of $W_{L:1}$. In turn, they will allow us to obtain the necessary results for effective rank (Definition 1) and distance from infimal rank of ${\mathcal{S}}$ (Definition 2).

The singular values of $W_{L:1}$ fulfill:

Define $W_{\mathcal{S}}:=\begin{pmatrix}w_{1,1}&1\\ 1&0\end{pmatrix}$, the orthogonal projection of $W_{L:1}$ onto the solution set ${\mathcal{S}}$. By Corollary 8.6.2 in we have that:

One can easily verify that $W_{\mathcal{S}}$ is a symmetric indefinite matrix with eigenvalues

Suppose that $w_{1,1}\geq 0$. We thus have:

By similar arguments, Equations (32) and (33) hold for $w_{1,1}<0$ as well. ∎

We turn to lower bound the quasi-norm of the product matrix. It holds that:

Plugging the inequality above and the lower bound on $|w_{1,1}|$ (Lemma 18) into Equation (35), we have:

Since $\left\|W_{L:1}\right\|$ is trivially lower bounded by zero, defining the constants

allows us, on the one hand, to arrive at a bound of the form:

D.5.2 Proof of Equation (9) (upper bound for effective rank)

D.5.3 Proof of Equation (10) (upper bound for distance from infimal rank)

According to Proposition 2, the infimal rank of ${\mathcal{S}}$ is $1$. The quantity we seek to upper bound is therefore $D(W_{L:1}(t),{\mathcal{M}}_{1})=\sigma_{2}(W_{L:1}(t))$. By Equation (32) in Lemma 19, for all $t\geq 0$ we have

D.6 Proof of Proposition 3

Define $W_{-1}$ to be the matrix obtained from $W$ by multiplying its first row by $-1$. On the one hand, symmetry around the origin implies that $W_{-1}$ and $W$ follow the same distribution. On the other hand, $\det(W_{-1})=-\det(W)$. Due to the fact that the set of matrices with zero determinant has probability under continuous distributions (see, e.g., Remark 2.5 in ), we may conclude $\Pr(\det(W)>0)=\Pr(\det(W)<0)=0.5$.

For $W_{1},W_{2},\ldots,W_{L}$ random matrices drawn independently, let $l\in[L]$ be the index such that $\Pr(\det(W_{l})>0)=0.5$. Since $Pr(\det(W_{l^{\prime}})=0)=0$ for any $l^{\prime}\in[L]$, the proof readily follows from determinant multiplicativity and the law of total probability:

An identical computation yields $\Pr\left(\det(W_{L}W_{L-1}\cdots W_{1})<0\right)=0.5$. ∎

D.7 Proof of Proposition 4

The proof makes use of the following lemma, proven in Subappendix D.7.1.

According to Lemma 20, the product matrix $W_{L:1}$ is symmetric and positive definite. Thus, we may write the loss and its gradient with respect to $W_{L:1}$ as:

where $\{w_{i,j}\}_{i,j\in}$ are the entries of $W_{L:1}$. Since the factors $W_{1}$ and $W_{2}$ are balanced at initialization (Equation (5)), the differential equation governing the product matrix (Lemma 4) for depth $L=2$ gives:

where the transition is by positive definiteness of $W_{L:1}$. Writing the differential equation of each entry separately, we have:

Let us characterize the behavior of these entries throughout time.

$w_{1,1}>0$ and is monotonically non-decreasing.

Since $W_{L:1}$ is positive definite, it follows that $w_{1,1}$ and $w_{2,2}$ are positive. Examining the behavior of $w_{1,2}$ (Equation (39)): on the one hand, when $w_{1,2}=0$ then $\dot{w}_{1,2}=w_{2,2}+w_{1,1}>0$, and on the other hand, when $w_{1,2}=1$ then $\dot{w}_{1,2}=-w_{2,2}<0$. Because $w_{1,2}$ is initialized at , it stays in the interval $$. Otherwise, by Lemma 14, we have a contradiction to the positivity of$\dot{w}_{1,2}$when$w_{1,2}=0$or its negativity when$w_{1,2}=1$. Similarly, if$w_{2,2}>\frac{1}{2}$we have$\dot{w}_{2,2}<2w_{1,2}(1-w_{1,2})-\frac{1}{2}\leq 0$. Since at initialization$w_{2,2}(0)=\alpha\leq 1$, by Lemma 14, it will not go above$1$. Lastly, since$w_{1,2}$is in the interval$$, it holds that$\dot{w}_{1,1}\geq 0$, i.e.$w_{1,1}$ is monotonically non-decreasing. ∎

We turn our focus to the derivative of the loss with respect to $t$:

Plugging in Equation (38) and recalling the fact that $\langle A,B\rangle=\operatorname{Tr}(A^{\top}B)$ for matrices $A,B$ of the same size:

where in the penultimate transition we bounded the square root of a sum by the sum of square roots. Returning to Equation (40) we have:

for $b=\frac{1}{2}\alpha$. We are now in a position to prove that $w_{1,2}\rightarrow 1$ as $t$ tends to infinity. Integrating both sides with respect to time:

Going back to the differential equation of $\dot{w}_{1,2}$ (Equation (39)), by applying the bounds on $w_{1,2}$ and $w_{2,2}$ (Lemma 21) we have that $\dot{w}_{1,2}\geq-1$. Defining $g(t):=(1-w_{1,2}(t))^{4}$, it then holds that $\dot{g}(t)\leq 4$. Since $g(\cdot)$ is non-negative and has an upper bounded integral and derivative, from Lemma 15, we can conclude that $lim_{t\rightarrow\infty}g(t)=0$ and $lim_{t\rightarrow\infty}w_{1,2}(t)=1$.

Such $\hat{t}$ exists since all terms above converge to . Returning to the differential equation of $\dot{w}_{2,2}$ (Equation (39)):

Recalling that $w_{2,2}(t)>0$ (Lemma 21), it follows that there exists $t_{\epsilon}\geq\hat{t}$ with $\dot{w}_{2,2}(t_{\epsilon})>-\epsilon$ (otherwise $w_{2,2}(t)$ goes to $-\infty$ as $t\rightarrow\infty$, in contradiction to the positivity of $w_{2,2}(t)$). For the above $t_{\epsilon}$, by rearranging the terms in Equation (42) we achieve $w_{2,2}(t_{\epsilon})<\sqrt{\epsilon}$. Finally, combined with Equation (41), the result readily follows:

The proof proceeds as follows. We initially consider initializations where $W_{1}(0),\ldots,W_{L}(0)$ form a symmetric factorization of $W_{L:1}(0)$ (Definition 4), and show that this ensures the product matrix stays symmetric. Then, we establish that for every balanced initial factors (Equation (5)) with a positive definite product matrix there exist alternative balanced factors such that: (i) the initial product matrix is the same; and (ii) the factors form a symmetric factorization of the product matrix. Since the product matrices for the original and the constructed initializations obey the exact same dynamics (Lemma 4), the proof concludes.

A straightforward result is that matrices with a symmetric factorization are symmetric themselves.

where $\sum_{l=1}^{L}i_{l}=k-1$ and $\binom{k-1}{i_{1},\ldots,i_{L}}=(k-1)!/\left(i_{1}!\cdots i_{L}!\right)$ for $i_{1},\ldots,i_{L}\in\{0,1,\ldots,k-1\}$. Taking the transpose of both sides we have: