An Optimization Principle Of Deep Learning?
Authors: Cheng Chen
Junjie Yang
Yi Zhou
Venue:  (2020)

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 $\gamma>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 $\mathcal{O}(1/\gamma K)$ sub-linear convergence rate, where $K$ is the number of iterations. Through extensive experiments, we show that DNN trainings consistently obey the $\gamma$-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 $\gamma$, which is consistent with the $\mathcal{O}(1/\gamma K)$ convergence rate result under the optimization principle. We think the $\gamma$-optimization principle captures and quantifies the impacts of various DNN training techniques and can be of independent interest from a theoretical perspective.

Under review as a conference paper at ICLR 2020
AN OPTIMIZATION PRINCIPLE OF DEEP LEARNING?
Anonymous authors
Paper under double-blind review
ABSTRACT
Training deep neural networks (DNNs) has achieved great success in recent years. Modern DNN trainings utilize various types of training techniques that are devel- oped in different aspects, e-g., activation functions for neurons, batch normalization for hidden layers, skip connections for network architecture and stochastic algo- rithms 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 7 > for stochas- tic algorithms in nonconvex and over- perepaarmmteri optimization. The principle guarantees the convergence of stochastic algorithms to a global minimum with monotonically diminishing parameter distance the minimizer and leads a ((1/~K) sub-linear convergence rate, where K is the number of iterations. Through extensive experiments, we show that DNN trainings consistently obey the n-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 7, which is consistent with the ((1/>K) con- vergence rate result under the optimization principle. We think the y-optimization principle captures and quantifies the impacts of various DNN training techniques and can be of independent interest from a theoretical perspective.
INTRODUCTION
Deep learning has been successfully applied to various domains such as computer vision, natural language processing, etc, and has achieved state-of-ar 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 loffe & 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, c.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 provides summary of these important DNN training techniques.
Table 1: Summary of DNN training techniques
Neuron Layer Network architecture
Optimization algorithm
activation
normalization
sigmoid, batch skip normalization
SGD,
tanh,
SGD-momemtum,
connection
ReLU
Adam

---

Under review as a conference paper at ICLR 2020
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. 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 popular replacement that avoids this issue Nair & Hinton (2010); Glorot et al. (201 1). 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 allows to use a large learning rate Bjorek 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 accelcrate deep learning Kingma & Ba (2015). While these studies provide partial explanations to the effectiveness of various DNN training techniques, their reasonings are from very different perspectives and 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.
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 global minimum. We summarize our contributions as follows.
1.1 OUR CONTRIBUTIONS
Theory: We propose an optimization principle that is parameterized by 7 > for stochastic algorithms in nonconvex and over- vec-pparamtteiieed optimization. The 7-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 y. We show that the 7-optimization principle guarantees the optimization path generated by stochastic algorithms approach global minimizer with a monotonically diminishing distance. Moreover, it leads to convergence of the optimization path to the global minimum with a ((1/TK) sub-linear convergence rate
Experiments: We conduct extensive experiments to examine the validity of the 7-optimization principle in DNN training. In specific, we find that all the tested DNN trainings obey the 7 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 Table on the parameterization of the optimization principle. We find that DNN trainings that apply the training techniques achieve fast convergence and obey the optimization principle with large 7. As comparison, DNN trainings without the training techniques converge slowly and obey the optimization principle with a small 7. These observations consistent with the convergence rate characterization of the 7-optimization principle that larger y leads to faster convergence. Therefore, the 7-optimization principle captures and quantifies the impacts of these training techniques on DNN training in unified way through the parameter 7, and sheds light on the underlying mechanism that leads to successful DNN training.
1.2 RELATED WORK
DNN training techniques: Various training techniques have been developed for DNN training. Examples include piece-wise linear activation functions, e.g., ReLU Nair & Hinton (2010). ELU Clevert et al. (2015), leaky ReLU Maas et al. (2013), 3), batch normalization Ioffe & Szegedy (2015), skip connection He et al. (2015); Szegedy et al. (2015); Srivastava et al. (2015) and advanced optimizers such as SGD with momentum Qian ( (1999), Adagrad Duchi et al. (2011), Adam Kingma & Ba 22015), AMSgrad Reddi et al. (2018). The ReLU activation function and skip connection have been shown to help avoid the vanishing gradient problem and improve the loss landscape Hardt & Ma (2016); Zhou & Liang (2017); Zhang et al. (2019); Zou et al. (2018). The batch normalization has been shown to help avoid the internal covariance shift problem loffe & Szegedy (2015). More recent studies show that batch normalization allows to adopt large learning rate Bjorck et al. (2018)
2

---

Under review as a conference paper at ICLR 2020
and improves the loss landscape in the training Santurkar et al. (2018). The convergence properties of the advanced optimizers have been studied in nonconvex optimization Chen et al. (2019).
Optimization properties of nonconvex ML: Many nonconvex ML models have amenable properties for accelerating the optimization. For example, nonconvex problems such as phase retrieval Zhang et al. (2017b), low-rank matrix recovery Tu et al. (2016), blind deconvolution Li et al. (2018h) and neural network sensing Zhong et al. (2017) satisfy the local regularity geometry around the global minimum Zhou al. (2016); Tu al. (2016); Li al. (2018b); Zhong al. (2017); Zhou & Liang (2017), which guarantees the linear convergence of gradient algorithms. More recently. DNN trainings that use SGD have been shown to follow star-convex optimization path Zhou et al. (2019).
AN OPTIMIZATION PRINCIPLE FOR OVER-PARAMETERIIED ML
In this section, introduce the 7-optimization principle that provides convergence guarantees for over- peer-aammeterized nonconvex machine learning (ML). We show empirically in the subsequent sections that practical DNN trainings obey this principle.
2.1 GI.OBAL MINIMUM OF
MODELS
The goal of machine learning task is to search for good ML model @ that minimizes the total loss on a set of training data samples 2 {2: | The problem is formally written as
min (0; 2)=2)==1 BER4
E(0; 2)),
(P)
where 2x) : IRd + R corresponds to the loss on the i-th data sample 2, For many nonconvex ML models, e.g., deep neural networks, prominent feature is the ver-parraettiizationn of the model, ie., 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 pree-paramtterized model are common minimizers of all the individual loss functions E(;;z)), = I,..., n. We summarize this fact formally as follows.
Fact 1. Consider the problem (P) with an over-parameterized model O. Every global minimizer 6" of the total loss f is also a global minimizer of each individual loss E(; 2:) for all i = 1,.., n.
To elaborate, note that typically use non 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) 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 zero. Throughout the rest of this section, we assume that Fact 1 holds for the problem (P).
2.2 THE 7-OPTIMIZZAIIO PRINCIPLEE
Consider a generic stochastic algorithm (SA) that is initialized with certain model 6g. In each iteration k. the SA samples a data sample RE, Z, where & E {1,...,,1) n is obtained via cyclic sampling with reshuffle. Based on the current model 0g and the sampled data =e., the SA generates a stochastic update Ufe: 25.) and applies it to update the model with a learning rate 77 0 according to
(SA) 0x+1 = 0₂ (Px: 25.). k = 0, 2,
(1)
Equation (1) covers the update rule of many existing optimizers for DNN training. For example, the stochastic gradient descent (SGD) algorithm chooses the update ((x: zę. ) to be the stochastic gradient Voe(Os; ). In comparison, the SGD with momentum algorithm generates the update using extra momentum step, and the Adam algorithm generates the update moving average of the stochastic gradients normalized by the moving average of their second moments
We next introduce the 7-optimization principle for the SA.
Definition (7-optimization principle for SA). Apply SA to solve the verrparamettrized problem (P). For a certain global minimizer 6" of the problem (P), the optimization path {0k) generated by the SA satisfies: for certain > 0 and all k = 0, 1, .....
(0g - 0*, (0x; zg.) )) Z " IU (0,; 212 + >/100 -
zg.) -(00) =(0);
(2)
'The Adam updates depend on the past stochastic samples.
3

---

Under review as a conference paper at ICLR 2020
To elaborate, the left hand side of eq. (2) measures the coherence between 0₂ - 0* and the current model update (0,; )t,). Intuitively, a positive coherence implies that the current model update points toward the global minimizer 6 from the current model 0g. 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 the sampled data scaled by the constant 7/160 0- Hence, a larger value of 7 implies that the update ('0g; ze,. is more coherent with the direction towards the minimizer 0₁- 0" and therefore facilitates the convergence. We show in Theorem later that the y plays a central role in characterizing the convergence rate of the SA.
Discussion:
The y-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 y110x= - 0* I¹2 and guarantees the linear convergence of {0x)x to 0". However, such 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 y = | 8- || (O,: ) Vl(6g: zzx)) and absence of the term (() 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 7-optimization principle is applicable to the more general SA and does not rely on additional assumption to have convergence guarantec as we elaborate below.
We obtain the following convergence results of SA under the 7-optimization principle.
Theorem 1 (Convergence of SA). Apply SA to solve the pver-parameterized problem (P). If the optimization process satisfies the principle in Definition 1, then the following statements hold.
1. The optimization path {0x a approaches the globul minimizer 0 with monotonicully diminishing distance, ie., [10x+1
S 100- - 0- for all k- = 0, 2, .....
2. For all i, each E(:; z:) converges to its global minimum along the optimization puth, i.e., denote (i(T)TTEN as the sequence of iterations that sample 2i then, lim ((O zi) = E(00; 2.).
3. For any K = nB, E N, the accumulated loss converges to the global minimum at the rate
K-1
(10m;eed) - -ww===))-1(1333 2)0 S 2077
(3)
K
K=
To elaborate, item 1 of Theorem 1 shows that the optimization path of SA approaches the global minimizer with monotonically diminishing distance under the y-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 y of the optimization principle in eq. (2). Intuitively, larger 7 implies more coherent update (0x; zEx) with the desired direction 0g 0* and therefore leads to a faster convergence.
Remark:
Under the 7-optimization principle, the sub-linear convergence rate in item 3 depends on the learning rate 1) and the parameter y only, which are fixed learning rate, the parameter y of the optimization principle provides universal quantification of the optimization quality. Inspired by this idea, in the subsequent sections, we conduct extensive experiments to examine the validity of the 7-optimization principle in DNN training. In particular, empirically quantify the impacts of different training techniques on the DNN training by evaluating the parameter 7 of the optimization principle in each optimization process.
parameters. Therefore, given
EXPERIMENTS ON NETWORK-LEVEL TRAINING TECHNIQUES
In this section, we examine the validity of the y-optimization principle in training DNNs with different neural network-level training techniques, i.c., 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.
4

---

Under review as a conference paper at ICLR 2020
Exploration plan: In all DNN trainings, we train the network for sufficient number of epochs to achieve an approximate global minimum. We store the network parameters h. loss {E(Os; εt, ) and update (0g, zg,)), T that are generated in each DNN training. Then, we compute the upper bound for 7 in each iteration according to eq. (2), where we set 8" 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.
3.1 IMPACT OF ACTIVATION FUNCTION ON 7-OPTIMIZATION PRINCIPLE
Experiment setup: We train a variant of the Alexnet Zhang et al. (2017a) and the Resnet-18 18 He et al. (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-3). We apply the standard SGD optimizer with fixed initialization point, mini-batch size 128 and a constant learning rate 0.05 to train these networks for 150 epochs on the Cifar10 10 and Cifar datasets Krizhevsky (2009), respectively.
In the three rows of Figure 1, we present the training results of the normalized distance-to-minimizz training loss and parameter 7 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 7-optimization principle with 7 > 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-minimee mo-miiiiizze diminishes monotonically and the training loss converges the global minimum in these trainings. These observations are consistent with the theoretical implications of the --optimizationn principle in items and of Theorem
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 y under the sigmoid activation has 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 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 of Theorem 1, where a larger implies faster convergence.
that the y in the trainings with ReL.U types of
AlexNet, CIFAR-10
AlexNat, CIFAR-100
ReaNeet-18 CIFAR-10
ReaNet-18, CIFAR-100
Tare
0.8
Leeo DetD
0.2
Leeg Tull
0.6
Leey Datk
0.8
Leady TuaL
0.6
0.6
0.6
0.6
0.4
0.4
0
10
20
30
40
50
60
10
20
30
40
20
60
70 D0
10
20
30
10
20
3D
40
50
60
Nunibon Epeclt
Number of Eyucha
Numbberr Epuchts
Number of Epucha
AlexNet, CIFAR-10
AlexNet, CIFAR-100
Res CIFAR-10
ReaNei-18, CIFAR-100
2.6
Tack
Tart Holl
Tar?
Twrt
Leer Rack
Reuk
1.5
0.5
0.5
20
30
40
10 70 30 40 60 60 70
00
20
20
30
40 60 00
Epochs
Number Fguche
Number Epochs
Number Fjweche
-10 AlseNNat CIFAR-10
10 AAlscNat, CIF CIFAR-100
Resliit- 18, CIFAR-10
RessNtt-10 CIFAR-100
0.04
Ta-h
Tam
Danoue 7
Leaty Faily
PanDOee 7
10
Purcowee
0.02
0.0-
10
20
20 Epoche
20
30
40
tpoochs
Rporhhe
Figure 1: Training Alexnet and Resnet- 18 with different activation functions.
5

---

Under review as a conference paper at ICLR 2020
The experiments in this subsection show that DNN trainings with different activation functions obey the y-optimization principle, which captures and quantifies the impact of choice of activation function on the training process via the parameter 7.
3.2 IMPACT OF BATCH NORMALIZATION ON O-OPTIMIZATION PRINCIPLE
Experiment 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 BN layer in each block; and 3) remove all the BN layers. We remove all the dropout layers in the Vgg networks. We apply SGD with fixed initialization point, a constant learning rate (1) = 0.05 for Resnet, 0.01 for Vgg) and batch size 128 to train these networks on the Cifar 10 and Cifar 10 datasets, respectively.
Figure 2 shows the training results on the Cifar10 dataset. Due to space limitation, we present the sillance-to-minmmizz results in Appendix B, where one can see that the distances are monotonically diminishing and therefore are consistent with item I 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 y values, they are all positive throughout these trainings, which demonstrates the validity of the 7-optimization principle. Moreover, the y in the trainings without any BN layer is considerably smaller than that in the trainings with either one BN layer 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.
ResNet- 18, CIFAR-10
ResNet-18, CIFAR-10
ResNiet34,, CIFAR-10
ResNet-34, CIFAR-10
2.5
0.05
2.5
0.00
Timp all
li nove all DM
0.04
Temeoe th
BM bloka
-0.44
Pameenter
0.00
0.01
00.1
20
20
Number Ripocht
Nomber Mpoche
Number
Number
VGG-11,
CIFAR-10
VGG-11, CIFAR--0
VGG-16, CIFAR-10
VGG-16, CIFAR-10
2.5
0.1
Keep
25
Kiw
0.15
heroos DN
nomer 24
0.05
Preseeter
0.1
0.55
0.02
Namber of Epozla
Namber of Epocial
Numbbrr
Epocla
Nitniisrr of Eprocio
Figure 2: Training Resnets and Vggs with and without BN on Cifar
We also report in Figure 3 the results of training these networks on the Cifar100 dataset, where one can see the positiveness of the 7 throughout the training that demonstrates the validity of the 7-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 y in the trainings without any BN layer has the smallest value. Similar observation is made in the training of the Vgg- 16 network. Morcover, in the training of the Vgg-11 11 network, the training with one BN layer in each block is sufficient to achieve comparable performance that of the training with all BN layers, and their y have similar values throughout the training. In comparison, the training without any BN layer is significantly slower and have much smaller yy values.
The experiments in this subsection demonstrate that the y-optimization principle is able to capture and quantify the impact of batch normalization on DNN training in terms of the parameter y.

---

Under review as a conference paper at ICLR 2020
1e CIFAR-100
11 CIFAR-100
R4aNet-34, CIFAR-100
-Reaaet--44 34, CIFAR-100
Korp thy,
lat aa sitacok Pareee
siiete sires onl.
5.
10
20
30
40
10
20
30
10
20
30
10
20
30
Number of Epucita
Number of Epucita
Number of Epochs
Number of Epuchu
VGG-11, CIFAR 100
VGG-11, CIFAR-100
VGG-16, CIFAR-100
VOG+16, CIFAR-100
Terice 60
Keke aetivaa bocks
Pormunte 7
Porsurtte 7
0.02
802
10 20
30
1.
20
30
40
10
20
20
40
50
10
90 Epochs
50
Number Byocho
Nimbber
Epocio
Byocks
Figure 3: Training Resnets and Vggs with and without BN on C0
3.3 IMPACT OF SKIP CONNECTION ON Y-OPIIIIZATION PRINCIPLE
Experiment setup: We train the Resnet-18 18 with the settings: 1) keep all the skip connections; and 2) keep the first skip connection in each block. For the Resnet-34, 34, we consider an additional setting where we keep the first two skip connections in each block. We apply SGD with a fixed initialization point, constant learning rate 7 = 0.05 and batch size 128 to train these networks for 150 epochs on the Cifar 10 and Cifar 100 datasets, respectively.
Figure 4 shows the training results and we present the distance-to- mo-iimiii-m results in Appendix C, where one can see that they are all monotonically diminishing in the trainings. One can see from the curves that all these trainings satisfy the 7-optimization principle. In specific, regarding the trainings of the Resnet-18 18 on Cifarl0, the training with one skip connection in each block has comparable performance to that of the training with all skip connections, and both trainings have comparable ? values. In the trainings of the Resnet- 18 on the more complex Cifar100 dataset, the training with more skip connections achieves a slightly faster convergence, and the corresponding 7 value is larger than that in the training with one skip connection in each block. Regarding the trainings of the deeper Resnet-34, it can be seen that skip connections significantly accelerate the training on both datasets. In particular, trainings are faster with more number of skip connections in each block, and the ? values are larger in the trainings with more skip connections in each block. All these observations are consistent with the theoretical implications of the ooptimizzaioon principle in Theorem 1. Therefore, the yoptimizzaioon principle is able to characterize and quantify the impact of skip connections on DNN training. Our training results imply that skip connections are more effective deeper resnets.
ResNet- 18, CIFAR-10
ResNet-18. CIFAR-10
ResNet-34, CIFAR-10
ReeNet-34, CIFAR-10
D.D4
a8l skip Dor Cornactane
0.04
Toep stopp coloeciitt 2nd 0.00
blikk
0.00
Kiee the tecin suck cook
Panesster
0.02
Panesuter
0.ce
0.5
0.01
0.5
-0.11
Number Epocia
Number Epocha
Number Epocha
Number Enoche
ResNet-18, CIFAR-100
L.ResNet-18, CIFAR-100
ResNet-04, CIFAR-100
-iResNee--4, CIFAR-100
10
10
Seep lel each blcds
Pr
Pr
10
Numlec of Epocia
Numlec Epoctis
Nundox of Eyodla
Numliex Epocla
Figure& 4: Training Resnets with and without skip connections.
4 EXPERIMENTS ON OPTIMIZATION-LEVELL TRAINING TECHNIQUES
In this section, we explore the impacts of stochastic optimizers the y-optimization principle.
7

---

Under review as a conference paper at ICLR 2020
Experiment setup: We train the Resnet- 18, 34 and the Vgg-11. 11, 16 networks using SGD, SGD with momentum and Adam, respectively. We remove all the dropout layers in the Vgg networks. We apply a fixed initialization point, constant learning rate 1) 0.001 and batch size 128 to all the optimizers and train these networks on the Cifarl0 and Cifar 100 datasets, respectively. We set the momentum to be 0.5 for the SGD with momentum and set 31 0.9, 82 = 0.999, 10-2 for the Adam.
Figure 5 presents the training results on the Cifar10 dataset, and we present the results in Appendix D.I where one can see that they are all monotonically diminishing. In all these trainings, the 7y curves are above zero and therefore demonstrates the validity of the 7-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 7, which is further enlarged in the SGD with momentum trainings. Moreover, the Adam trainings obey the optimization principle with the largest y. These observations are consistent with item 3 of Theorem 1, where a larger y implies faster convergence of the training.
ResNet-18, CIFAR-10
ResNet 18, CIFAR-10
ResNet-34, CIFAR-10
ResNet-34, CIFAR-10
2.5
853
800
1.5
Ada
Aleaa justint
1.5
Adan (-600)
Parmsater
Panmetrr
20
10
Number Epochs
Number Epocis
Number Epochs
Nomber
VGG-11, CIFAR-10
VGG-11, CIFAR-10
VGG-16, CIFAR-10
VGG-16, CIFAR-10
2.5
2.5
1.5
1-001
Dronee 7
On)
1.5
Acam lnck
Prosoce
0.5
Number of Epocia
Nommber
Eppocht
Nemmbr of Eppoch
Nemmabrr
Elpoche
Figure 5: Training Resnets and Vggs with different optimizers Cifar10.
The training results on the Cifar100 dataset are shown in Figure 6, where one can make very similar observations as those Cifar 10. In particular, for the Adam training of 16 on Cifar100, the sign of y 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 ooptimizatiion principle characterizes the impact of optimizers on DNN training.
ResNet- 18, CIFAR-100
ResNet- 18, CIFAR-100
ResNet-34, CIFAR-100
ResNet--3,, CIFAR-100
0.5
580
2000
580
M500 0m00.
0.5
J-
Adann (walin)
Pasmmter
0.5
Puummer
1000
1one
0.3
0.2
0.2
0.1
10 20 30 40 50 60
70
50 90
10 20 30
40 50 50 70 800 90 Number of Epochs
10
20
30
40
50
80
20 Number of Epochs
39
50
80
Number of Epochs
Number of Epocks
VGG-11, 100
VOG-11, 1IFAR-100
VGG-16, CIFAR-100
VOG-16, CIFAR-100
500 pa
550
0.
1--00-mee Sockmi B01)
yow 21 Aemmindd
de
Parmtotte
0.5
Toee
0.
0.2
-02
60 Epochs
Mumbor
Epucla:
Number
Figure 6: Training Resnets and Vggs with different optimizers on 100.
8

---

Under review as a conference paper at ICLR 2020
5 CONCLUSION
In this paper, we propose 7--otiimiatiion principle for general stochastic algorithms in nonconvex and over-vovvane wver-parameterized optimization. The 7-optimization principle provides solid convergence guarantees to stochastic optimization and achieves a sub-linear convergence rate that scales inverse proportionally to y and is independent of the problem parameters. Through extensive DNN training experiments, we show that practical DNN trainings obey the principle reasonably well, and the parameter "y provides a unified metric that measures the impacts different training techniques on DNN training. In the future work, expect that such optimization principle can be exploited to develop improved training techniques for deep learning.
REFERENCES
N. Bjorck, C. P. Gomes, B. Selman, and K. Q. Weinberger. Understanding batch normalization. In Proc. Advances in Neural Information Processing Systems (NeurIPS), pp. 7694-7705, 2018.
X. Chen, S. Liu, R. Sun, and M. Hong. On the convergence of class of Adam-type algorithms for non-convex optimization. In Proc. International Conference on Learning Representations (ICLR), 2019.
D. Clevert, T. Unterthiner, and S. Hochreiter. Fast and accurate deep network learning by exponential linear units (elus). In Proc. International Conference on Learning Representations (ICLR), 2015.
G. Cybenko. Approximation by superpositions of a sigmoidal function. Mathematics of Control, Signals and Systems, 304):303-3 Dec 1989.
Duchi, E. Hazan, and Y. Singer. Adaptive subgradient methods for online learning and stochastic optimization. Journal of Machine Learning Research, 12:2121-2159, July 2011.
S. Ghadimi and G. Lan. Accelerated gradient methods for nonconvex nonlinear and stochastic programming. Mathematical Programming, 1 156(1):59-99, Mar 2016.
X. Glorot, A. Bordes, and Y. Bengio. Deep sparse rectifier neural networks, In Proc. International Conference on Artificial Intelligence and Statistics (AISTATS), pp. 315-323, 11-13 Apr 2011.
M. Hardt and T. Ma. Identity matters deep learning. arXiv:1611.0422 042311, 2016.
K. He, X. Zhang, S. Ren, and Sun. Deep residual learning for image recognition. In Proc. IEEE Conference on Computer Vision and Patlern Recognition (CVPR), pp. 770-778, 2015.
G. Huang, Z. Liu, and K. Weinberger. Densely connected convolutional networks. In Proc. IEEE Conference on Computer Vision and Pattern Recognition (CVPR), pp. 2261-2269, 2016.
loffe and C. Szegedy. Batch normalization: Accelerating deep network training by reducing internal covariate shift. In Proc. International Conference Machine Learning (ICML), pp- 2015.
D. P. Kingma and J. Ba. Adam: A method for stochastic optimization. In Proc. International Conference Learning Representations (ICLR), 2015.
A. Krizhevsky. Learning multiple layers of features from tiny images. Technical report, 2009.
Hao Li, Zheng Xu, Gavin Taylor, Christoph Studer, and Tom Goldstein. Visualizing the loss landscape of neural nets. In Proc. Advances in Neural Information Processing Systems (NeurIPS). pp. 6389-6399 2018a.
X. Li, Ling, Strohmer, and K. Wei. Rapid, robust, and reliable blind deconvolution via nonconvex optimization. Applied and Computational Harmonic Analysis, 2018b.
A. Maas, Y. Hannun, and A. Ng. Rectifier nonlinearities improve neural network acoustic models. In Proc. ICML Workshop on Deep Learning for Audio, Speech and Language Processing, 2013.
V. Nair and G. E. Hinton. Rectified linear units improve restricted boltzmann machines. Proc.
International Conference Machine Learning (ICMI.), pp. 807-814, 2010.

---

Under review as a conference paper at ICLR 2020
Y. Nesterov. Introductory Lectures Convex Optimization: A Basic Course. Springer, 2014.
E. Orhan and X. Pitkow. Skip connections eliminate singularities. In Proc. International Conference on Learning Representations (ICLR), 2018.
N. Qian. On the momentum term in gradient descent learning algorithms, Neural Networks, 12(1): 145-151, January 1999.
Reddi, Kale, and S. Kumar. On the convergence of Adam and beyond. In Proc. International Conference Learning Representations (ICLR), 2018.
H. Robbins and S. Monro. A stochastic approximation method. The Annals Mathematical Statistics, 22(3):400-477, 09 1951.
D. E. Rumelhart, G. E. Hinton, and R. J. Williams. Learning Representations by Back-propagating Errors. Nature, 323(6088) 1986.
Santurkar, Tsipras, A. Ilyas, and Madry. How does batch normalization help optimization? In Proc. Advances in Neural Information Processing Systems (NeurIPS), 2018.
R. Srivastava, K. Greff, and J. Schmidhuber. Highway networks. ArXiv 1505.00387,
C. Szegedy, W. Liu, Y. Jia, P. Sermanet, S. Reed, D. Anguelov, D. Erhan, V. Vanhoucke, and A. Rabinovich. Going deeper with convolutions. In Proc. IEEE Conference on Computer Vision and Pattern Recognition (CVPR), 2015.
S. Tu, Boczar, M. Simchowitz, M. Soltanolkotabi, and Recht, Low-rank solutions of linear matrix equations via Procrustes flow. In Proc. 33rd International Conference on Machine Learning (ICML), pp. 964-973, 2016.
C. Zhang, S. Bengio, M. Hardt, B. Recht, and O. Vinyals. Understanding deep learning requires rethinking generalization. In Proc. International Conference on Learning Representations (ICLR), 2017a.
H. Zhang, Y. Zhou, Y. Liang and Y. Chi. A nonconvex approach for phase retrieval: reshaped Wirtinger flow and incremental algorithms. Journal of Machine Learning Research (JMLR), 18 (141):1-35. 2017b.
X. Zhang. Y. Yu, L. Wang, and Q Gu. Learning one-hidden-layer relu networks via gradient descent. In Proc. International Conference on Artificial Intelligence and Statistics (AISTATS), volume 89, pp. 1524 1534, 16 18 Apr 2019.
K. Zhong, 7. Song, P. Jain, P. L.. Bartlett, and I. S. Dhillon. Recovery guarantees for one-hidden-layer neural networks. In Proc. 34th International Conference on Machine Learning (ICML), volume 70, pp. 4140-4149, Aug 2017.
Y. Zhou and Liang. Characterization of gradient dominance and regularity conditions for neural networks. ArXiv: 171.0069 Oct 2017.
Y. Zhou, H. Zhang, and Y. Liang. Geometrical properties and accelerated gradient solvers of non- convex phase retrieval. Proc. 54th Annual Allerton Conference on Communication, Control, and Computing (Allerton), pp. 331-335, 2016.
Y. Zhou, J. Yang, H. Zhang, Y. Liang, and V. Tarokh. SGD converges global minimum in deep leam- ing via star-convex path. In Proc. International Conference on Learning Representatioos(|(CRR)) 2019.
D. Zou, Cao, D. Zhou, and Q Gu. Stochastic gradient descent optimizes over-parameterized deep relu networks. 1rIXiv118//1 08888, 2018.
10

---

Under review as a conference paper at ICLR 2020
Supplementary Materials
A PROOF OF THEOREM
To prove item 1, note that the SA update rule implies that
|0x+1 1- = |0 nU(02: - 112
| 8- 1/ 312 - 2n/00 - -0", (0xi zec))
< ||0g 8-11 + [ 1/ zc,)]l
- Sew Il
21 0" (((ON; FEL) -E(0=; ;.
where the last incquality follows from the 7-optimization principle in Definition 1. Note that 0* a common global minimizer for the loss on all indivisual data samples. Therefore, E(Oss sta))
e(0"; (()) 0 for all & and the above inequality further implies that
|1 1¹1 s ||0 11,
which completes the proof of item 1.
To prove item 2, note that the SA algorithm adopts the eyclic sampling with reshuffle scheme. Summing eq. (4) over the B-th epoch (i.e., k nB, nB 1,..., n(. + +1 1) gives that
m(B41)-1
10 1-2 < ||0,B - 8-1 2 11
(e(P)) e(0"; :c.))
AmnB
Further telescoping over the epoch index, we obtain that for all B
B-1 (P+))-
16n 1 < 100 8²1 21 - 111 Σ
Σ
(e(0ki E(00;
((0): (5)
k=nP
Note that the left hand side is nonegative for all B and ((0gi ((0); 2 for all k. Due to the cyclic sampling with reshuffle scheme, every data sample is visited once in each epoch. Fix an i E (1....,7) n. and denote the sequence of iterations which the data sample 2; is sampled as i()), i(B. 1). We can rewrite the above inequality
B-1
||0m - 1- < 16 - 11 207 - 1- Σ
Σ -((p);)))((0;11)))
Suppose for certain i the sequence (E( 2 does not converge to the global minimum 8(0"; 2.). Then, for any e > 0, ((0;(P); 2x) - E(0": 24) > e for infinitely many P. This implies that the above double summation diverges to too and the right hand side of the inequality eventually becomes negative, contradicting with the non-negativity of the left hand side. Therefore, ((0m())z)) P. E(0"; 24) for all í. This completes the proof of item 2.
Item 3 follows from eq. (5) after rearranging the terms and noting that 0" is common minimizer for all the indivisual loss functions.

---

Under review as a conference paper at ICLR 2020
B DISTANCE-TO-MINIMIIE RESULTS ON BATCH NORMALIZATION
All
diminishes monotonically and are consistent with the theoretical implica- tions of the 7-optimization principle in items I of Theorem
ResNet-18, CIFAR-10
ResNet-34, CIFAR-10
VGG-11, CIFAR-10
VGG-16, CIFAR-10
all slibids 5 Har sieN
Lo Kees all DM Hamoove
Kiep SS Ranova BN
Io Keep BNN Hlrris un
0.5
0.4
0.4
0.4
0
0
10 Number of Epoche
30
10
30
20
40
Nomber Epoche
Nember
Epochh
Nember Eporhs
Figure 7: Training Resnets and Vggs with and without BN on Cifar10.
ResNel-18, CIFAR-100
ResNet-34, CIFAR-100
VGG-11, 100
VGG-16, CIFAR-100
Keeg 2155
- Koee 1o Brih coca
tn Bamava
Keep Biiin trodes
Fl orl
Neesse BM
0.8
0.8
0.6
0.6
0.6
0.6
0.2
0.2
0.2
022
10
20
40
10
20
30
40
10
20
30
40
20
50
Nimbee of Eppocts
Nimmber Epocls
Number of Epocts
Niczaber Eppoche
Figure Training Resnets and Vggs with and without BN on Cifar100.
C DISTANCE-TO-MINMIZAE RESULTS ON SKIP CONNECTION
All distances-tor tomimmmizer diminishes monotonically and are consistent with the theoretical implica- tions of the 7-optimization principle in items I of Theorem 1.
ResNei-18, CIFAR-10
ResNet-34, CIFAR-10
ResNel-18, CIFAR-100
ResNet-34, CIFAR-100
slp Be treeet
dlg samrd are
-e-teeo toon
conectire bleck
st-ttap cauit dlikk
0.8
0.8
0.8
0.6
0.2
02
0.2
022
10
20
20
10
20
20
30
Number of Eporia
Number Eporia
Number of Eporia
Nember Epocle
Figure 9: Training Resnets with and without skip connections.
12

---

Under review as a conference paper at ICLR 2020
D MORE RESULTS ON OPTIMIZERS
D.I DISTANCE-TO-MINEE MINIMIZER RESULTS
All eestance--to-minniiee diminishes monotonically and are consistent with the theoretical implica- tions of the 7-optimization principle in items 1 of Theorem 1.
ResNei-18, CIFAR-10
ResNet-34, CIFAR-10
VGG-11, CIFAR-10
VOG-16, CIFAR-10
260
--522
200 Lwrkity
211
Azon judkin
Akerry 6011
0.6
0.6
0.6
0.
0.2
0.2
02
10
20
40
20
30
10
20
40
10
20
30
40
Number of Epoche
Nomber of Epothe
Number of Epochs
Nember of Epocht
Figure 10: Training Resnets and Vggs with different optimizers on Cifar10.
ResNet-34, CIFAR-100
VGG-11, CIFAR-100
VGG-16, CIFAR-100
ResNel-18, CIFAR-100
1.2
co0
1.2
1.2
2o0 0x
2E0 js a.
500 0.
500 (a-
0.8
0.8
0.6
0.6
0.6
0.6
0.4
0.4
0.4
02
0.2
0.2
10 30
40
20
30
t0 60
Number Eporiu
Number Eppccl
Nembeer of Epoclo
Number Epuchs
Figure 11: Training Resnets and Vggs with different optimizers on C0far100.
D.2 VISUALIZING OPTIMIZATION PATH OF DIFFERENT OPTIMIZERS
By exploiting the visualization method proposed Li al. (2018a), we plot the 2D visualization of the optimization paths of different optimizers on the loss landscape contours of the Resnet-18, 34, "gg-11, 16 networks in Figure 12. In specific, we store the optimization paths generated by both the SGD with momentum and Adam (c = 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 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 y in the SGD trainings are very different from those both the SGD with momentum trainings and Adam trainings.
ResNet-18, CIFAR-10
ResNet-18, CIFAR-10
ResNet-34, CIFAR-10
ResNet-34, CIFAR-10
10D dh
Mam
2nd 12.0%
1:1
24
Lst 52.2%
16 B5
VGG-11, CIFAR-10
VGG-11, CIFAR-10
VGG-16, CIFAR-10
VGG-16, CIFAR-10
No
1O 13
35. PC
7181
15.P0
72.78%
15 10 8r
Figure 12: Visualization of optimization paths of different optimizers and SGD updates
13


Reviews:
[{"review_id": "SkgvijzLtB", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 1, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "The paper proposes a new condition: $\\gamma$-optimization principle. \nThe 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.\n\nUnder this condition, the paper shows sublinear convergence.\n\nMain Comments：\nThe proposed conditions are similar to many previous works, as pointed out by authors. With these kinds of conditions, proving global convergence is trivial. \nOne 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.\nThe 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.\n\n\n--------------------------------------------------------------------------------------------\nI have read the rebuttal and I maintain the score. \nNote in the student-teacher setting even though teacher is unique, there can be multiple optimal students. I don't think this resolves my concern.", "extra_scores": {"experience_assessment": "I have published in this field for several years.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}, {"review_id": "S1gTwOG2Yr", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper proposes a \"gamma principle\" for stochastic updates in deep neural network optimization. First, the authors propose if Eq. (2) is satisfied then convergence is guaranteed (Thm. 1). Second, they use experimental results of Alexnet and Resnet-18 on cifar10/100 to show that Eq. (2) is satisfied by SGD, SGD with momentum, and Adam, with different activations and tricks like batch normalization, skip connection.\n\nPros:\n1. This paper is well written and the presentation is clear.\n2. The experiments are extensive.\n\nCons:\n1. Before Eq. (2), it is assumed that over-parameterized NNs are used as \\theta. But there is no quantization how many parameters are enough? Are the Alexnet/Resnet-18 in experiments enough over-parameterized and how can we tell that? Some quantitative conditions should be provided to show what kind of models this principle hold.\n\n2. The connection between Eq. (2) and Thm. 1 is too obvious and the gamma is just to characterize the progress of each update. Of course, large progress corresponds to fast convergence. Eq. (2) is a strong assumption rather than a theoretical contribution.\n\n3. Experiments are used to show that Eq. (2) is a \"principle\". However, the experiments are problematic as follows.\nFirst, \"we set \\theta^* to be the network parameters produced in the last training iteration\", then how do we make sure \\theta in the last training iteration is \\theta^*, even if the loss is close to (but not exactly) zero? For this point, I suggest using a teacher-student setting, where the optimal \\theta^* is already known.\nSecond, using \\theta in the last training iteration makes the experiments show the following simple fact, that methods/tricks/activations with faster convergence to certain parameter will have larger every update progress to that parameter, which is, of course, true and does not reveal an optimization principle of deep learning.\nThird, it is difficult to claim that this is a principle for general deep learning by using experiments on two datasets.\n\nOverall, I found the theory not inspiring and experiments not convincing.\n\n========Update=========\nThanks for the rebuttal.\nI have read it and using teacher-student setting is an improvement to resolve my question with respect to \\theta^*.\nHowever I would maintain my rating since\n1) the theoretical contribution is actually marginal;\n2) the argument that this \"gamma principle\" holds for over-parameterized NNs is vague in the sense (and the author did not resolve my concern of this) that for what kinds of over-parameterized NNs this would work and for what kinds of NNs it does not hold. In particular, mentioning other theory work of over-parameterized NNs is not enough, because usually in these work, the numbers of parameters in NNs are poly(n), like O(n^4), O(n^6), where n is number of training data. There is an obvious gap between poly(n) and the number of parameters in experiments. From this perspective, the experiments cannot verify the claim that this \"principle\" holds for over-parameterized NNs that mentioned by authors in the rebuttal.\n3) experiments on two datasets are not enough to claim this is a general \"principle\".\nConsidering this claim is for general over-parameterized NN optimization, I think it lacks of specifying types of NNs for which this claim would hold (of course it cannot hold for any NNs, but it possibly can hold for some NNs, and what are these NNs?), and experiments are not enough to show the generality of this claim.", "extra_scores": {"experience_assessment": "I have read many papers in this area.", "review_assessment:_checking_correctness_of_experiments": "I carefully checked the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper thoroughly.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I carefully checked the derivations and theory."}, "extra_text": {}}, {"review_id": "H1gGrehCOr", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 1, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "Summary: \n\nThis paper proposes an optimization principle that is called \\gamma-optimization principle for stochastic algorithms (SA) in nonconvex and over-parametrized optimization. The author(s) provide convergence results under this “\\gamma-optimization principle” assumption. Numerical experiments are conducted on classification datasets CIFAR-10 and CIFAR-100 for Alexnet and Resnet-18 with different activation functions. \n\nComments: \n\n1) Could you please explain how you could achieve the value of \\theta* (common global minimizer for the loss on all individual component functions)? It is unclear to me how you could obtain it. \n\n2) You have not mentioned the loss function that you are using for your numerical experiments. From my view, you are using softmax cross-entropy loss for classification problems (CIFAR-10, CIFAR-100). Can you show that Fact 1 is true for softmax cross-entropy loss? I wonder how you could train the total loss to achieve zero for this loss. \n\n3) Fact 1 with over-parameterized model could be true if the loss, for example, is mean square (for regression problems). Therefore, I would suggest you to consider other numerical examples rather than classification problems. If not, the numerical part is not very consistent with the theoretical part. \n\n4) The assumption that the author(s) use in the paper, that is, \\gamma-optimization principle in Definition 1, is indeed strong and not reasonable. You simply assume what you want in order to achieve the convergence result. It is not easy to verify this assumption since you include \\theta* unless it has only a unique solution. Note that the learning rate (eta) and gamma are very sensitive here and it is not clear how to determine these values. \n\n5) There is related work that you may need to consider: Vaswani et al 2019, \"Fast and Faster Convergence of SGD for Over-Parameterized Models (and an Accelerated Perceptron)\" in AISTATS 2019. \n\nI think the paper still needs lots of work to be ready. Theoretical result is not strong and the numerical experiments are not convincing. I do not support the publication for this paper at the current state. \n\nMinor: \n1) I am not really why you have a question mark (?) in the title. \n", "extra_scores": {"experience_assessment": "I have published in this field for several years.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I carefully checked the derivations and theory.", "review_assessment:_checking_correctness_of_experiments": "I carefully checked the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper thoroughly."}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper is rejected based on unanimous reviews.
Decision: Reject