# Implicit Bias of Deep Learning in the Large Learning Rate Phase: A Data Separability Perspective
## Appendix A  
This appendix is dedicated to proving the key results of this paper, namely Proposition A1, Theorems A1 and A2, and Corollary A1 which describe the dynamics of gradient descent with logistic and exponential loss in different learning rate phase. For a linear predictor \(f=w^{T}x\), along with a loss \(\ell\in\{\ell_{\text{exp}},\ell_{\text{log}}\}\). Under Assumption 1, the empirical loss is \(\beta\)-smooth. Then the gradient descent with constant learning rate \(\eta<\frac{2}{\beta}\) never increases the risk, and empirical loss will converge to zero:  
\[\mathcal{L}(w_{t+1})-\mathcal{L}(w_{t})\leq 0,\quad\lim_{t\to\infty}\mathcal{L}(w _{t})=0,\ \ \text{with}\ \ \ \eta<\frac{2}{\beta}\]  
Under Assumption 2, the empirical loss is \(\beta\)-smooth and \(\alpha\)-strongly convex, where \(\alpha\leq\beta\). Then the gradient descent with a constant learning rate \(\eta<\frac{2}{\beta}\) never increases the risk, and empirical loss will converge to a global minimum. On the other hand, the gradient descent with a constant learning rate \(\eta>\frac{2}{\alpha}\) never decreases the risk, and empirical loss will explode or saturate:  
\[\mathcal{L}(w_{t+1})-\mathcal{L}(w_{t})\leq 0,\quad\lim_{t\to\infty} \mathcal{L}(w_{t})=G_{0},\ \ \text{with}\ \ \eta<\frac{2}{\beta}\]  
where \(G_{0}\) is the value of a global minimum while \(G_{1}=\infty\) for exploding situation or \(G_{0}<G_{1}<\infty\) when saturating. Proof. : We first prove that empirical loss \(\mathcal{L}(u)\) regrading data-scaled weight \(u_{i}\equiv w^{T}x_{i}y_{i}\) for the linearly separable dataset is smooth. The empirical loss can be written as \(\mathcal{L}=\sum_{i=1}^{n}\ell(u_{i})\), then the second derivatives of logistic and exponential loss are,  
\[\mathcal{L}^{\prime\prime}_{\exp}=\sum_{i=1}^{n}\ell^{\prime\prime}_{\exp}(u_{i })=\sum_{i=1}^{n}\exp^{\prime\prime}(-u_{i})=\sum_{i=1}^{n}\exp(-u_{i})\]  
\[\mathcal{L}^{\prime\prime}_{\log}=\sum_{i=1}^{n}\ell^{\prime\prime}_{\log}(u_ {i})=\sum_{i=1}^{n}\log^{\prime\prime}(1+\exp(-u_{i}))=\sum_{i=1}^{n}\frac{ \exp(-u_{i})}{(1+\exp(-u_{i}))^{2}}\]  
when \(w_{t}\) is limited, there will be a \(\beta\) such that \(\mathcal{L}^{\prime\prime}<\beta\). Furthermore, because there exists a separator \(w_{*}\) such that \(\forall i:w_{*}^{T}x_{i}y_{i}>0\), the second derivative of empirical loss can be arbitrarily close to zero. This implies that the empirical loss function is not strongly convex. Recalling a property of the \(\beta\)-smooth function \(f\)[60],  
\[f(y)\leq f(x)+(\
abla_{x}f)^{T}(y-x)+\frac{1}{2}\beta\|y-x\|^{2}\]  
Taking the gradient descent into consideration,  
\[\mathcal{L}(w_{t+1}) \leq\mathcal{L}(w_{t})+\big{(}\
abla_{w_{t}}\mathcal{L}(w_{t}) \big{)}^{T}(w_{t+1}-w_{t})+\frac{1}{2}\beta\|w_{t+1}-w_{t}\|^{2}\] \[=\mathcal{L}(w_{t})+\big{(}\
abla_{w_{t}}\mathcal{L}(w_{t}) \big{)}^{T}\big{(}-\eta\
abla_{w_{t}}\mathcal{L}(w_{t})\big{)}+\frac{1}{2} \beta\|-\eta\
abla_{w_{t}}\mathcal{L}\|^{2}\] \[=\mathcal{L}(w_{t})+\big{(}\
abla_{w_{t}}\mathcal{L}(w_{t}) \big{)}^{T}\big{(}-\eta\
abla_{w_{t}}\mathcal{L}(w_{t})\big{)}+\frac{1}{2} \beta\|-\eta\
abla_{w_{t}}\mathcal{L}\|^{2}\] \[=\mathcal{L}(w_{t})-\eta(1-\frac{\eta\beta}{2})\|\
abla_{w_{t}} \mathcal{L}\|^{2}\]  
when \(1-\frac{\eta\beta}{2}>0\), that is \(\eta<\frac{2}{\beta}\), we have,  
\[\mathcal{L}(w_{t+1})\leq\mathcal{L}(w_{t})-\eta(1-\frac{\eta\beta}{2})\| \
abla_{w_{t}}\mathcal{L}\|^{2}\leq\mathcal{L}(w_{t})\]  
We now prove that empirical loss will converge to zero with learning rate \(\eta<\frac{2}{\beta}\). We changing the form of the above inequality,  
\[\mathcal{L}(w_{t+1})-\mathcal{L}(w_{t})\leq 0,\quad\lim_{t\to\infty} \mathcal{L}(w_{t})=G_{0},\ \ \text{with}\ \ \eta<\frac{2}{\beta}\]0  
this implies,  
\[\mathcal{L}(w_{t+1})-\mathcal{L}(w_{t})\leq 0,\quad\lim_{t\to\infty} \mathcal{L}(w_{t})=G_{0},\ \ \text{with}\ \ \eta<\frac{2}{\beta}\]1  
therefore, we have \(\lim_{t\to\infty}\|\
abla_{w_{t}}\mathcal{L}(w_{t})\|=0\).