ON THE IMPLICIT MINIMIZATION OF ALTERNATIVE LOSS FUNCTIONS WHEN TRAINING DEEP NETWORKS
Year: 2019

Abstract:
Understanding the implicit bias of optimization algorithms is important in order to improve generalization of neural networks. One approach to try to exploit such understanding would be to then make the bias explicit in the loss function. Conversely, an interesting approach to gain more insights into the implicit bias could be to study how different loss functions are being implicitly minimized when training the network. In this work, we concentrate our study on the inductive bias occurring when minimizing the cross-entropy loss with different batch sizes and learning rates. We investigate how three loss functions are being implicitly minimized during training. These three loss functions are the Hinge loss with different margins, the cross-entropy loss with different temperatures and a newly introduced Gcdf loss with different standard deviations. This Gcdf loss establishes a connection between a sharpness measure for the 0− 1 loss and margin based loss functions. We find that a common behavior is emerging for all the loss functions considered.

heading: 1 INTRODUCTION
text: In the last few years, deep learning has succeeded in establishing state of the art performances in a wide variety of tasks in fields like computer vision, natural language processing and bioinformatics (LeCun et al., 2015). Understanding when and how these networks generalize better is important to keep improving their performance. Many works starting mainly from Neyshabur et al. (2015), Zhang et al. (2017) and Keskar et al. (2017) hint to a rich interplay between regularization and the optimization process of learning the weights of the network. The idea is that a form of inductive bias can be realized implicitly by the optimization algorithm.
In this paper, we investigate the implicit bias induced from using different learning rates and batch sizes when minimizing the cross-entropy loss with SGD. A common theory is that more noise in the gradient bias the solution toward flatter minima (Keskar et al., 2017). We draw a connection between a particular measure of flatness and margin based loss functions1.
Our contributions are the following:
1. A new loss function (Gcdf loss) that can be interpreted as a measure of flatness for the 0−1 loss (for the top layer’s weights of the network).
2. A methodology consisting in tracking alternative loss functions during training and comparing them for a given training loss value to try to uncover implicit biases in the optimization algorithm applied to varying the learning rate and batch size in SGD.
3. Experimental results on CIFAR10 and MNIST showing that larger learning rates and smaller batch sizes are better at implicitly minimizing the cross-entropy loss with larger temperature parameter, the hinge loss with larger margin parameter and the Gcdf loss with larger standard deviation parameter. At the opposite, smaller learning rates and larger batch sizes are better at implicitly minimizing the cross-entropy loss, the hinge loss and the Gcdf loss with smaller values of their respective parameter.
1The concept of margin has been link to generalization of deep networks; see for example Bartlett et al. (2017), Poggio et al. (2019) and Jiang et al. (2019)
We do not propose to modify optimization algorithms to try to improve large batch training but we instead try to offer new insights on how the solutions it produces are different from solutions resulting from small batch training (or larger learning rates). The hope is to eventually succeed at incorporating the inductive bias in the objective being optimized instead of relying on the implicit bias of the optimization algorithm. It is not yet clear to what extent this goal can be realized (and by what means2) and we certainly do not claim to be reaching it. We offer only a partial understanding of some of the differences between large batch training (or using small learning rates) and small batch training (or using large learning rates) through the behavior of alternative loss functions during training.

heading: 2 RELATED WORK
text: It was observed by Zhang et al. (2017) that deep networks can often obtain good results without explicit regularization even if they have the capacity to essentially memorize the training set. They hypothesized that SGD is probably acting as an implicit regularizer. Also, the earlier work of Neyshabur et al. (2015) brought forward the idea that optimization might be implicitly biasing the trajectory toward low norm models. Since then, many works have investigated the idea of implicit regularization for neural networks (linear or non-linear). For example, Arora et al. (2019) studied how gradient descent finds low rank solutions for matrix completion with deep linear networks. Soudry et al. (2018) showed that gradient descent converges to the max-margin solution for logistic regression and Lyu & Li (2019) provides and extension to deep non-linear homogeneous networks. In contrast to these works, we study empirically how the optimization algorithm implicitly minimizes alternative loss functions during the course of training.
A highly studied source of implicit bias from the optimization algorithm is the ability to reach flatter minima. In Keskar et al. (2017), the worst loss that can be obtained when slightly perturbing the parameters is considered as a measure of sharpness while Neyshabur et al. (2017) considered the expected loss under Gaussian noise in the weights. We consider a measure of sharpness (section 3) similar to Neyshabur et al. (2017) and we apply it to the 0 − 1 loss directly instead of the usual surrogate cross-entropy loss.
The batch size and the learning rate are two ways to control the noise in the gradient which might influence the sharpness of the resulting solution (see for example Smith & Le (2018), Smith et al. (2018)). In conjunction with increasing the learning rate, different strategies like training for more epochs (Hoffer et al., 2017), “warm up” (Goyal et al., 2017) and using a separate learning rate for each layer based on the norm of the weights (You et al., 2017) have been proposed to improve the performance of large batch training. Instead of trying to offer a new modification to the optimization algorithm, we try here to capture the inductive bias into computationally efficient to use loss functions in the hope of eventually simplifying the design of optimization algorithms.

heading: 3 GCDF LOSS
text: This section introduces a loss function based on the idea of flat minima. It is defined as a measure of sharpness for the 0 − 1 loss. The main motivation for introducing this loss function is that it is simultaneously a measure of sharpness and a margin based loss function establishing a clear relationship between these ideas. Furthermore, as opposed to the cross-entropy loss and the Hinge loss, it is bounded and non-convex (see section 4.1 for a visual comparison). It thus offers more diversity to the loss functions investigated in this paper. We start with the binary linear case in 3.1 and then extend to the multi-class case in 3.2. For deep networks, this loss will be applied on the top layer. It is a possible extension to our work to consider loss functions applied on multiple layers maybe in a similar fashion to Elsayed et al. (2018).
2see for example Arora et al. (2019) about the difficulties to capture the implicit bias of gradient descent with norms.

heading: 3.1 BINARY LINEAR CASE
text: Let f(w, x) = wTx + b, where w, x ∈ Rn and b ∈ R. Consider the 0 − 1 loss for a binary linear classifier: L(f(w, x), y) = 1 [ y(wTx+b) < 0 ] , where 1 is the indicator function. Note that we will
write all the loss functions for single examples (x, y) throughout the paper and it will be understood that the training loss is obtained by taking the mean over the training set. We smooth (or “robustify”) the 0− 1 loss by considering its expectation under Gaussian noise in the weights. This loss function will then be denoted by Lσ(w, x, y) when the standard deviation is σ. Consider the random variable ∼ N (0, σ2I), where N (0, σ2I) is a zero mean isotropic Gaussian distribution with covariance matrix σ2I . Since (w + )Tx + b is distributed as a Gaussian distribution with mean wTx + b and variance σ2||x||2, we get that y((w + )Tx+ b) is distributed as a Gaussian distribution with mean y(wTx+ b) and the same variance. Therefore,
Lσ(w, x, y) = E L(f(w + , x), y) = Φ (−y(wTx+ b) σ||x|| ) , (1)
where Φ is the Gaussian cumulative distribution function (Gcdf) given by
Φ(z) = 1√ 2π ∫ z −∞ exp (−t2 2 ) dt. (2)
If we assume that x is normalized, the loss Lσ is a (decreasing) function of yf(w, x) (it is a margin based loss function in the terminology from Lin (2004) for example).

heading: 3.2 MULTI-CLASS CASE
text: Suppose the number of classes is m and now consider the affine mapping f(W,x) = Wx+ b with x ∈ Rn, b ∈ Rm and W ∈ Rm×n. For some fixed x ∈ Rn and denoting by wj the jth row of W , let sj := wTj x+ bj be the corresponding score for class j. Finally, let sj( j) := (wj + j)
Tx+ bj be the perturbed score, j an isotropic Gaussian random variable with mean 0 and covariance matrix σ2I . For a given class y, we get
P { sy( y) 6= max
j sj( j)
} ≤ ∑ j 6=y P { sj( j) > sy( y) } (3)
= ∑ j 6=y P { sj − sy > ( y − j)Tx } (4)
= ∑ j 6=y Φ ( sj − sy ||x||σ √ 2 ) , (5)
since ( y − j)Tx follows a zero mean Gaussian distribution with variance 2σ2||x||2. We define
Lσ(W,x, y) := ∑ j 6=y Φ ( sj − sy ||x||σ √ 2 ) . (6)
This is an upper bound on the probability that the classifier does not predict y under Gaussian noise on W . We will experiment with this Gcdf loss function on top of feedforward neural networks (and also with other loss functions) in the following sections. In all the experiments, we use normalization to enforce ||x|| = 1 (this x now represents the feature vector for the top layer).

heading: 4 IMPLICIT MINIMIZATION OF DIFFERENT LOSS FUNCTIONS
text: In this section, we track different loss functions while training deep neural networks with the crossentropy loss varying the learning rates and batch sizes in SGD with momentum. The results in the main text are obtained while training on CIFAR10. Results on MNIST are given in Appendix A. The following loss functions are considered: cross-entropy with different values of temperature, Hinge loss with different margin parameters and the Gcdf loss with different standard deviation parameters.
For the cross-entropy loss, the temperature T divides the scores sj before the softmax function. That is, the probability for class j is then given by
exp(sj/T )∑ k exp(sk/T ) . (7)
Remark that the positive homogeneity of the Relu implies that normalizing each layer of the network is equivalent to take T equal to the product of the norm of the layers. The cross-entropy loss after normalization at the end of training is investigated in Liao et al. (2018). In contrast, we consider here multiple values for T and investigate the behavior during training. Given the probabilities for each class, the cross-entropy loss (on a single example) is then the negative log probability for the correct class. For its part, the multi-class Hinge loss with margin parameter γ (on a single example) is given by ∑
j 6=y
max{0, γ + (sj − sy)}. (8)
The Gcdf loss with standard deviation parameter σ has been described and motivated in the previous section.

heading: 4.1 VISUAL COMPARISON OF THE LOSS FUNCTIONS
text: Assume that we have two classes and let z = sy − sj (for j 6= y). An example is correctly classified if z > 0. The Gcdf loss is then given by Φ( −z
σ √ 2 ), the Hinge loss by max{0, γ − z} and the cross-
entropy loss by log(exp(−zT )+1). These functions are plotted in figure 1. They share one interesting characteristic on the side z > 0: when their parameter (σ, T or γ) gets larger, the loss takes more time to get closer to zero when z increases. This kind of “heavier tail” behavior can encourage larger z values for some training points at the expense of other closer to zero training points more easily.

heading: 4.2 TRAINING CURVES OF THE ALTERNATIVE LOSS FUNCTIONS
text: In figures 2, 3 and 4, we investigate the effect of the size of the learning rate by considering the implicit training curves of the Gcdf loss, the cross-entropy loss and the Hinge loss for different values of their respective parameter (σ, T or γ). The learning rate is kept constant throughout training (no decaying schedule is used). We consider a small learning rate of 0.001 and a larger learning rate of 0.1. For the three loss functions considered, the larger learning rate is clearly better at implicitly minimizing them for larger values of their parameter. A similar conclusion holds when considering different batch sizes as is shown in figures 5, 13 (Appendix B) and 14 (Appendix B). In this case, the smaller batch size (256) is much better at implicitly minimizing the loss functions for larger values of their parameter than the larger batch size (16384). As a technical aside, note that ghost batch normalization Hoffer et al. (2017) is used when training with large batch sizes. The gradients are accumulated on a sequence of smaller mini-batches of size 256 before updating the weights.

heading: 4.3 ALTERNATIVE LOSS VERSUS ACTUAL TRAIN LOSS
text: At a given fixed training loss value two training runs have made the same progress toward minimizing their objective function but they might not have made the same progress with respect to other measures of performance. The other measures of performance considered here are of course our alternative loss functions. In figure 6, we plot the Gcdf loss against the actual train loss for different runs corresponding to different learning rates. We can see that smaller learning rates are actually better at minimizing the Gcdf loss with smaller σ during training while larger learning rates are better at minimizing the Gcdf loss with larger σ. There exists an intermediate value (here σ = 1) where all the learning rates considered in our experiments are essentially equivalent at implicitly minimizing the Gcdf loss. The train error behaves similarly to the Gcdf loss with a small value of σ. In the binary case, the Gcdf loss converges pointwise to the 0− 1 loss almost everywhere (except at 0) when σ goes to 0. It would therefore make sense to actually define the Gcdf loss for σ = 0 to be the train error (in the binary case; some modifications are needed in the multi-class case). In this light, it is not surprising that figure 6a and 6d are showing a similar behavior. In order to make even more clear how different choices of learning rates are not implicitly minimizing the alternative loss functions for different parameters (σ, T or γ) in the same way, we plotted the alternative losses
against their respective parameter for some fixed training loss value in figure 7. Similar results are obtained on MNIST (see figure 12 in Appendix A). See also figure 16 (Appendix B) for the results when considering different batch sizes on CIFAR10.

heading: 5 DISCUSSION AND CONCLUSION
text: Suppose is distributed according to an isotropic Gaussian distribution with covariance matrix σ2I and mean 0. Under a second order approximation to the cross-entropy loss Lc(w, x, y) at w, we get E [ Lc(w + , x, y) ] ≈ Lc(w, x, y) + σ 2
2 Tr(H), where H is the Hessian of Lc(w, x, y). For
simplicity consider the binary case. Furthermore, since we restricted ourselves to loss functions applied on the top layer only, assume that is applied only to the weights of the top layer. In our setup, the Hessian H is now restricted to the weights of the final layer. Since the 0 − 1 loss is bounded above by the cross-entropy loss (times a factor 1/ log(2)), we get
Lσ(w, x, y) ≤ 1 log(2) E [ Lc(w + , x, y) ] ≈ Lc(w, x, y) log(2) + σ2 2 log(2) Tr(H). (9)
Therefore, an optimization algorithm succeeding at finding a solution with small cross-entropy loss and small mean curvature of the cross-entropy loss must have a small Gcdf loss also. This might help to explain why larger learning rates and smaller batch sizes are good at implicitly minimizing
the Gcdf loss. Note however that this argument has some weaknesses. First, the approximation is only local and so might not be good for larger values of σ. Second, it cannot explain why smaller learning rates and larger batch sizes are better for smaller values of σ. Future work could concentrate on finding a rigorous explanation for these results.
Understanding the inductive biases of different optimization algorithms for training deep networks might allow to make the bias more explicit, that is to incorporate it in the loss function. We think that one strategy to make progress toward this long term goal might be to study how alternative loss functions are being implicitly minimized by a given optimization algorithm. This paper considered the learning rate and batch size parameters when training with SGD. A clear avenue for future research is to extend the investigation to adaptive first-order methods (which can sometimes exhibit worse generalization performance than SGD (Wilson et al., 2017)) and second-order methods.

heading: A RESULTS ON MNIST
text: This section contains the results when training a 6-layer fully connected network with batch normalization on MNIST. No data augmentation is used. The optimization algorithm is SGD with momentum (0.9) and without weight decay. The learning rate is constant during all training.

heading: B MORE RESULTS ON CIFAR10
text: This section contains additional results when training a convolutional network with batch normalization on CIFAR10. The network consists of two convolutional layers with max pooling followed by 3 fully connected layers. No data augmentation is used. The optimization algorithm is SGD with momentum (0.9) and without weight decay. The learning rate is constant during all training.

Review summaries:
This paper want to show that minimizing cross-entropy loss will simultaneously minimize Hinge loss with different margins, cross-entropy loss with different temperatures and a newly introduced Gcdf loss with different standard deviations. The main contribution is a new gcdf loss based on Gaussian-perturbed parameters. However, this loss can only be used with linear models. For deep models, the authors suggest that only measure this loss on the top layer of model.

This paper makes a step towards understanding of the implicit bias of optimization algorithms in deep learning. The authors consider alternative loss functions for deep networks: (1) the temperature-scaled cross-entropy loss with different values of the temperature; (2) the hinge-loss with different values of the margin parameter; (3) the Gcdf loss with different values of the variance parameter. The paper introduces the Gcdf loss which is derived as a modification of the 0-1 loss under the noise in the parameters of the linear output layer. The authors propose to use the alternative losses as measures of margin and sharpness associated with a solution found by an optimization algorithm. The experiments show how SGD in different learning scenarios (low/high learning rate and small/large batch) performs implicit minimization of the alternative loss functions with different parameters. Specifically, using larger learning rates/smaller batch sizes is shown to implicitly minimize the losses corresponding to higher values of the temperature/margin/variance. The results provide insights about margins and sharpness of solutions found by different modes of SGD.