# Implicit Bias of Deep Learning in the Large Learning Rate Phase: A Data Separability Perspective
## 4 Theoretical Results  
### Convex Optimization  
It is known that the Hessian of the logistic and exponential loss with respect to the linear predictor is non-constant. Moreover, the estimated \(\beta\)-smooth convexity and \(\alpha\)-strongly convexity vary across different finite-bounded subspaces. As a result, the learning rate threshold in Proposition A1 is not detailed in terms of optimization trajectory. However, we can obtain more elaborate thresholds of the learning rate for a linear predictor by considering the degeneracy assumption:  
**Assumption 3**. : _The dataset contains two data points that have the same feature and opposite label, that is_  
\[(x_{1}=1,y_{1}=1)\ \ \text{and}\ \ (x_{2}=1,y_{2}=-1).\]  
We call this assumption the degeneracy assumption since the features from opposite label degenerate. Without loss of generality, we simplify the dimension of data and fix the position of the feature. Note that this assumption can be seen as a special case of non-separable data. Theoretical work has characterized general non-separable data [11], and we leave the analysis of this setting for the large learning rate to future work. Thanks to the symmetry of the risk function in space at the basis of degeneracy assumption, we can construct the exact dynamics of empirical risk with respect to the whole learning rate space. **Theorem 1**. : _For a linear predictor \(f=w^{T}x\) equipped with an exponential (logistic) loss under Assumption 3, there is a critical learning rate that separates the whole learning rate space into two (three) regions. The critical learning rate satisfies_  
\[\mathcal{L}^{\prime}(w_{0})=-\mathcal{L}^{\prime}(w_{0}-\eta_{\mathrm{critical }}\mathcal{L}^{\prime}(w_{0})),\]  
_where \(w_{0}\) is the initial weight. Moreover,_  
1. _For exponential loss, the gradient descent with a constant learning rate_ \(\eta<\eta_{\mathrm{critical}}\) _never increases loss, and the empirical loss converges to the global minimum. On the other hand, the gradient descent with learning rate_ \(\eta=\eta_{\mathrm{critical}}\) _oscillates. Finally, when the learning rate_ \(\eta>\eta_{\mathrm{critical}}\)_, the training process never decreases the loss and the empirical loss will explode to infinity:_ \[\mathcal{L}(w_{t+1})-\mathcal{L}(w_{t})<0, \lim_{t\to\infty}\mathcal{L}(w_{t})=1,\qquad with \eta<\eta_{\mathrm{critical}},\] \[\mathcal{L}(w_{t+1})-\mathcal{L}(w_{t})=0, \lim_{t\to\infty}\mathcal{L}(w_{t})=\mathcal{L}(w_{0}),\qquad with \eta=\eta_{\mathrm{critical}},\] \[\mathcal{L}(w_{t+1})-\mathcal{L}(w_{t})>0, \lim_{t\to\infty}\mathcal{L}(w_{t})=\infty,\qquad with \eta>\eta_{\mathrm{critical}}.\]
2. _For logistic loss, the critical learning rate satisfies the condition:_ \(\eta_{\mathrm{critical}}>8\)_. The gradient descent with a constant learning rate_ \(\eta<8\) _never increases the loss, and the loss converges to the global minimum. On the other hand, the loss along with a learning rate_ \(8\leq\eta<\eta_{\mathrm{critical}}\) _does not converge to the global minimum but oscillates. Finally, when the learning rate_ \(\eta>\eta_{\mathrm{critical}}\)_, gradient descent never decreases the loss, and the loss saturates:_ \[\mathcal{L}(w_{t+1})-\mathcal{L}(w_{t})<0, \lim_{t\to\infty}\mathcal{L}(w_{t})=\log(2),\qquad with \eta<8,\] \[\mathcal{L}(w_{t+1})-\mathcal{L}(w_{t})\leq 0, \lim_{t\to\infty}\mathcal{L}(w_{t})=\mathcal{L}(w_{*})<\mathcal{ L}(w_{0}),\qquad with 8\leq\eta<\eta_{\mathrm{critical}},\] \[\mathcal{L}(w_{t+1})-\mathcal{L}(w_{t})\geq 0, \lim_{t\to\infty}\mathcal{L}(w_{t})=\mathcal{L}(w_{*})\geq \mathcal{L}(w_{0}),\qquad with \eta\geq\eta_{\mathrm{critical}}.\] _where_ \(w_{*}\) _satisfies_ \(-w_{*}=w_{*}-\frac{\eta}{2}\frac{\sinh(w_{*})}{1+\cosh(w_{*})}\)_._  
**Remark 1**. : _The difference between the two losses is due to the monotonicity of the loss.