Implicit Regularization Towards Rank Minimization in ReLU Networks

Introduction

A central puzzle in the theory of deep learning is how neural networks generalize even when trained without any explicit regularization, and when there are far more learnable parameters than training examples. In such an underdetermined optimization problem, there are many global minima with zero training loss, and gradient descent seems to prefer solutions that generalize well (see Zhang et al. (2017)). Hence, it is believed that gradient descent induces an implicit regularization (or implicit bias) (Neyshabur et al., 2015, 2017), and characterizing this regularization/bias has been a subject of extensive research.

Several works in recent years studied the relationship between the implicit regularization in linear neural networks and rank minimization. A main focus is on the matrix factorization problem, which corresponds to training a depth-2 linear neural network with multiple outputs w.r.t. the square loss, and is considered a well-studied test-bed for studying implicit regularization in deep learning. Gunasekar et al. (2018c) initially conjectured that the implicit regularization in matrix factorization can be characterized by the nuclear norm of the corresponding linear predictor. This conjecture was further studied in a string of works (e.g., Belabbas (2020); Arora et al. (2019); Razin and Cohen (2020)) and was formally refuted by Li et al. (2020). Razin and Cohen (2020) conjectured that the implicit regularization in matrix factorization can be explained by rank minimization, and also hypothesized that some notion of rank minimization may be key to explaining generalization in deep learning. Li et al. (2020) established evidence that the implicit regularization in matrix factorization is a heuristic for rank minimization. Razin et al. (2021) studied implicit regularization in tensor factorization (a generalization of matrix factorization). They demonstrated, both theoretically and empirically, implicit bias towards low-rank tensors. Going beyond factorization problems, Ji and Telgarsky (2018a, 2020) showed that in linear networks of output dimension $1$, gradient flow (GF) w.r.t. exponentially-tailed classification losses converges to networks where the weight matrix of every layer is of rank $1$.

However, once we move to nonlinear neural networks (which are by far the more common in practice), things are less clear. Empirically, a series of works studying neural network compression (cf. Denton et al. (2014); Yu et al. (2017); Alvarez and Salzmann (2017); Arora et al. (2018); Tukan et al. (2020)) showed that replacing the weight matrices by low-rank approximations results in only a small drop in accuracy. This suggests that the weight matrices in practice are not too far from being low-rank. However, whether they provably behave this way remains unclear.

In this work we consider fully-connected nonlinear networks employing the popular ReLU activation function, and study whether GF is biased towards networks where the weight matrices have low ranks. On the negative side, we show that already for small (depth and width $2$) ReLU networks, there is no rank-minimization bias in a rather strong sense. On the positive side, for deeper and possibly wider overparameterized networks, we identify reasonable settings where GF is biased towards low-rank solutions. In more details, our contributions are as follows:

Next, for ReLU networks that are overparameterized in terms of depth and have width $\geq 2$, we identify interesting settings in which GF is biased towards low ranks:

The implicit regularization in matrix factorization and linear neural networks with the square loss was extensively studied, as a first step toward understanding implicit regularization in more complex models (see, e.g., Gunasekar et al. (2018c); Razin and Cohen (2020); Arora et al. (2019); Belabbas (2020); Eftekhari and Zygalakis (2020); Li et al. (2018); Ma et al. (2018); Woodworth et al. (2020); Gidel et al. (2019); Li et al. (2020); Yun et al. (2020); Azulay et al. (2021); Razin et al. (2021)). As we already discussed, some of these works showed bias toward low ranks.

Organization. In Sec. 2 we provide necessary notations and definitions. In Sec. 3 we state our negative results for depth-$2$ networks. In Sec. 4 and 5 we state our positive results for deep ReLU networks. In Sec. 6 we describe the ideas for the proofs of the main theorems, with all formal proofs deferred to the appendix.

Preliminaries

Neural networks.

Optimization problem and gradient flow (GF).

We assume that the data is realizable, that is, $\min_{\boldsymbol{\theta}}L({\boldsymbol{\theta}})=0$. Moreover, we focus on settings where the network is overparameterized, in the sense that $L$ has multiple (or even infinitely many) global minima.

We consider gradient flow (GF) on the objective given in Eq. (1). This setting captures the behavior of gradient descent with an infinitesimally small step size. Let ${\boldsymbol{\theta}}(t)$ be the trajectory of GF. Starting from an initial point ${\boldsymbol{\theta}}(0)$, the dynamics of ${\boldsymbol{\theta}}(t)$ is given by the differential equation $\frac{d{\boldsymbol{\theta}}(t)}{dt}=-\nabla L_{X,Y}({\boldsymbol{\theta}}(t))$. Note that the ReLU function is not differentiable at . Practical implementations of gradient methods define the derivative $\sigma^{\prime}(0)$ to be some constant in $$. In this work we assume for convenience that$\sigma^{\prime}(0)=0$. We say that GF converges if$\lim_{t\to\infty}{\boldsymbol{\theta}}(t)$exists. In this case, we denote${\boldsymbol{\theta}}(\infty):=\lim_{t\to\infty}{\boldsymbol{\theta}}(t)$.

Gradient flow does not even approximately minimize ranks

In this section we consider rank minimization in depth-$2$ networks $N_{W,V}$ trained with the square loss. We show that even for the simple case of size-$2$ datasets, under mild assumptions, GF does not converge to a minimum-rank solution even approximately.

To make the setting non-trivial, we need to show that such low-rank zero-loss solutions exist at all. The following theorem shows that this is true for almost all size-$2$ datasets:

The theorem follows by constructing a network where the weight vectors of the neurons in the first layer have opposite directions (and hence the weight matrix is of rank $1$), such that each neuron is active for exactly one input. Then, it is possible to show that for an appropriate choice of the weights in the second layer the network achieves zero loss. See Appendix A for the formal proof.

Thm. 1 implies that zero-loss solutions of rank $1$ exist. However, we now show that GF does not converge to such solutions. We prove this result under the following assumptions:

The assumptions that $\mathbf{x}_{i},\mathbf{y}_{i}$ are of unit norm are mostly for technical convenience, and we believe that they are not essential.

and ${\left\|{\mathbf{v}_{i}(0)}\right\|}<\frac{1}{2}$ for all $i\in\{1,2\}$. If GF converges to a zero-loss solution $N_{W(\infty),V(\infty)}$, then $\operatorname{rank}(W(\infty))=2$.

By the above theorem, GF does not minimize the rank even in a very simple setting where the dataset contains two inputs with angle larger than $\pi/2$ (as long as the initialization point is sufficiently close to ). In particular, if the dataset is drawn from the uniform distribution on the sphere then this condition holds with probability $1/2$.

While Thm. 2 shows that GF does not minimize the rank, it does not rule out the possibility that it converges to a solution which is close to a low-rank solution. There are many ways to define such closeness, such as the ratio of the Frobenius and spectral norms, the Frobenius distance from a low-rank solution, or the exponential of the entropy of the singular values (cf. Rudelson and Vershynin (2007); Sanyal et al. (2019); Razin and Cohen (2020); Roy and Vetterli (2007)). However, for $2\times 2$ matrices they all boil down to either having the two rows of the matrix being nearly aligned, or having at least one of them very small (at least compared to the other). In the following theorem, we show that under the assumptions stated above, for any fixed dataset, with at least constant probability, GF converges to a zero-loss solution, where the two row vectors are bounded away from , the ratio of their norms are bounded, and the angle between them is bounded away from and from $\pi$ (all by explicit constants that depend just on the dataset and are large in general). Thus, with at least constant probability, GF does not minimize any reasonable approximate notion of rank.

Let $E$ be the event that GF converges to a zero-loss solution $N_{W(\infty),V(\infty)}$ such that

$\measuredangle\left(\mathbf{w}_{1}(\infty),\mathbf{w}_{2}(\infty)\right)\in\left[\frac{\pi}{2}-\left(\measuredangle(\mathbf{x}_{1},\mathbf{x}_{2})-\frac{\pi}{2}\right),\frac{3\pi}{4}+\frac{\measuredangle(\mathbf{x}_{1},\mathbf{x}_{2})-\pi/2}{2}\right]$,

${\left\|{\mathbf{w}_{i}(\infty)}\right\|}\in\left(\frac{\sqrt{3}}{2},\sqrt{\frac{1}{4}+\frac{4}{3\left(\sin\measuredangle(\mathbf{x}_{1},\mathbf{x}_{2})\right)^{2}}}\right)$ for all $i\in\left\{{1,2}\right\}$.

Then, $\Pr\left[E\right]\geq 2\cdot\left(\frac{\measuredangle(\mathbf{x}_{1},\mathbf{x}_{2})}{2\pi}\right)^{2}$.

We note that in Thm. 3 the weights in the second layer are initialized to zero, while in Thm. 2 the assumption on the initialization is weaker. This difference is for technical convenience, and we believe that Thm. 3 should hold also under weaker assumptions on the initialization, as the next empirical result demonstrates.

Our theorems imply that for standard initialization schemes, GF will not converge close to low-rank solutions, with some positive probability. We now present a simple experiment that corroborates this and suggests that, furthermore, this holds with high probability.

Equivalently, we have the following upper bound on the harmonic mean of the ratios $\frac{{\left\|{W_{i}^{*}}\right\|}_{F}}{{\left\|{W_{i}^{*}}\right\|}_{\sigma}}$:

By the above theorem if $k^{\prime}$ is much larger than $k$, then the average ratio between the spectral and the Frobenius norms (Eq. (3)) is at least roughly $1$. Likewise, the harmonic mean of the ratio between the Frobenius and the spectral norms (Eq. (4)), namely, the square root of the stable rank, is at most roughly $1$. Noting that both these ratios equal $1$ if and only if the matrix is of rank $1$, we see that there is a bias towards low-rank solutions as the depth $k^{\prime}$ of the trained network increases. Note that the result does not depend on the width of the networks. Thus, even if the width $m^{\prime}$ is large, the average ratio is close to $1$. Also, note that the network $N$ of depth $k$ in the theorem might have high ranks (e.g., rank $m$ for each weight matrix), but once we consider networks of a large depth $k^{\prime}$ then the dataset becomes realizable by a network of small average rank, and GF converges to such a network.

Rank minimization in deep networks with exponentially-tailed losses

In this section, we turn to consider GF in classification tasks with exponentially-tailed losses, namely, the exponential loss or the logistic loss.

The following well-known result characterizes the implicit bias in homogeneous neural networks trained with the logistic or the exponential loss:

Let $N_{{\boldsymbol{\theta}}}$ be a homogeneous ReLU neural network. Consider minimizing the average of either the exponential or the logistic loss over a binary classification dataset using GF. Suppose that the average loss converges to zero as $t\to\infty$. Then, GF converges in direction to a first order stationary point (KKT point) of the following maximum margin problem in parameter space:

Equivalently, we have the following upper bound on the harmonic mean of the ratios $\frac{{\left\|{W_{i}^{*}}\right\|}_{F}}{{\left\|{W_{i}^{*}}\right\|}_{\sigma}}$:

By the above theorem, if $k^{\prime}$ is much larger than $k$, then the average ratio between the spectral and the Frobenius norms (Eq. (7)) is at least roughly $1/\sqrt{2}$. Likewise, the harmonic mean of the ratio between the Frobenius and the spectral norms (Eq. (8)), i.e., the square root of the stable rank, is at most roughly $\sqrt{2}$. Note that the result does not depend on the width of the networks. Thus, it holds even if the width $m^{\prime}$ is very large. Similarly to the case of Thm. 4, we note that the network $N$ of depth $k$ might have high ranks (e.g., rank $m$ for each weight matrix), but once we consider networks of a large depth $k^{\prime}$, then the dataset becomes realizable by a network of small average rank, and GF converges to such a network.

The combination of the above result with Lemma 1 suggests that, in overparameterized deep fully-connected networks, GF tends to converge in direction to neural networks with low ranks. Note that we consider the exponential and the logistic losses, and hence if the loss tends to zero as $t\to\infty$, then we have ${\left\|{{\boldsymbol{\theta}}(t)}\right\|}\to\infty$. To conclude, in our case, the parameters tend to have an infinite norm and to converge in direction to a low-rank solution. Moreover, note that the ratio between the spectral and the Frobenius norms is invariant to scaling, and hence it suggests that after a sufficiently long time, GF tends to reach a network with low ranks.

Proof ideas

In this section we describe the main ideas for the proofs of Theorems 2, 3, 4 and 5. The full proofs are given in the appendix.

We define the following regions (see Fig. 2):

Intuitively, $\mathcal{D}$ defines the “dead” region where the relevant neuron will output on both $\mathbf{x}_{1},\mathbf{x}_{2}$; $\mathcal{S}$ is the “active” region where the relevant neuron will output a positive output on both $\mathbf{x}_{1},\mathbf{x}_{2}$; and $\mathcal{S}_{1},\mathcal{S}_{2}$ are the “partially active” regions, where the relevant neuron will output a positive output on one point, and on the other.

Assume towards contradiction that GF converges to some zero-loss network $N_{W(\infty),V(\infty)}$ with $\operatorname{rank}(W(\infty))<2$. Since $N_{W(\infty),V(\infty)}$ attains zero loss, then $Y=V(\infty)\sigma\left(W(\infty)X\right)$, and hence

Therefore, the weight vectors $\mathbf{w}_{1}(\infty)$ and $\mathbf{w}_{2}(\infty)$ are not in the region ${\cal D}$. Indeed, if $\mathbf{w}_{1}(\infty)$ or $\mathbf{w}_{2}(\infty)$ are in ${\cal D}$, then at least one of the rows of $\sigma(W(\infty)X)$ is zero, in contradiction to Eq. (9). In particular, it implies that $\mathbf{w}_{1}(\infty)$ and $\mathbf{w}_{2}(\infty)$ are non-zero. Since by our assumption we have $\operatorname{rank}(W(\infty))<2$, then we conclude that $\operatorname{rank}(W(\infty))=1$. We denote $\mathbf{w}_{2}(\infty)=\alpha\mathbf{w}_{1}(\infty)$ where $\alpha\neq 0$. Note that if $\alpha>0$, then $\sigma(\mathbf{w}_{2}(\infty)^{\top}\mathbf{x}_{j})=\alpha\sigma(\mathbf{w}_{1}(\infty)^{\top}\mathbf{x}_{j})$ for all $j\in\{1,2\}$, in contradiction to Eq. (9). Thus, $\alpha<0$. Since we also have $\mathbf{w}_{1}(\infty),\mathbf{w}_{2}(\infty)\not\in{\cal D}$, then one of these weight vectors is in ${\cal S}_{1}\setminus\partial{\cal S}_{1}$ and the other is in ${\cal S}_{2}\setminus\partial{\cal S}_{2}$ (as can be seen from Fig. 2). Assume w.l.o.g. that $\mathbf{w}_{1}(\infty)\in{\cal S}_{1}\setminus\partial{\cal S}_{1}$ and $\mathbf{w}_{2}(\infty)\in{\cal S}_{2}\setminus\partial{\cal S}_{2}$.

By observing the gradients of $L_{X,Y}$ w.r.t. $\mathbf{w}_{i}$ for $i\in\{1,2\}$, the following facts follow. First, if $\mathbf{w}_{i}(t)\in{\cal D}$ at some time $t$, then $\frac{d}{dt}\mathbf{w}_{i}(t)={\mathbf{0}}$, hence $\mathbf{w}_{i}$ remains at ${\cal D}$ indefinitely, in contradiction to $\mathbf{w}_{i}(\infty)\in{\cal S}_{i}\setminus\partial{\cal S}_{i}$. Thus, the trajectory $\mathbf{w}_{i}(t)$ does not visit ${\cal D}$. Second, if $\mathbf{w}_{i}(t)\in{\cal S}_{i}$ at time $t$, then $\frac{d}{dt}\mathbf{w}_{i}(t)\in\operatorname{span}\{\mathbf{x}_{i}\}$. Since $\mathbf{w}_{i}(\infty)\in{\cal S}_{i}\setminus\partial{\cal S}_{i}$, we can consider the last time $t^{\prime}$ that $\mathbf{w}_{i}$ enters ${\cal S}_{i}$, which can be either at the initialization (i.e., $t^{\prime}=0$) or when moving from ${\cal S}$ (i.e., $t^{\prime}>0$). For all time $t\geq t^{\prime}$ we have $\frac{d}{dt}\mathbf{w}_{i}(t)\in\operatorname{span}\{\mathbf{x}_{i}\}$. It allows us to conclude that $\mathbf{w}_{i}(\infty)$ must be in a region ${\cal A}_{i}$ which is illustrated in Fig. 3 (by the union of the orange and green regions).

Furthermore, we show that ${\left\|{\mathbf{w}_{i}(\infty)}\right\|}$ cannot be too small, namely, obtaining a lower bound on ${\left\|{\mathbf{w}_{i}(\infty)}\right\|}$. First, a theorem from Du et al. (2018) implies that ${\left\|{\mathbf{w}_{i}(t)}\right\|}^{2}-{\left\|{\mathbf{v}_{i}(t)}\right\|}^{2}$ remains constant throughout the training. Since at the initialization both ${\left\|{\mathbf{w}_{i}(0)}\right\|}$ and ${\left\|{\mathbf{v}_{i}(0)}\right\|}$ are small, the consequence is that ${\left\|{\mathbf{v}_{i}(\infty)}\right\|}$ is small if ${\left\|{\mathbf{w}_{i}(\infty)}\right\|}$ is small. Also, since $N_{W(\infty),V(\infty)}$ attains zero loss and $\mathbf{w}_{i}(\infty)\in{\cal S}_{i}$ for all $i\in\{1,2\}$, then we have $\mathbf{y}_{i}=\mathbf{v}_{i}(\infty)(\mathbf{w}_{i}(\infty)^{\top}\mathbf{x}_{i})$, namely, only the $i$-th hidden neuron contributes to the output of $N_{W(\infty),V(\infty)}$ for the input $\mathbf{x}_{i}$. Since ${\left\|{\mathbf{y}_{i}}\right\|}={\left\|{\mathbf{x}_{i}}\right\|}=1$, it is impossible that both ${\left\|{\mathbf{w}_{i}(\infty)}\right\|}$ and ${\left\|{\mathbf{v}_{i}(\infty)}\right\|}$ are small. Hence, we are able to obtain a lower bound on ${\left\|{\mathbf{w}_{i}(\infty)}\right\|}$, which implies that $\mathbf{w}_{i}(\infty)$ is in a region ${\cal F}_{i}$ which is illustrated in Fig. 3.

Finally, we show that since $\mathbf{w}_{1}(\infty)\in{\cal F}_{1}$ and $\mathbf{w}_{2}(\infty)\in{\cal F}_{2}$ then the angle between $\mathbf{w}_{1}(\infty)$ and $\mathbf{w}_{2}(\infty)$ is smaller than $\pi$, in contradiction to $\mathbf{w}_{2}(\infty)=\alpha\mathbf{w}_{1}(\infty)$.

2 Theorem 3

We show that if the initialization is such that $\mathbf{w}_{1}(0)\in{\cal S}_{1}\setminus\partial{\cal S}_{1}$ and $\mathbf{w}_{2}(0)\in{\cal S}_{2}\setminus\partial{\cal S}_{2}$ (or, equivalently, that $\mathbf{w}_{1}(0)\in{\cal S}_{2}\setminus\partial{\cal S}_{2}$ and $\mathbf{w}_{2}(0)\in{\cal S}_{1}\setminus\partial{\cal S}_{1}$), then GF converges to a zero-loss network, and ${\left\|{\mathbf{w}_{1}(\infty)}\right\|},{\left\|{\mathbf{w}_{2}(\infty)}\right\|}$, $\measuredangle(\mathbf{w}_{1}(\infty),\mathbf{w}_{2}(\infty))$ are in the required intervals. Since by simple geometric arguments we can show that the initialization satisfies this requirement with probability at least $2\cdot\left(\frac{\measuredangle(\mathbf{x}_{1},\mathbf{x}_{2})}{2\pi}\right)^{2}$, the theorem follows.

Indeed, suppose that $\mathbf{w}_{1}(0)\in{\cal S}_{1}\setminus\partial{\cal S}_{1}$ and $\mathbf{w}_{2}(0)\in{\cal S}_{2}\setminus\partial{\cal S}_{2}$. We argue that GF converges to a zero-loss network and ${\left\|{\mathbf{w}_{1}(\infty)}\right\|},{\left\|{\mathbf{w}_{2}(\infty)}\right\|},\measuredangle(\mathbf{w}_{1}(\infty),\mathbf{w}_{2}(\infty))$ are in the required intervals, as follows. By analyzing the dynamics of GF for such an initialization, we show that for all $t$ and $i$ we have $\frac{d}{dt}\mathbf{w}_{i}(t)=C_{i}(t)\mathbf{x}_{i}$ for some $C_{i}(t)\geq 0$. Thus, $\mathbf{w}_{i}(t)$ moves only in the direction of $\mathbf{x}_{i}$, and $\mathbf{w}_{i}(t)\in{\cal S}_{i}\setminus\partial{\cal S}_{i}$ for all $t$. Moreover, we are able to prove that these properties of the trajectories $\mathbf{w}_{1}(t)$ and $\mathbf{w}_{2}(t)$ imply that GF converges to a zero-loss network $N_{W(\infty),V(\infty)}$. Then, by similar arguments to the proof of Thm. 2 we have $\mathbf{w}_{i}(\infty)\in{\cal F}_{i}$ for all $i\in\{1,2\}$, where ${\cal F}_{i}$ are the regions from Fig. 3, and it allows us to obtain the required bounds on ${\left\|{\mathbf{w}_{1}(\infty)}\right\|},{\left\|{\mathbf{w}_{2}(\infty)}\right\|}$, and $\measuredangle(\mathbf{w}_{1}(\infty),\mathbf{w}_{2}(\infty))$.

3 Theorems 4 and 5

The intuition for the proofs of both theorems can be roughly described as follows. If the dataset is realizable by a shallow network where the Frobenius norm of each layer is $B$, then it is also realizable by a deep network where the Frobenius norm of each layer is $B^{*}$, where $B^{*}$ is much smaller than $B$. Moreover, if the network is sufficiently deep then $B^{*}$ is not much larger than $1$. On the other hand, since for the input $\mathbf{x}_{i}$ with ${\left\|{\mathbf{x}_{i}}\right\|}\leq 1$ the output of the network is of size at least $1$, then the average spectral norm of the layers is at least $1$. Hence, the average ratio between the spectral and the Frobenius norms cannot be too small.

We now describe the proof ideas in a bit more detail, starting with Thm. 4. We use the network $N$ of width $m$ and depth $k$ to construct a network $N^{\prime}$ of width $m^{\prime}\geq m$ and depth $k^{\prime}>k$ as follows. The first $k$ layers of $N^{\prime}$ are obtained by scaling the layers of $N$ by a factor $\alpha:=\left(\frac{1}{B}\right)^{\frac{k^{\prime}-k}{k^{\prime}}}$. Since the output dimension of $N$ is $1$, then the $k$-th hidden layer of $N^{\prime}$ has width $1$. Then, the network $N^{\prime}$ has $k^{\prime}-k$ additional layers of width $1$, such that the weight in each of these layers is $\beta:=\left(\frac{1}{B}\right)^{-\frac{k}{k^{\prime}}}$. Overall, given input $\mathbf{x}_{i}$, we have

We denote by ${\boldsymbol{\theta}}^{\prime}$ the parameters of the network $N^{\prime}$.

Let ${\boldsymbol{\theta}}^{*}=\left[W^{*}_{1},\ldots,W^{*}_{k^{\prime}}\right]$ be a global optimum of Problem 2. From the optimality of ${\boldsymbol{\theta}}^{*}$ it is possible to show that the layers in ${\boldsymbol{\theta}}^{*}$ must be balanced, namely, ${\left\|{W^{*}_{i}}\right\|}_{F}={\left\|{W^{*}_{j}}\right\|}_{F}$ for all $i,j\in[k^{\prime}]$. We denote by $B^{*}$ the Frobenius norm of the layers. From the global optimality of ${\boldsymbol{\theta}}^{*}$ we also have ${\left\|{{\boldsymbol{\theta}}^{*}}\right\|}\leq{\left\|{{\boldsymbol{\theta}}^{\prime}}\right\|}$. Hence, by a calculation we can obtain

Moreover, we show that since there is $i\in[n]$ with ${\left\|{\mathbf{x}_{i}}\right\|}\leq 1$ and $y_{i}\geq 1$, then

Combining the last two displayed equations we get

Note that the arguments above do not depend on the ranks of the layers in $N$. Thus, even if the weight matrices in $N$ have high ranks, once we consider deep networks which are optimal solutions to Problem 2, the ratios between the spectral and the Frobenius norms are close to $1$.

We now turn to Thm. 5. The proof follows a similar approach to the proof of Thm. 4. However, here the outputs of the network $N$ can be either positive or negative. Hence, when constructing the network $N^{\prime}$ as above, we cannot have width $1$ in layers $k+1,\ldots,k^{\prime}$, since the ReLU activation will not allow us to pass both positive and negative values. Still, we show that we can define a network $N^{\prime}$ such that the width in layers $k+1,\ldots,k^{\prime}$ is $2$ and we have $N^{\prime}(\mathbf{x}_{i})=N(\mathbf{x}_{i})$ for all $i\in[n]$. Then, the theorem follows by arguments similar to the proof of Thm. 4, with the required modifications.

Funding Acknowledgements

This research is supported in part by European Research Council (ERC) grant 754705.

References

Appendix A Proof of Thm. 1

Consider the matrix $\sigma(WX)$ of size ${d_{\text{hidden}}}\times n$, where $\sigma$ acts entrywise. Note that our assumption on $W$ implies that $\operatorname{rank}\left(\sigma(WX)\right)=n$. Thus, the ${d_{\text{hidden}}}\times{d_{\text{hidden}}}$ matrix $Z:=\begin{bmatrix}\sigma(WX)^{\dagger}\\ 0\end{bmatrix}$ satisfies $Z\sigma(WX)=\begin{bmatrix}I_{n}\\ 0\end{bmatrix}$, where $A^{\dagger}$ denotes the Moore-Penrose inverse of a matrix $A$, and $I_{n}$ is the $n\times n$ identity matrix. Hence, the matrix $M:=\begin{bmatrix}Y&0\end{bmatrix}$ of dimensions ${d_{\text{out}}}\times{d_{\text{hidden}}}$ yields $MZ\sigma(WX)=Y$. By setting $V:=MZ$, the network $N_{W,V}$ achieves zero loss. Namely, $N_{W,V}(X)=Y$. ∎

Appendix B Proof of Thm. 2

We define the following regions of interest:

Assume, for the sake of contradiction, that GF converges to some zero-loss network $N_{W(\infty),V(\infty)}$ with $\operatorname{rank}(W(\infty))<2$. On the one hand, in Lemma 3 we show that the weight vectors $\mathbf{w}_{1}(\infty)$ and $\mathbf{w}_{2}(\infty)$ are non-zero, and satisfy $\mathbf{w}_{2}(\infty)=\alpha\mathbf{w}_{1}(\infty)$ with $\alpha<0$. It implies that the straight line that connects $\mathbf{w}_{1}(\infty)$ and $\mathbf{w}_{2}(\infty)$, denoted as $\mathbf{w}_{1}\mathbf{w}_{2}$, goes through the origin. On the other hand, in Lemma 4 we show that $\mathbf{w}_{i}(\infty)\not\in\mathcal{D}$ for every $i\in\{1,2\}$. In other words, $\mathbf{w}_{1}\mathbf{w}_{2}$ cannot intersect the $\mathcal{D}\setminus\left\{{{\mathbf{0}}}\right\}$ region. Thus, one neuron must lie in $\mathcal{S}_{1}\setminus\partial\mathcal{S}_{1}$ and the other neuron in $\mathcal{S}_{2}\setminus\partial\mathcal{S}_{2}$. W.l.o.g., let $\mathbf{w}_{i}(\infty)\in\mathcal{S}_{i}\setminus\partial\mathcal{S}_{i}$ for all $i\in\{1,2\}$. Therefore, by Lemma 6, it holds that \measuredangle\big{(}\mathbf{w}_{1}(\infty),\mathbf{w}_{2}(\infty)\big{)}\in\Big{[}\pi-\measuredangle(\mathbf{x}_{1},\mathbf{x}_{2}),\measuredangle(\mathbf{x}_{1},\mathbf{x}_{2})+2\arcsin{\frac{2\max_{i\in}{\left\|{\mathbf{w}_{i}(0)}\right\|}}{\sqrt{3}}}\Big{)}. To complete the proof by contradiction, it remains to show that \measuredangle\big{(}\mathbf{w}_{1}(\infty),\mathbf{w}_{2}(\infty)\big{)}<\pi so that $\mathbf{w}_{2}(\infty)\neq\alpha\mathbf{w}_{1}(\infty)$. Recall that we initialize the network such that {\left\|{\mathbf{w}_{i}(0)}\right\|}<\frac{\sqrt{3}}{2}\cos\big{(}{\frac{\measuredangle(\mathbf{x}_{1},\mathbf{x}_{2})}{2}}\big{)}=\frac{\sqrt{3}}{2}\sin\big{(}\frac{\pi}{2}-\frac{\measuredangle(\mathbf{x}_{1},\mathbf{x}_{2})}{2}\big{)}. Hence, \measuredangle\big{(}\mathbf{w}_{1}(\infty),\mathbf{w}_{2}(\infty)\big{)}<\pi, as required.

Now, we prove that $\alpha<0$. Assume for the sake of contradiction that $\alpha>0$. Then, we have $\sigma(\mathbf{w}_{2}^{\top}\mathbf{x}_{j})=\alpha\sigma(\mathbf{w}_{1}^{\top}\mathbf{x}_{j})$ for all $j\in$. Thus, $\operatorname{rank}\left(\sigma\left(WX\right)\right)\leq 1$. Therefore, $\operatorname{rank}\left(V\sigma\left(WX\right)\right)\leq\min\{\operatorname{rank}(V),\operatorname{rank}\left(\sigma\left(WX\right)\right)\}\leq 1$. Since by Assumption 1 we have $\operatorname{rank}\left(Y\right)=2$, then we conclude that $Y\neq V\sigma(WX)$, in contradiction to the zero-loss assumption. Therefore, $\alpha<0$, as required. ∎

Assume that there is $i\in$ such that $\mathbf{w}_{i}\in\mathcal{D}$. Hence, $\sigma(\mathbf{w}_{i}^{\top}\mathbf{x}_{j})=0$ for all $j\in$. Thus, $\operatorname{rank}\left(\sigma\left(WX\right)\right)\leq 1$. Therefore, $\operatorname{rank}\left(V\sigma\left(WX\right)\right)\leq\min\{\operatorname{rank}(V),\operatorname{rank}\left(\sigma\left(WX\right)\right)\}\leq 1$. Since by Assumption 1 we have $\operatorname{rank}\left(Y\right)=2$, then we conclude that $Y\neq V\sigma(WX)$, in contradiction to the zero-loss assumption. ∎

Note that if $\mathbf{w}_{i}(t)\in\mathcal{D}$ then the gradient of $L_{X,Y}$ w.r.t. $\mathbf{w}_{i}$ is zero. Hence $\mathbf{w}_{i}$ remains constant for all $t^{\prime}\geq t$. Therefore, $\mathbf{w}_{i}(\infty)\in\mathcal{D}$. The claim now follows from Lemma 4. ∎

Case $t_{0}^{(i)}=0$: If the last time that $\mathbf{w}_{i}$ enters $\mathcal{S}_{i}$ is at initialization, then we have $t_{0}^{(i)}=0$. Our assumptions on the initialization imply that:

Note that by Lemma 5 it is not possible that $\mathbf{w}_{i}(0)\in\mathcal{D}$, and hence we cannot have $\mathbf{w}_{i}(0)\in\partial\mathcal{S}_{i}\cap\mathcal{D}$.

Otherwise (i.e., $t_{0}^{(i)}>0$): In that case, $t_{0}^{(i)}$ is when the neuron moves from some other region to $\mathcal{S}_{i}$. The other region can only be $\mathcal{S}$ or $\mathcal{D}$, due to the geometry that Assumption 2 imposes. Since Lemma 5 implies that at any time no neuron is in $\mathcal{D}$, then the previous region is necessarily $\mathcal{S}$. Hence, we have:

Therefore, the region of all neurons that are reachable under the aforementioned dynamics of GF is

We can assume that $\lambda\geq 0$ in the above definition, because every $\bar{\mathbf{a}}\in\{\mathbf{w}+\lambda\mathbf{x}_{i}\mid\mathbf{w}\in\mathcal{E}_{i},\lambda<0\}\setminus\mathcal{A}_{i}$ satisfies $\bar{\mathbf{a}}\notin\mathcal{S}_{i}$.

We denote $\epsilon_{0}^{(i)}:=\|\mathbf{w}_{i}(0)\|^{2}-\|\mathbf{v}_{i}(0)\|^{2}$. By Lemma 9 we have $\epsilon_{0}^{(i)}=\|\mathbf{w}_{i}(t)\|^{2}-\|\mathbf{v}_{i}(t)\|^{2}$ for any time $t\geq 0$, and hence $\epsilon_{0}^{(i)}=\|\mathbf{w}_{i}(\infty)\|^{2}-\|\mathbf{v}_{i}(\infty)\|^{2}$. By Lemma 8 we obtain $\|\mathbf{w}_{i}(\infty)\|\geq\sqrt{1-|\epsilon_{0}^{(i)}|}$ for every $i\in$. We define a new region of interest: The set of all feasible neurons at the convergence of GF, i.e., neurons that are reachable and satisfy the minimal norm requirement. Formally,

The regions $\mathcal{A}_{i}$ and $\mathcal{F}_{i}$ are illustrated in Figure 3. Recall that all neurons are initialized such that $\|\mathbf{w}_{i}(0)\|,\|\mathbf{v}_{i}(0)\|<\frac{1}{2}$ for all $i\in$. Thus, we have $\left|\epsilon_{0}^{(i)}\right|<(\frac{1}{2})^{2}=\frac{1}{4}$ for all $i\in$. Hence,

We now consider the angle between $\mathbf{w}_{1}(\infty)$ and $\mathbf{w}_{2}(\infty)$. On the one hand, the minimal angle between the neurons is achieved when $\mathbf{w}_{1}(\infty)$ and $\mathbf{w}_{2}(\infty)$ lie on the “non-dead boundaries” of $\mathcal{S}_{1},\mathcal{S}_{2}$. That is,

where $\mathbf{b}_{i}\in\partial(\mathcal{S}_{i})\setminus\mathcal{D}$. On the other hand, the angle between the neurons is maximized when

Note that in the above expression the angle \measuredangle\big{(}\mathbf{w}_{i}(\infty),\mathbf{x}_{i}\big{)} corresponds to the case where $\mathbf{w}_{i}(\infty)$ is in the direction w.r.t. $\mathbf{x}_{i}$ which is closer to $\mathcal{D}$ and farther from $\mathcal{S}$. Due to Eq. (10) and the definition of $\mathcal{F}_{i}$, the appropriate angle \measuredangle\big{(}\mathbf{w}_{i}(\infty),\mathbf{x}_{i}\big{)} in the above expression can be upper bounded by $\arcsin\frac{{\left\|{\mathbf{w}_{i}(0)}\right\|}}{\|\mathbf{w}_{i}(\infty)\|}$. It corresponds to the case where $\mathbf{w}_{i}$ is initialized in $\mathcal{S}_{i}$ such that $\measuredangle(\mathbf{w}_{i}(0),\mathbf{x}_{i})$ is close to $\pi/2$, and $\mathbf{w}_{i}$ follows the trajectory from Eq. (10). Using Eq. (11) we have $\arcsin\frac{{\left\|{\mathbf{w}_{i}(0)}\right\|}}{\|\mathbf{w}_{i}(\infty)\|}<\arcsin\frac{2{\left\|{\mathbf{w}_{i}(0)}\right\|}}{\sqrt{3}}$. Hence, we get

Combining the above with Eq. (12) we obtain

Finally, we obtain an upper bound for $\|\mathbf{w}_{i}(\infty)\|$. We have \mathbf{w}_{i}(\infty)^{\top}\mathbf{x}_{i}=\|\mathbf{w}_{i}(\infty)\|\cdot\|\mathbf{x}_{i}\|\cos{\measuredangle\big{(}\mathbf{w}_{i}(\infty),\mathbf{x}_{i}\big{)}}>\frac{\sqrt{3}}{2}\cos{\measuredangle\big{(}\mathbf{w}_{i}(\infty),\mathbf{x}_{i}\big{)}} for all $i\in$. Note that \measuredangle\big{(}\mathbf{w}_{i}(\infty),\mathbf{x}_{i}\big{)} corresponds either to the case where $\mathbf{w}_{i}(\infty)$ is in the direction w.r.t. $\mathbf{x}_{i}$ which is closer to $\mathcal{D}$ and farther from $\mathcal{S}$, or closer to $\mathcal{S}$ and farther from $\mathcal{D}$. For the former case, we saw that \measuredangle\big{(}\mathbf{w}_{i}(\infty),\mathbf{x}_{i}\big{)}<\arcsin{\frac{2{\left\|{\mathbf{w}_{i}(0)}\right\|}}{\sqrt{3}}}. In the latter case, \measuredangle\big{(}\mathbf{w}_{i}(\infty),\mathbf{x}_{i}\big{)}=\measuredangle\big{(}\mathbf{x}_{1},\mathbf{x}_{2}\big{)}-\measuredangle\big{(}\mathbf{w}_{i}(\infty),\mathbf{x}_{3-i}\big{)}\leq\measuredangle\big{(}\mathbf{x}_{1},\mathbf{x}_{2}\big{)}-\frac{\pi}{2}. Therefore, \mathbf{w}_{i}(\infty)^{\top}\mathbf{x}_{i}>\frac{\sqrt{3}}{2}\cos\max{\left\{{\arcsin{\frac{2{\left\|{\mathbf{w}_{i}(0)}\right\|}}{\sqrt{3}}},\measuredangle\big{(}\mathbf{x}_{1},\mathbf{x}_{2}\big{)}-\frac{\pi}{2}}\right\}}. Since the network has zero-loss, i.e., it interpolates the entire dataset, then we have that $\mathbf{v}_{i}(\infty)=\frac{1}{\mathbf{w}_{i}(\infty)^{\top}\mathbf{x}_{i}}\mathbf{y}_{i}$. Hence,

By Lemma 9, we have $\|\mathbf{w}_{i}(\infty)\|^{2}-\|\mathbf{v}_{i}(\infty)\|^{2}=\|\mathbf{w}_{i}(0)\|^{2}-\|\mathbf{v}_{i}(0)\|^{2}<\frac{1}{4}$. Therefore,

The derivative of the $L_{X,Y}$ w.r.t. the matrix $W$ is

Here, $\odot$ denotes the Hadamard product (i.e., the entrywise product). Note that $\frac{\partial L_{X,Y}\left(N_{W,V}\right)}{\partial W}$ is a matrix whose $(i,j)$-th entry is $\frac{\partial L_{X,Y}\left(W,V\right)}{\partial W_{i,j}}$. We denote the $i$-th row of $\sigma^{\prime}\left(WX\right)$ by $\sigma^{\prime}\left(WX\right)_{i}$. We have

If $\mathbf{w}_{i}\in\mathcal{S}_{i}$ then the $j$-th entry of the aforementioned row vector is

Since the derivative of the loss w.r.t. the $i$-th neuron $\mathbf{w}_{i}$ is the $i$-th row of $\frac{\partial}{\partial W}L_{X,Y}\left(W,V\right)$, we conclude that

By setting $c_{t}^{(i)}=-\alpha^{(i)}$, the proof is done. ∎

Since the network has zero loss, for all $i\in$ we have

Since $\mathbf{w}_{i}\in\mathcal{S}_{i}$ for every $i\in$, we have $\sigma(\mathbf{w}_{k}^{\top}\mathbf{x}_{i})=\begin{cases}\mathbf{w}_{i}^{\top}\mathbf{x}_{i}&\text{if }k=i\\ 0&\text{otherwise}\end{cases}$. Hence, the above expression is equal to

Case $\|\mathbf{w}_{i}\|\leq\|\mathbf{v}_{i}\|$: We have that $\|\mathbf{v}_{i}\|^{2}\geq 1$. Then,

Otherwise: Similarly, we have $\|\mathbf{w}_{i}\|^{2}\geq 1$. Then,

Let $N_{{\boldsymbol{\theta}}}$ be a fully-connected depth-$k$ ReLU network, where $k>1$. Denote ${\boldsymbol{\theta}}=[W^{(1)},\ldots,W^{(k)}]$. Consider minimizing any differentiable loss function (e.g., the square loss) over a dataset using GF. Then, for every $l\in[k-1]$ at all time $t$ we have

Moreover, for every $l\in[k-1]$ and $i\in[d_{l}]$ at all time $t$ we have

where $W^{(l)}[i,:]$ is the vector of incoming weights to the $i$-th neuron in the $l$-th hidden layer (i.e., the $i$-th row of $W^{(l)}$), and $W^{(l+1)}[:,i]$ is the vector of outgoing weights from this neuron (i.e., the $i$-th column of $W^{(l+1)}$).

Appendix C Proof of Thm. 3

for all $i\in$, where $\phi_{i}:=(\mathbf{w}_{i}^{\top}\mathbf{x}_{i})\mathbf{v}_{i}-\mathbf{y}_{i}=N_{W,V}(\mathbf{x}_{i})-\mathbf{y}_{i}$. We denote the parameters of the network by ${\boldsymbol{\theta}}=[W,V]$. Moreover, when $\mathbf{w}_{i}\in\mathcal{S}_{i}\setminus\partial\mathcal{S}_{i}$ for all $i\in$ we denote $L^{i}_{X,Y}({\boldsymbol{\theta}})=\frac{1}{2}{\left\|{\phi_{i}}\right\|}^{2}$. Then, we have $L_{X,Y}({\boldsymbol{\theta}})=\sum_{i=1}^{2}L^{i}_{X,Y}({\boldsymbol{\theta}})$.

Let $t_{1}>0$ and suppose that for all $t\in[0,t_{1}]$ and $i\in$ we have $\mathbf{w}_{i}(t)\in\mathcal{S}_{i}\setminus\partial\mathcal{S}_{i}$, and that $\mathbf{v}_{i}(0)={\mathbf{0}}$. Then, we have $L^{i}_{X,Y}({\boldsymbol{\theta}}(t_{1}))<L^{i}_{X,Y}({\boldsymbol{\theta}}(0))$. Moreover, for every time $t$ where $\mathbf{w}_{i}(t)\in\mathcal{S}_{i}\setminus\partial\mathcal{S}_{i}$ for all $i\in$ we have $\frac{d}{dt}L^{i}_{X,Y}({\boldsymbol{\theta}}(t))\leq 0$.

For time $t$ such that $\mathbf{w}_{i}(t)\in\mathcal{S}_{i}\setminus\partial\mathcal{S}_{i}$ for all $i\in$ we denote $F_{i}(t):=L^{i}_{X,Y}({\boldsymbol{\theta}}(t))=\frac{1}{2}{\left\|{\phi_{i}(t)}\right\|}^{2}$. Let ${\boldsymbol{\theta}}_{i}:=[\mathbf{w}_{i},\mathbf{v}_{i}]$. We have

where we used the fact that $L^{i}_{X,Y}({\boldsymbol{\theta}})$ depends only on ${\boldsymbol{\theta}}_{i}$. Therefore, $\frac{d}{dt}L^{i}_{X,Y}({\boldsymbol{\theta}}(t))\leq 0$.

Note that ${\left\|{\nabla_{{\boldsymbol{\theta}}_{i}}L^{i}_{X,Y}({\boldsymbol{\theta}}(t))}\right\|}^{2}$ is continuous as a function of $t$, and at time we have

where the last inequality is since $\mathbf{w}_{i}^{\top}(0)\mathbf{x}_{i}>0$ and $\mathbf{y}_{i}\neq{\mathbf{0}}$. Combining the above with Eq. (C), we conclude that there is some small enough $t_{0}\in(0,t_{1})$ such that for all $t\in[0,t_{0}]$ we have $\frac{d}{dt}F_{i}(t)<0$. Moreover, Eq. (C) implies that for all $t\in[t_{0},t_{1}]$ we have $\frac{d}{dt}F_{i}(t)\leq 0$. Hence, $F_{i}(t_{1})\leq F_{i}(t_{0})<F_{i}(0)$. ∎

Suppose that we initialize ${\boldsymbol{\theta}}(0)$ such that $\mathbf{w}_{i}(0)\in\mathcal{S}_{i}\setminus\partial\mathcal{S}_{i}$ and $\mathbf{v}_{i}(0)={\mathbf{0}}$ for all $i\in$. For every sufficiently small $t^{\prime}>0$ we have for every $t\in[0,t^{\prime}]$ and $i\in$ that $\mathbf{w}_{i}(t)\in\mathcal{S}_{i}\setminus\partial{S}_{i}$, and at time $t^{\prime}$ we have $\mathbf{v}_{i}^{\top}(t^{\prime})\phi_{i}(t^{\prime})<0$ and $\mathbf{v}_{i}(t^{\prime})\in\operatorname{span}\{\mathbf{y}_{i}\}$. Moreover, $L^{i}_{X,Y}({\boldsymbol{\theta}}(t^{\prime}))<L^{i}_{X,Y}({\boldsymbol{\theta}}(0))$.

Since $\mathbf{w}_{i}(0)\in\mathcal{S}_{i}\setminus\partial\mathcal{S}_{i}$ then $\mathbf{w}_{i}^{\top}(0)\mathbf{x}_{i}>0$ and hence we obtain $\frac{d}{dt}g_{i}(0)<0$.

Overall, the function $g_{i}$ is continuously differentiable with $g_{i}(0)=0$ and $\frac{d}{dt}g_{i}(0)<0$ and therefore we have $g_{i}(t^{\prime})<0$ for every small enough $t^{\prime}>0$.

It remains to show that $\mathbf{v}_{i}(t^{\prime})\in\operatorname{span}\{\mathbf{y}_{i}\}$. Since for every $t\in[0,t^{\prime}]$ we have $\mathbf{w}_{i}(t)\in\mathcal{S}_{i}\setminus\partial\mathcal{S}_{i}$, then for every $t\in[0,t^{\prime}]$ we have

Since the above holds for all $t\in[0,t^{\prime}]$ and $\mathbf{v}_{i}(0)={\mathbf{0}}$, then for all $t\in[0,t^{\prime}]$ we have $\mathbf{v}_{i}(t)\in\operatorname{span}\{\mathbf{y}_{i}\}$. Thus, $\mathbf{v}_{i}$ remains on the line $\operatorname{span}\{\mathbf{y}_{i}\}$. ∎

Suppose that we initialize ${\boldsymbol{\theta}}(0)$ such that $\mathbf{w}_{i}(0)\in\mathcal{S}_{i}\setminus\partial\mathcal{S}_{i}$ and $\mathbf{v}_{i}(0)={\mathbf{0}}$ for all $i\in$. Let $t^{\prime}>0$ as in Lemma 11, and denote $\mathbf{w}^{\prime}_{i}:=\mathbf{w}_{i}(t^{\prime})$ for $i\in$. Let

Then, for all $t\geq t^{\prime}$ we have ${\boldsymbol{\theta}}(t)\in G$.

Moreover, for all $t_{2}\geq t_{1}\geq t^{\prime}$ and all $i\in$ we have

By Lemma 11 we have ${\boldsymbol{\theta}}(t^{\prime})\in G$. Let $t\geq t^{\prime}$ and suppose that ${\boldsymbol{\theta}}(t)\in G$. Note that for all $i\in$ we have $\mathbf{w}_{i}(t)=\mathbf{w}^{\prime}_{i}+c_{i}(t)\mathbf{x}_{i}$ for some $c_{i}(t)\geq 0$. Since $\mathbf{w}^{\prime}_{i}\in\mathcal{S}_{i}\setminus\partial\mathcal{S}_{i}$ then we also have $\mathbf{w}_{i}(t)\in\mathcal{S}_{i}\setminus\partial\mathcal{S}_{i}$. Hence,

Since by the definition of $G$ we have $\mathbf{v}_{i}^{\top}(t)\phi_{i}(t)\leq 0$ then the above can be written as $c^{\prime}_{i}(t)\mathbf{x}_{i}$ for some $c^{\prime}_{i}(t)\geq 0$. Moreover,

Since by the definition of $G$ we have $\mathbf{v}_{i}(t)\in\operatorname{span}\{\mathbf{y}_{i}\}$, then the above is also in $\operatorname{span}\{\mathbf{y}_{i}\}$.

Moreover, by Lemma 10 we have $\frac{d}{dt}L^{i}_{X,Y}({\boldsymbol{\theta}}(t))\leq 0$.

The above observations imply that as long as $\mathbf{v}_{i}^{\top}(t)\phi_{i}(t)\leq 0$ the parameters $\mathbf{w}_{i}(t)$ and $\mathbf{v}_{i}(t)$ satisfy the conditions in $G$. We now show that if $\mathbf{v}_{i}^{\top}(t)\phi_{i}(t)=0$ then $\frac{d}{dt}\mathbf{w}_{i}(t)=\frac{d}{dt}\mathbf{v}_{i}(t)={\mathbf{0}}$, and hence GF will get stuck at $\mathbf{w}_{i}(t),\mathbf{v}_{i}(t)$. Thus, GF cannot reach $\mathbf{w}_{i},\mathbf{v}_{i}$ with $\mathbf{v}_{i}^{\top}\phi_{i}>0$.

Suppose that $\mathbf{v}_{i}^{\top}(t)\phi_{i}(t)=0$, $\mathbf{v}_{i}(t)\in\operatorname{span}\{\mathbf{y}_{i}\}$, and $L^{i}_{X,Y}({\boldsymbol{\theta}}(t))\leq L^{i}_{X,Y}({\boldsymbol{\theta}}(t^{\prime}))<L^{i}_{X,Y}({\boldsymbol{\theta}}(0))$. Note that $\mathbf{v}_{i}(t)\neq{\mathbf{0}}$, since otherwise we have

in contradiction to our assumption. Now, since $\mathbf{v}_{i}(t)\in\operatorname{span}\{\mathbf{y}_{i}\}$, then $\phi_{i}(t)=(\mathbf{w}_{i}^{\top}(t)\mathbf{x}_{i})\mathbf{v}_{i}(t)-\mathbf{y}_{i}\in\operatorname{span}\{\mathbf{y}_{i}\}$. Thus, both $\mathbf{v}_{i}(t)$ and $\phi_{i}(t)$ are in $\operatorname{span}\{\mathbf{y}_{i}\}$, and we have $\mathbf{v}_{i}(t)\neq{\mathbf{0}}$ and $\mathbf{v}_{i}^{\top}(t)\phi_{i}(t)=0$. Therefore, $\phi_{i}(t)={\mathbf{0}}$. By Eq. (C) it implies that $\frac{d}{dt}\mathbf{w}_{i}(t)=\frac{d}{dt}\mathbf{v}_{i}(t)={\mathbf{0}}$.

Thus, ${\boldsymbol{\theta}}(t)\in G$ for all $t\geq t^{\prime}$. It remains to show that for all $t_{2}\geq t_{1}\geq t^{\prime}$ and all $i\in$ we have $\mathbf{w}_{i}^{\top}(t_{2})\mathbf{x}_{i}\geq\mathbf{w}_{i}^{\top}(t_{1})\mathbf{x}_{i}$. By Eq. (15) and since $\mathbf{v}_{i}^{\top}(t)\phi_{i}(t)\leq 0$ for all $t\geq t^{\prime}$, we can write $\mathbf{w}_{i}(t_{1})=\mathbf{w}^{\prime}_{i}+\gamma_{1}\mathbf{x}_{i}$ and $\mathbf{w}_{i}(t_{2})=\mathbf{w}^{\prime}_{i}+\gamma_{2}\mathbf{x}_{i}$ where $\gamma_{2}\geq\gamma_{1}\geq 0$. Therefore

Suppose that we initialize ${\boldsymbol{\theta}}(0)$ such that $\mathbf{w}_{i}(0)\in\mathcal{S}_{i}\setminus\partial\mathcal{S}_{i}$ and $\mathbf{v}_{i}(0)={\mathbf{0}}$ for all $i\in$. Then, GF converges (i.e., $W(\infty)$ and $V(\infty)$ exist) and $L_{X,Y}(W(\infty),V(\infty))=0$. Moreover $\mathbf{w}_{i}(\infty)\in\mathcal{S}_{i}\setminus\partial\mathcal{S}_{i}$ for all $i\in$

By Lemma 12, there is $t^{\prime}>0$ such that for all $i\in$ and $t\geq t^{\prime}$ we have $\mathbf{w}_{i}(t)=\mathbf{w}_{i}(t^{\prime})+c_{i}(t)\mathbf{x}_{i}$ for $c_{i}(t)\geq 0$. Hence, $\mathbf{w}_{i}(t)\in\mathcal{S}_{i}\setminus\partial\mathcal{S}_{i}$ for all $t\geq t^{\prime}$. We have $\frac{d}{dt}L_{X,Y}({\boldsymbol{\theta}}(t))=\left(\nabla L_{X,Y}({\boldsymbol{\theta}}(t))\right)^{\top}\frac{d}{dt}{\boldsymbol{\theta}}(t)=-{\left\|{\nabla L_{X,Y}({\boldsymbol{\theta}}(t))}\right\|}^{2}$. Hence, for $T\geq t^{\prime}$ we have

Since it holds for every $T\geq t^{\prime}$, then we have

Moreover, since $\mathbf{w}_{i}(t)\in\mathcal{S}_{i}\setminus\partial\mathcal{S}_{i}$ for all $i\in$ and $t\geq t^{\prime}$, then by Eq. (C) we have

By Lemma 12 we have $\left(\mathbf{w}_{i}^{\top}(t)\mathbf{x}_{i}\right)^{2}\geq\left(\mathbf{w}_{i}^{\top}(t^{\prime})\mathbf{x}_{i}\right)^{2}$. Therefore

Letting $K:=\frac{1}{2}\sum_{i=1}^{2}\frac{1}{\left(\mathbf{w}_{i}^{\top}(t^{\prime})\mathbf{x}_{i}\right)^{2}}$ and combining the above with Eq. (16), we get