Title: THE IMPLICIT BIAS OF GRADIENT DESCENT ON SEPA-RABLE DATA

Abstract: 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.

1. INTRODUCTION:

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 (Neyshabur et al., 2014; 2015; Zhang et al., 2017; Keskar et al., 2017; Neyshabur et al., 2017; 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 Kingma & Ba (2015) , changes this implicit bias.

2. MAIN RESULTS:

Consider a dataset {x n , y n } N n=1 , with binary labels y n ∈ {-1, 1}. We analyze learning by minimizing an empirical loss of the form

L (w) = N n=1 y n w x n . (2.1)

where w ∈ R d is the weight vector. A bias term could be added in the usual way, extending x n by an additional '1' component. To simplify notation, we assume that ∀n : y n = 1 -this is true without loss of generality, since we can always re-define y n x n as x n .

We are particularly interested in problems that are linearly separable, and the loss is smooth monotone strictly decreasing and non-negative: Assumption 1. The dataset is strictly linearly separable: ∃w * such that ∀n : w * x n > 0 .

Assumption 2. (u) is a positive, differentiable, monotonically decreasing to zero1 , (so ∀u : (u) > 0, (u) < 0 and lim u→∞ (u) = lim u→∞ (u) = 0) and a β-smooth function, i.e. its derivative is β-Lipshitz.

Many common loss functions, including the logistic, exp-loss, probit and sigmoidal losses, follow Assumption 2. Assumption 2 also straightforwardly implies that L (w) is a βσ 2 max (X )-smooth function, where the columns of X are all samples, and σ max (X ) is the maximal singular value of X.

Under these conditions, the infimum of the optimization problem is zero, but it is not attained at any finite w. Furthermore, no finite critical point w exist. We consider minimizing eq. 2.1 using Gradient Descent (GD) with a fixed learning rate η, i.e., with steps of the form:

w (t + 1) = w (t) -η∇L (w(t)) = w (t) -η N n=1 w (t) x n x n .

(2.2)

We do not require convexity. Under Assumptions 1 and 2, gradient descent converges to the global minimum (i.e. to zero loss) even without it: Lemma 1. Let w (t) be the iterates of gradient descent (eq. 2.

2) with η < 2β -1 σ -2 max (X ) and any starting point w(0). Under Assumptions 1 and 2, we have: (1) 

lim t→∞ L (w (t)) = 0, (2) lim t→∞ w (t) = ∞, and (3) ∀n : lim t→∞ w (t) x n = ∞.

Proof. Since the data is strictly linearly separable, ∃w * which linearly separates the data, and therefore

w * ∇L (w) = N n=1 w x n w * x n .

For any finite w, this sum cannot be equal to zero, as a sum of negative terms, since ∀n : w * x n > 0 and ∀u : (u) < 0. Therefore, there are no finite critical points w, for which ∇L (w) = 0. But gradient descent on a smooth loss with an appropriate stepsize is always guaranteed to converge to a critical point: ∇L (w (t)) → 0 (see, e.g. Lemma 5 in Appendix A.4, slightly adapted from Ganti (2015), Theorem 2). This necessarily implies that w (t) → ∞ while ∀n : w (t) x n > 0 for large enough t-since only then w (t) x n → 0. Therefore, L (w) → 0, so GD converges to the global minimum.

The main question we ask is: can we characterize the direction in which w(t) diverges? That is, does the limit lim t→∞ w (t) / w (t) always exists, and if so, what is it? In order to analyze this limit, we will need to make a further assumption on the tail of the loss function: Definition 2. A function f (u) has a "tight exponential tail", if there exist positive constants c, a, µ + , µ -, u + and u -such that

∀u > u + :f (u) ≤ c (1 + exp (-µ + u)) e -au ∀u > u -:f (u) ≥ c (1 -exp (-µ -u)) e -au .

Assumption 3. The negative loss derivative -(u) has a tight exponential tail (Definition 2).

For example, the exponential loss (u) = e -u and the commonly used logistic loss (u) = log (1 + e -u ) both follow this assumption with a = c = 1. We will assume a = c = 1 -without loss of generality, since these constants can be always absorbed by re-scaling x n and η.

We are now ready to state our main result: Theorem 3. For almost all datasets (i.e., except for a measure zero) which are strictly linearly separable (Assumption 1) and given a β-smooth decreasing loss function (Assumption 2) with an exponential tail (Assumption 3), gradient descent (as in eq. 2.2) with stepsize η < 2β -1 σ -2 max (X ) and any starting point w(0) will behave as:

EQUATION

where the residual ρ (t) is bounded and so

lim t→∞ w (t) w (t) = ŵ ŵ

where ŵ is the L 2 max margin vector (the solution to the hard margin SVM):

EQUATION

Since the theorem holds for almost all datasets, in particular, it holds with probability 1 if {x n } N n=1 are sampled from an absolutely continuous distribution.

Proof Sketch We first understand intuitively why an exponential tail of the loss entail asymptotic convergence to the max margin vector: Assume for simplicity that (u) = e -u exactly, and examine the asymptotic regime of gradient descent in which ∀n : w (t) x n → ∞, as is guaranteed by Lemma 1. If w (t) / w (t) converges to some limit w ∞ , then we can write w (t) = g (t) w ∞ + ρ (t) such that g (t) → ∞, ∀n :x n w ∞ > 0, and lim t→∞ ρ (t) /g (t) = 0. The gradient can then be written as:

-∇L (w) = N n=1 exp -w (t) x n x n = N n=1 exp -g (t) w ∞ x n exp -ρ (t) x n x n .

(2.5) As g(t) → ∞ and the exponents become more negative, only those samples with the largest (i.e., least negative) exponents will contribute to the gradient. These are precisely the samples with the smallest margin argmin n w ∞ x n , aka the "support vectors". The negative gradient (eq. 2.5) would then asymptotically become a non-negative linear combination of support vectors. The limit w ∞ will then be dominated by these gradients, since any initial conditions become negligible as w (t) → ∞ (from Lemma 1). Therefore, w ∞ will also be non-negative linear combination of support vectors, and so will its scaling ŵ = w ∞ / min n w ∞ x n . We therefore have:

ŵ = N n=1 α n x n ∀n α n ≥ 0 and ŵ x n = 1 OR α n = 0 and ŵ x n > 1 (2.6)

These are precisely the KKT condition for the SVM problem (eq. 2.4) and we can conclude that ŵ is indeed its solution and w ∞ is thus proportional to it.

To prove Theorem 3 rigorously, we need to show that w (t) / w (t) has a limit, that g (t) = log (t) and to bound the effect of various residual errors, such as gradients of non-support vectors and the fact that the loss is only approximately exponential. To do so, we substitute eq. 2.3 into the gradient descent dynamics (eq. 2.

2), with w ∞ = ŵ being the max margin vector and g(t) = log t.

We then show that the increment in the norm of ρ (t) is bounded by C 1 t -ν for some C 1 > 0 and ν > 1, which is a converging series. This happens because the increment in the max margin term, ŵ [log (t + 1) -log (t)] ≈ ŵt -1 , cancels out the dominant t -1 term in the gradient -∇L (w (t)) (eq. 2.5 with g (t) = log (t) and w ∞ x n = 1). A complete proof can be found in Appendix A.

More refined analysis: characterizing the residual We can furthermore characterize the asymptotic behavior of ρ (t). To do so, we need to refer to the KKT conditions (eq. 2.6) of the SVM problem (eq. 2.4) and the associated support vectors S = argmin n ŵ x n . The following refinement of Theorem 3 is also proved in Appendix A: Theorem 4. Under the conditions and notation of Theorem 3, if, in addition the support vectors span the data (i.e. rank (X S ) = rank (X) where the columns of X are all samples and of X S are the support vectors), then lim t→∞ ρ (t) = w, where w is unique, given w (0), and a solution to

∀n ∈ S : η exp -x n w = α n (2.7)

Note these equations are well-defined for almost all datasets, since (see Lemma 8 in Appendix F) then there are at most d support vectors, α n are unique and ∀n ∈ S : α n = 0.

3. IMPLICATIONS: RATES OF CONVERGENCE:

The solution in eq. 2.3 implies that w (t) / w (t) converges to the normalized max margin vector ŵ/ ŵ . Moreover, this convergence is very slow-logarithmic in the number of iterations. Specifically, in Appendix B we show that Theorem 3 implies the following tight rates of convergence:

The normalized weight vector converges to normalized max margin vector in L 2 norm

EQUATION

and in angle

EQUATION

and the margin converges as

1 ŵ - min n x n w (t) w (t) = O (1/log t) ; (3.3)

this slow convergence is in sharp contrast to the convergence of the (training) loss:

L (w (t)) = O t -1 . (3.4)

A simple construction (also in Appendix B) shows that the rates in the above equations are tight. Thus, the convergence of w(t) to the max-margin ŵ can be logarithmic in the loss itself, and we might need to wait until the loss is exponentially small in order to be close to the max-margin solution. This can help explain why continuing to optimize the training loss, even after the training error is zero and the training loss is extremely small, still improves generalization performance-our results suggests that the margin could still be improving significantly in this regime. t

(E) -3 -2 -1 0 1 2 3 -3 -2 -1 0 1 2 3 x 1 x 2 (A) GD GDMO

Figure 1 : Visualization of or main results on a synthetic dataset in which the L 2 max margin vector ŵ is precisely known. (A) The dataset (positive and negatives samples (y = ±1) are respectively denoted by + and • ), max margin separating hyperplane (black line), and the asymptotic solution of GD (dashed blue). For both GD and GD with momentum (GDMO), we show: (B) The norm of w (t), normalized so it would equal to 1 at the last iteration, to facilitate comparison. As expected (eq. 2.3), the norm increases logarithmically; (C) the training loss. As expected, it decreases as t -1 (eq. 3.4); and (D&E) the angle and margin gap of w (t) from ŵ (eqs. 3.2 and 3.3). As expected, these are logarithmically decreasing to zero. Implementation details: The dataset includes four support vectors: x 1 = (0.5, 1.5) , x 2 = (1.5, 0.5) with y 1 = y 2 = 1, and

x 3 = -x 1 , x 4 = -x 2 with y 3 = y 4 = -1 (the L 2 normalized max margin vector is then ŵ = (1, 1) / √ 2 with margin equal to √

2 ), and 12 other random datapoints (6 from each class), that are not on the margin. We used a learning rate η = 1/σ max (X), where σ max (X) is the maximal singular value of X, momentum γ = 0.9 for GDMO, and initialized at the origin.

A numerical illustration of the convergence is depicted in Figure 1 . As predicted by the theory, the norm w(t) grows logarithmically (note the semi-log scaling), and w(t) converges to the max-margin separator, but only logarithmically, while the loss itself decreases very rapidly (note the log-log scaling).

An important practical consequence of our theory, is that although the margin of w(t) keeps improving, and so we can expect the population (or test) misclassification error of w(t) to improve for many datasets, the same cannot be said about the expected population loss (or test loss)! At the limit, the direction of w(t) will converge toward the max margin predictor ŵ. Although ŵ has zero training error, it will not generally have zero misclassification error on the population, or on a test or a validation set. Since the norm of w(t) will increase, if we use the logistic loss or any other convex loss, the loss incurred on those misclassified points will also increase. More formally, consider the logistic loss (u) = log(1+e -u ) and define also the hinge-at-zero loss h(u) = max(0, -u). Since ŵ classifies all training points correctly, we have that on the training set N n=1 h( ŵ x n ) = 0. However, on the population we would expect some errors and so E[h( ŵ x)] > 0. Since w(t) ≈ ŵ log t and (αu) → αh(u) as α → ∞, we have:

E[ (w(t) x)] ≈ E[ ((log t) ŵ x)] ≈ (log t)E[h( ŵ x)] = Ω(log t).

(3.5) That is, the population loss increases logarithmically while the margin and the population misclassification error improve. Roughly speaking, the improvement in misclassification does not out-weight the increase in the loss of those points still misclassified.

The increase in the test loss is practically important because the loss on a validation set is frequently used to monitor progress and decide on stopping. Similar to the population loss, the validation loss L val (w (t)) = x∈V w (t) x calculated on an independent validation set V, will increase logarithmically with t (since we would not expect zero validation error), which might cause us to think we are over-fitting or otherwise encourage us to stop the optimization. But this increase does not actually represent the model getting worse, merely w(t) getting larger, and in fact the model might be getting better (with larger margin and possibly smaller error rate). 

4. EXTENSIONS:

We discuss several possible extensions of our results.

4.1. MULTI-CLASS CLASSIFICATION WITH CROSS-ENTROPY LOSS:

So far, we have discussed the problem of binary classification. For multi-class problems commonly encountered, we frequently learn a predictor w k for each class, and use the cross-entropy loss with a softmax output, which is a generalization of the logistic loss. What do the linear predictors w k (t) converge to if we minimize the cross-entropy loss by gradient descent on the predictors? In Appendix C we analyze this problem for separable data, and show that again, the predictors diverge to infinity and the loss converges to zero. Furthermore, we show that, generically, the loss converges to a logistic loss for transformed data, for which our theorems hold. This strongly suggests that gradient descent converges to a scaling of the K-class SVM solution:

arg min w1,...,w K K k=1 w k 2 s.t. ∀n, ∀k = y n : w yn x n ≥ w k x n + 1 (4.1)

We believe this can also be established rigorously and for generic exponential tailed multi-class loss.

4.2. OTHER OPTIMIZATION METHODS:

In this paper we examined the implicit bias of gradient descent. Different optimization algorithms exhibit different biases, and understanding these biases and how they differ is crucial to understanding and constructing learning methods attuned to the inductive biases we expect. Can we characterize the implicit bias and convergence rate in other optimization methods?

In Figure 1 we see that adding momentum does not qualitatively affects the bias induced by gradient descent. In Figure 4 in Appendix E we also repeat the experiment using stochastic gradient descent, and observe a similar bias. This is consistent with the fact that momentum, acceleration and stochasticity do not change the bias when using gradient descent to optimize an under determined least squares problems. It would be beneficial, though, to rigorously understand how much we can generalize our result to gradient descent variants, and how the convergence rates might change in these cases.

Employing adaptive methods, such as AdaGrad (Duchi et al., 2011) and ADAM (Kingma & Ba, 2015), does significantly affect the bias. In Figure 2 Wilson et al. discuss the limit of AdaGrad on lest square problems, but fall short of providing an actual characterization of the limit. This is not surprising, as the limit of AdaGrad on least square problems is fragile and depends on the choice of stepsize and other parameters, and thus complicated to characterize. We expect our methodology could be used to precisely characterize the implicit bias of such methods on logistic regression problems. The asymptotic nature of the analysis is appealing here, as it is insensitive to the initial point, initial conditioning matrix, and large initial steps.

More broadly, it would be interesting to study the behavior of mirror descent and natural gradient descent, and relate the bias they induce to the potential function or divergence underlying them. A reasonable conjecture, which we have not yet investigated, is that for any potential function Ψ(w), these methods converge to the maximum Ψ-margin solution arg min w Ψ(w)s.t.∀n : w x n ≥ 1.

Since mirror descent can be viewed as regularizing progress using Ψ(w), it is worth noting the results of Rosset et al. (2004b) : they considered the regularization path w λ = arg min L(w) + λ w p p for similar loss function as we do, and showed that lim λ→0 w λ / w λ p is proportional to the maximum L p margin solution. Rosset et al. do not consider the effect of the optimization algorithm, and instead add explicit regularization-here we are specifically interested in the bias implied by the algorithm not by adding (even infinitesimal) explicit regularization.

Our analysis also covers the exp-loss used in boosting, as its tail is similar to that of the logistic loss. However, boosting is a coordinate descent procedure, and not a gradient descent procedure. Indeed, the coordinate descent interpretation of AdaBoost shows that coordinate descent on the exp-loss for a linearly separable problem is related to finding the maximum 

4.3. DEEP NETWORKS:

In this paper, we only consider linear prediction. Naturally, it is desirable to generalize our results also to non-linear models and especially multi-layer neural networks.

Even without a formal extension and description of the precise bias, our results already shed light on how minimizing the cross-entropy loss with gradient descent can have a margin maximizing effect, how the margin might improve only logarithmically slow, and why it might continue improving even as the validation loss increases. These effects are demonstrated in Figure 3 and Table 1 which portray typical training of a convolutional neural network using unregularized gradient descent2 . As can be seen, the norm of the weight increases, but the validation error continues decreasing, albeit very slowly (as predicted by the theory), even after the training error is zero and the training loss is extremely small. We can now understand how even though the loss is already extremely small, some sort of margin might be gradually improving as we continue optimizing. We can also observe how the validation loss increases despite the validation error decreasing, as discussed in Section 3.

As an initial advance toward tackling deep network, we can point out that for two special cases, our results may be directly applied to multi-layered networks. First, our results may be applied exactly, It would be interesting to study the same problem with a logistic loss instead of squared loss. Beyond the practical relevance of the logistic loss, taking our approach has the advantage that because of its asymptotic nature, it does not depend on the initialization and step-size.

It thus might prove easier to analyze logistic regression on a matrix factorization instead of the least square problem, providing significant insight into the implicit biases of gradient descent on non-convex multi-layered optimization.

5. SUMMARY:

We characterized the implicit bias induced by gradient descent when minimizing smooth monotone loss functions with an exponential tail. This is the type of loss commonly being minimized in deep learning. We can now rigorously understand:

1. How gradient descent, without early stopping, induces implicit L 2 regularization and converges to the maximum L 2 margin solution, when minimizing the logistic loss, or exploss, or any other monotone decreasing loss with appropriate tail. In particular, the non-tail part does not affect the bias and so the logistic loss and the exp-loss, although very different on non-separable problems, behave the same for separable problems. The bias is also independent of the step-size used (as long as it is small enough to ensure convergence) and (unlike for least square problem) is also independent on the initialization. 2. This convergence is very slow. This explains why it is worthwhile continuing to optimize long after we have zero training error, and even when the loss itself is already extremely small. 3. We should not rely on slow decrease of the training loss, or on no decrease of the validation loss, to decide when to stop. We might improve the validation, and test, errors even when the validation loss increases and even when the decrease in the training loss is tiny.

Perhaps that gradient descent leads to a max L 2 margin solution is not a big surprise to those for whom the connection between L 2 regularization and gradient descent is natural. Nevertheless, we are not familiar with any prior study or mention of this fact, let alone a rigorous analysis and study of how this bias is exact and independent of the initial point and the step-size. Furthermore, we also analyze the rate at which this happens, leading to the novel observations discussed above. Perhaps even more importantly, we hope that our analysis can open the door to further analysis of different optimization methods or in different models, including deep networks, where implicit regularization is not well understood even for least square problems, or where we do not have such a natural guess as for gradient descent on linear problems. Analyzing gradient descent on logistic/cross-entropy loss is not only arguably more relevant than the least square loss, but might also be technically easier.

Additionally, this result also implies that we cannot have r (t) > 1 ∀t > t 3 , since then we arrive to the contradiction.

r (t) 2 -r (t 3 ) 2 = t-1 u=t3 r (u + 1) 2 -r (u) 2 ≤ - t-1 u=t3 C 3 u -1 → -∞,

Therefore, ∃t 4 > t 3 such that r (t 4 ) ≤ 1 . Recall also that r (t) is a decreasing function whenever r (t) ≥ 1 (eq. A.19). Also, recall that t 4 > t 0 , so from eq. A.17, we have that ∀t > t 4 ,| r (t + 1) -r (t) | < 0 . Combining these three facts we conclude that ∀t > t 4 : r (t) ≤ 1 + 0 . Since this reasoning holds ∀ 1 , 0 , this implies that r (t) → 0.

Lastly, we note that since P 2 r (t) is not updated during GD, we have that P 2 ( ww (0)) = 0. This sets w uniquely, together with eq. 2.7.

A.4 PROOF OF LEMMA 5

Lemma 5. Let L (w) be a β-smooth non-negative objective. If η < 2β -1 , then, for any w(0), with the GD sequence

w (t + 1) = w (t) -η∇L (w(t)) (A.8)

we have that

∞ u=0 ∇L (w (u)) 2 < ∞ and therefore lim t→∞ ∇L (w (t)) 2 = 0.

This proof is a slightly modified version of the proof of Theorem 2 in (Ganti, 2015) . Recall a well-known property of β-smooth functions:

f (x) -f (y) -∇f (y) (x -y) ≤ β 2 x -y 2 . (A.20)

From the β-smoothness of L (w)

EQUATION

Thus, we have L (w (t)) -L (w (t + 1))

η 1 -βη 2 ≥ ∇L (w (t)) 2 which implies t u=0 ∇L (w (u)) 2 ≤ t u=0 L (w (u)) -L (w (u + 1)) η 1 -βη 2 = L (w (0)) -L (w (t + 1)) η 1 -βη 2 .

The right hand side is upper bounded by a finite constant, since L (w (0)) < ∞ and 0 ≤ L (w (t + 1)). This implies

∞ u=0 ∇L (w (u)) 2 < ∞ ,

and therefore ∇L (w (t)) 2 → 0.

A.5 PROOF OF LEMMA 6:

Recall that we defined r (t) = w (t) -ŵ log t -w, with ŵ and w follow the conditions of the Theorems 3 and 4, i.e. ŵ is the L 2 max margin vector and (eq. 2.4), and eq. 2.7 holds ∀n ∈ S : η exp -x n w = α n .

Lemma 6. We have

∃C 1 , t 1 : ∀t > t 1 : (r (t + 1) -r (t)) r (t) ≤ C 1 t -min(θ,-1-1.5µ+,-1-0.5µ-) . (A.9) Additionally, ∀ 1 > 0 , ∃C 2 , t 2 , such that ∀t > t 2 , if P 1 r (t) ≥ 1 , (A.10)

then the following improved bound holds

(r (t + 1) -r (t)) r (t) ≤ -C 2 t -1 < 0 . (A.11)

From Lemma 1, ∀n : lim t→∞ w (t) x n = ∞. In addition, from assumption 3 the negative loss derivative -(u) has an exponential tail e -u (recall we assume a = c = 1 without loss of generality).

Combining both facts, we have positive constants µ -, µ + , t -and t + such that ∀n

∀t > t + : -w (t) x n ≤ 1 + exp -µ + w (t) x n exp -w (t) x n (A.21) ∀t > t -: -w (t) x n ≥ 1 -exp -µ -w (t) x n exp -w (t) x n (A.22)

Next, we examine the expression we wish to bound, recalling that r (t) = w (t) -ŵ log t -w:

(r (t + 1) -r (t)) r (t) = (-η∇L (w (t)) -ŵ [log (t + 1) -log (t)]) r (t) = -η N n=1 w (t) x n x n r (t) -ŵ r (t) log 1 + t -1 = ŵ r (t) t -1 -log 1 + t -1 -η n / ∈S w (t) x n x n r (t) (A.23) -η n∈S t -1 exp -w x n + w (t) x n x n r (t)

where in last line we used eqs. 2.6 and 2.7 to obtain

ŵ = n∈S α n x n = η n∈S exp -w x n x n .

We examine the three terms in eq. A.23. The first term can be upper bounded by

EQUATION

≤ max ŵ P 1 r (t) , 0 t -2

(2)

≤ ŵ 1 t -2 , if P 1 r (t) ≤ 1 o t -1 , if P 1 r (t) > 1 (A.24)

where in (1) we used that P 2 ŵ = P 2 X S α = 0 from eq. 2.6, and in (2) we used that ŵ r (t) = o (t), since

ŵ r (t) = ŵ w (0) -η t u=0 ∇L (w (u)) -ŵ log (t) -w ≤ ŵ (w (0) -w -ŵ log (t)) -ηt min 0≤u≤t ŵ ∇L (w (u)) = o (t)

where in the last line we used that ∇L (w (t)) = o (1), from Lemma 5.

Next, we upper bound the second term in eq. A.23, ∀t > t + :

-

EQUATION

≤ η n / ∈S: x n r(t)≥0

EQUATION

≤ η n / ∈S: x n r(t)≥0

EQUATION

≤ ηN 1 + t -θ exp -min

n w x n µ+ exp -min n w x n t -θ (5) ≤ 2ηN exp -min n w x n t -θ , ∀t > t + , (A.25)

where in (1) we used eq. A.21, in (2) we used w (t) = ŵ log t + w + r (t), in (3) we used xe -x ≤ 1 and x n r (t) ≥ 0, in (4) we used θ > 1, from eq. A.2 and in (5) we defined t + = max t + , exp min n w x n .

Lastly, we will aim to bound the sum in the third term in eq. A.23

-η n∈S t -1 exp -w x n + w (t) x n x n r (t) . (A.26)

We examine each term k in this sum, and divide into two cases, depending on the sign of x k r (t).

First, if x k r (t) ≥ 0, then term k in eq. A.26 can be upper bounded ∀t > t + , using eq. A.21, by ηt -1 exp -w x k 1 + t -µ+ exp -µ + w x k exp -x k r (t) -1 x k r (t) (A.27) We further divide into cases:

1. If x k r(t) ≤ C 0 t -0.5µ+ , then we can upper bound eq. A.27 with

η exp -(1 + µ + ) min n w x n C 0 t -1-1.5µ+ .

(A.28)

2. If x k r(t) > C 0 t -0.5µ+ , then we can find t + > t + to upper bound eq. A.27 ∀t > t + :

EQUATION

≤ ηt -1 e -w x k 1 + t -µ+ e -µ+ w

EQUATION

≤ 0, ∀t > t + (A.29)

where in (1) we used the fact that e -x ≤ 1 -x + x 2 for x ≥ 0 and in (2) we defined t + so that the previous expression is negative -this is possible since t -0.5µ+ decreases slower then t -µ+ . 3. If x k r(t) ≥ 2 , then we define t + > t + such that t + > exp min n w x n e 0.5 2 -1 -1/µ+ , and therefore ∀t > t + , we have 1 + t -µ+ exp -µ + w x n e -2 < e -0.5 2 . This implies that ∀t > t + we can upper bound eq. A.27 by -η exp -max n w x n 1 -e -0.5 2 2 t -1 .

(A.30)

where in (1) we used P 1 x n = x n ∀n ∈ S, in (2) we denoted by σ min (X S ), the minimal non-zero singular value of X S and used eq. A.10. Therefore, for some k,

x k r ≥ 2 |S| -1 σ 2 min (X S ) 2 1 .

In this case, we denote C 0 as the minimum between C 0 (eq. A.36) and η exp -max n w x n 1 -e -0.5 2 2 (eq. A.30). Then we find that eq. A.26 can be upper bounded by -C 0 t -1 + o t -1 , ∀t > t 0 , given eq. A.10. Substituting this result, together with eqs. A.24 and A.25 into eq. A.23, we obtain ∀t > t 0

(r (t + 1) -r (t)) r (t) ≤ -C 0 t -1 + o t -1 .

This implies that ∃C 2 < C 0 and ∃t 2 > t 0 such that eq. A.11 holds. This implies also that eq. A.9 holds for P 1 r (t) ≥ 1 . 2. Otherwise, if P 1 r (t) < 1 , we find that ∀t > t 0 , each term in eq. A.26 can be upper bounded by either zero (eqs. A.29 and A.35), or terms proportional to t -1-1.5µ+ (eq. A.28) or t -1-0.5µ-, (eq. A.31). Combining this together with eqs. A.24, A.25 into eq. A.23 we obtain (for some positive constants C 3 , C 4 , C 5 , and C 6 )

(r (t + 1) -r (t)) r (t) ≤ C 3 t -1-1.5µ+ + C 4 t -1-0.5µ-+ C 5 t -2 + C 6 t -θ .

Therefore, ∃t 1 > t 0 and C 1 such that eq. A.9 holds.

B CALCULATION OF CONVERGENCE RATES:

From Theorem 3, we can write w (t) = ŵ log t + ρ (t), where ρ (t) has bounded norm.

Calculation of normalized weight vector (eq. 3.1):

w (t) w (t) = ρ (t) + ŵ log t ρ (t) ρ (t) + ŵ ŵ log 2 t + 2ρ (t) ŵ log t = ρ (t) / log t + ŵ ŵ 1 + 2ρ (t) ŵ/ ŵ 2 log t + ρ (t) 2 / ŵ 2 log 2 t = 1 ŵ ρ (t) 1 log t + ŵ   1 - ρ (t) ŵ ŵ 2 log t +   3 4 2 ρ (t) ŵ ŵ 2 2 - ρ (t) 2 2 ŵ 2   1 log 2 t + O 1 log 3 t   (B.1) = ŵ ŵ + ρ (t) ŵ - ŵ ŵ ρ (t) ŵ ŵ 2 1 log t + O 1 log 2 t = ŵ ŵ + I - ŵ ŵ ŵ 2 ρ (t) ŵ 1 log t + O 1 log 2 t

where to obtain eq. B.1 we used 1

√ 1+x = 1 -1 2 x + 3 4 x 2 + O x 3

, and in the last line we used the fact that ρ (t) has a bounded norm. We use eq. B.1 to calculate the angle (eq. 3.2): 

EQUATION

D DEEP NETWORKS, IF ONLY A SINGLE LAYER IS OPTIMIZED:

We examine a deep neural network (DNN) with m = 1, . . . , L layers, piecewise linear activation functions f l and loss function following assumption 3, parameterized by weights matrices W l . Since f l are piecewise linear, we can write for almost every u: f l (u) = ∇f l (u) u (an element-wise product). Given an input sample x n , for each layer l the input u n,l and output v n,l are calculated sequentially in a "forward propagation"

u n,l =W l v n,l-1 ; v n,l = f l (u n,l ) (D.1)

initialized by v n,0 = x n . Then, given the DNN output u n,L and target y n ∈ {-1, 1} the loss (y n u n,L ) can be calculated.

During training, the gradients of the loss are calculated using the chain rule in a "back-propagation" We got the same update as in eq. 2.2. Thus, if xn,l does not change between iterations and becomes linearly separable so the training error can go to zero, we can apply Theorem 3. This can happen if we only optimize W l , and the activation units stop crossing their thresholds, after a sufficient number of iterations. Furthermore, in this solution α n = 0 if ŵ x n = 1, i.e., x n is a support vector (n ∈ S), and there are at most d such support vectors.

EQUATION

E AN EXPERIMENT WITH STOCHASTIC GRADIENT DESCENT:

Proof. For almost every set X, no more than d points x n can be on the same hyperplane. Therefore, since all support vectors must lie on the same hyperplane, there can be at most d support vectors, for almost every X.

Given the set of support vectors, S, the KKT conditions of eq. 2.6 entail that α n = 0 if n / ∈ S and 1 = X S ŵ = X S X S α S , (F.1)

where we denoted α S as α restricted to the support vector components. For almost every set X, since d ≥ |S|, X S X S ∈ R |S|×|S| is invertible. Therefore, α S has the unique solution

X S X S -1 1 = α S . (F.2)

This implies that ∀n ∈ S, α n is equal to a rational function in the components of X S , i.e., α n = p n (X S ) /q n (X S ), where p n and q n are polynomials in the components of X S . Therefore, if α n = 0, then p n (X S ) = 0, so the components of X S must be at a root of the polynomial p n . The roots of the polynomial p n have measure zero, unless ∀X S : p n (X S ) = 0. However, p n cannot be identically equal to zero, since, for example, if X S = I |S|×|S| , 0 |S|×(d-|S|) , then X S X S = I |S|×|S| , and so in this case ∀n ∈ S, α n = 1 = 0, from eq. F.2.

Therefore, for a given S, the event that "eq. F.1 has a solution with a zero component" has a zero measure. Moreover, the union of these events, for all possible S, also has zero measure, as a finite union of zero measures sets (there are only finitely many possible sets S ⊂ {1, . . . , N } ). This implies that, for almost all datasets X, α n = 0 only if n / ∈ S. Furthermore, for almost all datasets the solution α is unique: for each dataset, S is uniquely deteremined, and given S , the solution eq. F.1 is uniquely given by eq. F.2.

:

The requirement of nonnegativity and that the loss asymptotes to zero is purely for convenience. It is enough to require the loss is monotone decreasing and bounded from below. Any such loss asymptotes to some constant, and is thus equivalent to one that satisfies this assumption, up to a shift by that constant.

Code available here: https://github.com/paper-submissions/MaxMargin

This matrix can be written as P1 = XS X + S , where M + is the Moore-Penrose pseudoinverse of M.

Figures and Tables:

Figure2: Same as Fig.1, except we multiplied all x 2 values in the dastaset by 20, and also train using ADAM. The final weight vector produced after 2 • 10 6 epochs of optimization using ADAM (red dashed line) does not converge to L2 max margin solution (black line), in contrast to GD (blue dashed line), or GDMO.

we show the predictors obtained by ADAM and by gradient descent on a simple data set. Both methods converge to zero training error solutions. But although gradient descent converges to the L 2 max margin predictor, as predicted by our theory, ADAM does not. The implicit bias of adaptive method has been a recent topic of interest, with Hoffer et al. (2017) and Wilson et al. (2017) suggesting they lead to worse generalization.

Figure3: Training of a convolutional neural network on CIFAR10 using stochastic gradient descent with constant learning rate and momentum, softmax output and a cross entropy loss, where we achieve 8.3% final validation error. We observe that, approximately:(1)  The training loss decays as a t -1 , (2) the L 2 norm of last weight layer increases logarithmically, (3) after a while, the validation loss starts to increase, and (4) in contrast, the validation (classification) error slowly improves.

L 1 margin solution (Schapire et al., 1998; Rosset et al., 2004a; Shalev-Shwartz & Singer, 2010).

initialized by δ n,L = 1. Finally, the weights are updated with GD. The basic update (without weight sharing) isW l (t + 1) -W l (t) = -η N n=1 ∂ ∂W l (y n u n,L ) (D.3) = -η N n=1 y n (y n u n,L ) δ n,l v n,l-1 (D.4) n δ n,l W l v n,l-1 δ n,l v n,l-1 , (D.5)where in the last line we used∀l : u n,L = W L L-∇f l (u n,m ) W m x n = δ n,l W l v n,l-Denoting xn,l = y n δ n,l ⊗ v n,l-1 and w l = vec W l we obtain w l (t + 1) -w l (t) = -η N n=1 w l xn,l xn,l .

Figure 4: Same as Fig. 1, except stochastic gradient decent is used (with mini-batch of size 4), instead of GD.

Sample values from various epochs in the experiment depicted in Fig.3. as we show in Appendix D, if only a single weight layer is being optimized, and furthermore, after a sufficient number of iterations, the activation units stop switching and the training error goes to zero. Second, our results may also be applied directly to the last weight layer if the last hidden layer becomes fixed and linearly separable after a certain number of iterations. This can become true, either approximately, if the input to the last hidden layer is normalized (e.g., using batch norm), or exactly, if the last hidden layer is quantized(Hubara et al., 2016).4.4 MATRIX FACTORIZATIONWith multi-layered neural networks in mind,Gunasekar et al. (2017) recently embarked on a study of the implicit bias of under-determined matrix factorization problems, where we minimize the squared loss of linear observation of a matrix by gradient descent on its factorization. Since a matrix factorization can be viewed as a two-layer network with linear activations, this is perhaps the simplest deep model one can study in full, and can thus provide insight and direction to studying more complex neural networks. Gunasekar et al. conjectured, and provided theoretical and empirical evidence, that gradient descent on the factorization for an under-determined problem converges to the minimum nuclear norm solution, but only if the initialization is infinitesimally close to zero and the step-sizes are infinitesimally small. With finite step-sizes or finite initialization, Gunasekar et al. could not characterize the bias.

Table content: <table><tr><td colspan="3">Published as a conference paper at ICLR 2018</td><td/><td/><td/><td/></tr><tr><td>Epoch</td><td>50</td><td>100</td><td>200</td><td>400</td><td>2000</td><td>4000</td></tr><tr><td>L 2 norm</td><td>13.6</td><td>16.5</td><td>19.6</td><td>20.3</td><td>25.9</td><td>27.54</td></tr><tr><td>Train loss</td><td>0.1</td><td>0.03</td><td>0.02</td><td>0.002</td><td>10 -4</td><td>3 • 10 -5</td></tr><tr><td>Train error</td><td>4%</td><td>1.2%</td><td colspan="2">0.6% 0.07%</td><td>0%</td><td>0%</td></tr><tr><td>Validation loss</td><td>0.52</td><td>0.55</td><td>0.77</td><td>0.77</td><td>1.01</td><td>1.18</td></tr><tr><td colspan="6">Validation error 12.4% 10.4% 11.1% 9.1% 8.92%</td><td>8.9%</td></tr></table>

has a limit k n , then we define xn = (A yn -A kn ) x n , so eq. C.2 is transformed to the standard logistic regression loss Recalling that A k w = w k , we can re-write this as ∀n, ∀k = y n : w yn x n ≥ w k x n + 1

Table content: <table><tr><td/><td>N</td><td/><td/></tr><tr><td/><td/><td colspan="3">log 1 + exp -w (t) xn</td><td>,</td></tr><tr><td/><td>n=1</td><td/><td/></tr><tr><td colspan="3">to which our Theorems directly apply.</td><td/></tr><tr><td colspan="3">Therefore, w (t) / w (t) → ŵ where</td><td/></tr><tr><td colspan="4">ŵ = argmin</td></tr><tr><td/><td>K</td><td/><td/></tr><tr><td>arg min w1,...,w K</td><td>k=1</td><td>w k</td><td>2 s.t.</td></tr><tr><td/><td/><td/><td> 1 log 2 t</td><td>+ O</td><td>1 log 3 t</td></tr></table>

Peer review (iclr2018):
 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 result should be viewed in the context of recent attempts at trying to understand the generalization ability of neural networks, which have turned to trying to understand the implicit regularization bias that comes from the choice of optimizer. Since we do not even understand the regularization bias of optimizers for the simpler case of linear models, I consider the paper*s topic very interesting and timely. The overall discussion of the paper is well written, but on a more detailed level the paper gives an unpolished impression, and has many technical issues. Although I suspect that most (or even all) of these issues can be resolved, they interfere with checking the correctness of the results. Unfortunately, in its current state I therefore do not consider the paper ready for publication. Technical Issues: The statement of Lemma 5 has a trivial part and for the other part the proof is incorrect: Let x_u = ||nabla L(w(u))||^2. - Then the statement sum_{u=0}^t x_u < infinity is trivial, because it follows directly from ||nabla L(w(u))||^2 < infinity for all u. I would expect the intended statement to be sum_{u=0}^infinity x_u < infinity, which actually follows from the proof of the lemma. - The proof of the claim that t*x_t -> 0 is incorrect: sum_{u=0}^t x_u < infinity does not in itself imply that t*x_t -> 0, as claimed. For instance, we might have x_t = 1/i^2 when t=2^i for i = 1,2,... and x_t = 0 for all other t. Definition of tilde{w} in Theorem 4: - Why would tilde{w} be unique? In particular, if the support vectors do not span the space, because all data lie in the same lower-dimensional hyperplane, then this is not the case. - The KKT conditions do not rule out the case that .hat{w}^top x_n = 1, but alpha_n = 0 (i.e. a support vector that touches the margin, but does not exert force against it). Such n are then included in cal{S}, but lead to problems in (2.7), because they would require tilde{w}^top x_n = infinity, which is not possible. In the proof of Lemma 6, case 2. at the bottom of p.14: - After the first inequality, C_0^2 t^{-1.5 epsilon_+} should be C_0^2 t^{-epsilon_+} - After the second inequality the part between brackets is missing an additional term C_0^2 t^{-.epsilon_+}. - In addition, the label (1) should be on the previous inequality and it should be mentioned that e^{-x} <= 1-x+x^2 is applied for x >= 0 (otherwise it might be false). In the proof of Lemma 6, case 2 in the middle of p.15: - In the line of inequality (1) there is a t^{-epsilon_-} missing. In the next line there is a factor t^{-epsilon_-} too much. - In addition, the inequality e^x >= 1 + x holds for all x, so no need to mention that x > 0. In Lemma 1: - claim (3) should be lim_{t .to .infty} w(t)^.top x_n = infinity - In the proof: w(t)^top x_n > 0 only holds for large enough t. Remarks: p.4 The claim that "we can expect the population (or test) misclassification error of w(t) to improve" because "the margin of w(t) keeps improving" is worded a little too strongly, because it presumes that the maximum margin solution will always have the best generalization error. In the proof sketch (p.3): - Why does the fact that the limit is dominated by gradients that are a linear combination of support vectors imply that w_infinity will also be a non-negative linear combination of support vectors? - "converges to some limit". Mention that you call this limit w_infinity Minor Issues: In (2.4): add "for all n". p.10, footnote: Shouldn*t "P_1 = X_s X_s^+" be something like "P_1 = (X_s^top X_s)^+"? A.9: ell should be ell* The paper needs a round of copy editing. For instance: - top of p.4: "where tilde{w} A is the unique" - p.10: "the solution tilde{w} to TO eq. A.2" - p.10: "might BOT be unique" - p.10: "penrose-moorse pseudo inverse" -> "Moore-Penrose pseudoinverse" In the bibliography, Kingma and Ba is cited twice, with different years.