We show that gradient descent on an unregularized logistic regression
 problem, for almost all separable datasets, converges to the same direction as the max-margin solution. The result generalizes also to other monotone decreasing loss functions with an infimum at infinity, and we also discuss a multi-class generalizations to the cross entropy loss. Furthermore,
 we show this convergence is very slow, and only logarithmic in the
 convergence of the loss itself. This can help explain the benefit
 of continuing to optimize the logistic or cross-entropy loss even
 after the training error is zero and the training loss is extremely
 small, and, as we show, even if the validation loss increases. Our
 methodology can also aid in understanding implicit regularization
 in more complex models and with other optimization methods. It is becoming increasingly clear that implicit biases introduced by the optimization algorithm play a crucial role in deep learning and in the generalization ability of the learned models BID7 BID1 BID15 BID5 Wilson et al., 2017) . In particular, minimizing the training error, without any explicit regularization, over models with more parameters and more capacity then the number of training examples, often yields good generalization, despite the empirical optimization problem being highly underdetermined. That is, there are many global minima of the training objective, most of which will not generalize well, but the optimization algorithm (e.g. gradient descent) biases us toward a particular minimum that does generalize well. Unfortunately, we still do not have a good understanding of the biases introduced by different optimization algorithms in different situations.We do have a decent understanding of the implicit regularization introduced by early stopping of stochastic methods or, at an extreme, of one-pass (no repetition) stochastic optimization. However, as discussed above, in deep learning we often benefit from implicit bias even when optimizing the (unregularized) training error to convergence, using stochastic or batch methods. For loss functions with attainable, finite, minimizers, such as the squared loss, we have some understanding of this: In particular, when minimizing an underdetermined least squares problem using gradient descent starting from the origin, we know we will converge to the minimum Euclidean norm solution. But the logistic loss, and its generalization the cross-entropy loss which is often used in deep learning, do not admit a finite minimizer on separable problems. Instead, to drive the loss toward zero and thus minimize it, the predictor must diverge toward infinity. Do we still benefit from implicit regularization when minimizing the logistic loss on separable data? Clearly the norm of the predictor itself is not minimized, since it grows to infinity. However, for prediction, only the direction of the predictor, i.e. the normalized w(t)/ w(t) , is important. How does w(t)/ w(t) behave as t → ∞ when we minimize the logistic (or similar) loss using gradient descent on separable data, i.e., when it is possible to get zero misclassification error and thus drive the loss to zero?In this paper, we show that even without any explicit regularization, for all most all datasets (except a zero measure set), when minimizing linearly separable logistic regression problems using gradient descent, we have that w(t)/ w(t) converges to the L 2 maximum margin separator, i.e. to the solution of the hard margin SVM. This happens even though the norm w , nor the margin constraint, are in no way part of the objective nor explicitly introduced into optimization. More generally, we show the same behavior for generalized linear problems with any smooth, monotone strictly decreasing, lower bounded loss with an exponential tail. Furthermore , we characterize the rate of this convergence, and show that it is rather slow, with the distance to the max-margin predictor decreasing only as O(1/ log(t)). This explains why the predictor continues to improve even when the training loss is already extremely small. We emphasize and demonstrate that this bias is specific to gradient descent, and changing the optimization algorithm, e.g. using adaptive learning rate methods such as ADAM BID6 , changes this implicit bias.
The normalized solution of gradient descent on logistic regression (or a similarly decaying loss) slowly converges to the L2 max margin solution on separable data. The paper offers a formal proof that gradient descent on the logistic loss converges very slowly to the hard SVM solution in the case where the data are linearly separable.  This paper focuses on characterising the behaviour of log loss minimisation on linearly separable data, and shows that log-loss, minimised with gradient descent, leads to convergence to the max-margin solution.