Title: AN OPTIMIZATION PRINCIPLE OF DEEP LEARNING?

Abstract: Training deep neural networks (DNNs) has achieved great success in recent years. Modern DNN trainings utilize various types of training techniques that are developed in different aspects, e.g., activation functions for neurons, batch normalization for hidden layers, skip connections for network architecture and stochastic algorithms for optimization. Despite the effectiveness of these techniques, it is still mysterious how they help accelerate DNN trainings in practice. In this paper, we propose an optimization principle that is parameterized by γ > 0 for stochastic algorithms in nonconvex and over-parameterized optimization. The principle guarantees the convergence of stochastic algorithms to a global minimum with a monotonically diminishing parameter distance to the minimizer and leads to a O(1/γK) sub-linear convergence rate, where K is the number of iterations. Through extensive experiments, we show that DNN trainings consistently obey the γ-optimization principle and its theoretical implications. In particular, we observe that the trainings that apply the training techniques achieve accelerated convergence and obey the principle with a large γ, which is consistent with the O(1/γK) convergence rate result under the optimization principle. We think the γ-optimization principle captures and quantifies the impacts of various DNN training techniques and can be of independent interest from a theoretical perspective.

1. INTRODUCTION:

Deep learning has been successfully applied to various domains such as computer vision, natural language processing, etc, and has achieved state-of-art performance in solving challenging tasks. Although deep neural networks (DNNs) have been well-known for decades to have great expressive power Cybenko (1989) , the empirical success of training DNNs postponed to recent years when sufficient computation power is accessible and effective DNN training techniques are developed.

The milestone developments of DNN training techniques can be divided into two categories. First, various techniques have been developed at different levels of neural network design. At the neuron level, various functions have been applied to activate the neurons, e.g., sigmoid function, hyperbolic tangent (tanh) function and the more popular rectified linear unit (ReLU) function Nair & Hinton (2010) . At the layer level, batch normalization (BN) has been widely applied to the hidden layers of DNNs to stabilize the training Ioffe & Szegedy (2015) . Moreover, at the architecture level, skip connections have been introduced to enable successful training of deep networks He et al. (2015) ; Szegedy et al. (2015) ; Srivastava et al. (2015) ; Huang et al. (2016) . Second, various efficient stochastic optimization algorithms have been developed for DNN training, e.g., stochastic gradient descent (SGD) Robbins & Monro (1951) ; Rumelhart et al. (1986) , SGD with momentum Qian (1999) ; Nesterov (2014) and Adam Kingma & Ba (2015) , etc. Table 1 provides a summary of these important DNN training techniques. In the existing literature, it is known that the sigmoid and tanh activation functions can cause the vanishing gradient problem, and the ReLU activation function is a popular replacement that avoids this issue Nair & Hinton (2010) ; Glorot et al. (2011) . On the other hand, the batch normalization is originally proposed to reduce the internal covariance shift Ioffe & Szegedy (2015) , and more recent studies show that it allows to use a large learning rate Bjorck et al. (2018) and improves the loss landscape Santurkar et al. (2018) . The skip connection has been shown to help eliminate singularities and degeneracies Orhan & Pitkow (2018) and improve the loss landscape Hardt & Ma (2016) . Moreover, regarding the optimization algorithm, the momentum scheme has been well-known to accelerate convex optimization Nesterov (2014) and is also widely applied to accelerate nonconvex optimization Ghadimi & Lan (2016) , whereas the Adam algorithm normalizes the update in each dimension to accelerate deep learning Kingma & Ba (2015) . While these studies provide partial explanations to the effectiveness of various This paper attempts to propose an optimization principle that characterizes and quantifies the impacts of various training techniques on DNN training. The proposed principle is applicable to general stochastic algorithms in the nonconvex and over-parameterized regime and leads to guaranteed convergence to a global minimum. We summarize our contributions as follows.

1.1. OUR CONTRIBUTIONS:

Theory: We propose an optimization principle that is parameterized by γ > 0 for stochastic algorithms in nonconvex and over-parameterized optimization. The γ-optimization principle (see Definition 1) requires the current update points toward a global minimizer, and the inner product between both directions is lower-bounded by the update norm and the loss gap that is scaled by the factor γ. We show that the γ-optimization principle guarantees the optimization path generated by stochastic algorithms to approach a global minimizer with a monotonically diminishing distance. Moreover, it leads to convergence of the optimization path to the global minimum with a O(1/γK) sub-linear convergence rate .

Experiments: We conduct extensive experiments to examine the validity of the γ-optimization principle in DNN training. In specific, we find that all the tested DNN trainings obey the γoptimization principle throughout the training process, and the generated optimization paths satisfy the theoretical properties of the principle that are mentioned above. Moreover, we explore the impacts of the training techniques that are listed in 

2. AN OPTIMIZATION PRINCIPLE FOR OVER-PARAMETERIZED ML:

In this section, we introduce the γ-optimization principle that provides convergence guarantees for over-parameterized nonconvex machine learning (ML). We show empirically in the subsequent sections that practical DNN trainings obey this principle.

2.1. GLOBAL MINIMUM OF OVER-PARAMETERIZED MODELS:

The goal of a machine learning task is to search for a good ML model θ that minimizes the total loss f on a set of training data samples Z :

{z i } n i=1 .

The problem is formally written as

EQUATION

where (•; z i ) : R d → R corresponds to the loss on the i-th data sample z i . For many nonconvex ML models, e.g., deep neural networks, a prominent feature is the over-parameterization of the model, i.e., the model capacity is sufficient to over-fit all the training data samples. In another word, the global minimizers of the total loss f under an over-parameterized model are common minimizers of all the individual loss functions (•; z i ), i = 1, ..., n. We summarize this fact formally as follows.

Fact 1. Consider the problem (P) with an over-parameterized model θ. Every global minimizer θ * of the total loss f is also a global minimizer of each individual loss (•; z i ) for all i = 1, ..., n.

To elaborate, note that we typically use non-negative loss in DNN training. Therefore, if the total loss f is trained to achieve zero (i.e., the global minimum), then each individual loss (•; z i ) must also achieve zero and the obtained model over-fits the training data. Of course, in practice, due to the termination of the optimization process within finite number of iterations, the total loss can only achieve an approximate global minimum that is very close to zero. Throughout the rest of this section, we assume that Fact 1 holds for the problem (P).

2.2. THE γ-OPTIMIZATION PRINCIPLE:

Consider a generic stochastic algorithm (SA) that is initialized with certain model θ 0 . In each iteration k, the SA samples a data sample z ξ k ∈ Z, where ξ k ∈ {1, ..., n} is obtained via cyclic sampling with reshuffle. Based on the current model θ k and the sampled data z ξ k , the SA generates a stochastic update U (θ k ; z ξ k ) and applies it to update the model with a learning rate η > 0 according to (SA) :

EQUATION

) Equation ( 1) covers the update rule of many existing optimizers for DNN training. For example, the stochastic gradient descent (SGD) algorithm chooses the update U (θ k ; z ξ k ) to be the stochastic gradient ∇ θ (θ k ; z ξ k ). In comparison, the SGD with momentum algorithm generates the update using an extra momentum step, and the Adam algorithm generates the update as a moving average of the stochastic gradients normalized by the moving average of their second moments1 .

We next introduce the γ-optimization principle for the SA. Definition 1 (γ-optimization principle for SA). Apply SA to solve the over-parameterized problem (P). For a certain global minimizer θ * of the problem (P), the optimization path {θ k } k generated by the SA satisfies: for certain γ > 0 and all k = 0, 1, 2, ...,,

EQUATION

To elaborate, the left hand side of eq. ( 2) measures the coherence between θ k -θ * and the current model update U (θ k ; z ξ k ). Intuitively, a positive coherence implies that the current model update points toward the global minimizer θ * from the current model θ k . On the other hand, the right hand side of eq. ( 2) regularizes the coherence by two non-negative terms: the square norm of the model update scaled by the learning rate η and the optimality gap of the loss on the sampled data scaled by the constant γ θ 0 -θ * 2 . Hence, a larger value of γ implies that the update U (θ k ; z ξ k ) is more coherent with the direction towards the minimizer θ k -θ * and therefore facilitates the convergence. We show in Theorem 1 later that the γ plays a central role in characterizing the convergence rate of the SA.

Discussion: The γ-optimization principle is related to other existing ones in nonconvex ML. In specific, nonconvex problems such as phase retrieval Zhang et al. (2017b) and low-rank matrix recovery Tu et al. (2016) have been shown to satisfy the regularity condition, which replaces the last term in eq. ( 2) by γ θ k -θ * 2 and guarantees the linear convergence of {θ k } k to θ * . However, such a fast convergence rate does not hold in practical DNN training. On the other hand, DNN trainings have been shown in Zhou et al. (2019) to follow a star-convex optimization path, which corresponds to eq. ( 2)

with γ = θ 0 -θ * -2 , U (θ k ; z ξ k ) = ∇ (θ k ; z ξ k ) and absence of the term η 2 U (θ k ; z ξ k ) 2

. However, such a principle is applicable to SGD updates only and an additional global Lipschitz assumption on the loss function is required in order to have theoretical convergence guarantee. In comparison, the γ-optimization principle is applicable to the more general SA and does not rely on additional assumption to have convergence guarantee as we elaborate below.

We obtain the following convergence results of SA under the γ-optimization principle.

Theorem 1 (Convergence of SA). Apply SA to solve the over-parameterized problem (P). If the optimization process satisfies the principle in Definition 1, then the following statements hold.

1. The optimization path {θ k } k approaches the global minimizer θ * with a monotonically diminishing distance, i.e., θ k+1 -θ * ≤ θ k -θ * for all k = 0, 1, 2, ...,.

2. For all i, each (•; z i ) converges to its global minimum along the optimization path, i.e., denote {i(T )} T ∈N as the sequence of iterations that sample z i , then, lim T →∞ (θ i(T ) ; z i ) = (θ * ; z i ).

3. For any K = nB, B ∈ N, the accumulated loss converges to the global minimum at the rate

EQUATION

To elaborate, item 1 of Theorem 1 shows that the optimization path of SA approaches the global minimizer with a monotonically diminishing distance under the γ-optimization principle, and item 2 further establishes the convergence of each individual loss to its global minimum. More importantly, item 3 shows that the average of the accumulated loss convergences to the global minimum of the total loss at a sub-linear convergence rate, which is inverse proportionally to the parameterization γ of the optimization principle in eq. ( 2). Intuitively, a larger γ implies a more coherent update U (θ k ; z ξ k ) with the desired direction θ k -θ * and therefore leads to a faster convergence.

Remark: Under the γ-optimization principle, the sub-linear convergence rate in item 3 depends on the learning rate η and the parameter γ only, which are problem-independent parameters. Therefore, given a fixed learning rate, the parameter γ of the optimization principle provides a universal quantification of the optimization quality. Inspired by this idea, in the subsequent sections, we conduct extensive experiments to examine the validity of the γ-optimization principle in DNN training. In particular, we empirically quantify the impacts of different training techniques on the DNN training by evaluating the parameter γ of the optimization principle in each optimization process.

Exploration plan: In all DNN trainings, we train the network for a sufficient number of epochs to achieve an approximate global minimum. We store the network parameters {θ k } k , loss { (θ k ; z ξ k )} k and update {U (θ k ; z ξ k )} k that are generated in each DNN training. Then, we compute the upper bound for γ in each iteration according to eq. ( 2), where we set θ * to be the network parameters produced in the last training iteration. We use mini-batch sampling and all the stored loss and updates correspond to their mini-batch versions. (2015) with different choices of activation functions for all the nonlinear neurons. The activation functions that we explore include sigmoid, tanh, ReLU and leaky ReLU (with slope 10 -2 ). We apply the standard SGD optimizer with a fixed initialization point, a mini-batch size 128 and a constant learning rate η = 0.05 to train these networks for 150 epochs on the Cifar10 and Cifar100 datasets Krizhevsky (2009) , respectively.

In the three rows of Figure 1 , we present the training results of the normalized distance-to-minimizer, training loss and parameter γ of the optimization principle along the optimization path, respectively. From the figures in the third row, one can see that these trainings with different activation functions obey the γ-optimization principle with γ > 0 in the training process. This demonstrates the validity of the principle in these DNN trainings. Also, the figures in the first and second rows respectively show that the distance-to-minimizer diminishes monotonically and the training loss converges to the global minimum in these trainings. These observations are consistent with the theoretical implications of the γ-optimization principle in items 1 and 2 of Theorem 1.

Moreover, regarding the trainings of the Alexnet (first two columns), we observe that the trainings with the sigmoid activation function converge much slower than those with the other activation functions, and the parameter γ under the sigmoid activation has a smaller value than those under the other activation functions. On the other hand, in the trainings of the Resnet-18 (last two columns), we observe that the convergence speed of the trainings with ReLU types of activation functions is the fastest, and is followed by that of the trainings with tanh activation function and sigmoid activation function, respectively. Moreover, one can see that the γ in the trainings with ReLU types of activation functions has the largest value, and is followed by that in the trainings with tanh activation function and sigmoid activation function, respectively. These observations are consistent with item 3 of Theorem 1, where a larger γ implies faster convergence. The experiments in this subsection show that DNN trainings different activation functions obey the γ-optimization principle, which captures and quantifies the impact of choice of activation function the training process via the γ.

3.2. IMPACT OF BATCH NORMALIZATION ON γ-OPTIMIZATION PRINCIPLE:

setup: We train the Resnet-18, 34 and the Vgg-11, 16 networks with the settings: 1) keep all the BN layers; 2) keep the first layer in each block; and 3) remove all BN layers. We remove all the dropout layers in the Vgg networks. We apply SGD with a fixed initialization point, a constant learning rate (η = 0.05 for Resnet, 0.01 for Vgg) and batch size 128 to train these networks on the Cifar10 and Cifar100 datasets, respectively.

Figure 2 shows the training results on the Cifar10 dataset. Due to space limitation, we present the distance-to-minimizer results in Appendix B, where one can see that the distances are monotonically diminishing and therefore are consistent with item 1 of Theorem 1. In all the trainings shown in Figure 2 , removing all BN layers significantly slows down the convergence of loss. In particular, vanishing gradient occurs after around 25 epochs in the trainings of resnets without any BN layer and we plot the corresponding curves up to the epoch when gradient vanishes. On the other hand, the trainings that keep the first BN layer in each block converge as fast as those with all BN layers, and they all converge to the global minimum.

Regarding the γ values, they are all positive throughout these trainings, which demonstrates the validity of the γ-optimization principle. Moreover, the γ in the trainings without any BN layer is considerably smaller than that in the trainings with either one BN layer or all BN layers. Such an observation is consistent with the convergence rate result in item 3 of Theorem 1, where a larger γ implies faster convergence. We also report in Figure 3 the results of training these networks on the Cifar100 dataset, where one can see the positiveness of the γ throughout the training that demonstrates the validity of the γ-optimization principle. Particularly in the trainings of the resnets (see top row), the convergence of the trainings with all BN layers is the fastest, and is followed by that of the trainings with one BN layer in each block and without any BN layer, respectively. Moreover, in the first 20 epochs where the training loss is close to the global minimum, one can see that the γ in the trainings with all BN layers is larger than that in the trainings with one BN layer in each block, and the γ in the trainings without any BN layer has the smallest value. Similar observation is made in the training of the Vgg-16 network. Moreover, in the training of the Vgg-11 network, the training with one BN layer in each block is sufficient to achieve comparable performance to that of the training with all BN layers, and their γ have similar values throughout the training. In comparison, the training without any BN layer is significantly slower and have much smaller γ values.

The experiments in this subsection demonstrate that the γ-optimization principle is able to capture and quantify the impact of batch normalization on DNN training in terms of the parameter γ. Experiment setup: We train the Resnet-18, 34 and the Vgg-11, networks using SGD, SGD with momentum and Adam, respectively. We remove all the dropout layers in Vgg networks. We apply a fixed point, a constant learning η = 0.001 and batch size 128 to all the optimizers and train these networks on the Cifar10 and Cifar100 datasets, respectively. We set the momentum to be 0.5 for the SGD with momentum and set β 1 = 0.9, β 2 = 0.999, = 10 -2 for the Adam.

Figure 5 presents the training results on the Cifar10 dataset, and we present the distance-to-minimizer results in Appendix D.1 where one can see that they are all monotonically diminishing. In all these trainings, the γ curves are above zero and therefore demonstrates the validity of the γ-optimization principle. Also, it can be seen that the SGD with momentum trainings achieve significantly faster convergence speed than that achieved by the SGD trainings, and the Adam trainings converge the fastest. Regarding the γ, it can be seen that the SGD trainings obey the optimization principle with the smallest γ, which is further enlarged in the SGD with momentum trainings. Moreover, the Adam trainings obey the optimization principle with the largest γ. These observations are consistent with item 3 of Theorem 1, where a larger γ implies faster convergence of the training. The training results on the Cifar100 dataset are shown in Figure 6 , where one can make very similar observations as those on Cifar10. In particular, for the Adam training of VGG-16 on Cifar100, the sign of γ fluctuates after 50 epochs, which is possibly caused by the stochastic pre-conditioner in the Adam update. In addition to these experiments, we also visualize the optimization paths of different optimizers in Appendix D.2, where one can see that the directions of SGD updates are very different from those of the updates generated by the SGD with momentum and Adam. These experiments show that the γ-optimization principle characterizes the impact of optimizers on DNN training. 12 . In specific, we store the optimization paths generated by both the SGD with momentum and Adam ( = 10 -2 ). For the parameters in each optimization path, we compute their first and second principle components as the 2D axes. Moreover, we also calculate the SGD updates evaluated at the parameters along each optimization path and project their directions onto the two principle components for visualization.

From the visualization results shown in Figure 12 , it can be seen that the directions of SGD updates are very different from those of the updates generated by the SGD with momentum and Adam. This is consistent with the experiments in the previous subsection where we observe that the γ in the SGD trainings are very different from those in both the SGD with momentum trainings and Adam trainings. 

:

The Adam updates depend on the past stochastic samples.

EXPERIMENTS ON NETWORK-LEVEL TRAINING TECHNIQUESIn this section, we examine the validity of the γ-optimization principle in training DNNs with different neural network-level training techniques, i.e., activation function, batch normalization and skip connection. We outline the exploration plan below and provide the details of the experiment setup in the corresponding subsections.

Figures and Tables:

IMPACT OF ACTIVATION FUNCTION ON γ-OPTIMIZATION PRINCIPLE Experiment setup: We train a variant of the Alexnet Zhang et al. (2017a) and the Resnet-18 He et al.

Figure 1: Training Alexnet and Resnet-18 with different activation functions.

Figure 2: Training Resnets and Vggs with and without BN on Cifar10.

Figure 5: Training Resnets and Vggs with different optimizers on Cifar10.

Figure 6: Training Resnets and Vggs with different optimizers on Cifar100.

Figure 12: Visualization of optimization paths of different optimizers and SGD updates

Summary of DNN training techniques While these training techniques have been widely applied in practical DNN training, there is limited understanding on how they help facilitate the training and achieve the global minimum of the network.

Table content: <table><tr><td>Neuron</td><td>Layer</td><td>Network</td><td>Optimization</td></tr><tr><td>activation</td><td>normalization</td><td>architecture</td><td>algorithm</td></tr><tr><td>sigmoid, tanh, ReLU</td><td>batch normalization</td><td>skip connection</td><td>SGD, SGD-momemtum, Adam</td></tr></table>

DNN training techniques, their reasonings are from very different perspectives and it is unclear whether a general principle can exist that guides these training techniques to facilitate the training process. In particular, these studies do not explain why DNN trainings with different techniques can achieve the global minimum in practice. Moreover, the existing explanations cannot quantify the impacts of the training techniques on training deep networks, and a principled quantification metric is still far from clear.

Table content: <table/>

Peer review (iclr2020):
The paper proposes a new condition: -optimization principle. The principle states that the inner product between the difference between the current iterate and a fixed global optimum and the stochastic gradient (or more general) is larger than the squared the gradient norm, plus the product of squared norm of the difference between the initialization and the global minimum, and the loss of the current iterate. Under this condition, the paper shows sublinear convergence. Main Comments? The proposed conditions are similar to many previous works, as pointed out by authors. With these kinds of conditions, proving global convergence is trivial. One question is that the condition holds uniformly for all models and every sampled data point. There is no randomness in the condition. I would expect a condition that has some *randomness* in it, e.g., the condition holds in expectation over random sampling over the data. The condition also requires a specific global minimizer. Because of the randomness in initialization and stochastic training, I expect the target global minimizer can change from iteration to iteration, but the current condition does not reflect that. -------------------------------------------------------------------------------------------- I have read the rebuttal and I maintain the score. Note in the student-teacher setting even though teacher is unique, there can be multiple optimal students. I don*t think this resolves my concern.