CROSS-ENTROPY LOSS LEADS TO POOR MARGINS
Year: 2018

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.

heading: 1 INTRODUCTION
text: 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.
1The term “maximum margin” is used for `2 norm throughout the paper.
SVM decision boundary (largest margin)
Cross-entropy min. decision boundary
(poor margin)

heading: 2 CLASSIFICATION OF TWO POINTS MANIFESTS POOR MARGIN
text: We start with a simple binary classification problem. Given two points x ∈ Rd and −y ∈ Rd from two different classes, we can find a linear classifier by minimizing the cross-entropy loss function
min w∈Rd,b∈R
{ − log ( 1
e−w>x−b + 1
) − log ( ew >y−b
ew>y−b + 1
)} ,
or equivalently, by solving
min w̃∈Rd+1
{ log(e−w̃ >x̃ + 1) + log(e−w̃ >ỹ + 1) } , (1)
where x̃ = [x> 1]>, −ỹ = [−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 ∈ Rd and −y ∈ Rd, let x̃ and −ỹ 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̃∈Rd+1
log(1 + e−w̃ >x̃) + log(1 + e−w̃ >ỹ)
by using the continuous-time approximation to the gradient descent algorithm
dw̃ dt = x̃
δe−w̃ >x̃
1 + e−w̃>x̃ + ỹ
δe−w̃ >ỹ
1 + e−w̃>ỹ
with the initialization w̃(0) = 0 and the learning rate δ, then
lim t→∞
w̃(t)
log(t) =
{ σy−σxy σxσy−σ2xy x̃+ σx−σxy σxσy−σ2xy
ỹ if σxy < σx, 1 σx x̃ if σxy ≥ σx,
(2)
where σx = ‖x̃‖2, σxy = x̃>ỹ and σy = ‖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 Rd, 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
cos2 ψ ≤ 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 {xi}i∈I will not produce a normalized set of features {φL−1(xi)}i∈I . Note that we could not normalize {φL−1(xi)}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.

heading: 3 DATA WITH LOW-DIMENSIONAL FEATURES ATTAIN POOR MARGIN
text: 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 {xi}i∈I and {−yj}j∈J that are linearly separable in Rd, let x̃i and −ỹ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̃∈Rd+1 ∑ i∈I log(1 + e−w̃ >x̃i) + ∑ j∈J log(1 + e−w̃ >ỹ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
w = argmin u∈Rd+1 ‖u‖2 s.t. 〈u, x̃i〉 ≥ 1, 〈u, ỹj〉 ≥ 1 ∀i ∈ I, ∀j ∈ J. (4)
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 {xi}i∈I and {−yj}j∈J , the maximum-margin solution given by the SVM solves
minimize w,b ‖w‖22
subject to 〈w, xi〉+ b ≥ 1 ∀i ∈ I, 〈w,−yj〉+ b ≤ −1 ∀j ∈ J.
(P1)
On the other hand, the solution given by Theorem 2 corresponds to
minimize w,b ‖w‖22 + b2
subject to 〈w, xi〉+ b = 〈w̃, x̃i〉 ≥ 1 ∀i ∈ I, 〈w,−yj〉+ b = 〈w̃,−ỹj〉 ≤ −1 ∀j ∈ J,
(P2)
where we define w̃ = [w> b]>, x̃i = [x>i 1] > and ỹ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 {xi}i∈I and {−yj}j∈J are linearly separable and lie in an affine subspace; that is, there exist a set of orthonormal vectors {rk}k∈K and a set of scalars {∆k}k∈K such that
〈rk, xi〉 = 〈rk,−yj〉 = ∆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 + b2 s.t. 〈w, xi〉+ b ≥ 1, 〈w,−yj〉+ 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 setK 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 {xi}i∈I and {−yj}j∈J in Rd are linearly separable and there exist a set of orthonormal vectors {rk}k∈K and a set of scalars {∆k}k∈K such that
〈rk, xi〉 ≥ ∆k, 〈rk,−yj〉 ≤ ∆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 + b2 s.t. 〈w, xi〉+ b ≥ 1, 〈w,−yj〉+ b ≤ −1 ∀i ∈ I, ∀j ∈ J.
Then the minimization of the cross-entropy loss (3) yields a margin smaller than or equal to
1√ B2 ∑ 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).

heading: 4 DIFFERENTIAL TRAINING IMPROVES MARGIN
text: 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‖22 subject to 〈w, xi + yj〉 ≥ 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 {xi + yj : i ∈ I, j ∈ J} instead of the individual sets {xi}i∈I and {−yj}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 {xi}i∈I and {−yj}j∈J that are linearly separable in Rd, if we solve
min w∈Rd ∑ i∈I ∑ j∈J log(1 + e−w >(xi+yj)) (5)
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.
lim t→∞
w(t)
‖w(t)‖ = wSVM ‖wSVM‖ , (6)
where wSVM is the solution of (P3).
Proof. Apply Theorem 2 by replacing the sets {xi}i∈I and {−yj}j∈J with {xi + yj}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, xi + yj〉 ≥ 1 ∀i ∈ I, ∀j ∈ J.
Since wSVM is the solution of (P3), we obtain w = 12wSVM, 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 ŵ of the decision boundary. The bias parameter, b, could be chosen by plotting the histogram of the inner products {〈ŵ, xi〉}i∈I and {〈ŵ,−yj〉}j∈J and fixing a value for b̂ such that
〈ŵ, xi〉+ b̂ ≥ 0 ∀i ∈ I, (7a) 〈ŵ,−yj〉+ b̂ ≤ 0 ∀j ∈ J. (7b)
The largest hard margin is achieved by
b̂ = −1 2 min i∈I 〈ŵ, xi〉 − 1 2 max j∈J 〈ŵ,−yj〉. (8)
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 {xi}i∈I and {−yj}j∈J that are linearly separable in Rd, assume the cost function (5) is minimized with the stochastic gradient method. Define
Rx = max{‖xi − xi′‖ : i, i′ ∈ I}, Ry = max{‖yj − yj′‖ : j, j′ ∈ J} and let γ denote the hard margin that would be obtained with the SVM:
2γ = maxu∈Rd mini∈I,j∈J 〈xi + yj , u/‖u‖〉. If 2γ ≥ 5 max(Rx, Ry), then the stochastic gradient algorithm produces a weight parameter, ŵ, only in one iteration which satisfies the inequalities (7a)-(7b) along with the bias, b̂, given by (8).

heading: 5 NUMERICAL EXPERIMENTS
text: 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.
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.

heading: 6 DISCUSSION
text: 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; MoosaviDezfooli 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 N2 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 N2 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.

heading: A PROOF OF THEOREM 1
text: 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
dw̃ dt = δx̃
e−w̃ >x̃
1 + e−w̃>x̃ + δỹ
e−w̃ >ỹ
1 + e−w̃>ỹ .
If w̃(0) = 0, then w̃(t) = p(t)x̃+ q(t)ỹ for all t ≥ 0, where
ṗ = δ e−p‖x̃‖ 2−q〈x̃,ỹ〉
1 + e−p‖x̃‖2−q〈x̃,ỹ〉 , q̇ = δ
e−q‖ỹ‖ 2−p〈x̃,ỹ〉
1 + e−q‖ỹ‖2−p〈x̃,ỹ〉 .
Define α = p‖x̃‖2 + q〈x̃, ỹ〉, β = q‖ỹ‖2 + p〈x̃, ỹ〉,
a = δ‖x̃‖2 = δσx, c = δ‖ỹ‖2 = δσy, b = δ〈x̃, ỹ〉 = δσ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
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 zv and z+1 v+1 , respectively. Then,
u̇ < 0 if w > a− b c− b u̇ > 0 if w < a− b c− b
ẇ < 0 if ( a w + b ) u < cw + b
ẇ > 0 if ( a w + b ) u > cw + b
Lemma 1. If b = 0, then
lim t→∞
w̃(t)
log(t) =
1
‖x̃‖ x̃+
1
‖ỹ‖ ỹ.
Proof. Note that
d(z + log(z))
dt = a =⇒ z(t)− z0 + log(z(t)/z0) = at,
d(v + log(v))
dt = c =⇒ v(t)− v0 + log(v(t)/v0) = ct.
Then,
lim t→∞
α(t)
log(t) = lim t→∞
log(z(t))
log(t) = 1 = lim t→∞
log(v(t))
log(t) = lim t→∞
β(t)
log(t) ,
and
lim t→∞
w̃(t)
log(t) =
x̃
‖x̃‖2 +
ỹ
‖ỹ‖2 .
Lemma 2. If b < 0, then there exists t0 ∈ (0,∞) such that
−b c ≤ z + 1 v + 1 ≤ a −b ∀t ≥ t0.
Proof. Note that −bc ≤ a−b c−b ≤ a −b because b < 0. First assume z0+1 v0+1 ≥ a−b . Then, ż ≤ 0 and
v̇ = v
v + 1
( c+ b v + 1
z + 1 ) ≥ v v + 1 ( c− b 2 a ) ≥ v0 v0 + 1 ac− b2 a ,
which implies that z + 1
v + 1 ≤ (z0 + 1)
( v0
v0 + 1
ac− b2
a t+ 1 )−1 as long as z+1v+1 ≥ a −b , and this can be satisfied only for a finite time. Now assume z0+1 v0+1
≤ −bc . Then, v̇ ≤ 0 and
ż = z
z + 1
( a+ b z + 1
v + 1 ) ≥ z0 z0 + 1 ac− b2 c ,
which implies z + 1 v + 1 ≥ ( z0 z0 + 1 ac− b2 c t+ 1 ) (v0 + 1) −1
as long as z+1v+1 ≤ −b c , and this can be satisfied only for a finite time as well.
Lemma 3. If b < 0, then
0 ≤ ż ≤ ac− b 2 c , 0 ≤ v̇ ≤ ac− b 2 a ∀t ≥ t0,
where t0 is given by Lemma 2.
Proof.
ż = z
z + 1
( a+ b z + 1
v + 1 ) ≤ z z + 1 ac− b2 c ≤ ac− b 2 c
v̇ = v
v + 1
( c+ b v + 1
z + 1 ) ≤ v v + 1 ac− b2 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+ bv + 1 z + 1 ≥ 0,
and
v ≤ ac− b 2
a t+ v′0.
Combining these two inequalities, we have
c+ b
a
[ (ac− b2)t+ v′0 + 1 ] 1 z + 1 ≥ 0 ⇐⇒ z + 1 ≥ −b ac [(ac− b2)t+ v′0 + 1]
As a result,
(−b)(ac− b2) ac t+ z1 ≤ z(t) ≤ ac− b2 c t+ z2 ∀t ≥ t0 =⇒ 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− b2 x̃+ δ a− b ac− b2 ỹ = σy − σxy σxσy − σ2xy x̃+ σx − σxy σxσy − σ2xy ỹ
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− b2 , lim t→∞ q log(t) = δ a− b ac− b2
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 ż ≥ 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
ẇ < 0 ⇐⇒ u < cw 2 + bw
a+ bw =: f(w).
We can compute
f ′(w) = 2acw + bcw2 + ab
b2w2 + 2abw + a2 .
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 ẇ = 0. Since limt→∞ u = limt→∞ 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
Lemma 7. If a > b > 0, then
lim t→∞
w̃(t)
log(t) = δ c− b ac− b2 x̃+ δ a− b ac− b2 ỹ = σy − σxy σxσy − σ2xy x̃+ σx − σxy σxσy − σ2xy ỹ.
Proof. From Lemma 6,
lim t→∞
z t = lim t→∞ ż = lim t→∞ z z + 1
( a+ b z + 1
v + 1
) = a+ b
a− b c− b = ac− b2 c− b ,
lim t→∞
v t = ac− b2 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− b2 , lim t→∞ q log(t) = δ a− b ac− b2 .
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.

heading: B PROOF OF COROLLARY 1
text: Since x>y = 1, we have σxy = x̃>ỹ = x>y − 1 = 0 < a. Then the normal vector of the decision boundary is proportional to 1σxx + 1 σy y. For the angle between this vector and the solution of the SVM, we can write
cosψ = 〈 1σxx+ 1 σy y, x+ y〉∥∥∥ 1σxx+ 1σy y∥∥∥∥∥x+ y∥∥ = 2∥∥∥ 1σxx+ 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 σ2x ) + ( 1 σx + 1 σy + σx σy − σx σ2y ) ≥ 2 + σy σx ( 1− 1 σx ) .
As a result,
cos2 ψ ≤ 4
2 + σy σx ( 1− 1σx ) .

heading: C PROOF OF THEOREM 3
text: Let 〈wSVM, ·〉+bSVM = 0 denote the hyperplane obtained as the solution of SVM, i.e., (wSVM, bSVM) is the solution to the problem
min w,b ‖w‖2 s.t. 〈w, xi〉+ b ≥ 1, 〈w,−yj〉+ b ≤ −1 ∀i ∈ I, ∀j ∈ J.
Assume that w = u+ ∑m k=1 αkrk, where u ∈ Rd and 〈u, rk〉 = 0 for all k ∈ K.
The Lagrangian of the problem (4) can be written as
1 2 ‖w‖2 + 1 2 b2 + ∑ i∈I µi(1− 〈w, xi〉 − b) + ∑ j∈J νj(1− 〈w, yj〉+ 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
w = ∑
i∈I µixi + ∑ j∈J νjyj ,
B = ∑
i∈I µi − ∑ j∈J νj ,
and consequently, for each k ∈ K,
〈w, rk〉 = ∑
i∈I µi〈xi, rk〉 − ∑ j∈J νj〈−yj , rk〉 = ∑ i∈I ∆kµi − ∑ j∈J ∆kνj = B∆k.
Then, we can write w as
w = u+ ∑
k∈K B∆krk.
Remember, by definition,
wSVM = arg min ‖w‖2 s.t. 〈w, xi + yj〉 ≥ 2 ∀i ∈ I, ∀j ∈ J.
Since the vector u also satisfies 〈u, xi + yj〉 = 〈w, xi + yj〉 ≥ 2 for all i ∈ I, j ∈ J , we have ‖u‖ ≥ ‖wSVM‖ = 1γ . As a result, the margin obtained by minimizing the cross-entropy loss is
1
‖w‖ = 1√ ‖u‖2 + ∑ ‖B∆krk‖2 ≤ 1√ 1 γ2 +B 2 ∑ ∆2k .

heading: D PROOF OF THEOREM 4
text: If B < 0, we could consider the hyperplane 〈w, ·〉 − B = 0 for the points {−xi}i∈I and {yj}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 = ∑
i∈I µixi + ∑ j∈J νjyj , B = ∑ i∈I µi − ∑ j∈J νj
where µi ≥ 0 and νj ≥ 0 for all i ∈ I, j ∈ J . Note that for each k ∈ K, 〈w, rk〉 = ∑
i∈I µi〈xi, rk〉 − ∑ j∈J νj〈−yj , rk〉
= B∆k + ∑
i∈I µi(〈xi, rk〉 −∆k)− ∑ j∈J νj(〈−yj , rk〉 −∆k) ≥ B∆k.
Since {rk}k∈K is an orthonormal set of vectors, ‖w‖2 ≥ ∑
k∈K 〈w, rk〉2 ≥ ∑ k∈K B2∆2k.
The result follows from the fact that ‖w‖−1 is an upper bound on the margin.

heading: E PROOF OF THEOREM 6
text: In order to achieve zero training error in one iteration of the stochastic gradient algorithm, it is sufficient to have
mini′∈I〈xi′ , xi + yj〉 > maxj′∈J〈−yj′ , xi + yj〉 ∀i ∈ I, ∀j ∈ J,
or equivalently, 〈xi′ + yj′ , xi + yj〉 > 0 ∀i, i′ ∈ I, ∀j, j′ ∈ J. (9)
By definition of the margin, there exists a vector wSVM ∈ Rd with unit norm which satisfies
2γ = mini∈I,j∈J〈xi + yj , wSVM〉.
Note that wSVM is orthogonal to the decision boundary given by the SVM. Then we can write every xi + yj as
xi + yj = 2γwSVM + δ x i + δ y j ,
where δxi , δ y j ∈ Rd and ‖δxi ‖ ≤ Rx and ‖δ y j ‖ ≤ Ry . Then, condition (9) is satisfied if
〈2γwSVM + δxi + δ y j , 2γwSVM + δ x i′ + δ y j′〉 > 0 ∀i, i ′ ∈ I, ∀j, j′ ∈ J,
or equivalently if
4γ2 + 2γ〈wSVM, δxi + δ 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 γ > 52 max(Rx, Ry), we have
4γ2 − 2γ(2Rx + 2Ry)− (Rx +Ry)2 > 0,
which guarantees (10) and completes the proof.

Review summaries:
This paper investigates the properties of minimizing cross-entropy of linear functions over separable data (looks like logistic loss). The authors show a simple example where the minimizer of the cross-entropy loss leads to maximum margin hyperplane where the bias term is regarded as an extra dimension, which is different from the standard max. margin solution of  SVMs with bias not regarded as an extra dimension. The authors then propose a method to obtain the latter solution by minimizing the cross-entropy loss.