# Implicit Bias of Deep Learning in the Large Learning Rate Phase: A Data Separability Perspective
## 4 Theoretical Results
### Non-Convex Optimization  
To investigate the relationship between the dynamics of gradient descent and the learning rate for deep linear networks, we consider linear networks with one hidden layer, and the information propagation in these networks is governed by,  
\[f(x)=m^{-1/2}w^{(2)}w^{(1)}x, \tag{3}\]  
where \(m\) is the width, i.e., the number of neurons in the hidden layer, \(w^{(1)}\in\mathbb{R}^{m\times d}\) and \(w^{(2)}\in\mathbb{R}^{m}\) are the parameters of the model. Taking the exponential loss as an example, the gradient descent equations at training step \(t\) are,  
\[ \begin{split} w^{(1)}_{t+1}&=w^{(1)}_{t}-\frac{1}{ n}\frac{\eta}{m^{1/2}}(-e^{-y_{\alpha}f_{t}(x_{\alpha})})w^{(2)}_{t}x_{\alpha}y_{ \alpha},\\ w^{(2)}_{t+1}&=w^{(2)}_{t}-\frac{1}{n}\frac{\eta}{m ^{1/2}}(-e^{-y_{\alpha}f_{t}(x_{\alpha})})w^{(1)}_{t}x_{\alpha}y_{\alpha}, \end{split}  \tag{4}\]  
where we use the [PERSON] summation convention to simplify the expression and apply this convention in the following derivation. We introduce the neural tangent kernel, an essential element for the evolution of output function in Equation 8. The neural tangent kernel (NTK) originates from [1] and is formulated as,  
\[\Theta_{\alpha\beta}=\frac{1}{m}\sum_{p=1}^{p}\frac{\partial f(x_{\alpha})}{ \partial_{\theta_{p}}}\frac{\partial f(x_{\beta})}{\partial_{\theta_{p}}}. \tag{5}\]  
where \(P\) is the number of parameters. For a two-layer linear neural network, the NTK can be written as,  
\[\Theta_{\alpha\beta}=\frac{1}{mn}\big{(}(w^{(1)}x_{\alpha})(w^{(1)}x_{\beta}) +(w^{(2)})^{2}(x_{\alpha}x_{\beta})\big{)}. \tag{6}\]  
Here we use normalized NTK which is divided by the number of samples \(n\). Under the degeneracy Assumption 3, the loss function becomes \(\mathcal{L}=\cosh(m^{-1/2}w^{(2)}w^{(1)})\). Then Equation (4) reduces to  
\[ \begin{split} w^{(1)}_{t+1}&=w^{(1)}_{t}-\frac{\eta }{m^{1/2}}w^{(2)}_{t}\sinh(m^{-1/2}w^{(2)}_{t}w^{(1)}_{t}),\\ w^{(2)}_{t+1}&=w^{(2)}_{t}-\frac{\eta}{m^{1/2}}w^{ (1)}_{t}\sinh(m^{-1/2}w^{(2)}_{t}w^{(1)}_{t}).\end{split}  \tag{7}\]  
Figure 2: Showing the dependence of the dynamics of the training loss on the learning rate for linear predictors using both exponential and logistic loss functions. Examples 1 and 2 were used to test the performance of the linear predictors. The sub-graphs (**a**,**c**) show the experimental learning curves for separable data, consistent with the theoretical predictions. The critical learning rates were found to be \(\eta_{\text{critical}}=1.66843\) and \(\eta_{\text{critical}}=8.485\) for the exponential and logistic loss functions, respectively. Sub-graphs (**b**,**d**) show the dynamics of the training loss for non-separable data. The dynamics of training loss regarding the learning rate for non-separable data are similar to those of degenerate cases. Hence, the critical learning rates can be approximated by \(\eta_{\text{critical}}=0.895\) and \(\eta_{\text{critical}}=4.65\), respectively. The updates of output function \(f_{t}\) and the eigenvalue of NTK \(\lambda_{t}\), which are both scalars in our setting:  
\[ \begin{split} f_{t+1}&=f_{t}-\eta\lambda_{t}\tilde{f}_ {\text{exp}}+\frac{\eta^{2}}{m}f_{t}\tilde{f}_{t}^{2}\exp^{\prime},\\ \lambda_{t+1}&=\lambda_{t}-\frac{4\eta}{m}f_{t}\tilde{ f}_{\text{exp}}+\frac{\eta^{2}}{m}\lambda_{t}\tilde{f}_{t}^{2}\exp.\end{split}  \tag{8}\]  
where \(\tilde{f}_{\text{exp}}:=\text{sinh}(f_{t})\) while \(\tilde{f}_{t\text{log}}:=\frac{\text{sinh}(f_{t})}{1+\text{cosh}(f_{t})}\) for logistic loss. We have previously introduced the catapult phase where the loss grows at the beginning and then drops until it converges to a global minimum. In the following theorem, we prove the existence of the catapult phase on the degenerate data with exponential and logistic loss. Under appropriate initialization and Assumption 3, there exists a catapult phase for both the exponential and logistic loss.