When Are Bias-Free ReLU Networks Effectively Linear Networks?

## Abstract

Abstract We investigate the expressivity and learning dynamics of bias-free ReLU networks. We firstly show that two-layer bias-free ReLU networks have limited expressivity: the only odd function two-layer bias-free ReLU networks can express is a linear one. We then show that, under symmetry conditions on the data, these networks have the same learning dynamics as linear networks. This allows us to give closed-form time-course solutions to certain two-layer bias-free ReLU networks, which has not been done for nonlinear networks outside the lazy learning regime. While deep bias-free ReLU networks are more expressive than their two-layer counterparts, they still share a number of similarities with deep linear networks. These similarities enable us to leverage insights from linear networks, leading to a novel understanding of bias-free ReLU networks. Overall, our results show that some properties established for bias-free ReLU networks arise due to equivalence to linear networks, and suggest that including bias or considering asymmetric data are avenues to engage with nonlinear behaviors.

## 1 Introduction

Theorists make simplifications to real-world models because simplified models are mathematically more tractable, yet discoveries made in them may hold in general. For instance, linear models have illuminated double descent (Advani et al., ) and benign overfitting (Bartlett et al., ) in practical neural networks.
In this paradigm, understanding the consequences of a simplification is critical, since it informs us which discoveries in simple models extend to complex ones. Here we consider a specific simplification that is common in theoretical work on ReLU networks (Zhang et al., ; Du et al., ; Arora et al., ; Lyu and Li, ; Vardi and Shamir, ): the removal of the bias terms.
We investigate how removing the bias affects the expressivity and the learning dynamics of ReLU networks and identify scenarios where bias-free ReLU networks are like linear networks.

For expressivity, we show that two-layer bias-free (leaky) ReLU networks cannot express odd functions except linear functions. This was proven for input uniformly distributed on a sphere (Basri et al., ), but we prove it for arbitrary input and use a simpler approach. We then consider deep bias-free (leaky) ReLU networks and show a depth separation result.
For learning dynamics, we show that two-layer bias-free (leaky) ReLU networks have the same learning dynamics as linear networks when trained on symmetric datasets with square loss or logistic loss starting from small initialization. Our symmetry condition on the dataset incorporates several previous results as special cases (Sarussi et al., ; Lyu et al., ). Finally, we empirically find that deep bias-free ReLU networks form low-rank weights similar to those in deep linear networks when the target function is linear.

By revealing regimes in which bias-free ReLU networks are like linear networks, we offer a novel perspective on bias-free ReLU networks. This perspective draws from linear networks, which enjoy much richer theoretical understanding (Baldi and Hornik, ; Fukumizu, ; Saxe et al., , ; Arora et al., ) than ReLU networks. In particular, we are able to give exact time-course solutions to certain two-layer ReLU networks in closed form, which has never been done for nonlinear networks outside the lazy learning regime. Our findings suggest that the bias terms in the network and the structures in the data play an essential role in learning nonlinear tasks with ReLU networks.

Our contributions are the following: (i) Section 3 proves the limited expressivity of bias-free (leaky) ReLU networks, and shows a depth separation result between two-layer and deep bias-free ReLU networks; (ii) Section 4.1 gives general conditions for when the two-layer bias-free (leaky) ReLU networks evolve like a linear network throughout training, shows why this equivalence occurs for both square loss and logistic loss, and gives closed-form time-course solutions to ReLU networks in this regime; (iii) Section 4.2 reports the similarities between deep bias-free ReLU networks and deep linear networks, and finds a low-rank structure in the weights.

### 1.1 Related Work

Prior work has reported that two-layer bias-free ReLU networks behave like linear networks in certain settings. We discuss two closest works here and provide additional related work in Appendix A.

Basri et al. Basri et al. () proved, using harmonic analysis, that two-layer bias-free ReLU networks can neither learn nor express odd nonlinear functions when input is uniformly distributed on a sphere. We show a more general result with a simpler proof. Our Theorem 3.1 handles arbitrary input, includes both ReLU and leaky ReLU networks, and the proof only involves rewriting the (leaky) ReLU activation function as the sum of a linear function and an absolute value function.

Lyu et al. Lyu et al. () proved two-layer bias-free leaky ReLU networks trained with logistic loss converge to a linear, max-margin classifier on linearly separable tasks with a data augmentation procedure. The learning dynamics they studied is the same as that of a linear network, although this equivalence was not mentioned in the paper. We relax the assumption on the task from being linearly separable to being odd. And we show that two-layer bias-free ReLU and leaky ReLU networks evolve like linear networks on these datasets with square or logistic loss. We thus offer an additional perspective: convergence to the max-margin solution is not a speciality of leaky ReLU networks, but a property of linear networks, which extends to ReLU networks when they evolve like linear networks. The equivalence between ReLU and linear networks can be undesirable when the target model is nonlinear. Furthermore, we identify a practical challenge: the data augmentation procedure of Lyu et al. () can cause the ReLU network to fail in learning a linearly non-separable task — a task the network might have succeeded on without the data augmentation.

## 2 Preliminaries

Notation. We use bold symbols to denote vectors and matrices. Double-pipe brackets $\|\cdot\|$ denote the L2 norm of a vector or the Frobenius norm of a matrix. Angle brackets $\left\langle\cdot\right\rangle$ denote taking the average over the dataset.

A two-layer bias-free (Leaky) ReLU network with $H$ hidden neurons is defined as

$$ $\displaystyle f({\bm{x}};{\bm{W}})={\bm{W}}_{2}\sigma({\bm{W}}_{1}{\bm{x}})= \sum_{h=1}^{H}w_{2h}\sigma({\bm{w}}_{1h}{\bm{x}}),\quad\text{where }\sigma(z)= \max(z,\alpha z),\alpha\in[0,1].$ (1) $$

Here ${\bm{x}}\in{\mathbb{R}}^{D}$ is the input, ${\bm{W}}_{1}\in{\mathbb{R}}^{H\times D}$ is the first-layer weight, ${\bm{W}}_{2}\in{\mathbb{R}}^{1\times H}$ is the second-layer weight, and ${\bm{W}}$ denotes weights of both layers collectively.
It is a linear network when $\alpha=1$ and can be written as $f({\bm{x}})={\bm{W}}_{2}{\bm{W}}_{1}{\bm{x}}$. We also denote the linear network as $f^{\mathrm{lin}}\left({\bm{x}};{\bm{W}}^{\mathrm{lin}}\right)={\bm{W}}_{2}^{
\mathrm{lin}}{\bm{W}}_{1}^{\mathrm{lin}}{\bm{x}}$ when we need to distinguish it from (leaky) ReLU networks.

A deep bias-free network of depth $L$ is $f({\bm{x}})={\bm{h}}_{L}$ where ${\bm{h}}_{L}$ is recursively defined as ${\bm{h}}_{l}={\bm{W}}_{l}\sigma({\bm{h}}_{l-1}),2\leq l\leq L,$ and ${\bm{h}}_{1}={\bm{W}}_{1}{\bm{x}}$.

We consider the rich regime (Woodworth et al., ) in which the network is initialized with small random weights. The network is trained with full-batch gradient flow on a dataset $\{{\bm{x}}_{\mu},y_{\mu}\}_{\mu=1}^{P}$ consisting of $P$ samples.
We study the square loss $\mathcal{L}=\left\langle(y-f({\bm{x}}))^{2}\right\rangle/2$ and the logistic loss $\mathcal{L}_{\text{LG}}=\left\langle\ln\left(1+e^{yf({\bm{x}})}\right)\right\rangle$. The gradient flow dynamics are given in Appendix C.

## 3 Network Expressivity

We first examine the expressivity of bias-free ReLU networks.
Although standard ReLU networks are universal approximators (Hornik et al., ; Pinkus, ), bias-free ReLU networks are not since they can only express positively homogeneous functions, i.e., $g(a{\bm{x}})=ag({\bm{x}})\,\forall a>0$. Moreover, Section 3.1 shows that two-layer bias-free ReLU networks cannot express any odd function except linear functions. Section 3.2 shows that deep bias-free ReLU networks are more expressive than two-layer ones, but are still limited to positively homogeneous functions.

### 3.1 Two-Layer Bias-Free (Leaky) ReLU Networks

###### Theorem 3.1 .

Two-layer bias-free (leaky) ReLU networks can only express a linear function plus a positively homogeneous even function.

###### Proof 3.2 .

.
An arbitrary two-layer (leaky) ReLU network can be written as

$$ $\displaystyle\sum_{h=1}^{H}w_{2h}\sigma({\bm{w}}_{1h}{\bm{x}})=\sum_{h=1}^{H}w _{2h}\left[\frac{1+\alpha}{2}{\bm{w}}_{1h}{\bm{x}}+\frac{1-\alpha}{2}|{\bm{w}} _{1h}{\bm{x}}|\right],\vspace{-4ex}$ (2) $$

which is a linear function plus a positively homogeneous even function.

###### Corollary 3.3 .

The only odd function that bias-free two-layer (leaky) ReLU networks can express is the linear function.

###### Theorem 3.1 .

###### Proof 3.2 .

###### Corollary 3.3 .

### 3.2 Deep Bias-Free (Leaky) ReLU Networks

Similarly to two-layer bias-free ReLU networks, deep bias-free ReLU networks can express only positively homogeneous functions. However, in contrast to two-layer bias-free ReLU networks, deep bias-free ReLU networks can express some odd nonlinear functions.
For instance, for two-dimensional input ${\bm{x}}=[x_{1},x_{2}]^{\top}$, the function below is odd, nonlinear, and can be implemented by a three-layer bias-free ReLU network,

$$ $\displaystyle g({\bm{x}})=\sigma(\sigma(x_{1})-\sigma(x_{2}))-\sigma(\sigma(-x _{1})-\sigma(-x_{2})),\quad\text{where }\sigma(z)=\max(z,0).$ (3) $$

Thus, we have a depth separation result for bias-free ReLU networks: there exist odd nonlinear functions, such as $g({\bm{x}})$ above, that two-layer bias-free ReLU networks cannot express but deep bias-free ReLU networks can.

## 4 Learning Dynamics

### 4.1 Two-Layer Bias-Free (Leaky) ReLU Networks

Section 3.1 has proved that two-layer bias-free (Leaky) ReLU networks cannot express odd functions except linear functions. We now show that under the \conditionrefass:sym-data on the dataset, two-layer bias-free (Leaky) ReLU networks not only find a linear solution but also have the same learning dynamics as a two-layer linear network.

The dataset satisfies the following two symmetry conditions:

- 1.
The empirical input data distribution is even: $p({\bm{x}})=p(-{\bm{x}})$.
- 2.
The target model is odd: $y({\bm{x}})=-y(-{\bm{x}})$.

Under \conditionrefass:sym-data, the dynamics of two-layer bias-free (leaky) ReLU networks and linear networks initialized with small weights can both be approximated by a linear differential equation in the early phase of learning. Thus weights in the ReLU network form the same rank-one structure as weights in a linear network, as specified in Theorem E.3. At the end of the early phase, the weights are rank-one with small errors. To simplify the analysis, \assumptionrefass:L2-rank1 assumes the weights are exactly rank-one, which is justified by the initialization approaching 0 0 and the width approaching infinity. Simulations in Figure 1 also show that errors are indeed small in the finite case.
{assumption}
The two-layer bias-free network’s weights satisfy ${\bm{W}}_{1}={\bm{W}}_{2}^{\top}{\bm{r}}^{\top}$ where ${\bm{r}}$ is an arbitrary unit vector.
The second-layer weights ${\bm{W}}_{2}$ have equal L2 norms for their positive and negative elements.

Under \conditionrefass:sym-data and \assumptionrefass:L2-rank1, the learning dynamics of two-layer bias-free (leaky) ReLU networks reduces to Equation 34, which is the same as that of linear networks given in Equation 8 modulo scale factors. Thus, apart from the fact that learning is $(\alpha+1)/2$ times slower and the weights are $\sqrt{2/(\alpha+1)}$ times larger, the ReLU network has the same learning dynamics as its linear counterpart. We formally state this equivalence below.

###### Theorem 4.1 .

A two-layer (leaky) ReLU network and a linear network are trained with square or logistic loss starting from weights which differ by a scale factor, ${\bm{W}}(0)=\sqrt{2/(\alpha+1)}\,{\bm{W}}^{\mathrm{lin}}(0)$. Under \conditionrefass:sym-data on the dataset and \assumptionrefass:L2-rank1 on the weights at time $t=0$, we have that $\forall\,t\geq 0$, \assumptionrefass:L2-rank1 retains valid and:

- 1.
The (leaky) ReLU network implements the same linear function as the linear network with scaled time
$\displaystyle f({\bm{x}};{\bm{W}}(t))=f^{\mathrm{lin}}\left({\bm{x}};{\bm{W}}^
{\mathrm{lin}}\left(\frac{\alpha+1}{2}t\right)\right).$
(4)
- 2.
The weights in the (leaky) ReLU network are the same as scaled weights in the linear network
$\displaystyle{\bm{W}}(t)=\sqrt{\frac{2}{\alpha+1}}{\bm{W}}^{\mathrm{lin}}\left
(\frac{\alpha+1}{2}t\right).$
(5)

We validate Theorem 4.1 and the plausibility of \assumptionrefass:L2-rank1 with numerical simulations in Figure 1.

Figure: Figure 1: Two-layer bias-free (leaky) ReLU networks that evolve like a linear network. (a) Loss curves with different leaky ReLU parameter $\alpha$ (note $\alpha=1$ is a linear network). The simulations match the theoretical solutions in Equation 38. The loss converges to global minimum, which is not zero due to the restricted expressivity of two-layer bias-free ReLU networks. (b) The simulated loss curves are plotted against a rescaled time axis; they collapse to one curve, demonstrating the networks are implementing the same linear function as in Equation 4. The error, defined as $\left\|\sqrt{\frac{\alpha+1}{2}}{\bm{W}}\left(\frac{2}{\alpha+1}t\right)-{\bm{ W}}^{\mathrm{lin}}(t)\right\|/\left\|{\bm{W}}^{\mathrm{lin}}(t)\right\|$, is less than $1\%$, demonstrating that the weights in the (leaky) ReLU network are close to the weights in the linear network as in Equation 5. The errors are not exactly zero because the initialization is small but nonzero in the simulations. Hyperparameters in Appendix G.
Refer to caption: x1.png

If the input covariance is white, we can further write down the exact time-course solution in closed form for two-layer bias-free (leaky) ReLU networks by adopting the solutions of linear networks (Braun et al., , Theorem 3.1), as specified in \corollaryrefcor:exact-sol.

Since the time evolution of two-layer bias-free (leaky) ReLU networks is the same as that of linear networks (modulo scale factors), their converged weights will also be the same. For learning with square loss, linear networks converge to the ordinary least squares solution (Saxe et al., ). For linearly separable binary classification with logistic loss, linear networks converge to the max-margin solution (Soudry et al., ). Thus two-layer bias-free (leaky) ReLU networks also converge to these solutions when they behave like linear networks; see Section E.4.

###### Corollary 4.2 .

Under the same conditions as Theorem 4.1, the two-layer bias-free (leaky) ReLU network converges to a linear solution $f({\bm{x}};{\bm{W}}(\infty))={{\bm{w}}^{*}}^{\top}{\bm{x}}$. For square loss, ${\bm{w}}^{*}$ is the ordinary least squares solution, ${\bm{\Sigma}}^{-1}{\bm{\beta}}$, which is the global minimum. For linearly separable binary classification with logistic loss, ${\bm{w}}^{*}$ is the max-margin (hard margin SVM) solution.

###### Theorem 4.1 .

###### Corollary 4.2 .

### 4.2 Deep Bias-Free ReLU Networks

The equivalence between two-layer ReLU and linear networks stated in Theorem 4.1 does not extend to deep ReLU networks. Nonetheless, we find deep bias-free ReLU networks can form low-rank weights similar to those in deep linear networks when the empirical input distribution is even, the target function is linear, and the initialization is small.
For the first and last layers, the linear and ReLU networks form rank-one weights of the same structure. For intermediate layers, weights of the linear network are rank-one, while weights of the ReLU network are rank-two and all weights are approximately non-negative as shown in Figure 3. Deep ReLU networks that have formed such low-rank weights will retain the low-rank structure and implement a linear map; see Appendix F.

## Acknowledgement

The authors are grateful to Peter Orbanz, Spencer Frei, Ingo Steinwart, Rodrigo Carrasco-Davis, Lukas Braun, Clémentine Dominé, and William Dorrell for helpful discussions.
The authors thank the following funding sources: Gatsby Charitable Foundation to YZ, AS, and PEL; Sainsbury Wellcome Centre Core Grant from Wellcome (219627/Z/19/Z) to AS; a Sir Henry Dale Fellowship from the Wellcome Trust and Royal Society (216386/Z/19/Z) to AS; Wellcome Trust (110114/Z/15/Z) to PEL.

## Appendix A Additional Related Work

Connections Between ReLU & Linear Networks.
Section 1.1 has discussed Basri et al. (); Lyu et al. () in detail.
In addition, Sarussi et al. () discovered that two-layer bias-free leaky ReLU networks converge to a decision boundary that is very close to linear when the teacher model is linear. Their theoretical results assume that the second layer is fixed while we train all layers of the network. We also consider more general datasets that are not restricted to the linear teacher model.
Saxe et al. () studied gated deep linear networks and found they closely approximate a two-layer bias-free ReLU network trained on an XOR task. But they did not generalize the connection between gated linear networks and ReLU networks beyond the XOR case.
Boursier and Flammarion () gave an example dataset with three scalar input data points, in which two-layer bias-free (leaky) ReLU networks converge to the linear, ordinary least square estimator. Holzmüller and Steinwart () studied two-layer leaky ReLU networks with bias and found that they perform linear regression on certain data distributions because the bias fails to move far away from their initialization at zero. However, Boursier and Flammarion (); Holzmüller and Steinwart () have only dealt with one-dimensional inputs.

Implicit / Simplicity Bias.
Many works have studied the implicit bias or simplicity bias of two-layer bias-free ReLU networks under various assumptions on the dataset. Brutzkus et al. (); Wang et al. (); Lyu et al. (); Sarussi et al. (); Wang and Ma () considered linearly separable binary classification tasks.
Phuong and Lampert (); Wang and Pilanci (); Min et al. () studied orthogonally separable classification (i.e., where for every pair of labeled examples $({\bm{x}}_{i},y_{i}),({\bm{x}}_{j},y_{j})$ we have ${\bm{x}}_{i}^{\top}{\bm{x}}_{j}>0$ if $y_{i}=y_{j}$ and ${\bm{x}}_{i}^{\top}{\bm{x}}_{j}\leq 0$ if otherwise).
Boursier et al. (); Frei et al. (, ); Kou et al. () studied binary classification with exactly or nearly orthogonal input (i.e., where ${\bm{x}}_{i}^{\top}{\bm{x}}_{j}=0$ if $i\neq j$). Orthogonal input is a sufficient condition for linear separability for binary classification tasks. Frei et al. (); Meng et al. (); Xu et al. () studied XOR-like datasets. Vardi et al. (); Frei et al. () studied datasets with adversarial noise.
We add to this line of research by studying a case with extreme simplicity bias, i.e., behaving like linear networks.

Low-Rank Weights.
Maennel et al. () is the seminal work on the low-rank weights in two-layer ReLU networks trained from small initialization. They described the phenomenon as “quantizing", where the first layer weight vectors align with a small number of directions in the early phase of training. Luo et al. () identified when two-layer bias-free ReLU networks form low-rank weights in terms of the initialization and the network width. Timor et al. () provided cases where gradient flow on two-layer and deep ReLU networks provably minimize or not minimize the ranks of weight matrices. Frei et al. (); Kou et al. () computed the numerical rank of the converged weights of two-layer bias-free ReLU networks for nearly orthogonal datasets, and found that weights in leaky ReLU networks have rank at most two and weights in ReLU networks have a numerical rank upper bounded by a constant. Chistikov et al. () showed two-layer bias-free ReLU networks are implicitly biased to learn
the network of minimal rank under the assumption that training points are correlated with the teacher neuron. Min et al. (); Boursier and Flammarion () studied the early phase learning dynamics to understand how the low-rank weights form. Petrini et al. (, ) conducted experiments on practical datasets to show that two-layer bias-free ReLU networks learn sparse features, which can be detrimental and lead to overfitting. Le and Jegelka () generalize the low-rank phenomenon in linear and ReLU networks to arbitrary non-homogeneous networks whose last few layers contain linear fully-connected and linear ResNet blocks.

## Appendix B Discussion

Figure: Figure 2: Two-layer bias-free ReLU network trained on a dataset that approximately satisfies the symmetry \conditionrefass:sym-data. The right middle data point is slight asymmetric. (a) Loss curve. (b,c) The network output is plotted in color during and at the end of training. The circles are data points with $+1$ labels and the lines are data points with $-1$ labels.
Refer to caption: x3.png

Perturbed Symmetric Dataset.
We have shown an exact equivalence between two-layer bias-free (leaky) ReLU networks and linear networks in Theorem 4.1 under symmetry \conditionrefass:sym-data on the dataset.
In practice, no datasets satisfy \conditionrefass:sym-data precisely. However, two-layer bias-free ReLU networks may still struggle to fit a dataset that approximately satisfies \conditionrefass:sym-data. We present a simple dataset with six data points, as shown in Figure 2. Because this dataset does not satisfy \conditionrefass:sym-data precisely, the two-layer bias-free ReLU can find a nonlinear solution and the loss converges to zero as shown in Figure 2. However, the loss undergoes a long plateau when the network is stuck in an approximately linear solution as shown in Figure 2. Moreover, as shown in Figure 2, the decision boundaries at convergence are close to the data points, and thus possibly non-robust.

Implication of Bias Removal.
We have studied the implications of removing bias in ReLU networks in terms of the expressivity and learning dynamics.
One common argument in studies of bias-free ReLU networks is that we can stack the input ${\bm{x}}$ with an additional one, i.e., $[{\bm{x}},1]$.
Then results derived for bias-free networks could extend to networks with bias and the removal of bias might thus have a minor implication. This argument is valid for some studies (Allen-Zhu et al., ; Zou et al., ), but not all. For example, Soudry et al. () found that two-layer bias-free ReLU networks trained with logistic loss converge to the max-margin classifier on linearly separable datasets. As clarified by (Soudry et al., ), this technical result still holds if the inputs are stacked with an additional one. However, the max-margin solution for the dataset with stacked inputs is not the max-margin solution for the original dataset. Thus, the convergence to max-margin solution result does not directly extend to ReLU networks with bias.

## Appendix C Gradient Flow Differential Equations

### C.1 Two-Layer Networks

#### C.1.1 Two-Layer (Leaky) ReLU Networks

The gradient flow dynamics of a two-layer (leaky) ReLU network trained with square loss are given by

$$ $\displaystyle\tau\dot{\bm{W}}_{1}$ $\displaystyle=\left\langle\sigma^{\prime}({\bm{W}}_{1}{\bm{x}})\odot{\bm{W}}_{ 2}^{\top}\left(y-{\bm{W}}_{2}\sigma({\bm{W}}_{1}{\bm{x}})\right){\bm{x}}^{\top }\right\rangle,$ (6a) $\displaystyle\tau\dot{\bm{W}}_{2}$ $\displaystyle=\left\langle\left(y-{\bm{W}}_{2}\sigma({\bm{W}}_{1}{\bm{x}}) \right)\sigma({\bm{W}}_{1}{\bm{x}})^{\top}\right\rangle.$ (6b) $$

where $\odot$ is the Hadamard product, $\sigma^{\prime}$ is the derivative of $\sigma$, $\tau$ is the time constant.

The gradient flow dynamics of a two-layer (leaky) ReLU network trained with logistic loss are

$$ $\displaystyle\tau\dot{\bm{W}}_{1}$ $\displaystyle=\left\langle\frac{\sigma^{\prime}({\bm{W}}_{1}{\bm{x}})\odot{\bm {W}}_{2}^{\top}{\bm{W}}_{2}\sigma({\bm{W}}_{1}{\bm{x}}){\bm{x}}^{\top}}{e^{y{ \bm{W}}_{2}\sigma({\bm{W}}_{1}{\bm{x}})}+1}\right\rangle,$ (7a) $\displaystyle\tau\dot{\bm{W}}_{2}$ $\displaystyle={\bm{W}}_{2}\left\langle\frac{\sigma({\bm{W}}_{1}{\bm{x}})\sigma ({\bm{W}}_{1}{\bm{x}})^{\top}}{e^{y{\bm{W}}_{2}\sigma({\bm{W}}_{1}{\bm{x}})}+1 }\right\rangle.$ (7b) $$

#### C.1.2 Two-Layer Linear Networks

For linear networks, $\sigma(z)=z$, the gradient flow dynamics with square loss can be written

$$ $\displaystyle\tau\dot{\bm{W}}_{1}^{\mathrm{lin}}$ $\displaystyle={{\bm{W}}_{2}^{\mathrm{lin}}}^{\top}\left({\bm{\beta}}^{\top}-{ \bm{W}}_{2}^{\mathrm{lin}}{\bm{W}}_{1}^{\mathrm{lin}}{\bm{\Sigma}}\right),$ (8a) $\displaystyle\tau\dot{\bm{W}}_{2}^{\mathrm{lin}}$ $\displaystyle=\left({\bm{\beta}}^{\top}-{\bm{W}}_{2}^{\mathrm{lin}}{\bm{W}}_{1 }^{\mathrm{lin}}{\bm{\Sigma}}\right){{\bm{W}}_{1}^{\mathrm{lin}}}^{\top},$ (8b) $$

where ${\bm{\Sigma}}$ denotes the input data covariance and ${\bm{\beta}}$ denotes the input-output correlation

$$ $\displaystyle{\bm{\Sigma}}=\bigl{\langle}{\bm{x}}{\bm{x}}^{\top}\bigr{\rangle} ,\quad{\bm{\beta}}=\left\langle y{\bm{x}}\right\rangle,$ (9) $$

The gradient flow dynamics with logistic loss are

$$ $\displaystyle\tau\dot{\bm{W}}_{1}^{\mathrm{lin}}$ $\displaystyle={{\bm{W}}_{2}^{\mathrm{lin}}}^{\top}{\bm{W}}_{2}^{\mathrm{lin}}{ \bm{W}}_{1}^{\mathrm{lin}}\left\langle\frac{{\bm{x}}{\bm{x}}^{\top}}{e^{y{\bm{ W}}_{2}^{\mathrm{lin}}{\bm{W}}_{1}^{\mathrm{lin}}{\bm{x}}}+1}\right\rangle,$ (10a) $\displaystyle\tau\dot{\bm{W}}_{2}^{\mathrm{lin}}$ $\displaystyle={\bm{W}}_{2}^{\mathrm{lin}}{\bm{W}}_{1}^{\mathrm{lin}}\left \langle\frac{{\bm{x}}{\bm{x}}^{\top}}{e^{y{\bm{W}}_{2}^{\mathrm{lin}}{\bm{W}}_ {1}^{\mathrm{lin}}{\bm{x}}}+1}\right\rangle{{\bm{W}}_{1}^{\mathrm{lin}}}^{\top}.$ (10b) $$

### C.2 Deep Networks

The gradient flow dynamics of a deep neural network with square loss is

$$ $\displaystyle\tau\dot{\bm{W}}_{l}=\left\langle\frac{\partial{\bm{h}}_{L}}{ \partial{\bm{h}}_{l}}(y-{\bm{h}}_{L})\frac{\partial{\bm{h}}_{l}}{\partial{\bm{ W}}_{l}}\right\rangle.$ (11) $$

For deep linear networks, the gradient flow dynamics can be written as

$$ $\displaystyle\tau\dot{\bm{W}}_{l}^{\mathrm{lin}}=\left(\prod_{i=l+1}^{L}{\bm{W }}_{i}^{\mathrm{lin}}\right)^{\top}\left({\bm{\beta}}^{\top}-\prod_{i=1}^{L}{ \bm{W}}_{i}^{\mathrm{lin}}{\bm{\Sigma}}\right)\left(\prod_{i=1}^{l-1}{\bm{W}}_ {i}^{\mathrm{lin}}\right)^{\top},$ (12) $$

where $\prod_{i}{\bm{W}}_{i}$ represents the ordered product of matrices with the largest index on the left and smallest on the right.

## Appendix D Useful Lemmas

Grönwall’s Inequality (Gronwall, ) is a common tool to obtain error bounds when considering approximate differential equations.

###### Lemma D.1 (Grönwall’s Inequality) .

Let $I$ denote an interval of the real line of the form $[a,\infty)$ or $[a,b]$ or $[a,b)$ with $a<b$. Let $\alpha,\beta$ and $u$ be real-valued functions defined on $I$. Assume that $\beta$ and $u$ are continuous and that the negative part of $\alpha$ is integrable on every closed and bounded subinterval of $I$.
If $\beta$ is non-negative and $u$ satisfies the integral inequality

$$ $\displaystyle u(t)\leq\alpha(t)+\int_{a}^{t}\beta(s)u(s)ds,\quad\forall t\in I,$ $$

then

$$ $\displaystyle u(t)\leq\alpha(t)+\int_{a}^{t}\alpha(s)\beta(s)e^{\int_{s}^{t} \beta(r)dr}ds,\quad t\in I.$ (13) $$

Terms in the gradient flow Equation 6 can be bounded by the norm of the weights and the trace of the input covariance matrix.

###### Lemma D.2 .

$\left\|\left\langle\sigma({\bm{W}}_{1}{\bm{x}})\sigma({\bm{W}}_{1}{\bm{x}})^{
\top}\right\rangle\right\|\leq\|{\bm{W}}_{1}\|^{2}\operatorname{Tr}{\bm{\Sigma}}$.

###### Proof D.3 .

$$ $\displaystyle\left\|\left\langle\sigma({\bm{W}}_{1}{\bm{x}})\sigma({\bm{W}}_{1 }{\bm{x}})^{\top}\right\rangle\right\|$ $\displaystyle\leq\left\langle\|\sigma({\bm{W}}_{1}{\bm{x}})\|^{2}\right\rangle$ $\displaystyle\leq\left\langle\|{\bm{W}}_{1}{\bm{x}}\|^{2}\right\rangle$ $\displaystyle\leq\left\langle\|{\bm{W}}_{1}\|^{2}\|{\bm{x}}\|^{2}\right\rangle$ $\displaystyle=\|{\bm{W}}_{1}\|^{2}\operatorname{Tr}{\bm{\Sigma}}$ $$

###### Lemma D.4 .

$\left\|\left\langle\sigma({\bm{W}}_{1}{\bm{x}})\sigma^{\prime}({\bm{W}}_{1}{
\bm{x}})\right\rangle\right\|\leq\|{\bm{W}}_{1}\|\operatorname{Tr}{\bm{\Sigma}}$.

###### Proof D.5 .

$$ $\displaystyle\left\|\left\langle\sigma({\bm{W}}_{1}{\bm{x}})\sigma^{\prime}({ \bm{W}}_{1}{\bm{x}})\right\rangle\right\|$ $\displaystyle\leq\left\langle\|\sigma({\bm{W}}_{1}{\bm{x}})\|\|\sigma^{\prime} ({\bm{W}}_{1}{\bm{x}})\|\right\rangle$ $\displaystyle\leq\left\langle\|{\bm{W}}_{1}{\bm{x}}\|\|{\bm{x}}\|\right\rangle$ $\displaystyle\leq\left\langle\|{\bm{W}}_{1}\|\|{\bm{x}}\|^{2}\right\rangle$ $\displaystyle=\|{\bm{W}}_{1}\|\operatorname{Tr}{\bm{\Sigma}}$ $$

The key implication of \conditionrefass:sym-data we exploit is that the input covariance matrix and the input-output correlation averaged over any half space is equal to those averaged over the entire space.

###### Lemma D.6 .

Let set ${\mathbb{S}}^{+}$ be an arbitrary half space divided by a hyperplane with normal vector ${\bm{r}}$, namely ${\mathbb{S}}^{+}=\{{\bm{x}}\in{\mathbb{R}}^{D}|{\bm{r}}^{\top}{\bm{x}}>0\}$. Under the first condition in \conditionrefass:sym-data, we have $\forall{\bm{r}}$

$$ $\displaystyle\left\langle{\bm{x}}{\bm{x}}^{\top}\right\rangle_{{\mathbb{S}}^{+ }}={\bm{\Sigma}}.$ (14) $$

Under \conditionrefass:sym-data, we have $\forall{\bm{r}}$

$$ $\displaystyle\left\langle{\bm{x}}y({\bm{x}})\right\rangle_{{\mathbb{S}}^{+}}={ \bm{\beta}}$ (15) $$

Recall that ${\bm{\Sigma}}$ and ${\bm{\beta}}$ are averages over the entire space as defined in Equation 9.

###### Proof D.7 .

.
Define ${\mathbb{S}}^{-}=\{{\bm{x}}\in{\mathbb{R}}^{D}|{\bm{r}}^{\top}{\bm{x}}<0\}$. Because \conditionrefass:sym-data states that $p({\bm{x}})$ is even, we have $\int_{{\mathbb{S}}^{+}}p({\bm{x}})d{\bm{x}}=\int_{{\mathbb{S}}^{-}}p({\bm{x}})
d{\bm{x}}=\nicefrac{{1}}{{2}}$.
Because ${\bm{x}}{\bm{x}}^{\top}$ is an even function about ${\bm{x}}$, its average in ${\mathbb{S}}^{+}$ is equal to its average in the other half space ${\mathbb{S}}^{-}$,

$$ $\displaystyle\left\langle{\bm{x}}{\bm{x}}^{\top}\right\rangle_{{\mathbb{S}}^{+ }}\equiv\frac{1}{2}\int_{{\mathbb{S}}^{+}}{\bm{x}}{\bm{x}}^{\top}p({\bm{x}})d{ \bm{x}}=\frac{1}{2}\int_{{\mathbb{S}}^{-}}{\bm{x}}{\bm{x}}^{\top}p({\bm{x}})d{ \bm{x}}.$ $$

Thus the average in ${\mathbb{S}}^{+}$ is equal to the average in the entire space,

$$ $\displaystyle{\bm{\Sigma}}$ $\displaystyle\equiv\int{\bm{x}}{\bm{x}}^{\top}p({\bm{x}})d{\bm{x}}$ $\displaystyle=\frac{1}{2}\int_{{\mathbb{S}}^{+}}{\bm{x}}{\bm{x}}^{\top}p({\bm{ x}})d{\bm{x}}+\frac{1}{2}\int_{{\mathbb{S}}^{-}}{\bm{x}}{\bm{x}}^{\top}p({\bm{ x}})d{\bm{x}}$ $\displaystyle=\int_{{\mathbb{S}}^{+}}{\bm{x}}{\bm{x}}^{\top}p({\bm{x}})d{\bm{x }}.$ $$

The same holds for ${\bm{x}}y({\bm{x}})$.

###### Lemma D.8 .

Under \conditionrefass:sym-data, the first terms in the differential Equation 6 can be simplified to

$$ $\displaystyle\left\langle\sigma^{\prime}({\bm{W}}_{1}{\bm{x}})\odot{\bm{W}}_{2 }^{\top}y{\bm{x}}^{\top}\right\rangle$ $\displaystyle=\frac{\alpha+1}{2}{\bm{W}}_{2}^{\top}{\bm{\beta}}^{\top},$ (16a) $\displaystyle\left\langle y\sigma({\bm{W}}_{1}{\bm{x}})^{\top}\right\rangle$ $\displaystyle=\frac{\alpha+1}{2}{\bm{\beta}}^{\top}{\bm{W}}_{1}^{\top}.$ (16b) $$

###### Proof D.9 .

.
Let us consider the $h$-th row of the matrix $\left\langle\sigma^{\prime}({\bm{W}}_{1}{\bm{x}})\odot{\bm{W}}_{2}^{\top}y{\bm
{x}}^{\top}\right\rangle$, which is

$$ $\displaystyle\left\langle\sigma^{\prime}({\bm{w}}_{1h}{\bm{x}})w_{2h}y{\bm{x}} ^{\top}\right\rangle=\frac{1}{2}\left\langle\alpha w_{2h}y{\bm{x}}^{\top} \right\rangle_{{\bm{w}}_{1h}{\bm{x}}<0}+\frac{1}{2}\left\langle w_{2h}y{\bm{x} }^{\top}\right\rangle_{{\bm{w}}_{1h}{\bm{x}}>0}=\frac{\alpha+1}{2}w_{2h}{\bm{ \beta}}^{\top},$ $$

where the second equality uses Equation 15. Since this holds for all rows, we arrive at Equation 16a.

Let us consider the $h$-th element of the row vector $\left\langle y\sigma({\bm{W}}_{1}{\bm{x}})^{\top}\right\rangle$, which is

$$ $\displaystyle\left\langle y\sigma({\bm{w}}_{1h}{\bm{x}})\right\rangle=\frac{1} {2}\left\langle\alpha y{\bm{w}}_{1h}{\bm{x}}\right\rangle_{{\bm{w}}_{1h}{\bm{x }}<0}+\frac{1}{2}\left\langle y{\bm{w}}_{1h}{\bm{x}}\right\rangle_{{\bm{w}}_{1 h}{\bm{x}}>0}=\frac{\alpha+1}{2}{\bm{w}}_{1h}{\bm{\beta}},$ $$

where the second equality uses Equation 15. Since this holds for all elements, we arrive at Equation 16b.

###### Lemma D.1 (Grönwall’s Inequality) .

###### Lemma D.2 .

###### Proof D.3 .

###### Lemma D.4 .

###### Proof D.5 .

###### Lemma D.6 .

###### Proof D.7 .

###### Lemma D.8 .

###### Proof D.9 .

## Appendix E Two-Layer Network Learning Dynamics on Symmetric Datasets

### E.1 Early Phase

In the early phase of learning, the network output is small compared with the target output since the initialization is small. We specify how small the norm of the weights is in \lemmareflemma:normbound.

###### Lemma E.1 .

Denote the larger L2 norm of the weights in a two-layer network as $u(t)=\max\{\|{\bm{W}}_{1}(t)\|,\|{\bm{W}}_{2}(t)\|\}$. For two-layer linear, ReLU, or leaky ReLU networks trained with square loss from small initialization (that is $u(0)\ll 1$), $u(t)$ is bounded by

$$ $\displaystyle u(t)\leq u(0)e^{(s+\operatorname{Tr}{\bm{\Sigma}})t/\tau},$ (17) $$

for time $t<\frac{\tau}{s+\operatorname{Tr}{\bm{\Sigma}}}\ln\frac{1}{u(0)}$.

###### Proof E.2 .

.
For two-layer linear, ReLU, or leaky ReLU networks, the learning dynamics are given in general in Equation 6. Using the inequality in \lemmareflemma:sigsig-bound, we can bound the dynamics of $u$ as

$$ $\displaystyle\tau\frac{d}{dt}u^{2}=\tau\frac{d}{dt}\|{\bm{W}}_{2}\|^{2}$ $\displaystyle=(\alpha+1){\bm{\beta}}^{\top}{\bm{W}}_{1}^{\top}{\bm{W}}_{2}^{ \top}-2{\bm{W}}_{2}\left\langle\sigma({\bm{W}}_{1}{\bm{x}})\sigma({\bm{W}}_{1} {\bm{x}})^{\top}\right\rangle{\bm{W}}_{2}^{\top}$ $\displaystyle\leq\left|(\alpha+1){\bm{\beta}}^{\top}{\bm{W}}_{1}^{\top}{\bm{W} }_{2}^{\top}\right|+\left|2{\bm{W}}_{2}\left\langle\sigma({\bm{W}}_{1}{\bm{x}} )\sigma({\bm{W}}_{1}{\bm{x}})^{\top}\right\rangle{\bm{W}}_{2}^{\top}\right|$ $\displaystyle\leq 2\|{\bm{\beta}}\|\|{\bm{W}}_{1}\|\|{\bm{W}}_{2}\|+2\|{\bm{W} }_{2}\|^{2}\|{\bm{W}}_{1}\|^{2}\operatorname{Tr}{\bm{\Sigma}}$ $\displaystyle\leq 2su^{2}+2u^{4}\operatorname{Tr}{\bm{\Sigma}}.$ $$

For $u<1$, we have

$$ $\displaystyle\tau\frac{d}{dt}u^{2}\leq 2su^{2}+2u^{4}\operatorname{Tr}{\bm{ \Sigma}}<2\left(s+\operatorname{Tr}{\bm{\Sigma}}\right)u^{2}.$ $$

Via \lemmareflemma:gronwall Grönwall’s Inequality, we obtain

$$ $\displaystyle u^{2}\leq u(0)^{2}e^{2(s+\operatorname{Tr}{\bm{\Sigma}})t/\tau} \quad\Rightarrow\quad u(t)\leq u(0)e^{(s+\operatorname{Tr}{\bm{\Sigma}})t/\tau}.$ $$

This holds for

$$ $\displaystyle t<\frac{\tau}{s+\operatorname{Tr}{\bm{\Sigma}}}\ln\frac{1}{u(0)}.$ $$

Since the weights are small in the early phase, we can approximate the early phase dynamics with only the first terms in Equation 6, that is

$$ $\displaystyle\tau\dot{\bm{W}}_{1}$ $\displaystyle\approx\left\langle\sigma^{\prime}({\bm{W}}_{1}{\bm{x}})\odot{\bm {W}}_{2}^{\top}y{\bm{x}}^{\top}\right\rangle=\frac{\alpha+1}{2}{\bm{W}}_{2}^{ \top}{\bm{\beta}}^{\top},$ (18) $\displaystyle\tau\dot{\bm{W}}_{2}$ $\displaystyle\approx\left\langle y\sigma({\bm{W}}_{1}{\bm{x}})^{\top}\right \rangle=\frac{\alpha+1}{2}{\bm{\beta}}^{\top}{\bm{W}}_{1}^{\top},$ (19) $$

where the equalities hold under \conditionrefass:sym-data as proved by \lemmareflemma:ealy-dynamics-reduce.
We solve the approximate early phase dynamics and prove that the approximation introduces small errors in Theorem E.3.

###### Theorem E.3 .

Assume the initial norm of both layers are equally small, that is $\|{\bm{W}}_{1}(0)\|=\|{\bm{W}}_{2}(0)\|=w_{\mathrm{init}}$ is small.
For time $t<\frac{\tau}{s+\operatorname{Tr}{\bm{\Sigma}}}\ln\frac{1}{w_{\mathrm{init}}}$, the solution to Equation 6 is exponential growth along one direction with small errors

$$ $\displaystyle{\bm{W}}_{1}(t)=e^{\frac{\alpha+1}{2\tau}st}{\bm{r}}_{1}{\bar{\bm {\beta}}}^{\top}+O(w_{\mathrm{init}}),\quad{\bm{W}}_{2}(t)=e^{\frac{\alpha+1}{ 2\tau}st}{\bm{r}}_{1}^{\top}+O(w_{\mathrm{init}}).$ (20) $$

where $s=\|{\bm{\beta}}\|,\bar{\bm{\beta}}={\bm{\beta}}/s$, and ${\bm{r}}_{1}$ is determined by random initialization ${\bm{r}}_{1}=\left({\bm{W}}_{1}(0)\bar{\bm{\beta}}+{{\bm{W}}_{2}}^{\top}(0)
\right)/2$.

###### Proof E.4 .

.
We first consider the approximate learning dynamics:

$$ $\displaystyle\tau\dot{\widetilde{\bm{W}}_{1}}=\frac{\alpha+1}{2}{\widetilde{ \bm{W}}_{2}}^{\top}{\bm{\beta}}^{\top},\quad\tau\dot{\widetilde{\bm{W}}_{2}}= \frac{\alpha+1}{2}{\bm{\beta}}^{\top}{\widetilde{\bm{W}}_{1}}^{\top}.$ (21) $$

This is a linear dynamical system with an analytical solution available. We re-write it as:

$$ $\displaystyle\tau\frac{d}{dt}\widetilde{\bm{W}}=\frac{\alpha+1}{2}{\bm{M}} \widetilde{\bm{W}},\quad\text{where }{\bm{M}}=\begin{bmatrix}{\bm{0}}&{\bm{ \beta}}\\ {\bm{\beta}}^{\top}&0\end{bmatrix},\widetilde{\bm{W}}=\begin{bmatrix} \widetilde{\bm{W}}_{1}^{\top}\\ \widetilde{\bm{W}}_{2}\end{bmatrix}.$ (22) $$

Since matrix ${\bm{M}}$ only has two nonzero eigenvalues $\pm s$, the solution to Equation 22 is

$$ $\displaystyle\begin{split}\widetilde{\bm{W}}(t)&=\frac{1}{2}e^{\frac{\alpha+1} {2\tau}st}\begin{bmatrix}{\bar{\bm{\beta}}}\\ 1\end{bmatrix}\left(\bar{\bm{\beta}}^{\top}{\bm{W}}_{1}^{\top}(0)+{\bm{W}}_{2} (0)\right)\\ &+\frac{1}{2}e^{-\frac{\alpha+1}{2\tau}st}\begin{bmatrix}{\bar{\bm{\beta}}}\\ -1\end{bmatrix}\left(\bar{\bm{\beta}}^{\top}{\bm{W}}_{1}^{\top}(0)-{\bm{W}}_{2 }(0)\right)+\begin{bmatrix}\left({\bm{I}}-\bar{\bm{\beta}}\bar{\bm{\beta}}^{ \top}\right){\bm{W}}_{1}^{\top}(0)\\ 0\end{bmatrix}.\end{split}$ (23) $$

Note that only the first term in Equation 23 is growing.

We then consider the exact learning dynamics given by Equation 6 and prove its solution is close to $\widetilde{\bm{W}}$.
The dynamics of the difference between the exact and approximate dynamics are

$$ $\displaystyle\tau\frac{d}{dt}\left(\widetilde{\bm{W}}_{1}-{\bm{W}}_{1}\right)$ $\displaystyle=\frac{\alpha+1}{2}\left({\widetilde{\bm{W}}_{2}}-{\bm{W}}_{2} \right)^{\top}{\bm{\beta}}^{\top}+{{\bm{W}}_{2}}^{\top}{\bm{W}}_{2}\left \langle\sigma({\bm{W}}_{1}{\bm{x}})\sigma^{\prime}({\bm{W}}_{1}{\bm{x}})\right\rangle$ (24a) $\displaystyle\tau\frac{d}{dt}\left(\widetilde{\bm{W}}_{2}-{\bm{W}}_{2}\right)$ $\displaystyle=\frac{\alpha+1}{2}{\bm{\beta}}^{\top}\left({\widetilde{\bm{W}}_{ 1}}-{\bm{W}}_{1}\right)^{\top}+{\bm{W}}_{2}\left\langle\sigma({\bm{W}}_{1}{\bm {x}})\sigma({\bm{W}}_{1}{\bm{x}})^{\top}\right\rangle.$ (24b) $$

We re-write Equation 24 as

$$ $\displaystyle\tau\frac{d}{dt}\delta{\bm{W}}=\frac{\alpha+1}{2}{\bm{M}}\delta{ \bm{W}}+\bm{\epsilon},$ (25) $$

We can bound the norm of the two terms of $\bm{\epsilon}$ via \lemmareflemma:sigsig-bound,lemma:sigsig’-bound

$$ $\displaystyle\left\|{{\bm{W}}_{2}}^{\top}{\bm{W}}_{2}\left\langle\sigma({\bm{W }}_{1}{\bm{x}})\sigma^{\prime}({\bm{W}}_{1}{\bm{x}})\right\rangle\right\|$ $\displaystyle\leq u^{3}\operatorname{Tr}{\bm{\Sigma}},$ $\displaystyle\|{\bm{W}}_{2}\left\langle\sigma({\bm{W}}_{1}{\bm{x}})\sigma({\bm {W}}_{1}{\bm{x}})^{\top}\right\rangle\|$ $\displaystyle\leq u^{3}\operatorname{Tr}{\bm{\Sigma}}.$ $$

We can then substitute in Equation 17 and obtain

$$ $\displaystyle\|\bm{\epsilon}\|\leq\sqrt{2}u^{3}\operatorname{Tr}{\bm{\Sigma}}< \sqrt{2}u_{0}^{3}e^{3(s+\operatorname{Tr}{\bm{\Sigma}})t/\tau}\operatorname{Tr }{\bm{\Sigma}}.$ $$

We now bound the norm of ${\bm{W}}-\widetilde{\bm{W}}$:

$$ $\displaystyle\left\|{\bm{W}}-\widetilde{\bm{W}}\right\|$ $\displaystyle=\left\|\int_{0}^{t}\frac{\alpha+1}{2}{\bm{M}}\left({\bm{W}}- \widetilde{\bm{W}}\right)+\bm{\epsilon}dt\right\|$ $\displaystyle\leq\int_{0}^{t}\|{\bm{M}}\|\left\|{\bm{W}}-\widetilde{\bm{W}} \right\|+\|\bm{\epsilon}\|dt$ $\displaystyle\leq\int_{0}^{t}\left(\sqrt{2}s\left\|{\bm{W}}-\widetilde{\bm{W}} \right\|+\sqrt{2}u_{0}^{3}e^{3(s+\operatorname{Tr}{\bm{\Sigma}})t/\tau} \operatorname{Tr}{\bm{\Sigma}}\right)dt$ $\displaystyle\leq\frac{\sqrt{2}u_{0}^{3}\operatorname{Tr}{\bm{\Sigma}}}{3(s+ \operatorname{Tr}{\bm{\Sigma}})}\left(e^{3(s+\operatorname{Tr}{\bm{\Sigma}})t/ \tau}-1\right)+\sqrt{2}\int_{0}^{t}s\left\|{\bm{W}}-\widetilde{\bm{W}}\right\|dt.$ $$

Via \lemmareflemma:gronwall Grönwall’s Inequality, we obtain

$$ $\displaystyle\left\|{\bm{W}}-\widetilde{\bm{W}}\right\|$ $\displaystyle\leq\frac{\sqrt{2}\operatorname{Tr}{\bm{\Sigma}}u_{0}^{3}}{3(s+ \operatorname{Tr}{\bm{\Sigma}})}\left[e^{3(s+\operatorname{Tr}{\bm{\Sigma}})t/ \tau}-1+\int_{0}^{t}\left(e^{3(s+\operatorname{Tr}{\bm{\Sigma}})t^{\prime}/ \tau}-1\right)\sqrt{2}se^{\sqrt{2}st^{\prime}}dt^{\prime}\right]$ $\displaystyle=\frac{\sqrt{2}\operatorname{Tr}{\bm{\Sigma}}u_{0}^{3}}{3(s+ \operatorname{Tr}{\bm{\Sigma}})}\left[e^{3(s+\operatorname{Tr}{\bm{\Sigma}})t/ \tau}+\frac{\sqrt{2}s\left(e^{[3(s+\operatorname{Tr}{\bm{\Sigma}})+\sqrt{2}s]t /\tau}-1\right)}{3(s+\operatorname{Tr}{\bm{\Sigma}})+\sqrt{2}s}-e^{\sqrt{2}st} \right].$ $$

When $t<\frac{\tau}{s+\operatorname{Tr}{\bm{\Sigma}}}\ln\frac{1}{u_{0}}$, we have $\left\|{\bm{W}}-\widetilde{\bm{W}}\right\|<C_{1}u_{0}^{2}$ for some constant $C_{1}$.

We are now ready to bound the difference between the exact solution and an exponential function along one direction

$$ $\displaystyle{\bm{W}}-e^{\frac{\alpha+1}{2\tau}st}\begin{bmatrix}{\bar{\bm{ \beta}}}\\ 1\end{bmatrix}{\bm{r}}_{1}^{\top}$ $\displaystyle=$ $\displaystyle\left({\bm{W}}-\widetilde{\bm{W}}\right)+\left(\widetilde{\bm{W}} -e^{-\frac{\alpha+1}{2\tau}st}\begin{bmatrix}{\bar{\bm{\beta}}}\\ 1\end{bmatrix}{\bm{r}}_{1}^{\top}\right)$ $\displaystyle=$ $\displaystyle\left({\bm{W}}-\widetilde{\bm{W}}\right)+\frac{1}{2}e^{-\frac{ \alpha+1}{2\tau}st}\begin{bmatrix}{\bar{\bm{\beta}}}\\ -1\end{bmatrix}\left(\bar{\bm{\beta}}^{\top}{\bm{W}}_{1}^{\top}(0)-{\bm{W}}_{2 }(0)\right)+\begin{bmatrix}\left({\bm{I}}-\bar{\bm{\beta}}\bar{\bm{\beta}}^{ \top}\right){\bm{W}}_{1}^{\top}(0)\\ 0\end{bmatrix}.$ $$

The first term arises from our approximation of dropping the cubic terms in the dynamics. Its norm is bounded by $C_{1}w_{\mathrm{init}}^{2}$. The second term arises from initialization, which is $O(w_{\mathrm{init}})$. Via triangle inequality, the norm of the total error is order $O(w_{\mathrm{init}})$.

$$ $\displaystyle\left\|{\bm{W}}-e^{\frac{\alpha+1}{2\tau}st}\begin{bmatrix}{\bar{ \bm{\beta}}}\\ 1\end{bmatrix}{\bm{r}}_{1}^{\top}\right\|<C_{1}w_{\mathrm{init}}^{2}+C_{2}w_{ \mathrm{init}}<Cw_{\mathrm{init}}.$ $$

Theorem E.3 can imply two messages. Firstly, the (leaky) ReLU network has the same time-course solution as its linear counterpart except a scale factor determined by $\alpha$, which is consistent with Theorem 4.1. Secondly, the (leaky) ReLU and linear networks form rank-one weights with small errors in the early phase. We will exploit the rank-one weights to reduce the learning dynamics to Equation 34.

###### Lemma E.1 .

###### Proof E.2 .

###### Theorem E.3 .

###### Proof E.4 .

### E.2 Late Phase

###### Proof E.5 .

of Theorem 4.1 (square loss).

Theorem 4.1 relies on \conditionrefass:sym-data and \assumptionrefass:L2-rank1 and arrives at three statements: implementing the same function as in Equation 4, having the same weights as in Equation 5, and retaining rank-one weights as \assumptionrefass:L2-rank1 retains valid. We prove them one by one.

Part 1: We first prove that the (leaky) ReLU network and the linear network implements the same linear function except scaling when their weights are rank-one, satisfying \assumptionrefass:L2-rank1.
Denote ${\bm{W}}_{2}=[{\bm{W}}_{2}^{+},{\bm{W}}_{2}^{-}]$ where ${\bm{W}}_{2}^{+}$ are the positive elements in ${\bm{W}}_{2}$ and ${\bm{W}}_{2}^{-}$ are the negative elements in ${\bm{W}}_{2}$.
For a (leaky) ReLU network with rank-one weights as in \assumptionrefass:L2-rank1, we have

$$ $\displaystyle f({\bm{x}};{\bm{W}})={\bm{W}}_{2}\sigma({\bm{W}}_{1}{\bm{x}})={ \bm{W}}_{2}\sigma\left({\bm{W}}_{2}^{\top}{\bm{r}}^{\top}{\bm{x}}\right).$ $$

Notate the positive and negative half-space as

$$ $\displaystyle{\mathbb{S}}^{+}=\left\{{\bm{x}}\in{\mathbb{R}}^{D}\big{|}{\bm{r} }^{\top}{\bm{x}}\geq 0\right\},\quad{\mathbb{S}}^{-}=\left\{{\bm{x}}\in{ \mathbb{R}}^{D}\big{|}{\bm{r}}^{\top}{\bm{x}}<0\right\}.$ (26) $$

For ${\bm{x}}\in{\mathbb{S}}^{+}$, we have

$$ $\displaystyle f({\bm{x}};{\bm{W}})={\bm{r}}^{\top}{\bm{x}}{\bm{W}}_{2}\sigma({ \bm{W}}_{2}^{\top})={\bm{r}}^{\top}{\bm{x}}\begin{bmatrix}{\bm{W}}_{2}^{+}&{ \bm{W}}_{2}^{-}\end{bmatrix}\begin{bmatrix}{{\bm{W}}_{2}^{+}}^{\top}\\ \alpha{{\bm{W}}_{2}^{-}}^{\top}\end{bmatrix}={\bm{r}}^{\top}{\bm{x}}\left(\|{ \bm{W}}_{2}^{+}\|^{2}+\alpha\|{\bm{W}}_{2}^{-}\|^{2}\right).$ $$

For ${\bm{x}}\in{\mathbb{S}}^{-}$, we have

$$ $\displaystyle f({\bm{x}};{\bm{W}})=-{\bm{r}}^{\top}{\bm{x}}{\bm{W}}_{2}\sigma( -{\bm{W}}_{2}^{\top})={\bm{r}}^{\top}{\bm{x}}\begin{bmatrix}{\bm{W}}_{2}^{+}&{ \bm{W}}_{2}^{-}\end{bmatrix}\begin{bmatrix}\alpha{{\bm{W}}_{2}^{+}}^{\top}\\ {{\bm{W}}_{2}^{-}}^{\top}\end{bmatrix}={\bm{r}}^{\top}{\bm{x}}\left(\alpha\|{ \bm{W}}_{2}^{+}\|^{2}+\|{\bm{W}}_{2}^{-}\|^{2}\right).$ $$

Under \assumptionrefass:L2-rank1, we have $\|{\bm{W}}_{2}^{+}\|=\|{\bm{W}}_{2}^{-}\|$. Hence, the (leaky) ReLU network implements

$$ $\displaystyle f({\bm{x}};{\bm{W}})={\bm{W}}_{2}\sigma({\bm{W}}_{1}{\bm{x}})= \frac{\alpha+1}{2}{\bm{r}}^{\top}{\bm{x}}\|{\bm{W}}_{2}\|^{2}.$ (27) $$

Under \assumptionrefass:L2-rank1, the linear network implements

$$ $\displaystyle f^{\mathrm{lin}}({\bm{x}};{\bm{W}})={\bm{W}}_{2}{\bm{W}}_{1}{\bm {x}}={\bm{W}}_{2}{\bm{W}}_{2}^{\top}{\bm{r}}^{\top}{\bm{x}}={\bm{r}}^{\top}{ \bm{x}}\|{\bm{W}}_{2}\|^{2}.$ (28) $$

Comparing Equations 27 and 28, we find that when the weights satisfy \assumptionrefass:L2-rank1, the (leaky) ReLU network implements the same function as the linear network except a constant scale

$$ $\displaystyle{\bm{W}}_{2}\sigma({\bm{W}}_{1}{\bm{x}})=\frac{\alpha+1}{2}{\bm{W }}_{2}{\bm{W}}_{1}{\bm{x}}.$ (29) $$

Part 2: We then look into the learning dynamics to prove that the weights in the (leaky) ReLU and the linear network are the same except scaling. Substituting Equation 29 into the dynamics, we obtain

$$ $\displaystyle\begin{split}\tau\dot{\bm{W}}_{1}&=\frac{\alpha+1}{2}{\bm{W}}_{2} ^{\top}{\bm{\beta}}^{\top}-\left\langle\sigma^{\prime}({\bm{W}}_{1}{\bm{x}}) \odot{\bm{W}}_{2}^{\top}{\bm{W}}_{2}\sigma({\bm{W}}_{1}{\bm{x}}){\bm{x}}^{\top }\right\rangle\\ &=\frac{\alpha+1}{2}{\bm{W}}_{2}^{\top}{\bm{\beta}}^{\top}-\frac{\alpha+1}{2} \left\langle\sigma^{\prime}({\bm{W}}_{1}{\bm{x}})\odot{\bm{W}}_{2}^{\top}{\bm{ W}}_{2}{\bm{W}}_{1}{\bm{x}}{\bm{x}}^{\top}\right\rangle,\end{split}$ (30a) $\displaystyle\begin{split}\tau\dot{\bm{W}}_{2}&=\frac{\alpha+1}{2}{\bm{\beta}} ^{\top}{\bm{W}}_{1}^{\top}-{\bm{W}}_{2}\left\langle\sigma({\bm{W}}_{1}{\bm{x}} )\sigma({\bm{W}}_{1}{\bm{x}})^{\top}\right\rangle\\ &=\frac{\alpha+1}{2}{\bm{\beta}}^{\top}{\bm{W}}_{1}^{\top}-\frac{\alpha+1}{2}{ \bm{W}}_{2}{\bm{W}}_{1}\left\langle{\bm{x}}\sigma({\bm{W}}_{1}{\bm{x}})^{\top} \right\rangle.\end{split}$ (30b) $$

We compute the second terms in the dynamics under \conditionrefass:sym-data and \assumptionrefass:L2-rank1

$$ $\displaystyle\left\langle\sigma^{\prime}({\bm{W}}_{1}{\bm{x}})\odot{\bm{W}}_{2 }^{\top}{\bm{W}}_{2}{\bm{W}}_{1}{\bm{x}}{\bm{x}}^{\top}\right\rangle$ (31) $\displaystyle=$ $\displaystyle\frac{1}{2}\left\langle\sigma^{\prime}({\bm{W}}_{1}{\bm{x}})\odot {\bm{W}}_{2}^{\top}{\bm{W}}_{2}{\bm{W}}_{1}{\bm{x}}{\bm{x}}^{\top}\right \rangle_{{\mathbb{S}}^{+}}+\frac{1}{2}\left\langle\sigma^{\prime}({\bm{W}}_{1} {\bm{x}})\odot{\bm{W}}_{2}^{\top}{\bm{W}}_{2}{\bm{W}}_{1}{\bm{x}}{\bm{x}}^{ \top}\right\rangle_{{\mathbb{S}}^{-}}$ $\displaystyle=$ $\displaystyle\frac{1}{2}\begin{bmatrix}{\bm{1}}\\ \alpha{\bm{1}}\end{bmatrix}\odot{\bm{W}}_{2}^{\top}{\bm{W}}_{2}{\bm{W}}_{1} \left\langle{\bm{x}}{\bm{x}}^{\top}\right\rangle_{{\mathbb{S}}^{+}}+\frac{1}{2 }\begin{bmatrix}\alpha{\bm{1}}\\ {\bm{1}}\end{bmatrix}\odot{\bm{W}}_{2}^{\top}{\bm{W}}_{2}{\bm{W}}_{1}\left \langle{\bm{x}}{\bm{x}}^{\top}\right\rangle_{{\mathbb{S}}^{-}}$ $\displaystyle=$ $\displaystyle\frac{1}{2}\begin{bmatrix}{{\bm{W}}_{2}^{+}}^{\top}\\ \alpha{{\bm{W}}_{2}^{-}}^{\top}\end{bmatrix}{\bm{W}}_{2}{\bm{W}}_{1}{\bm{ \Sigma}}+\frac{1}{2}\begin{bmatrix}\alpha{{\bm{W}}_{2}^{+}}^{\top}\\ {{\bm{W}}_{2}^{-}}^{\top}\end{bmatrix}{\bm{W}}_{2}{\bm{W}}_{1}{\bm{\Sigma}}$ $\displaystyle=$ $\displaystyle\frac{\alpha+1}{2}{\bm{W}}_{2}^{\top}{\bm{W}}_{2}{\bm{W}}_{1}{\bm {\Sigma}},$ (32) $$

and

$$ $\displaystyle\left\langle{\bm{x}}\sigma({\bm{W}}_{1}{\bm{x}})^{\top}\right\rangle$ $\displaystyle=\frac{1}{2}\left\langle{\bm{x}}\sigma({\bm{W}}_{1}{\bm{x}})^{ \top}\right\rangle_{{\mathbb{S}}^{+}}+\frac{1}{2}\left\langle{\bm{x}}\sigma({ \bm{W}}_{1}{\bm{x}})^{\top}\right\rangle_{{\mathbb{S}}^{-}}$ $\displaystyle=\frac{1}{2}\left\langle{\bm{x}}{\bm{x}}^{\top}\right\rangle_{{ \mathbb{S}}^{+}}{\bm{r}}\begin{bmatrix}{\bm{W}}_{2}^{+}&\alpha{\bm{W}}_{2}^{-} \end{bmatrix}+\frac{1}{2}\left\langle{\bm{x}}{\bm{x}}^{\top}\right\rangle_{{ \mathbb{S}}^{-}}{\bm{r}}\begin{bmatrix}\alpha{\bm{W}}_{2}^{+}&{\bm{W}}_{2}^{-} \end{bmatrix}$ $\displaystyle=\frac{\alpha+1}{2}{\bm{\Sigma}}{\bm{r}}{\bm{W}}_{2}$ $\displaystyle=\frac{\alpha+1}{2}{\bm{\Sigma}}{\bm{W}}_{1}^{\top}.$ (33) $$

Substituting Equations 31 and E.5 into Equation 30, we obtain the reduced dynamics

$$ $\displaystyle\tau\dot{\bm{W}}_{1}$ $\displaystyle=\frac{\alpha+1}{2}{\bm{W}}_{2}^{\top}{\bm{\beta}}^{\top}-\left( \frac{\alpha+1}{2}\right)^{2}{{\bm{W}}_{2}}^{\top}{\bm{W}}_{2}{\bm{W}}_{1}{\bm {\Sigma}},$ (34a) $\displaystyle\tau\dot{\bm{W}}_{2}$ $\displaystyle=\frac{\alpha+1}{2}{\bm{\beta}}^{\top}{\bm{W}}_{1}^{\top}-\left( \frac{\alpha+1}{2}\right)^{2}{\bm{W}}_{2}{\bm{W}}_{1}{\bm{\Sigma}}{{\bm{W}}_{1 }}^{\top}.$ (34b) $$

If we scale the weights

$$ $\displaystyle\overline{\bm{W}}_{1}=\sqrt{\frac{\alpha+1}{2}}{\bm{W}}_{1},\quad \overline{\bm{W}}_{2}=\sqrt{\frac{\alpha+1}{2}}{\bm{W}}_{2},$ (35) $$

the (leaky) ReLU network dynamics is the same as that of a linear network given in Equation 8 except the time constant

$$ $\displaystyle\frac{2\tau}{\alpha+1}\dot{\overline{\bm{W}}_{1}}={\overline{\bm{ W}}}_{2}^{\top}\left({\bm{\beta}}^{\top}-\overline{\bm{W}}_{2}\overline{\bm{W} }_{1}{\bm{\Sigma}}\right),\quad\frac{2\tau}{\alpha+1}\dot{\overline{\bm{W}}_{2 }}=\left({\bm{\beta}}^{\top}-\overline{\bm{W}}_{2}\overline{\bm{W}}_{1}{\bm{ \Sigma}}\right){\overline{\bm{W}}}_{1}^{\top}.$ $$

Because Theorem 4.1 defines the initial condition $\overline{\bm{W}}(0)=\sqrt{\frac{\alpha+1}{2}}{\bm{W}}(0)={\bm{W}}^{\mathrm{
lin}}(0)$, the weights in the linear network and the scaled weights in the (leaky) ReLU network start from the same initialization, obey the same dynamics, and consequently stay the same $\forall\,t\geq 0$

$$ $\displaystyle\overline{\bm{W}}(t)$ $\displaystyle={\bm{W}}^{\mathrm{lin}}\left(\frac{\alpha+1}{2}t\right)$ $\displaystyle\Leftrightarrow{\bm{W}}(t)$ $\displaystyle=\sqrt{\frac{2}{\alpha+1}}{\bm{W}}^{\mathrm{lin}}\left(\frac{ \alpha+1}{2}t\right).$ $$

This proves Equation 5. Substituting Equation 5 into Equation 29 proves Equation 4

$$ $\displaystyle f({\bm{x}};{\bm{W}}(t))=\frac{\alpha+1}{2}{\bm{W}}(t){\bm{W}}(t) {\bm{x}}$ $\displaystyle={\bm{W}}_{2}^{\mathrm{lin}}\left(\frac{\alpha+1}{2}t\right){\bm{ W}}_{1}^{\mathrm{lin}}\left(\frac{\alpha+1}{2}t\right){\bm{x}}$ $\displaystyle\equiv f^{\mathrm{lin}}\left({\bm{x}};{\bm{W}}^{\mathrm{lin}} \left(\frac{\alpha+1}{2}t\right)\right).$ $$

Part 3: We now show that \assumptionrefass:L2-rank1 made at time $t=0$ remains valid for $t>0$, meaning that weights which start with rank-one structure remain rank-one. With \assumptionrefass:L2-rank1 at time $t=0$, the dynamics of the (leaky) ReLU network is described by Equation 34. This dynamics is the same as scaled dynamics in a linear network and thus satisfy the balancing property in linear networks (Ji and Telgarsky, ; Du et al., )

$$ $\displaystyle\frac{d}{dt}\left({\bm{W}}_{1}{\bm{W}}_{1}^{\top}-{\bm{W}}_{2}^{ \top}{\bm{W}}_{2}\right)=0.$ (36) $$

Under \assumptionrefass:L2-rank1 at time $t=0$, this quantity is zero at time $t=0$ and will stay zero because of the balancing property

$$ $\displaystyle\forall\,t\geq 0:\quad{\bm{W}}_{1}(t){\bm{W}}_{1}(t)^{\top}-{\bm{ W}}_{2}(t)^{\top}{\bm{W}}_{2}(t)={\bm{W}}_{1}(0){\bm{W}}_{1}(0)^{\top}-{\bm{W} }_{2}(0)^{\top}{\bm{W}}_{2}(0)={\bm{0}}.$ $$

Because $\text{rank}\left({\bm{W}}_{1}{\bm{W}}_{1}^{\top}\right)=\text{rank}({\bm{W}}_{
1})$, the balancing property enforces that ${\bm{W}}_{1}$ and ${\bm{W}}_{2}$ have equal rank. Since ${\bm{W}}_{2}$ is a vector, ${\bm{W}}_{1}$ has rank one. We can write a rank-one matrix as the outer-product between two vectors ${\bm{W}}_{1}={\bm{v}}{\bm{r}}^{\top}$. We can assume $\|{\bm{r}}\|=1$ for convenience and get

$$ $\displaystyle{\bm{W}}_{1}{\bm{W}}_{1}^{\top}={\bm{v}}{\bm{r}}^{\top}{\bm{r}}{ \bm{v}}^{\top}={\bm{v}}{\bm{v}}^{\top}={\bm{W}}_{2}^{\top}{\bm{W}}_{2}\quad \Rightarrow\quad{\bm{v}}=\pm{\bm{W}}_{2}^{\top}.$ $$

Because \assumptionrefass:L2-rank1 specifies ${\bm{W}}_{1}={\bm{W}}_{2}^{\top}{\bm{r}}^{\top}$, then ${\bm{v}}={\bm{W}}_{2}^{\top}$. To summarize, \assumptionrefass:L2-rank1 at time $t=0$ reduces the learning dynamics of the ReLU network to be similar to that of a linear network. The reduced dynamics satisfies the balancing property which enforces that the weights retain rank-one, satisfying \assumptionrefass:L2-rank1 for all $t\geq 0$.

###### Proof E.6 .

of Theorem 4.1 (logistic loss).

Part 1: Same as the square loss case because Equation 29 holds regardless of the loss function.

Part 2: Substituting Equation 29 into Equation 7, we get

$$ $\displaystyle\tau\dot{\bm{W}}_{1}$ $\displaystyle=\frac{\alpha+1}{2}\left\langle\frac{\sigma^{\prime}({\bm{W}}_{1} {\bm{x}})\odot{\bm{W}}_{2}^{\top}{\bm{W}}_{2}{\bm{W}}_{1}{\bm{x}}{\bm{x}}^{ \top}}{e^{\frac{\alpha+1}{2}y{\bm{W}}_{2}{\bm{W}}_{1}{\bm{x}}}+1}\right\rangle,$ (37a) $\displaystyle\tau\dot{\bm{W}}_{2}$ $\displaystyle=\frac{\alpha+1}{2}{\bm{W}}_{2}{\bm{W}}_{1}\left\langle\frac{{\bm {x}}\sigma({\bm{W}}_{1}{\bm{x}})^{\top}}{e^{\frac{\alpha+1}{2}y{\bm{W}}_{2}{ \bm{W}}_{1}{\bm{x}}}+1}\right\rangle.$ (37b) $$

Under \conditionrefass:sym-data and \assumptionrefass:L2-rank1 Equation 37 can be simplified

$$ $\displaystyle\left\langle\frac{\sigma^{\prime}({\bm{W}}_{1}{\bm{x}})\odot{\bm{ W}}_{2}^{\top}{\bm{W}}_{2}{\bm{W}}_{1}{\bm{x}}{\bm{x}}^{\top}}{e^{\frac{\alpha +1}{2}y{\bm{W}}_{2}{\bm{W}}_{1}{\bm{x}}}+1}\right\rangle$ $\displaystyle=$ $\displaystyle\frac{1}{2}\left\langle\frac{\sigma^{\prime}({\bm{W}}_{1}{\bm{x}} )\odot{\bm{W}}_{2}^{\top}{\bm{W}}_{2}{\bm{W}}_{1}{\bm{x}}{\bm{x}}^{\top}}{e^{ \frac{\alpha+1}{2}y{\bm{W}}_{2}{\bm{W}}_{1}{\bm{x}}}+1}\right\rangle_{{\mathbb {S}}^{+}}+\frac{1}{2}\left\langle\frac{\sigma^{\prime}({\bm{W}}_{1}{\bm{x}}) \odot{\bm{W}}_{2}^{\top}{\bm{W}}_{2}{\bm{W}}_{1}{\bm{x}}{\bm{x}}^{\top}}{e^{ \frac{\alpha+1}{2}y{\bm{W}}_{2}{\bm{W}}_{1}{\bm{x}}}+1}\right\rangle_{{\mathbb {S}}^{-}}$ $\displaystyle=$ $\displaystyle\frac{1}{2}\begin{bmatrix}\alpha{{\bm{W}}_{2}^{+}}^{\top}\\ {{\bm{W}}_{2}^{-}}^{\top}\end{bmatrix}{\bm{W}}_{2}{\bm{W}}_{1}\left\langle \frac{{\bm{x}}{\bm{x}}^{\top}}{e^{\frac{\alpha+1}{2}y{\bm{W}}_{2}{\bm{W}}_{1}{ \bm{x}}}+1}\right\rangle_{{\mathbb{S}}^{+}}+\frac{1}{2}\begin{bmatrix}{{\bm{W} }_{2}^{+}}^{\top}\\ \alpha{{\bm{W}}_{2}^{-}}^{\top}\end{bmatrix}{\bm{W}}_{2}{\bm{W}}_{1}\left \langle\frac{{\bm{x}}{\bm{x}}^{\top}}{e^{\frac{\alpha+1}{2}y{\bm{W}}_{2}{\bm{W }}_{1}{\bm{x}}}+1}\right\rangle_{{\mathbb{S}}^{-}}$ $\displaystyle=$ $\displaystyle\frac{\alpha+1}{2}{{\bm{W}}_{2}}^{\top}{\bm{W}}_{2}{\bm{W}}_{1} \left\langle\frac{{\bm{x}}{\bm{x}}^{\top}}{e^{\frac{\alpha+1}{2}y{\bm{W}}_{2}{ \bm{W}}_{1}{\bm{x}}}+1}\right\rangle,$ $$

and

$$ $\displaystyle\left\langle\frac{{\bm{x}}\sigma({\bm{W}}_{1}{\bm{x}})^{\top}}{e^ {\frac{\alpha+1}{2}y{\bm{W}}_{2}{\bm{W}}_{1}{\bm{x}}}+1}\right\rangle$ $\displaystyle=$ $\displaystyle\frac{1}{2}\left\langle\frac{{\bm{x}}\sigma({\bm{W}}_{1}{\bm{x}}) ^{\top}}{e^{\frac{\alpha+1}{2}y{\bm{W}}_{2}{\bm{W}}_{1}{\bm{x}}}+1}\right \rangle_{{\mathbb{S}}^{+}}+\frac{1}{2}\left\langle\frac{{\bm{x}}\sigma({\bm{W} }_{1}{\bm{x}})^{\top}}{e^{\frac{\alpha+1}{2}y{\bm{W}}_{2}{\bm{W}}_{1}{\bm{x}}} +1}\right\rangle_{{\mathbb{S}}^{-}}$ $\displaystyle=$ $\displaystyle\frac{1}{2}\left\langle\frac{{\bm{x}}{\bm{x}}^{\top}}{e^{\frac{ \alpha+1}{2}y{\bm{W}}_{2}{\bm{W}}_{1}{\bm{x}}}+1}\right\rangle_{{\mathbb{S}}^{ +}}{\bm{r}}\begin{bmatrix}\alpha{\bm{W}}_{2}^{+}&{\bm{W}}_{2}^{-}\end{bmatrix} +\frac{1}{2}\left\langle\frac{{\bm{x}}{\bm{x}}^{\top}}{e^{\frac{\alpha+1}{2}y{ \bm{W}}_{2}{\bm{W}}_{1}{\bm{x}}}+1}\right\rangle_{{\mathbb{S}}^{-}}{\bm{r}} \begin{bmatrix}{\bm{W}}_{2}^{+}&\alpha{\bm{W}}_{2}^{-}\end{bmatrix}$ $\displaystyle=$ $\displaystyle\frac{\alpha+1}{2}\left\langle\frac{{\bm{x}}{\bm{x}}^{\top}}{e^{ \frac{\alpha+1}{2}y{\bm{W}}_{2}{\bm{W}}_{1}{\bm{x}}}+1}\right\rangle{{\bm{W}}_ {1}}^{\top}.$ $$

Thus, the reduced dynamics of the two-layer (leaky) ReLU network are

$$ $\displaystyle\tau\dot{\bm{W}}_{1}$ $\displaystyle=\left(\frac{\alpha+1}{2}\right)^{2}{{\bm{W}}_{2}}^{\top}{\bm{W}} _{2}{\bm{W}}_{1}\left\langle\frac{{\bm{x}}{\bm{x}}^{\top}}{e^{\frac{\alpha+1}{ 2}y{\bm{W}}_{2}{\bm{W}}_{1}{\bm{x}}}+1}\right\rangle,$ $\displaystyle\tau\dot{\bm{W}}_{2}$ $\displaystyle=\left(\frac{\alpha+1}{2}\right)^{2}{\bm{W}}_{2}{\bm{W}}_{1}\left \langle\frac{{\bm{x}}{\bm{x}}^{\top}}{e^{\frac{\alpha+1}{2}y{\bm{W}}_{2}{\bm{W }}_{1}{\bm{x}}}+1}\right\rangle{{\bm{W}}_{1}}^{\top}.$ $$

If we scale the weights as Equation 35, the (leaky) ReLU network dynamics is the same as that of a linear network given in Equation 10 except the time constant

$$ $\displaystyle\frac{2\tau}{\alpha+1}\dot{\overline{\bm{W}}_{1}}$ $\displaystyle={\overline{\bm{W}}_{2}}^{\top}\overline{\bm{W}}_{2}\overline{\bm {W}}_{1}\left\langle\frac{{\bm{x}}{\bm{x}}^{\top}}{e^{y\overline{\bm{W}}_{2} \overline{\bm{W}}_{1}{\bm{x}}}+1}\right\rangle,$ $\displaystyle\frac{2\tau}{\alpha+1}\dot{\overline{\bm{W}}_{2}}$ $\displaystyle=\overline{\bm{W}}_{2}\overline{\bm{W}}_{1}\left\langle\frac{{\bm {x}}{\bm{x}}^{\top}}{e^{y\overline{\bm{W}}_{2}\overline{\bm{W}}_{1}{\bm{x}}}+1 }\right\rangle{\overline{\bm{W}}_{1}}^{\top}.$ $$

Through the same reasoning as the square loss case, Equations 4 and 5 are proved.

Part 3: Same as the square loss case.

###### Proof E.5 .

###### Proof E.6 .

### E.3 Time-Course Solution

###### Corollary E.7 .

For learning with square loss, if the input covariance is white, ${\bm{\Sigma}}={\bm{I}}$, the solution to Equation 4 is $f({\bm{x}};{\bm{W}})={\bm{w}}(t)^{\top}{\bm{x}}$ with

$$ $\displaystyle{\bm{w}}(t)=$ $\displaystyle\left(1+\frac{q_{1}}{q_{2}}e^{-2s\tilde{t}}\right)\left[\bar{\bm{ \beta}}\left(1-\frac{q_{1}}{q_{2}}e^{-2s\tilde{t}}\right)+\frac{2}{q_{2}}\left ({\bm{I}}-\bar{\bm{\beta}}\bar{\bm{\beta}}^{\top}\right){\bm{r}}e^{-s\tilde{t} }\right]$ $\displaystyle\left[\frac{4}{q_{2}^{2}}\left(u_{0}^{-2}+\left(1-\left({\bm{r}}^ {\top}\bar{\bm{\beta}}\right)^{2}\right)\tilde{t}\right)e^{-2s\tilde{t}}+\frac {1}{s}\left(1+\frac{q_{1}^{2}}{q_{2}^{2}}e^{-2s\tilde{t}}\right)\left(1-e^{-2s \tilde{t}}\right)\right]^{-1},$ (38) $$

where $\tilde{t}$ is a shorthand for rescaled time $\tilde{t}=\frac{\alpha+1}{2\tau}t$ and the constant quantities are $s=\|{\bm{\beta}}\|,\bar{\bm{\beta}}={\bm{\beta}}/s,q_{1}=1-{\bm{r}}^{\top}\bar
{\bm{\beta}},q_{2}=1+{\bm{r}}^{\top}\bar{\bm{\beta}},u_{0}=\|{\bm{W}}_{1}(0)\|$.

###### Proof E.8 .

.
Based on the equivalence stated in Theorem 4.1, we directly adopt the solution of linear networks (Braun et al., , Theorem 3.1) to two-layer bias-free (leaky) ReLU networks.

The solution given in Equation 38 matches the simulations in Figure 1.

###### Corollary E.7 .

###### Proof E.8 .

### E.4 Global Minimum

###### Proof E.9 .

of \corollaryrefcor:L2-converge.

The converged solution ${\bm{w}}^{\ast}$ is a direct consequence of the equivalence we showed in Theorem 4.1 and prior results of linear networks (Saxe et al., ; Soudry et al., ).

We now show that for symmetric datasets satisfying \conditionrefass:sym-data, the global minimum of a two-layer bias-free (leaky) ReLU network trained with square loss is a linear map.
Based on Theorem 3.1, we can write a two-layer bias-free (leaky) ReLU network as a linear function plus an even function $f({\bm{x}})={\bm{x}}^{\top}{\bm{w}}^{\ast}+f_{e}({\bm{x}})$ where $f_{e}(\cdot)$ denotes an even function. For datasets satisfying \conditionrefass:sym-data, the square loss is

$$ $\displaystyle\mathcal{L}$ $\displaystyle=\frac{1}{2}\left\langle\left(y-{\bm{x}}^{\top}{\bm{w}}^{\ast}-f_ {e}({\bm{x}})\right)^{2}\right\rangle_{p({\bm{x}})}$ $\displaystyle=\frac{1}{2}\left\langle\left(y-{\bm{x}}^{\top}{\bm{w}}^{\ast} \right)^{2}-2(y-{\bm{A}}{\bm{x}})f_{e}({\bm{x}})+f_{e}({\bm{x}})^{2}\right \rangle_{p({\bm{x}})}$ $\displaystyle=\frac{1}{2}\left\langle\left(y-{\bm{x}}^{\top}{\bm{w}}^{\ast} \right)^{2}\right\rangle_{p({\bm{x}})}+\frac{1}{2}\left\langle f_{e}({\bm{x}}) ^{2}\right\rangle_{p({\bm{x}})}.$ $$

The square loss attains its minimum when both $\left\langle\left(y-{\bm{x}}^{\top}{\bm{w}}^{\ast}\right)^{2}\right\rangle_{p(
{\bm{x}})}$ and $\left\langle f_{e}({\bm{x}})^{2}\right\rangle_{p({\bm{x}})}$ are minimized. The former is minimized when ${\bm{w}}^{\ast}={\bm{\Sigma}}^{-1}{\bm{\beta}}$. The latter is minimized when $f_{e}({\bm{x}})=0$. Hence, for symmetric datasets satisfying \conditionrefass:sym-data, the two-layer bias-free (leaky) ReLU network achieves globally minimum square loss with the linear, ordinary least squares solution $f({\bm{x}})={{\bm{w}}^{\ast}}^{\top}{\bm{x}}$.

###### Proof E.9 .

## Appendix F Deep ReLU Network

### F.1 Low-Rank Weights

We empirically find that deep bias-free ReLU networks can form low-rank weights that are similar to those in deep linear networks when the empirical input distribution is even and the target function is linear.

In a deep linear network, weights form a rank-one structure and adjacent layers are aligned when trained from small initialization (Advani et al., ; Ji and Telgarsky, ; Atanasov et al., ). The rank-one weight matrices can be written as outer-products of two vectors

$$ $\displaystyle{\bm{W}}_{1}^{\mathrm{lin}}$ $\displaystyle=u{\bm{r}}_{1}{\bm{r}}^{\top}=u\begin{bmatrix}{\bm{r}}_{1}^{+}\\ {\bm{r}}_{1}^{-}\end{bmatrix}{\bm{r}}^{\top},$ (39a) $\displaystyle{\bm{W}}_{l}^{\mathrm{lin}}$ $\displaystyle=u{\bm{r}}_{l}{\bm{r}}_{l-1}^{\top}=u\begin{bmatrix}{\bm{r}}_{l}^ {+}{{\bm{r}}_{l-1}^{+}}^{\top}&{\bm{r}}_{l}^{+}{{\bm{r}}_{l-1}^{-}}^{\top}\\ {\bm{r}}_{l}^{-}{{\bm{r}}_{l-1}^{+}}^{\top}&{\bm{r}}_{l}^{-}{{\bm{r}}_{l-1}^{- }}^{\top}\end{bmatrix},\quad l=2,\cdots,L-1,$ (39b) $\displaystyle{\bm{W}}_{L}^{\mathrm{lin}}$ $\displaystyle=u{\bm{r}}_{L-1}^{\top}=u\begin{bmatrix}{{\bm{r}}_{L-1}^{+}}^{ \top}&{{\bm{r}}_{L-1}^{-}}^{\top}\end{bmatrix},$ (39c) $$

where $u$ represents the norm of each layer, and ${\bm{r}},{\bm{r}}_{1},{\bm{r}}_{2},\cdots,{\bm{r}}_{L}$ are unit norm column vectors. The vectors ${\bm{r}}_{l}^{+},{\bm{r}}_{l}^{-}$ denote the positive and negative elements in ${\bm{r}}_{l}$. The equal norm $u$ of all layers is a consequence of small initialization (Du et al., ). Note that the weights can be written in blocks, as Equation 39, only after permuting the positive and negative elements. We use this permuted notation for convenience only; no additional assumptions are required.

In a deep ReLU network, we find empirically that when the weights are trained from small initialization and the target function is linear, the weights form a rank-one and rank-two structure. The deep bias-free network’s weights can be written approximately as

$$ $\displaystyle{\bm{W}}_{1}$ $\displaystyle=u{\bm{r}}_{1}{\bm{r}}^{\top}=u\begin{bmatrix}{\bm{r}}_{1}^{+}\\ {\bm{r}}_{1}^{-}\end{bmatrix}{\bm{r}}^{\top},$ (40a) $\displaystyle{\bm{W}}_{l}$ $\displaystyle=u\begin{bmatrix}\sqrt{2}{\bm{r}}_{l}^{+}{{\bm{r}}_{l-1}^{+}}^{ \top}&{\bm{0}}\\ {\bm{0}}&\sqrt{2}{\bm{r}}_{l}^{-}{{\bm{r}}_{l-1}^{-}}^{\top}\end{bmatrix}, \quad l=2,\cdots,L-1,$ (40b) $\displaystyle{\bm{W}}_{L}$ $\displaystyle=u{\bm{r}}_{L-1}^{\top}=u\begin{bmatrix}{{\bm{r}}_{L-1}^{+}}^{ \top}&{{\bm{r}}_{L-1}^{-}}^{\top}\end{bmatrix}.$ (40c) $$

For the first and last layers, the weights in the deep ReLU network have the same rank-one structure as their linear counterpart. For the intermediate layers, weights in the deep ReLU network are rank-two. Moreover, positive weights in the ReLU network correspond to positive weights in the linear network and zero weights in the ReLU network correspond to negative weights in the linear network. We present an example of a three-layer linear and a bias-free ReLU network in Figure 3.

Figure: Figure 3: Low-rank weights in deep linear and ReLU bias-free networks. A three-layer linear network and a three-layer ReLU network are trained on the same dataset starting from the same small random weights. The dataset has a linear target function and an even empirical input data distribution. We plot the weights when the loss has approached zero. ${\bm{W}}_{1}$, ${\bm{W}}_{3}$, and positive elements in ${\bm{W}}_{2}$ have approximately the same structure in the linear and ReLU networks. Elements of ${\bm{W}}_{2}$ that are negative in the linear network are approximately zero in the ReLU network. The neurons are permuted for better visualization.
Refer to caption: x6.png

Assuming $\|{\bm{r}}_{l}^{+}\|=\|{\bm{r}}_{l}^{-}\|,(l=1,2,\cdots,L-1)$, which is justified as the network width approaches infinity, the deep bias-free ReLU network with weights defined in Equation 40 implements a linear function

$$ $\displaystyle f({\bm{x}};{\bm{W}})={\bm{W}}_{L}{\bm{W}}_{L-1}\cdots{\bm{W}}_{2 }\sigma({\bm{W}}_{1}{\bm{x}})=\frac{1}{2}{\bm{W}}_{L}\cdots{\bm{W}}_{2}{\bm{W} }_{1}{\bm{x}}.$ (41) $$

In the first equality, we drop the activation functions except the one between the first and second layers. This is because the output of a ReLU activation function, $\sigma({\bm{W}}_{1}{\bm{x}})$, is non-negative, and so are the second layer weights, ${\bm{W}}_{2}$. Therefore, their product, ${\bm{W}}_{2}\sigma({\bm{W}}_{1}{\bm{x}})$, is also non-negative. We thus have $\sigma({\bm{W}}_{2}\sigma({\bm{W}}_{1}{\bm{x}}))={\bm{W}}_{2}\sigma({\bm{W}}_{
1}{\bm{x}})$. The same applies to all subsequent layers.

When the empirical input distribution is even and the target function is linear, the learning dynamics of the deep bias-free ReLU network with weights as Equation 40 reduces to (see Section F.2)

$$ $\displaystyle\tau\dot{\bm{W}}_{l}=\left(\prod_{l^{\prime}=l+1}^{L}{\bm{W}}_{l^ {\prime}}\right)^{\top}\left(\frac{1}{2}{\bm{\beta}}^{\top}-\frac{1}{4}\prod_{ l^{\prime}=1}^{L}{\bm{W}}_{l^{\prime}}{\bm{\Sigma}}\right)\left(\prod_{l^{ \prime}=l-1}^{L}{\bm{W}}_{l^{\prime}}\right)^{\top}.$ (42) $$

Except for constant coefficients, these equations are the same as that of the deep linear network given in Equation 12. We show, in Section F.2, that weights which have formed a low-rank structure as defined in Equation 40 maintain the structure over training.

We conjecture that the rank-one and rank-two weights in the deep ReLU network relate to the property of aligning between layers discovered in deep linear networks (Ji and Telgarsky, ).
To take the second layer as an example, the linear network has rank-one weights, ${\bm{W}}_{2}=u{\bm{r}}_{2}{\bm{r}}_{1}^{\top}$, so every row of ${\bm{W}}_{2}$ aligns with ${\bm{r}}_{1}$ and thus aligns with the input to the second layer, ${\bm{W}}_{1}{\bm{x}}=u{\bm{r}}_{1}{\bm{r}}^{\top}{\bm{x}}$. The ReLU network has rank-two weights, and the rows of ${\bm{W}}_{2}$ either align with $\begin{bmatrix}{{\bm{r}}_{1}^{+}}^{\top}&{\bm{0}}\end{bmatrix}$ or $\begin{bmatrix}{\bm{0}}&{{\bm{r}}_{1}^{-}}^{\top}\end{bmatrix}$. The former aligns with some inputs to the second layer $\sigma({\bm{W}}_{1}{\bm{x}})=u\begin{bmatrix}{\bm{r}}_{1}^{+}\\
{\bm{0}}\end{bmatrix}{\bm{r}}^{\top}{\bm{x}}$ (where ${\bm{r}}^{\top}{\bm{x}}>0$). The latter aligns with $\sigma({\bm{W}}_{1}{\bm{x}})=u\begin{bmatrix}{\bm{0}}\\
{\bm{r}}_{1}^{-}\end{bmatrix}{\bm{r}}^{\top}{\bm{x}}$ (where ${\bm{r}}^{\top}{\bm{x}}<0$).

### F.2 Learning Dynamics

According to Equation 40, all weight elements in the intermediate layers (${\bm{W}}_{L-1},\cdots,{\bm{W}}_{3},{\bm{W}}_{2}$) are non-negative numbers. According to the definition of the ReLU activation function, $\sigma({\bm{W}}_{1}{\bm{x}})$ yields a vector with non-negative numbers. Thus, ${\bm{W}}_{2}\sigma({\bm{W}}_{1}{\bm{x}})$ yields a vector with non-negative numbers and we have $\sigma({\bm{W}}_{2}\sigma({\bm{W}}_{1}{\bm{x}}))={\bm{W}}_{2}\sigma({\bm{W}}_{
1}{\bm{x}})$. Similarly, all subsequent ReLU activation functions can be ignored(^1^11The activation functions can be ignored when calculating the network output but cannot be ignored when calculating the gradients. This is because for a ReLU function $\sigma(z)=\max(z,0)$ and a linear function $\phi(z)=z$, the function values are equal at zero $\sigma(0)=\phi(0)$ but the derivatives are not equal at zero $\sigma^{\prime}(0)\neq\phi^{\prime}(0)$.). With weights satisfying Equation 40, a deep bias-free ReLU network reduces to

$$ $\displaystyle f({\bm{x}};{\bm{W}})\equiv{\bm{W}}_{L}\sigma(\cdots\sigma({\bm{W }}_{2}\sigma({\bm{W}}_{1}{\bm{x}})))={\bm{W}}_{L}\cdots{\bm{W}}_{2}\sigma({\bm {W}}_{1}{\bm{x}}).$ $$

We stick to the notation for the positive and negative half-space defined in Equation 26. For ${\bm{x}}\in{\mathbb{S}}^{+}$, we have

$$ $\displaystyle f({\bm{x}};{\bm{W}})=u{\bm{W}}_{L}\cdots{\bm{W}}_{2}\begin{ bmatrix}{\bm{r}}_{1}^{+}\\ {\bm{0}}\end{bmatrix}{\bm{r}}^{\top}{\bm{x}}=\cdots=\frac{u^{L-1}}{(\sqrt{2})^ {L-2}}{\bm{W}}_{L}\begin{bmatrix}{\bm{r}}_{L-1}^{+}\\ {\bm{0}}\end{bmatrix}{\bm{r}}^{\top}{\bm{x}}=\left(\frac{u}{\sqrt{2}}\right)^{ L}{\bm{r}}^{\top}{\bm{x}}.$ $$

For ${\bm{x}}\in{\mathbb{S}}^{-}$, we have

$$ $\displaystyle f({\bm{x}};{\bm{W}})=u{\bm{W}}_{L}\cdots{\bm{W}}_{2}\begin{ bmatrix}{\bm{0}}\\ {\bm{r}}_{1}^{-}\end{bmatrix}{\bm{r}}^{\top}{\bm{x}}=\cdots=\frac{u^{L-1}}{( \sqrt{2})^{L-2}}{\bm{W}}_{L}\begin{bmatrix}{\bm{0}}\\ {\bm{r}}_{L-1}^{-}\end{bmatrix}{\bm{r}}^{\top}{\bm{x}}=\left(\frac{u}{\sqrt{2} }\right)^{L}{\bm{r}}^{\top}{\bm{x}}.$ $$

Hence, the deep bias-free ReLU network implements a linear function $f({\bm{x}};{\bm{W}})=\left(\frac{u}{\sqrt{2}}\right)^{L}{\bm{r}}^{\top}{\bm{x}}$. Notice that a deep linear network with such weights implement

$$ $\displaystyle{\bm{W}}_{L}\cdots{\bm{W}}_{2}{\bm{W}}_{1}{\bm{x}}=u{\bm{W}}_{L} \cdots{\bm{W}}_{2}\begin{bmatrix}{\bm{r}}_{1}^{+}\\ {\bm{r}}_{1}^{-}\end{bmatrix}{\bm{r}}^{\top}{\bm{x}}=\cdots=\frac{u^{L-1}}{( \sqrt{2})^{L-2}}{\bm{W}}_{L}{\bm{r}}_{L-1}{\bm{r}}^{\top}{\bm{x}}=\frac{u^{L}} {(\sqrt{2})^{L-2}}{\bm{r}}^{\top}{\bm{x}}.$ $$

Equation 41 is thus proved.

We now prove that under Equation 40 on the weights at time $t=0$, we have that $\forall\,t\geq 0$, Equation 40 retains valid. We assume that $\sigma^{\prime}(0)=0$. We substitute the low-rank weights defined in Equation 40 into the learning dynamics of deep bias-free ReLU networks and make simplifications.
For the first layer,

$$ $\displaystyle\tau\dot{\bm{W}}_{1}$ $\displaystyle=\left\langle\sigma^{\prime}({\bm{W}}_{1}{\bm{x}})\odot{\bm{W}}_{ 2}^{\top}\cdots{\bm{W}}_{L}^{\top}(y-f({\bm{x}})){\bm{x}}^{\top}\right\rangle$ $\displaystyle=\frac{u^{L-1}}{(\sqrt{2})^{L-2}}\left\langle\sigma^{\prime}({\bm {W}}_{1}{\bm{x}})\odot{\bm{r}}_{1}\left(y-\left(\frac{u}{\sqrt{2}}\right)^{L}{ \bm{r}}^{\top}{\bm{x}}\right){\bm{x}}^{\top}\right\rangle$ $\displaystyle=\frac{u^{L-1}}{(\sqrt{2})^{L}}\begin{bmatrix}{\bm{r}}_{1}^{+}\\ {\bm{0}}\end{bmatrix}\left\langle\left(y-\left(\frac{u}{\sqrt{2}}\right)^{L}{ \bm{r}}^{\top}{\bm{x}}\right){\bm{x}}^{\top}\right\rangle_{{\mathbb{S}}^{+}}+ \frac{u^{L-1}}{(\sqrt{2})^{L}}\begin{bmatrix}{\bm{0}}\\ {\bm{r}}_{1}^{-}\end{bmatrix}\left\langle\left(y-\left(\frac{u}{\sqrt{2}} \right)^{L}{\bm{r}}^{\top}{\bm{x}}\right){\bm{x}}^{\top}\right\rangle_{{ \mathbb{S}}^{-}}$ $\displaystyle=\frac{u^{L-1}}{(\sqrt{2})^{L}}{\bm{r}}_{1}\left({\bm{\beta}}^{ \top}-\left(\frac{u}{\sqrt{2}}\right)^{L}{\bm{r}}^{\top}{\bm{\Sigma}}\right).$ (43) $$

For intermediate layers $1<l<L$,

$$ $\displaystyle\tau\dot{\bm{W}}_{l}$ $\displaystyle=\left\langle\sigma^{\prime}({\bm{h}}_{l})\odot{\bm{W}}_{l+1}^{ \top}\cdots{\bm{W}}_{L}^{\top}(y-f({\bm{x}}))\sigma({\bm{h}}_{l-1})^{\top}\right\rangle$ $\displaystyle=\left(\frac{u}{\sqrt{2}}\right)^{L-1}\begin{bmatrix}{\bm{1}}\\ {\bm{0}}\end{bmatrix}\odot\begin{bmatrix}{\bm{r}}_{l}^{+}\\ {\bm{r}}_{l}^{-}\end{bmatrix}\left\langle\left(y-\left(\frac{u}{\sqrt{2}} \right)^{L}{\bm{r}}^{\top}{\bm{x}}\right){\bm{x}}^{\top}\right\rangle_{{ \mathbb{S}}^{+}}{\bm{r}}\begin{bmatrix}{{\bm{r}}_{l-1}^{+}}^{\top}&{\bm{0}} \end{bmatrix}$ $\displaystyle+\left(\frac{u}{\sqrt{2}}\right)^{L-1}\begin{bmatrix}{\bm{0}}\\ {\bm{1}}\end{bmatrix}\odot\begin{bmatrix}{\bm{r}}_{l}^{+}\\ {\bm{r}}_{l}^{-}\end{bmatrix}\left\langle\left(y-\left(\frac{u}{\sqrt{2}} \right)^{L}{\bm{r}}^{\top}{\bm{x}}\right){\bm{x}}^{\top}\right\rangle_{{ \mathbb{S}}^{-}}{\bm{r}}\begin{bmatrix}{\bm{0}}&{{\bm{r}}_{l-1}^{-}}^{\top} \end{bmatrix}$ $\displaystyle=\left(\frac{u}{\sqrt{2}}\right)^{L-1}\begin{bmatrix}{\bm{r}}_{l} ^{+}{{\bm{r}}_{l-1}^{+}}^{\top}&{\bm{0}}\\ {\bm{0}}&{\bm{0}}\end{bmatrix}\left({\bm{\beta}}^{\top}-\left(\frac{u}{\sqrt{2 }}\right)^{L}{\bm{r}}^{\top}{\bm{\Sigma}}\right){\bm{r}}$ $\displaystyle+\left(\frac{u}{\sqrt{2}}\right)^{L-1}\begin{bmatrix}{\bm{0}}&{ \bm{0}}\\ {\bm{0}}&{\bm{r}}_{l}^{-}{{\bm{r}}_{l-1}^{-}}^{\top}\end{bmatrix}\left({\bm{ \beta}}^{\top}-\left(\frac{u}{\sqrt{2}}\right)^{L}{\bm{r}}^{\top}{\bm{\Sigma}} \right){\bm{r}}$ $\displaystyle=\frac{u^{L-1}}{(\sqrt{2})^{L}}\begin{bmatrix}\sqrt{2}{\bm{r}}_{l }^{+}{{\bm{r}}_{l-1}^{+}}^{\top}&{\bm{0}}\\ {\bm{0}}&\sqrt{2}{\bm{r}}_{l}^{-}{{\bm{r}}_{l-1}^{-}}^{\top}\end{bmatrix}\left ({\bm{\beta}}^{\top}-\left(\frac{u}{\sqrt{2}}\right)^{L}{\bm{r}}^{\top}{\bm{ \Sigma}}\right){\bm{r}}.$ (44) $$

For the last layer,

$$ $\displaystyle\tau\dot{\bm{W}}_{L}$ $\displaystyle=\left\langle(y-f({\bm{x}}))\sigma({\bm{h}}_{L-1})^{\top}\right\rangle$ $\displaystyle=\frac{u^{L-1}}{(\sqrt{2})^{L}}\left\langle\left(y-\left(\frac{u} {\sqrt{2}}\right)^{L}{\bm{r}}^{\top}{\bm{x}}\right){\bm{x}}^{\top}\right \rangle_{{\mathbb{S}}^{+}}{\bm{r}}\begin{bmatrix}{{\bm{r}}_{L-1}^{+}}^{\top}&{ \bm{0}}\end{bmatrix}$ $\displaystyle+\frac{u^{L-1}}{(\sqrt{2})^{L}}\left\langle\left(y-\left(\frac{u} {\sqrt{2}}\right)^{L}{\bm{r}}^{\top}{\bm{x}}\right){\bm{x}}^{\top}\right \rangle_{{\mathbb{S}}^{-}}{\bm{r}}\begin{bmatrix}{\bm{0}}&{{\bm{r}}_{L-1}^{-}} ^{\top}\end{bmatrix}$ $\displaystyle=\frac{u^{L-1}}{(\sqrt{2})^{L}}\left({\bm{\beta}}^{\top}-\left( \frac{u}{\sqrt{2}}\right)^{L}{\bm{r}}^{\top}{\bm{\Sigma}}\right){\bm{r}}{\bm{r }}_{L-1}^{\top}.$ (45) $$

Sections F.2, F.2 and F.2 can be re-written as Equation 42, which is easy to verify by substituting in the low-rank weights defined in Equation 40. The dynamics of a deep ReLU network given in Equation 42 and the dynamics of a deep linear network given in Equation 12 are the same except for constant coefficients.

We now prove that the low-rank weights retain low-rank once formed. We substitute the low-rank weights defined in Equation 40 into the left-hand side of Sections F.2, F.2 and F.2 and get

$$ $\displaystyle\tau\frac{d}{dt}u{\bm{r}}_{1}{\bm{r}}^{\top}$ $\displaystyle=\frac{u^{L-1}}{(\sqrt{2})^{L}}{\bm{r}}_{1}\left({\bm{\beta}}^{ \top}-\left(\frac{u}{\sqrt{2}}\right)^{L}{\bm{r}}^{\top}{\bm{\Sigma}}\right),$ $\displaystyle\tau\frac{d}{dt}u\begin{bmatrix}\sqrt{2}{\bm{r}}_{l}^{+}{{\bm{r}} _{l-1}^{+}}^{\top}&{\bm{0}}\\ {\bm{0}}&\sqrt{2}{\bm{r}}_{l}^{-}{{\bm{r}}_{l-1}^{-}}^{\top}\end{bmatrix}$ $\displaystyle=\frac{u^{L-1}}{(\sqrt{2})^{L}}\begin{bmatrix}\sqrt{2}{\bm{r}}_{l }^{+}{{\bm{r}}_{l-1}^{+}}^{\top}&{\bm{0}}\\ {\bm{0}}&\sqrt{2}{\bm{r}}_{l}^{-}{{\bm{r}}_{l-1}^{-}}^{\top}\end{bmatrix}\left ({\bm{\beta}}^{\top}-\left(\frac{u}{\sqrt{2}}\right)^{L}{\bm{r}}^{\top}{\bm{ \Sigma}}\right){\bm{r}},$ $\displaystyle\tau\frac{d}{dt}u{\bm{r}}_{L-1}^{\top}$ $\displaystyle=\frac{u^{L-1}}{(\sqrt{2})^{L}}\left({\bm{\beta}}^{\top}-\left( \frac{u}{\sqrt{2}}\right)^{L}{\bm{r}}^{\top}{\bm{\Sigma}}\right){\bm{r}}{\bm{r }}_{L-1}^{\top}.$ $$

By cancelling out the nonzero common terms on both sides, we reduce the dynamics to two differential equations. The first one is about the norm of a layer $u$. The second one is about the rank-one direction in the first layer $u{\bm{r}}$.

$$ $\displaystyle\tau\frac{d}{dt}u$ $\displaystyle=\frac{u^{L-1}}{(\sqrt{2})^{L}}\left({\bm{\beta}}^{\top}-\left( \frac{u}{\sqrt{2}}\right)^{L}{\bm{r}}^{\top}{\bm{\Sigma}}\right){\bm{r}},$ $\displaystyle\tau\frac{d}{dt}u{\bm{r}}^{\top}$ $\displaystyle=\frac{u^{L-1}}{(\sqrt{2})^{L}}\left({\bm{\beta}}^{\top}-\left( \frac{u}{\sqrt{2}}\right)^{L}{\bm{r}}^{\top}{\bm{\Sigma}}\right).$ $$

After the weights have formed the low-rank structure specified in Equation 40, the norm of each layer $u$ and the rank-one direction of the first layer ${\bm{r}}$ evolve while ${\bm{r}}_{1},{\bm{r}}_{2},\cdots,{\bm{r}}_{L-1}$ stay fixed. Hence, under Equation 40 on the weights at time $t=0$, we have that $\forall\,t\geq 0$, Equation 40 retains valid.

## Appendix G Implementation Details

All networks are initialized with small random weights. Specifically, the initial weights in the $l$-th layer are sampled i.i.d. from a normal distribution $\mathcal{N}(0,\gamma^{2}/N_{l})$ where $N_{l}$ is the number of weights in the $l$-th layer. The initialization scale $\gamma$ is specified below.

Figure 1.
The networks have width 500. The initialization scale is $\gamma=10^{-8}$. The learning rate is $0.004$. The input is 20-dimensional, ${\bm{x}}\in{\mathbb{R}}^{20}$. We sample 1000 i.i.d. vectors ${\bm{x}}_{n}\sim\mathcal{N}({\bm{0}},{\bm{I}})$ and include both ${\bm{x}}_{n}$ and $-{\bm{x}}_{n}$ in the dataset, resulting in 2000 data points. The output is generated as $y={\bm{w}}^{\top}{\bm{x}}+\sin\left(4{\bm{w}}^{\top}{\bm{x}}\right)$ where elements of ${\bm{w}}$ are randomly sampled from a uniform distribution $\mathcal{U}[-0.5,0.5]$. This dataset satisfy \conditionrefass:sym-data since the empirical input distribution is even and the output is generated by an odd function.

Figure 2.
The dataset contains six data points $[1,1],[-1,-1],[1,-1],[-1,1],[-1,0],[1,0.15]$. The network width is 100. The initialization scale is $\gamma=10^{-3}$. The learning rate is $0.025$.

Figure 3.
The networks have width 100. The initialization scale is $\gamma=10^{-2}$. The learning rate is $0.1$. The networks are trained 20000 epochs. The dataset is generated in the same way as Figure 1 except that the output is generated as $y={\bm{w}}^{\top}{\bm{x}}$.

## Peer Reviews

confidence: 4
contribution: 3
initial_rating: 6
presentation: 4
questions: Is there any possibility of deriving the empirical results in Section 5 analytically? In terms of results, this is possibly the most interesting part of the paper. What are the main difficulties in doing so?

It would also be interesting to somehow quantify the observed lack of robustness when a two-layer bias-free network is trained on a dataset that nearly satisfies Condition 3. Although, once again, I appreciate this may be a very challenging task.
soundness: 4
strengths: The paper is predominantly theoretical and full proofs are provided. The experimental parts complement the paper well and illustrate the theoretical findings.

The presentation is very good and polished and the main claims in the paper are clearly presented.

Understanding the expressiveness and training dynamics of different network architectures is important. The impact of removing bias from the architecture is also an interesting topic to study, in particular, as the authors point out, because in analytical studies of networks, bias terms are sometimes omitted for simplicity. The results on expressiveness of bias-free networks are mostly relatively simple observations. Understanding the training dynamics is much more involved.

Formally studying training dynamics is important, interesting, and challenging. This paper makes some welcome contributions. I found Section 5 as well as the discussion on "perturbed symmetric datasets" particularly intriguing.
summary: The paper studies what functions bias-free ReLU and leaky ReLU networks can represent and what the training dynamics are. A difference between two-layer networks and deeper networks is established. Specifically, it is observed that such bias-free networks that are limited to two layers cannot express any odd function except linear ones. However, the exists non-linear odd functions that can be expressed if the network has at least three layers. It is also established that under certain assumptions on the training data, the training dynamics of bias-free two-layer (leaky) ReLU networks is essentially the same as that of linear networks.
weaknesses: The main limitation of the results on training dynamics is that the results are limited to the case that the target model is odd (in addition to some more mild assumptions). Specifically, it is shown that in this case, two-layer bias-free (leaky) ReLU networks essentially behave like a linear network. There is evidence that even slight violations of this property of the target model, make the network behave in a non-linear way in later phases of training. I appreciate that it is challenging, but deriving training dynamics for more different types of datasets would of course benefit the work.

In the writeup, I think it would be helpful to reemphasize the core assumption made on the target model more explicitly in places where the results are summarized or discussed. For example, in Section 6, in the sentence "Theorem 7 shows that under symmetry conditions on the dataset, two-layer bias-free (leaky) ReLU networks have the same time evolution as a linear network (modulo scale factors)", the phrase "symmetry conditions" does a lot of heavy lifting and it may be helpful to be more explicit about what Condition 3 says.

The authors could clarify that Assumption 5 is only for the initialization.

---

confidence: 3
contribution: 3
initial_rating: 6
presentation: 3
questions: - The main result on the dynamics of bias-free networks (Theorem 7) is shown for infinite data (training on the distribution) and with gradient flow. How would these results change for finite data and/or training with GD/SGD?
soundness: 3
strengths: The paper gives novel insights on both expressivity and optimization of bias-free networks. As these networks have been studied often in prior theoretical works, discussing their limitations sheds new light on the conclusions from past theoretical works. Additionally, while ReLU networks often are trained with bias in practice, in certain situations bias-free networks have been used in practice, and thus understanding their behavior and limitation is important. The insights on the dynamics of these networks, drawing the connection to linear networks which are much better understood theoretically, helps advance our theoretical understanding of the dynamics and solutions found by ReLU networks.
summary: The paper studies the bias-free ReLU and leaky-ReLU networks, both two-layer networks and deep ones. The authors show that bias-free two-layer ReLU and leaky ReLU networks have limited expressivity, and cannot express non-linear odd functions. Showing that deep bias-free ReLU networks can express non-linear odd functions, the paper establishes a separation between bias-free deep and shallow networks. Additionally, the authors analyze the dynamics of training bias-free shallow networks under some distributional assumptions, showing theoretically and experimentally that their dynamics follows the dynamics of linear networks. Additionally, the authors provide some insights on the dynamics of deep bias-free ReLU networks.
weaknesses: - Previous work by Basri et al. (cited by the authors) shows that two-layer bias free networks cannot express non-linear odd functions when the inputs are uniformly distributed. The authors claim that the result in the paper is stronger, but it's not clear to me that this is the case. My understanding is that the authors show: for any non-linear odd function $f$, for any bias-free (leaky) ReLU network $h$, there exists some input $x$ such that $f(x) \neq h(x)$. My understanding is that Basri et al. shows a stronger result: for $x$ sampled from the uniform distribution, $f(x) \neq h(x)$ (with high probability?). It is possible that I am misunderstanding either the Basri et al. result or the result shown in the paper, so I would appreciate it if the authors clarify this point. In any case, I believe that writing the result in the paper more formally with the right order of quantifiers will help clarify things.
- The fact that bias-free ReLU networks are very limited is already evident from the somewhat trivial (and previously observed) fact that bias-free ReLU networks can only express positively homogenous functions. While the results shown in the paper are indeed stronger, showing that the networks cannot express a larger family of functions, it is worth emphasizing that the fact that bias-free ReLU networks are very restricted is not a novel contribution of this work.
- The introduction of Assumption 5 feels a little bit without context and missing some details. Is this an assumption on the initialization? Throughout the network training? What is the vector $r$ - is this satisfied for some $r$? It would be helpful to write this more formally, and clarify these points.
- The bottom-line result/message of Section 5 is not clear. If the main point is stating a conjecture, it is worthwhile to state more precisely what the conjecture is, and how it is supported by the experiments.

---

confidence: 4
contribution: 2
initial_rating: 5
presentation: 3
questions: - I would appreciate if the authors could comment on my concerns re novelty and significance stated above.
- Line 438 states that the second layer weights $W_2$ are nonnegative. Why is this true?

Minor comments:
- It might be helpful to add a plot of the depth separation function in Section 3.2.
- line 1329 "sumed"
soundness: 3
strengths: - Prior theoretical work considers networks with no bias, and thus it is an interesting question to understand the expressivity and learning dynamics of such networks.
- The proofs appear to the best of my knowledge to be sound, and the paper is well-written and easy to follow.
summary: This paper compares the gradient descent dynamics of ReLU networks with no bias to linear networks. First, the authors show that two-layer bias-free networks have limited expressivity. Next, the main result (Theorem 7) is that for "symmetric datasets" (Condition 3) and under a specific initialization (Assumption 5), the gradient flow trajectories of a two-layer ReLU network and a linear network are the same, up to weight and time-rescaling. The authors also consider extensions to other data distributions (such as orthogonal or XOR), and ReLU networks with depth > 2.
weaknesses: - My main concern with the paper is that I find the contribution to be rather incremental, which limits the significance/impact of the work. For example, Theorem 7 requires both symmetry on the data and for the first layer to be initialized as rank 1 ($W_1 = W_2^Tr^T$). While the latter assumption is justified as a consequence of training from infinitesimal initialization, I still find these to be rather strong assumptions, and I do not think such equivalence between linear networks and ReLU networks holds beyond this limited case.
- I find that the currently paper does not have much additional novelty, compared to the prior work Lyu et al. (2021). Lyu et al. (2021) shows that for a two-layer ReLU network trained on symmetric data 1) starting from infinitesimal initialization, the weight $W_1$ becomes rank 1 and 2) as training continues, this rank 1 component converges in the direction of the max-margin linear classifier. This second stage is exactly the same as the dynamics of a linear neural network (Ji & Telgarsky, 2019; Soudry et al., 2018). While the current paper does consider a slightly more general target which is not necessarily linearly separable, to me it seems as that the linear separability assumption in Lyu et al. (2021) was so that they could show convergence to max-margin, and thus I find the generalization to be rather minor
- In the setting of section 4.2 (orthogonal or XOR data), the derivation in Appendix D relies on initializing the network so that the neurons $W_1$ are perfectly aligned with the directions of the data points. This also seems like a rather strong assumptions, and to me the important part of understanding these dynamics is showing that the neurons will align in the direction of the data points. Proving this for the setting of XOR data has been the goal of prior works [1, 2], and is quite challenging.

[1] Sgd finds then tunes features in two-layer neural networks with near-optimal sample complexity: A case study in the xor problem. Margalit Glasgow. ICLR 2024.
[2] Random Feature Amplification: Feature Learning and Generalization in Neural Networks. Spencer Frei, Niladri S. Chatterji, Peter L. Bartlett. JMLR 2024.

---

confidence: 4
contribution: 2
initial_rating: 5
presentation: 4
questions: In Appendix C.5, the fact that the equivalence with a linear map holds even with large-scale initialization is very interesting, and could be further investigated. Does this equivalence also hold for larger learning rates?
soundness: 4
strengths: The paper is very clearly written. It tackles the crucial question of understanding training dynamics of deep neural networks. I appreciate that the authors find settings simple enough for elementary analysis and exposition. An interesting and important contribution of the paper is to warn people wanting to study (bias-free) ReLU networks that their assumptions might make them inadvertently fall back to the linear case.
summary: This paper studies various cases where bias-free ReLU networks are equivalent to linear networks. This requires assumptions on the data (e.g., symmetry or linear target) and on the initialization (e.g., rank-one and balanced). These assumptions allow to show conservation laws, which imply that the network remains equivalent to a linear network throughout the dynamics.
weaknesses: My main concern regards the soundness and importance of the contribution. Most results rely on conservation laws, which show that, under a specific initialization and a particular family of data distributions, the network is equivalent to a (sum of independent) linear network throughout training. However, deviations from these conversation laws are not studied in a thorough manner, which would be crucial in order to substantiate the claim that “the bias terms in the network and the structures in the data play an essential role in learning nonlinear tasks with ReLU networks” (line 59). For instance, the results of Figure 2b strongly rely on a very small-scale initialization (and perhaps a small learning rate), and this is not clearly discussed. Furthermore, for several cases studied in the paper, preexisting works already gave similar results and additionally rigorously control some of the deviation terms to this ideal initialization scenario.

More precisely, the results of Section 4.1 are close to the ones of Lyu et al. While the current paper lifts the assumption of linear separability, it considers the ideal case of a rank-one and balanced initialization. On the contrary, in Lyu et al., the deviation terms from this perfect scenario are carefully controlled, showing that the network still converges to a (global-max-margin) linear solution. This makes the latter analysis more nuanced, challenging the assertion in the present paper that they “incorporate as special case” the latter (l. 48). The claim that "we are able to give exact time-course solutions to certain two-layer ReLU networks in closed form, which has never been done for nonlinear networks outside the lazy learning regime” is therefore misleading, because Lyu et al provide a richer, though not closed-form, description, since they control additional error terms.

The situation is similar in Section 4.2: the decoupled dynamics from Appendix D is a simplification from the study of Boursier et al., which does not assume that the weight matrices are aligned with the data at initialization, but rather control the deviation from alignment.

I encourage authors to:
- clarify that they study idealized cases both in terms of data and initialization, and that these idealized cases lead to conservation laws which entail equivalence with linear networks.
- study more thoroughly deviations from this scenario, both in terms of data assumption and initialization assumptions (what happens for a Gaussian initialization depending on scale? Learning rate?).

Minor remarks:
- A relevant reference for rank-one structure in deep linear networks for regression (to complement references of lines 400) is Marion and Chizat, Deep linear networks for regression are implicitly regularized towards flat minima, NeurIPS 2024. Also, the rank-one structure is only approximate for a non-vanishingly small initialization, whereas authors seem to indicate the contrary on line 400.
- A study of the rank of matrices in deep ReLU networks was done in Timor et al., Implicit Regularization Towards Rank Minimization in ReLU Networks, ALT 2023.

Meta-review: The authors provide a theoretical analysis of expressivity and training dynamics of ReLU networks with no bias, and in particular compare it against a linear network. The most novel result being Theorem 7, where under some conditions, the gradient flow trajectories of a two layer ReLU network is the same as a linear network up to symmetry. 

While no significant issues were raised, all the reviewers seem to be skeptical about (1) how useful Theorem 7 is under the restrictive conditions, and (2) the novelty of the rest of the results, which seem to be an incremental improvement over existing ones. This led to all the reviews being very borderline, despite all of them acknowledging the rebuttals. 

Given that I have quite a few submissions in my batch with borderline reviews, and that no reviewers are willing the champion the acceptance of this paper, I would recommend reject for this paper. 

However, I believe this is a close case. The authors have a well written set of results, where novelty is the main the criticism, which can be a great fit for other venues such as TMLR. If any improvements can be made in terms of technical conditions or overall conceptual understanding, this paper could also be a clearer accept.

Decision: Reject