# Implicit Bias of Deep Learning in the Large Learning Rate Phase: A Data Separability Perspective
## 3 Background
### Separation Conditions of Dataset  
It is known that landscapes of cross-entropy loss on linearly separable and non-separable data are different. Thus, the separation condition plays a crucial role in understanding the dynamics of gradient descent in terms of the learning rate. To build towards this, we define the two classes of separation conditions and review existing results for loss landscapes of a linear predictor in terms of separability. **Assumption 1**. : _The dataset is linearly separable, i.e., there exists a separator \(w_{*}\) such that \(\forall i:w_{*}^{T}x_{i}y_{i}>0\)._  
**Assumption 2**. : _The dataset is non-separable, i.e., there is no separator \(w_{*}\) such that \(\forall i:w_{*}^{T}x_{i}y_{i}>0\)._  
**Linearly separable. ** Consider the data under Assumption 1, one can examine that the loss of a linear predictor, i.e., \(f(x)=w^{T}x\), is \(\beta\)-smooth convex with respect to \(w\), and the global minimum is at infinity. The implicit bias of gradient descent with a sufficient small learning rate (\(\eta<\frac{2}{\beta}\)) in this phase was studied by [8]. They showed that the predictor converges to the direction of the maximum margin (hard margin SVM) solution, which implies the gradient descent method itself will find a proper solution with an implicit regularization instead of picking up a random solver. If one increases the learning rate until it exceeds \begin{table}
\begin{tabular}{l l} \hline \hline
**Symbol** & **Definition** \\ \hline \(x\) & Input \\ \(y\) & Label \\ \(\eta\) & Learning rate \\ \(\ell(\cdot)\) & Loss function \\ \(\mathcal{L}\) & Empirical loss \\ \(w_{t}\) & Parameters of the model at time step \(t\) \\ \(\beta\) & \(\beta\)-smooth convexity \\ \(\alpha\) & \(\alpha\)-strongly convexity \\ \(\Theta_{\alpha\beta}\) & Neural Tangent Kernel \\ \hline \hline \end{tabular}
\end{table} 
Table 1: Key symbols and their definition. \(\eta<\frac{2}{\beta}\), then the result of converging to the maximum margin is not guaranteed, though loss can still converge to a global minimum. **Non-separable. ** Suppose we consider the data under Assumption 2, which is not linearly separable. The empirical risk of a linear predictor on these data are \(\alpha\)-strongly convex, and the global minimum is finite. In this case, given an appropriate small learning rate (\(\eta<\frac{2}{\beta}\)), the gradient descent converges towards the unique finite solution. When the learning rate is large enough, i.e., \(\eta>\frac{2}{\alpha}\), we can rigorously show that gradient descent updates with this large learning rate leading to risk exploding or saturating. We formally construct the relationship between loss surfaces and learning dynamics of gradient descent with respect to different learning rates on the two classes of data through the following proposition. **Proposition 1**. : _For a linear predictor \(f=w^{\mathrm{T}}x\), along with a loss \(\ell\in\{\ell_{\mathrm{exp}},\ell_{\mathrm{log}}\}\)._  
1. _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,\ \ \lim_{t\to\infty}\mathcal{L}(w_{t})=0,\ \ \ with\ \ \eta<\frac{2}{\beta}.\]
2. _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.