Title: CROSS-ENTROPY LOSS LEADS TO POOR MARGINS

Abstract: Neural networks could misclassify inputs that are slightly different from their training data, which indicates a small margin between their decision boundaries and the training dataset. In this work, we study the binary classification of linearly separable datasets and show that linear classifiers could also have decision boundaries that lie close to their training dataset if cross-entropy loss is used for training. In particular, we show that if the features of the training dataset lie in a low-dimensional affine subspace and the cross-entropy loss is minimized by using a gradient method, the margin between the training points and the decision boundary could be much smaller than the optimal value. This result is contrary to the conclusions of recent related works such as (Soudry et al., 2018), and we identify the reason for this contradiction. In order to improve the margin, we introduce differential training, which is a training paradigm that uses a loss function defined on pairs of points from each class. We show that the decision boundary of a linear classifier trained with differential training indeed achieves the maximum margin. The results reveal the use of cross-entropy loss as one of the hidden culprits of adversarial examples and introduces a new direction to make neural networks robust against them.
We start with a simple binary classification problem. Given two points x ∈ R d and -y ∈ R d from two different classes, we can find a linear classifier by minimizing the cross-entropy loss function min w∈R d ,b∈R

1. INTRODUCTION:

Training neural networks is challenging and involves making several design choices. Among these are the architecture of the network, the training loss function, the optimization algorithm used for training, and their hyperparameters, such as the learning rate and the batch size. Most of these design choices influence the solution obtained by the training procedure and have been studied in detail (Kingma & Ba, 2014; Hardt et al., 2015; He et al., 2016; Wilson et al., 2017; Nar & Sastry, 2018; Smith et al., 2018) . Nevertheless, one choice has been mostly taken for granted when the network is trained for a classification task: the training loss function.

Cross-entropy loss function is almost the sole choice for classification tasks in practice. Its prevalent use is backed theoretically by its association with the minimization of the Kullback-Leibler divergence between the empirical distribution of a dataset and the confidence of the classifier for that dataset. Given the particular success of neural networks for classification tasks (Krizhevsky et al., 2012; Simonyan & Zisserman, 2014; He et al., 2016) , there seems to be little motivation to search for alternatives for this loss function, and most of the software developed for neural networks incorporates an efficient implementation for it, thereby facilitating its use.

Recently there has been a line of work analyzing the dynamics of training a linear classifier with the cross-entropy loss function (Soudry et al., 2018; Nacson et al., 2018a; b; Ji & Telgarsky, 2018) . They specified the decision boundary that the gradient descent algorithm yields on linearly separable datasets and claimed that this solution achieves the maximum margin.1 However, these claims were observed not to hold in the simple experiments we ran. For example, Figure 1 displays a case where the cross-entropy minimization for a linear classifier leads to a decision boundary which attains an extremely poor margin and is nearly orthogonal to the solution given by the hard-margin support vector machine (SVM).

We set out to understand this discrepancy between the claims of the previous works and our observations on the simple experiments. We can summarize our contributions as follows.

SVM decision boundary (largest margin):

Cross-entropy min. decision boundary (poor margin)

Figure 1 : Orange and blue points represent the data from two different classes in R 2 . Cross-entropy minimization for a linear classifier on the given training points leads to the decision boundary shown with the solid line, which attains a very poor margin and is almost orthogonal to the solution given by the SVM.

1. We analyze the minimization of the cross-entropy loss for a linear classifier by using only two training points, i.e., only one point from each of the two classes, and we show that the dynamics of the gradient descent algorithm could yield a poor decision boundary, which could be almost orthogonal to the boundary with the maximum margin.

2. We identify the source of discrepancy between our observations and the claims of the recent works as the misleading abbreviation of notation in the previous works. We clarify why the solution obtained with cross-entropy minimization is different from the SVM solution.

3. We show that for linearly separable datasets, if the features of the training points lie in an affine subspace, and if the cross-entropy loss is minimized by a gradient method with no regularization to train a linear classifier, the margin between the decision boundary of the classifier and the training points could be much smaller than the optimal value. We verify that when a neural network is trained with the cross-entropy loss to classify two classes from the CIFAR-10 dataset, the output of the penultimate layer of the network indeed produces points that lie on an affine subspace.

4. We show that if there is no explicit and effective regularization, the weights of the last layer of a neural network could grow to infinity during training with a gradient method. Even though this has been observed in recent works as well, we are the first to point out that this divergence drives the confidence of the neural network to 100% at almost every point in the input space if the network is trained for long. In other words, the confidence depends heavily on the training duration, and its exact value might be of little significance as long as it is above 50%.

5. We introduce differential training, which is a training paradigm that uses a loss function defined on pairs of points from each class -instead of only one point from any class. We show that the decision boundary of a linear classifier trained with differential training indeed produces the SVM solution with the maximum hard margin.

or equivalently, by solving min w∈R d+1

log(e -w x + 1) + log(e -w ỹ + 1) , log(1 + e -w x) + log(1 + e -w ỹ ) by using the continuous-time approximation to the gradient descent algorithm

d w dt = x δe -w x 1 + e -w x + ỹ δe -w ỹ

1 + e -w ỹ with the initialization w(0) = 0 and the learning rate δ, then

EQUATION

where σ x = x 2 , σ xy = x ỹ and σ y = ỹ 2 .

Note that first d coordinates of (2) represent the normal vector of the decision boundary obtained by minimizing the cross-entropy loss (1). This vector is different from x + y, which is the direction of the maximum-margin solution given by the SVM. In fact, the direction in (2) could be almost orthogonal to the SVM solution in certain cases, which implies that the margin between the points and the decision boundary could be much smaller than the optimal value. Corollary 1 describes a subset of these cases.

Corollary 1. Given two points x and -y in R d , let ψ denote the angle between the solution given by (2) and the solution given by the SVM, i.e., (x + y). If x y = 1, then

cos 2 ψ ≤ 4 2 + σy σx 1 -1 σx ,

where σ x = x 2 +1 and σ y = y 2 +1. Consequently, as x / y approaches 0 while maintaining the condition x y = 1, the angle ψ converges to π/2. Remark 1. Corollary 1 shows that if x and -y have disparate norms, the minimization of the crossentropy loss with gradient descent algorithm could lead to a direction which is almost orthogonal to the maximum-margin solution. It may seem like this problem could be avoided with preprocessing the data so as to normalize the data points. However, this approach will not be effective for neural networks: if we consider an L-layer neural network, w φ L-1 (x), and regard the first L -1 layers, φ L-1 (•), as a feature mapping, preprocessing a dataset {x i } i∈I will not produce a normalized set of features {φ L-1 (x i )} i∈I . Note that we could not normalize {φ L-1 (x i )} i∈I directly either, since the mapping φ L-1 (•) evolves during training. Remark 2. Theorem 1 shows that the norm of w keeps growing unboundedly as the training continues. The same behavior will be observed for larger datasets in the next sections as well. Since the "confidence" of the classifier for its prediction at a point x is given by max 1 e -w x-b + 1 , e -w x-b e -w x-b + 1 , this unbounded growth of w drives the confidence of the classifier to 100% at every point in the input space, except at the points on the decision boundary, if the algorithm is run for long. Given the lack of effective regularization for neural networks, a similar unbounded growth is expected to be observed in neural network training as well, which is mentioned in (Bartlett et al., 2017) . As a result, the confidence of a neural network might be highly correlated with the training duration, and whether a neural network gives 99% or 51% confidence for a prediction might be of little importance as long as it is above 50%. In other words, regarding this confidence value as a measure of similarity between an input and the training dataset from the most-likely class should be reconsidered.

3. DATA WITH LOW-DIMENSIONAL FEATURES ATTAIN POOR MARGIN:

In this section, we examine the binary classification of a linearly separable dataset by minimizing the cross-entropy loss function. Recently, this problem has also been studied in (Soudry et al., 2018; Nacson et al., 2018b; a; Ji & Telgarsky, 2018) . We restate an edited version of the main theorem of (Soudry et al., 2018) , followed by the reason of the edition.

Theorem 2 (Adapted from Theorem 3 of (Soudry et al., 2018) ). Given two sets of points {x i } i∈I and {-y j } j∈J that are linearly separable in R d , let xi and -ỹ j denote [x i 1] and [-y j 1] , respectively, for all i ∈ I, j ∈ J. Then the iterate of the gradient descent algorithm, w(t), on the cross-entropy loss function

min w∈R d+1 i∈I log(1 + e -w xi ) + j∈J log(1 + e -w ỹj ) (3)

with a sufficiently small step size will converge in direction:

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

where w is the solution to

EQUATION

The solution (4) given in Theorem 2 was referred in (Soudry et al., 2018) , and consequently in the other works, as the maximum-margin solution. However, due to the misleading absence of the bias term in the notation, this is incorrect. Given the linearly separable sets of points {x i } i∈I and {-y j } j∈J , the maximum-margin solution given by the SVM solves minimize

w,b w 2 2 subject to w, x i + b ≥ 1 ∀i ∈ I, w, -y j + b ≤ -1 ∀j ∈ J. (P1)

On the other hand, the solution given by Theorem 2 corresponds to minimize

w,b w 2 2 + b 2 subject to w, x i + b = w, xi ≥ 1 ∀i ∈ I, w, -y j + b = w, -ỹ j ≤ -1 ∀j ∈ J, (P2)

where we define w = [w b] , xi = [x i 1] and ỹj = [y j -1] for all i ∈ I, j ∈ J. Even though the sets of constraints for both problems are identical, their objective functions are different, and consequently, the solutions are different. As a result, the decision boundary obtained by crossentropy minimization does not necessarily attain the maximum hard margin. In fact, as the following theorem shows, its margin could be arbitrarily worse than the maximum margin. Theorem 3. Assume that the points {x i } i∈I and {-y j } j∈J are linearly separable and lie in an affine subspace; that is, there exist a set of orthonormal vectors {r k } k∈K and a set of scalars

{∆ k } k∈K such that r k , x i = r k , -y j = ∆ k ∀i ∈ I, ∀j ∈ J, ∀k ∈ K.

Let w, • + B = 0 denote the decision boundary obtained by minimizing the cross-entropy loss, i.e. the pair (w, B) solves

min w,b w 2 + b 2 s.t. w, x i + b ≥ 1, w, -y j + b ≤ -1 ∀i ∈ I, ∀j ∈ J.

Then the minimization of the cross-entropy loss (3) yields a margin smaller than or equal to

1 1 γ 2 + B 2 k∈K ∆ 2 k

where γ denotes the optimal hard margin given by the SVM solution.

Remark 3. Theorem 3 shows that if the training points lie in an affine subspace, the margin obtained by the cross-entropy minimization will be smaller than the optimal margin value. As the dimension of this affine subspace decreases, the cardinality of the set K increases and the term k∈K ∆ 2 k could become much larger than 1/γ 2 . Therefore, as the dimension of the subspace containing the training points gets smaller compared to the dimension of the input space, cross-entropy minimization with a gradient method becomes more likely to yield a poor margin. Note that this argument also holds for classifiers of the form w φ(x) with the fixed feature mapping φ(•).

The next theorem relaxes the condition of Theorem 3 and allows the training points to be near an affine subspace instead of being exactly on it. Note that the ability to compare the margin obtained by cross-entropy minimization with the optimal value is lost. Nevertheless, it highlights the fact that same set of points could be assigned a different margin by cross-entropy minimization if all of them are shifted away from the origin by the same amount in the same direction.

Theorem 4. Assume that the points {x i } i∈I and {-y j } j∈J in R d are linearly separable and there exist a set of orthonormal vectors {r k } k∈K and a set of scalars {∆ k } k∈K such that

r k , x i ≥ ∆ k , r k , -y j ≤ ∆ k ∀i ∈ I, ∀j ∈ J, ∀k ∈ K.

Let w, • + B = 0 denote the decision boundary obtained by minimizing the cross-entropy loss, i.e. the pair (w, B) solves

min w,b w 2 + b 2 s.t. w, x i + b ≥ 1, w, -y j + b ≤ -1 ∀i ∈ I, ∀j ∈ J.

Then the minimization of the cross-entropy loss (3) yields a margin smaller than or equal to

1 B 2 k∈K ∆ 2 k

Remark 4. Both Theorem 3 and Theorem 4 consider linearly separable datasets. If the dataset is not linearly separable, (Ji & Telgarsky, 2018) predicts that the normal vector of the decision boundary, w, will have two components, one of which converges to a finite vector and the other diverges.

The diverging component still has the potential to drive the decision boundary to a direction with a poor margin. In fact, the margin is expected to be small especially if the points intruding into the opposite class lie in the same subspace as the optimal normal vector for the decision boundary. In this work, we focus on the case of separable datasets as this case provides critical insight into the issues of state-of-the-art neural networks, given they can easily attain zero training error even on randomly generated datasets, which indicates the linear separability of the features obtained at their penultimate layers (Zhang et al., 2017) .

4. DIFFERENTIAL TRAINING IMPROVES MARGIN:

In previous sections, we saw that the cross-entropy minimization could lead to poor margins, and the main reason for this was the appearance of the bias term in the objective function of (P2). In order to remove the effect of the bias term, consider the SVM problem (P1) and note that this problem could be equivalently written as

minimize w w 2 2 subject to w, x i + y j ≥ 2 ∀i ∈ I, ∀j ∈ J (P3)

if we only care about the weight parameter w. This gives the hint that if we use the set of differences {x i + y j : i ∈ I, j ∈ J} instead of the individual sets {x i } i∈I and {-y j } j∈J , the bias term could be excluded from the problem. This was also noted in (Keerthi et al., 2000; Ishibashi et al., 2008) previously. Indeed, this approach allows obtaining the SVM solution with a loss function similar to the cross-entropy loss, as the following theorem shows.

Theorem 5. Given two sets of points {x i } i∈I and {-y j } j∈J that are linearly separable in R d , if we solve min

EQUATION

by using the gradient descent algorithm with a sufficiently small learning rate, the direction of w converges to the direction of maximum-margin solution, i.e.

EQUATION

where w SVM is the solution of (P3).

Proof. Apply Theorem 2 by replacing the sets {x i } i∈I and {-y j } j∈J with {x i + y j } i∈I,j∈J and the empty set, respectively. Then the minimization of the loss function ( 5) with the gradient descent algorithm leads to

lim t→∞ w w = w w where w satisfies w = arg min w w 2 such that w, x i + y j ≥ 1 ∀i ∈ I, ∀j ∈ J.

Since w SVM is the solution of (P3), we obtain w = 1 2 w SVM , and the claim of the theorem holds. Remark 5. Theorem 5 is stated for the gradient descent algorithm, but the identical statement could be made for the stochastic gradient method as well by invoking the main theorem of (Nacson et al., 2018) .

Minimization of the cost function (5) yields the weight parameter ŵ of the decision boundary. The bias parameter, b, could be chosen by plotting the histogram of the inner products { ŵ, x i } i∈I and { ŵ, -y j } j∈J and fixing a value for b such that

EQUATION

EQUATION

The largest hard margin is achieved by

EQUATION

However, by choosing a larger or smaller value for b, it is possible to make a tradeoff between the Type-I and Type-II errors.

The cost function (5) includes a loss defined on every pair of data points from the two classes. This cost function can be considered as the cross-entropy loss on a new dataset which contains |I| × |J| points. There are two aspects of this fact:

1. When standard loss functions are used for classification tasks, we need to oversample or undersample either of the classes if the training dataset contains different number of points from different classes. This problem does not arise when we use the cost function (5). 2. Number of pairs in the new dataset, |I| × |J|, will usually be much larger than the original dataset, which contains |I| + |J| points. Therefore, the minimization of (5) might appear more expensive than the minimization of the standard cross-entropy loss computationally. However, if the points in different classes are well separated and the stochastic gradient method is used to minimize (5), the algorithm achieves zero training error after using only a few pairs, which is formalized in Theorem 6. Further computation is needed only to improve the margin of the classifier. In addition, in our experiments to train a neural network to classify two classes from the CIFAR-10 dataset, only a few percent of |I| × |J| points were observed to be sufficient to reach a high accuracy on the training dataset. Theorem 6. Given two sets of points {x i } i∈I and {-y j } j∈J that are linearly separable in R d , assume the cost function ( 5) is minimized with the stochastic gradient method. Define R x = max{ x i -x i : i, i ∈ I}, R y = max{ y j -y j : j, j ∈ J} and let γ denote the hard margin that would be obtained with the SVM: 2γ = max u∈R d min i∈I,j∈J x i + y j , u/ u . If 2γ ≥ 5 max(R x , R y ), then the stochastic gradient algorithm produces a weight parameter, ŵ, only in one iteration which satisfies the inequalities (7a)-(7b) along with the bias, b, given by (8).

5. NUMERICAL EXPERIMENTS:

In this section, we present numerical experiments supporting our claims.

Differential training. In Figure 2 , we show the decision boundaries of two linear classifiers, where one of them is trained by minimizing the cross-entropy loss, and the other through differential training. Unlike the example shown in Figure 1 , here the data do not exactly lie in an affine subspace. In particular, one of the classes is composed of 10 samples from a normal distribution with mean (2, 12) and variance 25, and the other class is composed of 10 samples from a normal distribution with mean (40, 50) and variance 25. As can be seen from the figure, the cross-entropy minimization yields a margin that is smaller than differential training, even though when the training dataset is not low-dimensional, which is predicted by Theorem 4.

Differential training boundary:

Cross-entropy min. boundary Low-dimensionality. We empirically evaluated if the features obtained at the penultimate layer of a neural network indeed lie in a low-dimensional affine subspace. For this purpose, we trained a convolutional neural network architecture to classify horses and planes from the CIFAR-10 dataset (Krizhevsky & Hinton, 2009) . Figure 3 shows the cumulative variance explained for the features that feed into the soft-max layer as a function of the number of principle components used. We observe that the features, which are the outputs of the penultimate layer of the network, lie in a low-dimensional affine subspace, and this holds for a variety of training modalities for the network. This observation is relevant to Remark 3. The dimension of the subspace containing the training points is at most 20, which is much smaller than the dimension of the feature space, 84. Consequently, cross-entropy minimization with a gradient method is expected to yield a poor margin on these features.

6. DISCUSSION:

We compare our results with related works and discuss their implications for the following subjects.

Adversarial examples. State-of-the-art neural networks have been observed to misclassify inputs that are slightly different from their training data, which indicates a small margin between their decision boundaries and the training dataset (Szegedy et al., 2013; Goodfellow et al., 2015; Moosavi-Dezfooli et al., 2017; Fawzi et al., 2017) . Our results reveal that the combination of gradient methods, cross-entropy loss function and the low-dimensionality of the training dataset (at least in some domain) has a responsibility for this problem. Note that SVM with the radial basis function was shown to be robust against adversarial examples, and this was attributed to the high nonlinearity of the radial basis function in (Goodfellow et al., 2015) . Given that the SVM uses neither the cross entropy loss function nor the gradient descent algorithm for training, we argue that the robustness of SVM is no surprise -independent of its nonlinearity. Lastly, effectiveness of differential training for neural networks against adversarial examples is our ongoing work. Low-dimensionality of the training dataset. As stated in Remark 3, as the dimension of the affine subspace containing the training dataset gets very small compared to the dimension of the input space, the training algorithm will become more likely to yield a small margin for the classifier. This observation confirms the results of (Marzi et al., 2018) , which showed that if the set of training data is projected onto a low-dimensional subspace before feeding into a neural network, the performance of the network against adversarial examples is improved -since projecting the inputs onto a low-dimensional domain corresponds to decreasing the dimension of the input space. Even though this method is effective, it requires the knowledge of the domain in which the training points are low-dimensional. Because this knowledge will not always be available, finding alternative training algorithms and loss functions that are suited for low-dimensional data is still an important direction for future research.

Robust optimization. Using robust optimization techniques to train neural networks has been shown to be effective against adversarial examples (Madry et al., 2018; Athalye et al., 2018) . Note that these techniques could be considered as inflating the training points by a presumed amount and training the classifier with these inflated points. Consequently, as long as the cross-entropy loss is involved, the decision boundaries of the neural network will still be in the vicinity of the inflated points. Therefore, even though the classifier is robust against the disturbances of the presumed magnitude, the margin of the classifier could still be much smaller than what it could potentially be.

Differential training. We introduced differential training, which allows the feature mapping to remain trainable while ensuring a large margin between different classes of points. Therefore, this method combines the benefits of neural networks with those of support vector machines. Even though moving from 2N training points to N 2 seems prohibitive, it points out that a true classification should in fact be able to differentiate between the pairs that are hardest to differentiate, and this search will necessarily require an N 2 term. Some heuristic methods are likely to be effective, such as considering only a smaller subset of points closer to the boundary and updating this set of points as needed during training. If a neural network is trained with this procedure, the network will be forced to find features that are able to tell apart between the hardest pairs.

Nonseparable data. What happens when the training data is not linearly separable is an open direction for future work. However, as stated in Remark 4, this case is not expected to arise for the state-of-the-art networks, since they have been shown to achieve zero training error even on randomly generated datasets (Zhang et al., 2017) , which implies that the features represented by the output of their penultimate layer eventually become linearly separable. A PROOF OF THEOREM 1

Theorem 1 could be proved by using Theorem 2, but we provide an independent proof here. Gradient descent algorithm with learning rate δ on the cross-entropy loss (1) yields

d w dt = δ x e -w x

1 + e -w x + δ ỹ e -w ỹ 1 + e -w ỹ .

If w(0) = 0, then w(t) = p(t)x + q(t)ỹ for all t ≥ 0, where ṗ = δ e -p x 2 -q x,ỹ 1 + e -p x 2 -q x,ỹ , q = δ e -q ỹ 2 -p x,ỹ 1 + e -q ỹ 2 -p x,ỹ .

Define α = p x 2 + q x, ỹ , β = q ỹ 2 + p x, ỹ , a = δ x 2 = δσ x , c = δ ỹ 2 = δσ y , b = δ x, ỹ = δσ xy .

Then we can write

α = a e -α 1 + e -α + b e -β 1 + e -β , β = c e -β 1 + e -β + b e -α 1 + e -α .

Finally, define z = e α and v = e β so that

ż = z z + 1 a + b z + 1 v + 1 , v = v v + 1 c + b v + 1 z + 1 .

Without loss of generality, assume c ≥ a. Before we proceed, note that

d dt z v = c -b z + 1 z v a -b c -b - z + 1 v + 1 , d dt z + 1 v + 1 = z (v + 1) 2 v + 1 z + 1 a - v z b - v z z + 1 v + 1 c -b .

Let u and w denote z v and z+1 v+1 , respectively. Then,

u < 0 if w > a -b c -b u > 0 if w < a -b c -b ẇ < 0 if a w + b u < cw + b ẇ > 0 if a w + b u > cw + b Lemma 1. If b = 0, then lim t→∞ w(t) log(t) = 1 x x + 1 ỹ ỹ.

Proof. Note that Lemma 2. If b < 0, then there exists t 0 ∈ (0, ∞) such that

d(z + log(z)) dt = a =⇒ z(t) -z 0 + log(z(t)/z 0 ) = at, d(v + log(v)) dt = c =⇒ v(t) -v 0 + log(v(t)/v 0 ) = ct.

-b c ≤ z + 1 v + 1 ≤ a -b ∀t ≥ t 0 . Proof. Note that -b c ≤ a-b c-b ≤ a -b because b < 0. First assume z0+1 v0+1 ≥ a -b . Then, ż ≤ 0 and v = v v + 1 c + b v + 1 z + 1 ≥ v v + 1 c - b 2 a ≥ v 0 v 0 + 1 -b 2 a , which implies that z + 1 v + 1 ≤ (z 0 + 1) v 0 v 0 + 1 ac -b 2 a t + 1 -1

as long as z+1 v+1 ≥ a -b , and this can be satisfied only for a finite time. Now assume z0+1 v0+1 ≤ -b c . Then, v ≤ 0 and

ż = z z + 1 a + b z + 1 v + 1 ≥ z 0 z 0 + 1 ac -b 2 c , which implies z + 1 v + 1 ≥ z 0 z 0 + 1 ac -b 2 c t + 1 (v 0 + 1) -1

as long as z+1 v+1 ≤ -b c , and this can be satisfied only for a finite time as well.

Lemma 3. If b < 0, then

0 ≤ ż ≤ ac -b 2 c , 0 ≤ v ≤ ac -b 2 a ∀t ≥ t 0 ,

where t 0 is given by Lemma 2.

Proof.

ż = z z + 1 a + b z + 1 v + 1 ≤ z z + 1 ac -b 2 c ≤ ac -b 2 c v = v v + 1 c + b v + 1 z + 1 ≤ v v + 1 ac -b 2 a ≤ ac -b 2 a Lemma 4. If b < 0, then lim t→∞ log(z) log t = lim t→∞ log(v) log t = 1 Proof. From Lemma 3, v ≤ 0 ⇐⇒ c + b v + 1 z + 1 ≥ 0, and v ≤ ac -b 2 a t + v 0 .

Combining these two inequalities, we have

c + b a (ac -b 2 )t + v 0 + 1 1 z + 1 ≥ 0 ⇐⇒ z + 1 ≥ -b ac [(ac -b 2 )t + v 0 + 1]

As a result,

(-b)(ac -b 2 ) ac t + z 1 ≤ z(t) ≤ ac -b 2 c t + z 2 ∀t ≥ t 0 =⇒ lim t→∞ log(z) log(t) = 1.

By using Lemma 2,

log(-b/c) ≤ log(z + 1) -log(v + 1) ≤ log(-a/b) =⇒ lim t→∞ log(v) log(t) = 1. Lemma 5. If b < 0, then lim t→∞ w(t) log(t) = δ c -b ac -b 2 x + δ a -b ac -b 2 ỹ = σ y -σ xy σ x σ y -σ 2 xy x + σ x -σ xy σ x σ y -σ 2 xy ỹ Proof.

Solving the set of equations

1 = lim α log(t) = a δ lim p log(t) + b δ lim q log(t)

,

1 = lim β log(t) = c δ lim q log(t) + b δ lim p log(t)

,

we obtain lim t→∞ p log(t) = δ c -b ac -b 2 , lim t→∞ q log(t) = δ a -b ac -b 2 Lemma 6. If b > 0, then lim t→∞ z v = lim t→∞ z + 1 v + 1 = 0 if a ≤ b a-b c-b if a > b

Proof. Note that ż ≥ a/2 and v ≥ c/2; therefore,

lim t→∞ z + 1 v + 1 = lim t→∞ z v =⇒ lim t→∞ u = lim t→∞ w if either side exists. Remember that ẇ < 0 ⇐⇒ u < cw 2 + bw a + bw =: f (w).

We can compute f (w) = 2acw + bcw 2 + ab b 2 w 2 + 2abw + a 2 . The function f is strictly increasing and convex for w > 0. We have

f (0) = 0, f a -b c -b = a -b c -b .

Therefore, when b ≥ a, the only fixed point of f over [0, ∞) is the origin, and when a > b, 0 and (a -b)/(c -b) are the only fixed points of f over [0, ∞).

Figure 4 shows the curves over which u = 0 and ẇ = 0. Since lim t→∞ u = lim t→∞ w, the only points (u, w) can converge to are the fixed points of f . Remember that

u = c -b z + 1 u a -b c -b -w ,

so when a > b, the origin (0, 0) is unstable in the sense of Lyapunov, and (u, w) cannot converge to it. Otherwise, (0, 0) is the only fixed point, and it is stable. As a result,

lim t→∞ z v = lim t→∞ z + 1 v + 1 = 0 if a ≤ b a-b c-b if a > b w u u = f (w) a-b c-b a-b c-b Figure 4: Stationary points of function f . Lemma 7. If a > b > 0, then lim t→∞ w(t) log(t) = δ c -b ac -b 2 x + δ a -b ac -b 2 ỹ = σ y -σ xy σ x σ y -σ 2 xy x + σ x -σ xy σ x σ y -σ 2 xy ỹ.

Proof. From Lemma 6,

lim t→∞ z t = lim t→∞ ż = lim t→∞ z z + 1 a + b z + 1 v + 1 = a + b a -b c -b = ac -b 2 c -b , lim t→∞ v t = ac -b 2 a -b .

Consequently,

lim t→∞ log(z) log(t) = lim t→∞ log(v) log(t) = 1

which gives the same solution as Lemma 5:

lim t→∞ p log(t) = δ c -b ac -b 2 , lim t→∞ q log(t) = δ a -b ac -b 2 . Lemma 8. If b ≥ a, then lim t→∞ w(t) log(t) = 1 x x Proof. lim t→∞ z t = a, lim t→∞ log(z) log(t) = 1, lim t→∞ v t = lim t→∞ v = ∞ lim t→∞ log(v) log(t) = lim t→∞ v v t = lim t→∞ 1 v + 1 c + b v + 1 z + 1 t = lim t→∞ ct v + 1 + lim t→∞ bt z + 1 = b a lim t→∞ p log(t) = 1 x 2 , lim t→∞ q log(t) = 0 =⇒ lim t→∞ px + qy log(t) = 1 x 2 x

Proof of Theorem 1. Lemma 1, Lemma 5, Lemma 7 and Lemma 8 prove all cases of Theorem 1.

B PROOF OF COROLLARY 1:

Since x y = 1, we have σ xy = x ỹ = x y -1 = 0 < a. Then the normal vector of the decision boundary is proportional to 1 σx x + 1 σy y. For the angle between this vector and the solution of the SVM, we can write

cos ψ = 1 σx x + 1 σy y, x + y 1 σx x + 1 σy y x + y = 2 1 σx x + 1 σy y √ σ x + σ y .

We can obtain a lower bound for square of the denominator as

1 σ x x + 1 σ y y 2 (σ x + σ y ) ≥ 2 + σ y σ x - σ y σ 2 x + 1 σ x + 1 σ y + σ x σ y - σ x σ 2 y ≥ 2 + σ y σ x 1 - 1 σ x .

As a result, Then, we can write w as

w = u + k∈K B∆ k r k .

Remember, by definition, w SVM = arg min w 2 s.t. w, x i + y j ≥ 2 ∀i ∈ I, ∀j ∈ J.

Since the vector u also satisfies u, x i + y j = w, x i + y j ≥ 2 for all i ∈ I, j ∈ J, we have u ≥ w SVM = 1 γ . As a result, the margin obtained by minimizing the cross-entropy loss is

1 w = 1 u 2 + B∆ k r k 2 ≤ 1 1 γ 2 + B 2 ∆ 2 k .

D PROOF OF THEOREM 4:

If B < 0, we could consider the hyperplane w, • -B = 0 for the points {-x i } i∈I and {y j } j∈J , which would have the identical margin due to symmetry. Therefore, without loss of generality, assume B ≥ 0. As in the proof of Theorem 3, KKT conditions for the optimality of w and B requires w = where µ i ≥ 0 and ν j ≥ 0 for all i ∈ I, j ∈ J. Note that for each k ∈ K, w, r k = i∈I µ i x i , r k -j∈J ν j -y j , r k

= B∆ k + i∈I µ i ( x i , r k -∆ k ) - j∈J ν j ( -y j , r k -∆ k ) ≥ B∆ k .

Since {r k } k∈K is an orthonormal set of vectors,

w 2 ≥ k∈K w, r k 2 ≥ k∈K B 2 ∆ 2 k .

The result follows from the fact that w -1 is an upper bound on the margin.

E PROOF OF THEOREM 6:

In order to achieve zero training error in one iteration of the stochastic gradient algorithm, it is sufficient to have min i ∈I x i , x i + y j > max j ∈J -y j , x i + y j ∀i ∈ I, ∀j ∈ J, or equivalently, x i + y j , x i + y j > 0 ∀i, i ∈ I, ∀j, j ∈ J.

By definition of the margin, there exists a vector w SVM ∈ R d with unit norm which satisfies 2γ = min i∈I,j∈J x i + y j , w SVM .

Note that w SVM is orthogonal to the decision boundary given by the SVM. Then we can write every x i + y j as

x i + y j = 2γw SVM + δ x i + δ y j , where δ x i , δ y j ∈ R d and δ x i ≤ R x and δ y j ≤ R y . Then, condition (9) is satisfied if 2γw SVM + δ x i + δ y j , 2γw SVM + δ x i + δ y j > 0 ∀i, i ∈ I, ∀j, j ∈ J, or equivalently if 4γ 2 + 2γ w SVM , δ x i + δ y j + δ x i + δ y j + δ x i + δ y j , δ x i + δ y j > 0 ∀i, i ∈ I, ∀j, j ∈ J. (10)

If we choose γ > 5 2 max(R x , R y ), we have 4γ 2 -2γ(2R x + 2R y ) -(R x + R y ) 2 > 0, which guarantees (10) and completes the proof.

:

The term "maximum margin" is used for

norm throughout the paper.

Figures and Tables:

where x = [x 1] , -ỹ = [-y 1] and w = [w b] . Unless the two points x and -y are equal, the function (1) does not attain its minimum at a finite value of w. Consequently, if the gradient descent algorithm is used to minimize (1), the iterate at time k, w[k], diverges as k increases. The following theorem characterizes the growth rate of w[k] and its direction in the limit by using a continuous-time approximation to the gradient descent algorithm. Theorem 1. Given two points x ∈ R d and -y ∈ R d , let x and -ỹ denote [x 1] and [-y 1], respectively. Without loss of generality, assume x ≤ y . If the two points are in different classes and we minimize the cross-entropy loss min w∈R d+1

Figure 2: Classification boundaries obtained using differential training and cross-entropy minimization. The margin recovered by cross-entropy minimization is worse than differential training even when the training dataset is not low-dimensional.

Figure3: The activations feeding into the soft-max layer could be considered as the features for a linear classifier. Plot shows the cumulative variance explained for these features as a function of the number of principle components used. Almost all the variance in the features is captured by the first 20 principle components out of 84, which shows that the input to the soft-max layer resides predominantly in a low-dimensional subspace.

w SVM , • +b SVM = 0 denote the hyperplane obtained as the solution of SVM, i.e., (w SVM , b SVM ) is the solution to the problem min w,bw 2 s.t. w, x i + b ≥ 1, w, -y j + b ≤ -1 ∀i ∈ I, ∀j ∈ J.Assume that w = u + m k=1 α k r k , where u ∈ R d and u, r k = 0 for all k ∈ K. The Lagrangian of the problem (4) can be written as 1 -w, x i -b)+ j∈J ν j (1 -w, y j + b),where µ i ≥ 0 for all i ∈ I and ν j ≥ 0 for all j ∈ J. KKT conditions for the optimality of w and B requires that i , r k -j∈J ν j -y j , r k = i∈I ∆ k µ i -j∈J ∆ k ν j = B∆ k .

Christian Szegedy, Wojciech Zaremba, Ilya Sutskever, Joan Bruna, Dumitru Erhan, Ian J. Goodfellow, and Rob Fergus. Intriguing properties of neural networks. CoRR, abs/1312.6199, 2013. Ashia C Wilson, Rebecca Roelofs, Mitchell Stern, Nati Srebro, and Benjamin Recht. The marginal value of adaptive gradient methods in machine learning. In Advances in Neural Information Processing Systems, pp. 4148-4158, 2017.

Table content: <table><tr><td>Chiyuan Zhang, Samy Bengio, Moritz Hardt, Benjamin Recht, and Oriol Vinyals. Understanding</td></tr><tr><td>deep learning requires rethinking generalization. In International Conference on Learning Rep-</td></tr><tr><td>resentations, 2017.</td></tr></table>

Peer review (iclr2019):
 Due to the large variance in reviewer scores, I was asked to give this additional review. Background: [Soudry et al. 2018] showed that the iterates of gradient descent, when optimizing logistic regression on separable data, converge to the L2 max-margin (SVM) solution for homogeneous linear separators (without bias). These results were later extended to other models and optimization methods. This paper has two main results: 1) It clarifies that the results of [Soudry et al. 2018] do not apply to logistic regression when the linear separator has a bias term (“b”). This is because the homogenous max margin solution in the extended [x,1] space is not the same as non-homogeneous max margin solution in the original space: the first has a penalty on the size of the bias term, i.e. min_{w,b} ||w||^2 + b^2 s.t. y_n (w’x_n+b) >= 1 , while the latter does not: min_{w,b} ||w||^2 s.t. y_n(w’x_n+b) >= 1 2) It suggests using differential training to correct this issue. However, I do not believe these contributions are enough for a publication in ICLR. First, (2) is simply a combination of two known results, as mentioned by Reviewer 2. Second, though I commend the authors for pointing out (1), I do not feel this by itself warrants a publication, for the following reasons: a) It is very simple to explain (1) in only a few lines (as I did above). Therefore, it would be more informative just to write (1) as a comment on the original paper (the ICLR 2018 forum is still open), not as a completely new publication. For me, all the numerical demonstrations and examples of this simple issue did not add much. b) Regularizing the bias term usually does not make a significant difference to the sample complexity (see the end of section 15.1.1 in the textbook “Understanding Machine Learning: From Theory to Algorithms” by Shai Shalev Shwartz.). Furthermore, the main motivation behind [Soudry et al. 2018] was to explain implicit bias and generalization in deep networks, where there such max-margin results (which penalize all the parameters) could be used to derive generalization bounds (e.g., https://arxiv.org/abs/1810.05369). c) Lastly, the authors here say that “the solution obtained by cross-entropy minimization is different from the SVM solution”. This (as well as the title and abstract) may mislead the readers to think there is something wrong in the proofs of [Soudry et al. 2018] and later papers, and that logistic regression does not converge to the max-margin solution for homogeneous linear separators. However, the max-margin solution for homogeneous linear separators is also called the “max margin” or SVM solution (just for a different family). For example, see the previous paper on the topic [“Margin Maximizing Loss Functions”, Rosset et al. 2004] or section 15.1.1 in the textbook “Understanding Machine Learning: From Theory to Algorithms” by Shai Shalev Shwartz. As I see it, the only issue in [Soudry et al. 2018] is the sentence “A bias term could be added in the usual way, extending x_n by an additional ’1’ component." which is confusing since it cannot be applied directly to the SVM solution. The authors should aim to pinpoint this issue, and clarify their phrasing to avoid such confusions.