Scheduled Restart Momentum for Accelerated Stochastic Gradient Descent
Authors: Bao Wang
Tan Minh Nguyen
Tao Sun
Andrea Bertozzi
Richard Baraniuk
Stanley Osher
Venue:  (2021)
Keywords: Nesterov Accelerated Gradient
Deep Learning
Image Classification

Abstract: Stochastic gradient descent (SGD) algorithms, with constant momentum and its variants such as Adam, are the optimization methods of choice for training deep neural networks (DNNs). There is great interest in speeding up the convergence of these methods due to their high computational expense. Nesterov accelerated gradient (NAG) with a time-varying momentum, denoted as NAG below, improves the convergence rate of gradient descent (GD) for convex optimization using a specially designed momentum; however, it accumulates error when an inexact gradient is used (such as in SGD), slowing convergence at best and diverging at worst. In this paper, we propose scheduled restart SGD (SRSGD), a new NAG-style scheme for training DNNs. SRSGD replaces the constant momentum in SGD by the increasing momentum in NAG but stabilizes the iterations by resetting the momentum to zero according to a schedule. Using a variety of models and benchmarks for image classification, we demonstrate that, in training DNNs, SRSGD significantly improves convergence and generalization; for instance, in training ResNet-200 for ImageNet classification, SRSGD achieves an error rate of 20.93% vs. the benchmark of 22.13%. These improvements become more significant as the network grows deeper. Furthermore, on both CIFAR and ImageNet, SRSGD reaches similar or even better error rates with  significantly fewer training epochs compared to the SGD baseline.

Under review as a conference paper at ICLR 2021
SCHEDULED RESTART MOMENTUM FOR ACCELERATED STOCHASTIC GRADIENT DESCENT
Anonymous authors Paper under double-blind review
ABSTRACT
Stochastic gradient descent (SGD) algorithms, with constant momentum and its variants such as Adam, are the optimization methods of choice for training deep neural networks (DNNs). There is great interest in speeding up the convergence these methods due to their high computational expense. Nesterov accelerated gradient (NAG) with time-varying momentum, denoted as NAG below, improves the convergence rate of gradient descent (GD) for convex optimization using a specially designed momentum; however, it accumulates error when inexact gradient is used (such as in SGD), slowing convergence at best and diverging at worst. In this paper, propose scheduled restart SGD (SRSGD), a new NAG-style scheme for training DNNs. SRSGD replaces the constant momentum in SGD by the increasing momentum in NAG but stabilizes the iterations by resetting the momentum to zero according to schedule. Using variety of models and bench- marks for image classification, we demonstrate that, in training DNNs, SRSGD significantly improves convergence and generalization; for instance, in training Res.ett-200 for ImageNet classification, SRSGD achieves an error rate of 20.93% vs. the benchmark of 23%... These improvements become more significant as the network grows deeper. Furthermore, on both CIFAR and ImageNet, SRSGD reaches similar or even better error rates with significantly fewer training epochs compared to the SGD baseline.
INTRODUCTION
Training many machine learning (ML) models reduces solving the following finite-sum optimiza- tion problem
1
min f(w) min N
Σ f((w) min (lo(,,, v.). E Rd.
(1)
where (x, Ji are the training samples and is the loss function, e.g., cross-entropy loss for a classification task, that measure the discrepancy between the ground-truth label y; and the prediction by the model g(, w), parametrized by w. The problem (1) is known as empirical risk minimization (ERM). In many applications, f(w) is non-convex, and g(; w) is chosen among deep neural networks (DNNs) due to their preeminent performance across various tasks. These deep models are heavily overparametrized and require large amounts of training data. Thus, both N and the dimension of w can scale up to millions or even billions. These complications pose serious computational challenges.
One of the simplest algorithms to solve (1) is gradient descent (GD), which updates w according to:
w
w
88
Vi(w"))
where 8y > is the step size at the k-th iteration. Computing V Vf(w*) on the entire training set is memory intensive and often prohibitive for devices with limited random access memory (RAM) such as graphics processing units (GPUs) used for deep learning (DL). In practice, we sample subset of the training set, of size m with m & N, to approximate v.(w*) by the mini- batch gradient 1 1/m E Va, (w*),, resulting in the (mini-batch)-ssochastie gradient descent (SGD). SGD and its

---

Under review as a conference paper at ICLR 2021
accelerated variants are among the most used optimization algorithms in ML. These gradient- tradient-based algorithms have low computational complexity, and they are easy to parallelize, making them suitable for large scale and high dimensional problems (Zinkevich et al., 2010; Zhang et al., 2015).
Nevertheless, GD and SGD have issues with slow convergence, especially when the problem is ill-conditioned. There are two common techniques accelerate GD and SGD: adaptive step size (Duchi et al., 2011; Hinton et al.: Zeiler, 2012) and momentum (Polyak, 1964). The integration of both adaptive step size and momentum with SGD leads Adam (Kingma & Ba, 2014), one of the most used optimizers for training DNNs. Many recent developments have improved Adam (Reddi et al., 2019; Dozat, 2016; Loshchilov & Hutter, 2018; Liu al., 2020). GD with constant momentum leverages the previous step to accelerate GD according to:
*+1 w² 8% V(w")) ==*1 0 *+1 + p(p
where 1a > 0 is a constant. A similar acceleration can be achieved by the heavy-ball (HB) method (Polyak, 1964). The momentum update in both (3) and HB have the same convergence rate of O(1/k) as that of GD for convex smooth optimization. A breakthrough due to Nesterov (1983; 2018) replaces μ with (k- 1)/(k (A: + 2). which is known the Nesterov accelerated gradient (NAG) with time-varying momentum. For simplicity, we denote this method as NAG below. NAG accelerates the convergence rate to ( ((1/k²), which is optimal for convex and smooth loss functions (Nesterov, 1983; 2018). NAG can also speed up the process of escaping from saddle points (Jin et al., 2017). In practice, NAG momentum can accelerate GD for nonconvex optimization, especially when the underlying problem is poorly conditioned (Goh, 2017). However, NAG accumulates error and causes instability when the gradient is inexact (Devolder al., 2014; Assran & Rabbat, 2020). In many DL applications, constant momentum achieves offe-of-theear result. For instance, training DNNs for image classification. Since NAG momentum achieves a much better convergence rate than constant momentum with exact gradient for general convex optimization, we consider the following question:
Can we leverage NAG with a time-varying momentum parameter to accelerate SGD in training DNNs and improve the test accuracy of the trained models?
Contributions. We answer the above question by proposing the first algorithm that integrates sched- uled restart NAG momentum with plain SGD. Here, we restart the momentum, which is orthogonal to the learning rate restart (Loshchilov & Hutter, 2016). We name the resulting algorithm scheduled restart SGD (SRSGD). Theoretically, we prove the error accumulation of Nesterov accelerated SGD (NASGD) and the convergence of SRSGD. The major practical benefits of SRSGD are fourfold:
SRSGD remarkably speeds up DNN training. For image classification, SRSGD significantly reduces the number of training epochs while preserving or even improving the network's 's accuracy. In particular, on CIFAR 10/100, the number of training epochs is reduced by half with SRSGD, while on ImageNet the reduction in training epochs is also remarkable.
DNNs trained by SRSGD generalize significantly better than the current benchmark optimizers. The improvement becomes more significant as the network grows deeper as shown in Fig. 1.
SRSGD reduces overfitting in training very deep networks such as ResNet-200 for ImageNet classification, enabling the accuracy to keep increasing with depth.
SRSGD is straighfforward to implement and only requires changes in a few lines of the SGD code. There is also no additional computational or memory overhead.
We focus on image classification with DNNs, in which SGD with constant momentum is the choice
Related Work. Momentum has long been used to accelerate SGD. SGD with scheduled momentum and a good initialization can handle the curvature issues in training DNNs and enable the trained models generalize well (Sutskever et al., 2013). Kingma& & Ba (2014) and Dozat (2016) integrated momentum with adaptive step size to accelcrate SGD. In this work, we study the time-varying momentum version of NAG with restart for stochastic optimization. Adaptive and scheduled restart have been used to accelerate NAG with the exact gradient (Nemirovskii & Nesterov, 1985; Nesterov, 2013; Iouditski & Nesterov, 2014; Lin & Xiao, 2014; Renegar, 2014; Freund & Lu, 2018; Roulet et al., 2015; O' O'donoghue & Candes, 2015; Giselsson & Boyd, 2014: Su et al., 2014). These studies of restart NAG momentum are for convex optimization with the exact gradient. Restart techniques have also been used for stochastic optimization (Kulunchakov & Mairal, 2019). In particular, Aybat et al. (2019) developed a multistage variant of NAG with momentum restart between stages. Our work focuses on developing NAG-based optimization for training DNNs. Many efforts have also been
2

---

Under review as a conference paper at ICLR 2021
SGD
SRSGD
CIFARIO
CIFAR100
ImageNet
24.0
24.0
5.0
4.5
22.0
22.5
Test
20.0
21.0
110
290 470
650
1001
110
290
470
650
1001
50
101
152
200
Number of Layers
Figure 1: Error rate depth of ResNet models trained with SRSGD and the baseline SGD with constant momemtum. Advantage SRSGD continues grow with depth.
devoted to studying the non-acceleration issues of SGD with HB and NAG momentum (Kidambi al., 2018; Liu & Belkin, 2020), well as accelerating first-order algorithms with noise-corrupted gradients (Cohen et al., 2018; Aybat al., 2018; Lan, 2012). Ghadimi & Lan (2013; 2016) provides analysis for the general stochastic gradient-based optimization algorithms..
Organization. In Section 2, we review and discuss momentum for accelerating GD for convex smooth optimization. In Section 3, we present the SRSGD algorithm and its theoretical guarantees. In Section 4, we verify the efficacy of the proposed SRSGD training DNNs for image classification on CIFAR and ImageNet. In Section 4.3, we perform empirical analysis of SRSGD. We end with some concluding remarks. Technical proofs, some experimental details, and more results in training LSTMs (Hochreiter & Schmidhuber, 1997) and WGANs (Arjovsky al., 2017; Gulrajani al., 2017) are provided in the Appendix.
Notation. We denote scalars and vectors by lower case and lower case bold face letters, respectively, and matrices by upper case bold face letters. For a vector æ = (I1, .Ia) E R we denote its ép IIp to denote its induced norm
norm (p 1) by ||œ||, (E/ [z.|())/rr, For a matrix A. we || by the vector Ep norm. Given two sequences {a, and [b, we write (included) as (a, 6]. For a function f(w): Rd + R, we denote its gradient as f((w) and its Hessian as f2w(w.
O(b,) if there exists a
positive constant s.t. a, S Cb2,, We denote the interval
2 REVIEW: MOMENTUM IN GRADIENT DESCENT
GD. GD (2) is popular approach to solve (1), which dates back to Cauchy (1847). If f(w) is convex and L-smooth (i.e., [ f s L), then GD converges with rate O(1/k) by letting Sy 1/L (we use this sy in all the discussion below), which is independent of the dimension of w.
HB. HB (4) (Polyak, 1964) accelerates GD by using the historical information, which gives w k+1 w*
8 (w) + v(w * / 0.
4)
We can also accelerate GD by using the Nesterov/lookaheadd momentum, which leads to (3). Both (3) and (4) have a convergence rate of (1/k)) for convex smooth optimization. Recently, several variants of (3) have been proposed for DI., e.g., (Sutskever et al., 2013) and (Bengio et al., 2013).
NAG. NAG (Nesterov, 1983; 2018; Beck & Teboulle, 2009) replaces μ with (fx 1)/1441, where 4-11 (1+ /I /2 with to 1. NAG iterates as following
b k+1 u= 3k V f w k+1 b+1 La
(5)
fx+1
NAG achieves convergence rate O(1/k²) with the step size 5k = 1/L.
Remark 1. Su et al. (2014) showed that (k 1))(kk + 2) is the asymptotic limit of (tx- 11)/t441 In the following presentation of NAG with restart, for the ease of notation, we will replace the momentum coefficient (tx 1)/t&+1 with (k - 1)/(k: + +)..
Adaptive Restart NAG (ARNAG). The sequences, (ff - f(w")) where w" is the minimum of fw),, generated by GD and GD with constant momentum (GD Momentum, which follows (3)) converge monotonically to zero. However, that sequence generated by NAG oscillates. as illustrated in Fig. (a) when (w) is quadratic function. O'donoghue & Candes (2015) proposed ARNAG
3

---

Under review as a conference paper at ICLR 2021
(6), which restart the time vareing momentum of NAG according to the change of function values, to alleviate this oscillatory phenomenon. ARNAG iterates as following
0 h+1 wº Vf(w");
w h+1 = m(k)
m(k) + (v h+1 -²"),
where m(1) = 1; mk + 1) m(k) + if fww S f(w*),, and m(k + 1) otherwise.
Scheduled Restart NAG (SRNAG). SR is another strategy to restart the time-varying momentum of NAG. We first divide the total iterations (0, I"] (integers only) into few intervals {4,
(T;-1, TiJ. such that (0, T] = U 4. In each 1 we restart the momentum after every F; iterations. The update rule is then given by:
w sg ff(w") uhtt1_ = a1 =
(k mod F')
k+1 -v)).
(k mod Fi) +
Both AR and SR accelrratee NAG to linear convergence for convex problems with the Polyak- Lojasiewiez (PL) condition (Roulet & d' Aspremont, 2017).
Case Study Quadratic Function. Consider the following quadratic optimization (Hardt, 2014)
min f(x) = 2 - Lx b,
where L E Rdxd is the Laplacian of cycle graph, and is d-dimensional vector whose first entry and all the other entries are O. Note that f(x is convex with Lipschitz constant 4. In particular, set d = 1K (1K:= 10y). We T 50K iterations with step size 1/4. 4. In SRNAG, we restart, ie., we set the momentum to 0, after every 1K iterations. Fig. 2 (a) shows that GD + Momentum as in (3) converges faster than GD, while NAG speeds up GD Momentum dramatically and converges to the minimum in an oscillatory fashion. Both AR and SR accelerate NAG significantly.
GD
GD + Momentum
NAG
ARNAG
SRNAG
(a)
(b)
(c)
f(x")
10-2
10
10
10-3
10
10
10-1
10k
20k
30K
40k
50K
10K Z0k
30k
40k
50k
10k
20k
30k
40K
50k
Iteration
Figure 2: Comparison between different schemes in optimizing the quadratic function in (8) with (a) exact gradient, (b) gradient with constant variance Gaussian noise, and (c) gradient with decaying variance Gaussian noise. NAG, ARNAG, and SRNAG can speed up convergence remarkably when exact gradient is used. Also, SRNAG is more robust to noisy gradient than NAG and ARNAG.
ALGORITHM PROPOSED: SCHEDULED RESTART SGD (SRSGD)
Computing gradient for ERM, (1), can be computational costly and memory intensive, especially when the training set is large. In many applications, such as training DNNs, SGD is used. In this section, we first prove that the error bound of SGD with NAG cannot be bounded by convergent sequence, then we formulate our new SRSGD as a solution to accelerate the convergence of SGD using the NAG momentum.
3.1 UNCONTROLLED BOUND OF NESTEROV ACCELERATED SGD (NASGD)
Replacing f((w") I/N Vf((w") in (5) with the mini-batch gradient 1/m En V (wo*) will lead to uncontrolled error bound. Theorem formulates this observation for NASGD. Theorem (Uncontrolled Bound of NASGD). Let f(w be convex and L-smooth function with f < R, where > is a constant. The sequence {w Ja20 generated by (5), with stochastic gradient of bounded variance (Bubeck, 2014; Bottou et al., 2018) and using any constant step size 8% < 1/L, satisfies
E (f(w²) f(w"" = O(k),
(9)
We leave the analysis under the other assumptions (Jain et al., 2018) future work.
4

---

Under review as a conference paper at ICLR 2021
where w" is the minimum of f, and the expectation is taken over the generation of the stochastic gradient.
One idea to prove Theorem is by leveraging the established resulting in Lan (2012). We will provide new proof of Theorem I in Appendix A. The proof shows that the uncontrolled error bound because the time-varying momentum gets close as iteration increases. To remedy this, we can restart the momentum in order to guarantee that the time-varying momentum with restart is less than number that strictly less than 1. Devolder et (2014) proved a similar error bound for the 5-inexact gradient, and we provide a brief review of NAG with 8 8-inexact gradient in Appendix B. As far as we know that there is no lower bound of (()(=") - f(w") ")) available even for the Ó-inexact gradient, and we leave the lower bound estimation as an open problem.
We consider three different inexact gradients: Gaussian noise with constant and decaying variance corrupted gradients for the quadratic optimization (8), and training logistic regression model for MNIST (LeCun & Cortes, 2010) classification. The detailed settings and discussion are provided in Appendix B. We denote SGD with NAG momentum as NASGD) and NASGD with AR and SR as ARSGD and SRSGD, respectively. The results shown in Fig. 2 (b) and (c) (iteration vs. optimal gap for quadratic optimization (8)) and Fig. 3 (a) (iteration vs. loss for training logistic regression) confirm Theorem 1. For these cases, SR improves the performance of NAG with inexact gradients. Moreover, when an inexact gradient used, ARNAG/ARS ARSGD performs almost the same GD/SGD asymptotically because ARNAG/ARSGD restarts too often and almost degenerates to GD/SGD.
3.2 SRSGD AND ITS CONVERGENCE
For ERM (1), SRSGD replaces (w) in (7) with stochastic gradient with batch size m and gives (A mod Fi) Ve (w"); - (I: mod Ri) + (o (p )*,,
u w
8k m
(10)
where Fi is the restart frequency used in the interval 4. We implemented SRSGD, in both PyTorch (Paszke et al., 2019) and Keras (Chollet et al., 2015), by changing just a few lines of code on top of the existing implementation of the SGD optimizer. We provide a snippet of SRSGD code in Appendix (PyTorch) and K (Keras). We formulate the convergence of SRSGD for general convex and nonconvex problems in Theorem 2 and provide its proof in Appendix C.
Theorem 2 (Convergence of SRSGD). Suppose f(w) is L-smooth. Consider the sequence (w Juz0 generaled by (10) with stochastic gradient that is bounded and has bounded vari- ance, and consider any restart frequency F using any constant step size 8k == S 1/L. As- -Bf(w"")) = R < +oo with R being constant and the set A = [k E Z Ef +1 2 Ef(w")), then have
sume that ΣREA (Ef(w"
V 113) = -0 (+ sK' ).
min ISkK
(11)
If f(w) is further convex and and the set = [k E z I
Σ keB (Ef(w EE((=*)) R < too with R being a constant
k-1 w0 2 2 El|w=* w 2112 then
(E (f(w"))((w")) = sK) ISKSK
min
(12)
where wn is the minimum of f. To obtain (Ve 0) error, set $ O(c) and K 0(1/e).
Theorem 2 relies the assumption that ΣleA or (Ef(w*+)) (((((=+)))E((( is bounded, and provide an empirical verification in Appendix C.I. We leave it open for how to establish the convergence result for SRSGD without this assumption.
EXPERIMENTAL RESULTS
We evaluate SRSGD on variety of benchmarks for image classification, including CIFAR10. CIFARIO0 and ImageNet. In all experiments, we show the advantage of SRSGD over the widely used and well-calibrated SGD baselines with constant momentum of 0.9 and decreasing learning
5

---

Under review as a conference paper at ICLR 2021
SGD
SGD + Momentum
NASGD
ARSGD
SRSGD
SGD + Momentum
SRSGD ImageNet
MNIST
CIFAR10
10'
10a
(b)
x 10a
(c)
Train Loss
4 10
10-
10-1
x 10"
100
100
10-
10a
10"
12k
100
200
0
25
50
75
Iteration
Epoch
Epoch
Figure 3: (a) Training loss comparison between different schemes in training logistic regression for MNIST classification. Here, SGD the plain SGD without momentum, and SGD Momentum that follows (3) and replaces gradient with the mini-batch stochastic gradient. NASGD is not robust to noisy gradient, ARSGD almost degenerates SGD, and SRSGD performs the best in this case. (b, c) Training loss vs. training epoch of ResNet models trained with SRSGD (blue) and the SGD baseline with constant momentum as in PyTorch implementation, which denoted by SGD in Section (red).
rate at certain epochs, which we denote as SGD. We also compare SRSGD with the well-calibrated SGD in which we switch momentum to the Nesterov momentum of 0.9, and we denote this optimizer as SGD + NM. We fine tune the SGD and SGD + NM baselines to obtain the best validation performance, and we then adopt the same set of parameters for training with SRSGD. In the SRSGD experiments, we tune the restart frequencies on small DNNs for each task based on the validation performance and upply the calibrated restart frequencies to large DNNs for the same task. Note that ARSGD is impractical for training on large-scale datasets since it requires to compute the loss over the whole training set at each iteration, which very computationally inefficient. Alternatively, ARSGI can estimate loss and restart using to SGD without momentum as we mentioned in Section 3. Thus, we do not compare with ARSGD in our CIFAR and ImageNet experiments. The details about hyper-pane parameters calibration can be found in Appendix D.4. We provide the detailed description of datasets and experimental settings in Appendix D. Additional experimental results in training LSTMs (Hochreiter & Schmidhuber, 1997) and WGANs (Arjovsky et al., 2017: Gulrajani et al., 2017) with SRSGD, as well as the comparison between SRSGD and SGD + NM on ImageNet classification task, are provided in Appendix E. We also note that in all the following experiments, the training loss will blow up if we apply NASGD without restart. These further confirm the stabilizing effect of scheduled restart in training DNNs.
but then ARSGD restarts too often and degenerates
4.1 CIFARIO AND CI
We summarize our results for CIFAR in Tables and 2. We also explore two different restarting frequency schedules for SRSGD: linear and exponential schedule. These schedules are governed by two parameters: the initial restarting frequency Fi and the growth rate r. In both scheduling schemes, the restarting frequency at the 1st learning rate stage is set to Fi during training. Then the restarting frequency at the (I: + 1)-th learning rate stage determined by:
( Fi x
exponential schedule
F
(1+ k), linear schedule.
We search Fi and using the method outlined in Appendix D.4. For CIFARIO, (F1 = 40, 1.25)
and (Fi = 30, r = 2) are good initial restarting frequencies and growth rates for the exponential and linear schedules, respectively. For CIFARION 100, those values are (F) = 45, r = 1.5) for the exponential schedule and (F)- 50, r 2) for the linear schedule.
Improvement in Accuracy Increases with Depth. We observe that the linear schedule of restart yields better test error on CIFAR than the exponential schedule for most of the models except for Pre- Pre-ResNet-470 and Pre-ResNet-IO0 1001 on CIFARI00 (see Tables and 2). SRSGD with either linear or exponential restart schedule outperforms SGD. Furthermore, the advantage of SRSGD over SGD is more significant for deeper networks. This observation holds strictly when using the linear schedule (see Fig. 1) and is generally true when using the exponential schedule with only few exceptions.
Faster Convergence Reduces the Training Time by Half. SRSGD also converges faster than SGD. This result is consistent with our MNIST case study in Section 3 and indeed expected since SRSGI)

---

Under review as a conference paper at ICLR 2021
Table 1: Classification test error (%) on CIFARIO using SGD, SGD NM, and SRSGD. We report
the results of SRSGD with two restarting schedules: linear (lin) and exponential (exp). The numbers of iterations after which we restart the momentum in the lin schedule are 30, 60. 90, 120 for the 1st, 2nd, 3rd, and 4th stage. Those numbers for the exp schedule are 40, 50, 63, 78. We include the
reported results from (He et al., 2016b) (in parentheses) in addition to our reproduced results.
Network
Params
SGD (baseline)
SGD-NM
SRSGI
SRSGD
Imgrove over
Improve over
(lin)
(exp)
SGD (lin/exp)
SGD H-M (lin/exp)
1re-ResNet110
1.1M
5.25 1:5:::00 (6.34
5.24 1 0.16
4.93
0.13
5.00
1: 0.47
0.32/0.25
0.31/0.22 24
Pro- Re-NeeN9
3.0M
5.05 :: 0.23
5.04 2 0.12
4.37
0.15
4.50
2 0.18
0.68/0.55
0.67/0.54
475
4.92 0.10
4.97 : 0.15
4.18
+: 0.09
4.49 + 0.19
0.74/0.43
0.79/0.48
Pre- ResNes-660
6.7M
4.87
4,80
4.00
0.07
4.40
0.13
0.87/0.47
0.80/0.40
Pre RosNet-1001
19.3M
4.84 + 0.19 (4.92)
4.62 + 0.14
3.87
4: 0.07
4.13 # 0.10
0.97/u.71
0.75//049
Table 2: Classification test error (%) on CIFARIO0 using SGD, SGD + NM, and SRSGD, We report
the results of SRSGD with two restarting schedules: linear (lin) and exponential (exp). The numbers of iterations after which we restart the momentum in the lin schedule are 50, 100, 150, 200 for the 1st, 2nd, 3rd, and 4th stage. Those numbers for the exp schedule are 45, 68, 101, 152. We include the reported results from (He et al., 2016b) (in parentheses) in addition to our reproduced results.
Network
SGD (bascline)
SGD+NM
SRSGD
SRSGD
Improve
Improve
(in)
(exp)
SGD (lin/xxp)
SGD+NM (lin/exp)
Pre-ResNe-110
1.2M
23.75 4: 0.20
23.65 à 0.36
23.49 + 0.23
23.50 + 0.39
0.26/0.25
0.16/0.13
Pre-ResNa-290
3. AM
21.78 0.21
21.68
0.21
21.49 : 0.27
21.58 + 0.20
0.29/0.20
0.19/0.10
Pre-ReNNa-170
21.43
20.64 0.18
0.72/0.79
0.50/0.57
Pro-ReiNet-610
6.7M
21.27 : 0.14
21.04 0.38
20.36
+ 0.25
20.41 + 0.21
0.91/0.86
0.68/0.63
Pro-ResNet-1001
10.4M
20.87 + 0.20
20.13 0.16
19.75 1 0.11
19.53 + 0.19
1.12/1.34
0.38/0.60
Table On CIFART0/100 (%), SRSGD training with only 100 epochs achieves comparable classifi- cation errors (%) to the SGD baseline training with 200 epochs.
CIFARTO
CIFAR 100
Network
SRSGD
Improvement
SRSGD
Improvement
Pee-ResNett-110
5.43 + D.18
-0.18
23.85 + 0.19
-0.10
Pre-ResNet-200
4.83 + D.11
0.22
21.77 + 0.43
0.01
R45Nett470
+
21.42
0.19
0.01
Pre Tre-ResNett650
4.43 + D.14
0.44
21.04
0.20
0.23
Pre Re--ReeNet--ae 1001
4.17 + 0.20
0.67
20.27 +: 0.11
0.60
Pre-ResNet-IID 10
5.25 + 0.10 epochs)
0.00
23.73 +: 0.23 (140 epochs)
0.02
Table 4: Test errors on CIFARIO (% of 10 (Left)/90 (Right) using different optimizers.
SRSGD
Adam
RMSProp
SRSGD
Adama
RMSPhop
4.93 1 0.13%
6.83 0.10%
7.31
0.31%
4.37 1 0.15%
6.12 1: 0.18%
7.18 1 0.03%
can avoid the error accumulation when there is an inexact oracle. For CIFAR, Fig. 3 (b) shows that SRSGD yields smaller training loss than SGD during the training. Interestingly, SRSGD converges quickly to good loss values in the 2nd and 3rd stages. This suggests that the model can be trained with SRSGD in muny fewer epochs compured to SGD while achieving a similar error rate.
Results in Table 3 confirm the hypothesis above. We train Pre-ResNet models with SRSGD in only 100 epochs, decreasing the learning rate by a factor of 10 at the 80th, 90th, and 95th epoch while using the same linear schedule for restarting frequency as before with (F) 30, 2) for CIFARIO 10 and (Fi = 50,7 r = 2) for CIFAR100. We compare the test error of the trained models with those trained by the SGD baseline in 200 epochs. We observe that SRSGD training consistently yields lower test errors than SGD except for the case of Pre-ResNet- 10 even though the number of training epochs of our method is only half of the number of training epochs required by SGD) For Pre-ResNet-I 10, SRSGD needs 110 epochs with learning rate decreased at the 80th, 90th, and 100th epoch to achieve the same error rate as the 200-epoch SGD training on CIFARIO. On CIFAR 100. SRSGD training for Pre- Fre-ResNet-1 10 needs 140 epochs with learning rate decreased at the 80th, 100th and 120th epoch to outperform the 200-epoch SGD. Comparison with SGD short training provided in Appendix F.2.
Comparison with Adam and RMSProp. SRSGD outperforms not only SGD with momentum but also other popular optimizers including Adam and RMSProp (Tieleman & Hinton, 2012) for image classification tasks. In fact, for image classification tasks, Adam and RMSProp yield worse performance than the baseline SGD with momentum (Chen & Kyrillidis, 2019). Table compares SRSGD with Adam and RMSprop CIFARIO.
7

---

Under review as a conference paper at ICLR 2021
Table 5: Single crop validation errors (%) on ImageNet of ResNets trained with SGD baseline and SRSGD. We report the results of SRSGD with the increasing restarting frequency in the first two learning rates. In the last learning rate, the restarting frequency is linearly decreased to 1. For baseline results, we also include the reported single-crop validation errors (He et al., 2016c) (in parentheses).
Nerwork
Params
SGD
SRSGD
Impowement
top-1
top-1
top-5
top-1
Rop-5
ResNet.50
26.5GM
24.11 + 0.10 70)
7.22 0.14
23.85 # 0.09
7.10 # 0.09
0.26
0.12
ResNet-111
44.55M
22.
1:
0.03 (23, 80)
6.22
0.01 (7.10)
22.06 : 0.10
6.09
+ 0.07
0.36
0.13
ResNet-152
22.03
1: (2(3000)
6.04
0.07 (6.70)
21.46
5.69
0.35
RosNe-2000
64.67M
22.13
0.12
6.00 0.07
20.93 + 0.13
5.57 + 0.05
1.20
0.43
Table 6: Comparison of single crop validation emors on ImageNet (%) between SRSGD training with
fewer epochs and SGD training with full 90 epochs.
Network
SRSGD
Reduction
Improvement
Network
SRSGD
Reduction
Improvement
ResNet-50
24.30 0.21
10
-0.19
ResNet-152
21.79 0.07
15
0.24
ResNet.
22.32 0.06
10
0.1
ResNet 200
21.92 0.17
30
0.21
4.2 IMAGENET
Next, we discuss our experimental results on the 1000-way ImageNet classification task (Russakovsky et al., 2015). We conduct our experiments on ResNet-50, 101, 152, and 200 with 5 different seeds. We use the official PyTorch implementation for all of our ResNet models (Paszke et al., 2019), Following common practice, we train each model for 90 epochs and decrease the learning rate by a factor of 10 at the 30th and 60th epoch. We use an initial learning rate of 0. momentum scaled by 0.9, and weight decay value of 0.0001. Additional details and comparisons between SRSGD and SGD + NM are given in Appendix E.
We report single crop validation errors of ResNet models trained with SGD and SRSGD on ImageNet in Table 5. In contrast to our CIFAR experiments, we observe that for ResNets trained on ImageNet with SRSGD, linearly decreasing the restarting frequency to at the last stage (i.c., after the 60th epoch) helps improve the generalization of the models. Thus, in our experiments, use linear scheduling with (Fi = 40, r = 2). From epoch 60 to 90, the restarting frequency decays to 1 linearly.
Advantage of SRSGD continues to grow with depth. Similar to the CIFAR experiments, observe that SRSGD outperforms the SGD baseline for all ResNet models that we study. As shown in Fig. 1. the advantage of SRSGD over SGD grows with network depth, just as in our CIFAR experiments with Pre-ResNet architectures.
Avoiding Overfitting in ResNet-200. ResNet-200 demonstrates that SRSGI is better than the SGD baseline at avoiding overfitting". The ResNet-200 trained with SGD has top-1 error of 22. 13%, higher than the ResNet-152 trained with SGD, which achieves top-1 error of 22.03% (see Table 5). He et al. (2016b) pointed out that ResNet-200 suffers from overfitting. The ResNet-200 trained with our SRSGD has top-1 1 error of 20.93%. which 1.2% lower than the ResNet-2200 trained with the SGD and also lower than the ResNet-151 trained with both SRSGD and SGD, an improvement by 0.53% and 1.1%, respectively. We hypothesize that SRSGD with appropriate restart frequency is locally not monotonic (see Fig. 3 (b, c)), and this property allows SRSGD to escape from bad minima in order to reach a better one, which helps avoid overfitting in very deep networks. Theoretical analysis of the observation that SRSGD is less overfitting in training DNNs is under our investigation.
Training ImageNet in Fewer Number of Epochs. As in the CIFAR experiments, we note that when training on ImageNet, SRSGD converges faster than SGD the first and last learning rate while quickly reaching a good loss value at the second learning rate (see Fig. 3 (c)). This observation suggests that ResNets can be trained with SRSGD in fewer epochs while still achieving comparable error rates to the same models trained by the SGD baseline using all 90 epochs. We summarize the results in Table 6. On ImageNet, we note that SRSGD helps reduce the number of training epochs for very deep networks 10e, 152, 200). For smaller networks like ResNet-50, training with fewer epochs slightly decreases the accuracy.
4.3 EMPIRICAL ANALYSIS
SRSGD Helps Reduce the Training Time. We find that SRSGD training using fewer epochs yields comparable error rates to both the SGD baseline and the SRSGD full training with 200 epochs on CIFAR. We conduct ablation study to understand the impact of reducing the number of epochs
By overfitting, we mean that the model achieves low training error hut high error.
8

---

Under review as a conference paper at ICLR 2021
on the final error rate when training with SRSGD CIFARIO and ImageNet. In the CIFARIO experiments, we vary the number of epoch reduction from 15 to 90 while in the ImageNet experiments, we vary the number of epoch reduction from 10 to 30. We summarize provide detailed results in Appendix F. For CIFAR 10, we can train with 30 fewer epochs while still maintaining comparable error rate to the full SRSGI training, and with better error rate than the SGD baseline trained in full 200 epochs. For ImageNet, SRSGD training with fewer epochs decreases the accuracy but still obtains comparable results the 90-epoch SGD baseline.
results in Fig. 4, and
Pre Reee-Re-tt-2
results the corresponding ResNet 152 - ResNett-2DD
Pre- R75Net-470
Figure Test error vs. number of training epochs. Dashed lines are test errors of SGD trained with 200 epochs for CIFARIO (left) and 90 epochs for ImageNet (right). For CIFAR, SRSGD with fewer epochs achieves comparable results to SRSGD with 200 epochs. For ImageNet, training with less epochs slightly decreases the performance of SRSGD but still achieves comparable results to 200-epoch SGD.
SED trainings which use 200 epochs for CIFAR10 and 90 epechs for ImageNet
CIFARIO
ImageNet
5.0
Valldaation Error
22.5
Test Ervor
4.8
Singto Crop
<2.0
21.5
21.0
140
125
Number Training Epochs
Impact of Restarting Frequency. We examine the impact of restarting frequency on the network training. We choose case study of training a Pre-ResNet-299 on CIFAR 10 using SRSGD with linear schedule scheme for the restarting frequency. We fix the growth rate r = 2 and vary the initial restarting frequency F1 from I to 80. As shown in Fig. 5, SRSGD with large F1 e.g. F1 80, approximates NASGD (yellow). We also show the training loss and test accuracy of NASGD in red. As discussed in Section 3, it suffers from error accumulation due to stochastic gradients and converges slowly or even diverges. SRSGD with small Fj, e.g. Fi = 1, approximates SGD without momentum (green). It converges faster initially but reaches worse local minimum (i.e. larger loss). Typical SRSGD (blue) converges faster than NASGD and to a better local minimum than both NASGD and SGD without momentum. It also achieves the best test error. We provide more empirical analysis results in Appendix F, G and H. The impact of the growth rate r is studied in Appendix G.2.
F,=1
F,=10
F,=30
F,=50
F,=80
NASGD (F,
10a
NASGD
6.5
Approximate SGD without
Test Error NASGD 32.44
Train Loss
Approximate NASGD
Test Error
momentum
Approximate
10-1
NASGD
Approximate SGD without
10-2
4.5
momentum
100
200
1
10
30
50
80
Epoch
Initial Restarting Frequency (F,)
Figure 5: Training loss (left) and test error (right) of Pre-ResNet-290 trained on CIFARIO with different initial restarting frequencies F3 (linear schedule). SRSGD with small A approximates SGD without momentum, while SRSGD with large F1 approximates NASGD. The training loss curve and test accuracy of NASGD are shown in red and confirm the result of Theorem that NASGD accumulates error due to the stochastic gradients.
5 CONCLUSIONS
We propose the Scheduled Restart SGD (SRSGD), with two major changes from the widely used SGD with constant momentum. First, we replace the momentum in SGD with the iteration- momentum that used in Nesterov accelerated gradient (NAG). Second, we restart the NAG momentum according to schedule to prevent error accumulation when the stochastic gradient is used. For image classification, SRSGD can significantly improve the accuracy of the trained DNNs. Also, compared to the SGD baseline, SRSGD requires fewer training epochs to reach the same trained model's 's accuracy. There are numerous avenues for future work: 1) deriving the optimal restart scheduling and the corresponding convergence rate of SRSGD and 2) integrating the scheduled restart NAG momentum with adaptive learning rate algorithms, e.g., Adam (Kingma & Ba, 2014).

---

Under review as a conference paper at ICLR 2021
REFERENCES
Martin Arjovsky, Soumith Chintala, and Léon Bottou. Wasserstein generative adversarial net- works. In Doina Precup and Yee Whye Teh (eds.), Proceedings of the 34th International Con- ference on Machine Learning, volume 70 of Proceedings of Machine Learning Research, pp. 214-223, International Convention Centre, Sydney, Australia, 06-11 Aug 2017. PMLR. URL wwwp h7.html.
Mahmoud Assran and Michael Rabbat. On the convergence of nesterov's accelerated gradient method in stochastic settings. arXiv preprint crXiv:2002.12414, 2020.
Necdet Serhat Aybat, Alireza Fallah, Mert Gurbuzbalaban, and Asuman Ozdaglar. Robust accelerated gradient methods for smooth strongly convex functions. arXiv preprint 180i 10579, 2018.
Necdet Serhat Aybat, Alireza Fallah, Mert Gurbuzbalaban, and Asuman Ozdaglar. A universally optimal multistage accelerated stochastic gradient method. Advances Neural Information 2019.
Processing Systems, pp.
Amir Beck and Marc Teboulle. A fast iterative shrinkage-thresholdingg algorithm for linear inverse problems. SIAM Journal on Imaging Sciences, 2(1):183-202, 2009.
Yoshua Bengio, Nicolas Boulanger-Lewanddowsk. and Razvan Pascanu. Advances in optimizing recurrent networks. 2013 IEEE International Conference on Acoustics, Speech and Signal Processing, pp. 8624-8628. IEBE, 2013.
Léon Bottou, Frank Curtis, and Jorge Nocedal. Optimization methods for large-scale machine learning. Siam Review, 60(2):223-311 -11,, 2018.
Sébastien Bubeck. Convex optimmizaiiin:nn Algorithms and complexity. arXiv preprint 1405::4005.9900 2014.
Augustin Cauchy. Méthode générale pour la résolution des systemes d' l'équations simultanées. Comp. Rend. Sci. Puris, 1847.
John Chen and Anastasios Kyrillidis. Decaying momentum helps neural network training. arXiv preprint arXiv:1910.04900 2019.
François Chollet et al. Keras. https://keras.io, 2015.
Michael B Cohen, Jelena Diakonikolas, and Lorenzo Orecchia. On acceleration with noise-corrupted gradients. arXiv preprint arXiv: 180.119, 2018.
Olivier Devolder, François Glineur, and Yurii Nesterov. First-order methods of smooth convex optimization with inexact oracle. Mathematical Programming, 146(1-2):37-75, 2014.
Timothy Dozat. Incorporating Nesterov momentum into Adam. 2016.
John Duchi, Elad Hazan, and Yoram Singer. Adaptive subgradient methods for online learning and stochastic optimization. Journal of Machine Learning Research, 12(11):2121-2159) 201
Robert M Freund and Haihao Lu. New computational guarantees for solving convex optimization problems with first order methods, via a function growth condition measure. Mathematical Programming, 170(2)445-477, 2018.
Saeed Ghadimi and Guanghui Lan. Stochastic first-and zeroth-order methods for nonconvex stochastic programming. SIAM Journal on Optimization, 23(4):2341 -2368,, 2013.
Saced Ghadimi and Guanghui Lan. Accelerated gradient methods for nonconvex nonlinear and stochastic programming. Mathematical Programming, 156(1-2):59 99, 2016.
Pontus Giselsson and Stephen Boyd. Monotonicity and restart in fast gradient methods, In 53rd IEEE Conference on Decision and Control, pp. 5058-5063. IEEE, 2014.
Gabriel Goh. Why momentum really works. Distill, 2(4):e6, 2017.
10

---

Under review as a conference paper at ICLR 2021
Ishaan Gulrajani, Faruk Ahmed, Martin Arjovsky, Vincent Dumoulin, and Aaron C Courville. Improved training of Wasserstein GANs. Advances in Neural Information Processing Systems, pp. 5767-7777, 2017. 2017.
Moritz Hardt.
Robustness
acceleration.
http://log..mtt..rg222144000
2014.
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recognition. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pp. 770-778, 2016a.
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Identity mappings in deep residual networks. In European Conference on Computer Vision, pp. 630-645. Springer, 2016b.
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual networks. http://github Haaiiiinnneddeep--siduuul------
2016c.
Geoffrey Hinton, Nitish Srivastava, and Kevin Swersky. Neural networks for machine learning lecture 6a overview of mini-batch gradient descent.
Sepp Hochreiter and Jürgen Schmidhuber. Long short-term memory. Neural Computation, 9()): 1735-17800 1997.
W Ronny Huang, Zeyad Emam, Micah Goldblum, Liam Fowl, Justin K Terry, Furong Huang, and Tom Goldstein. Understanding generalization through visualizations. arXiv preprint orXiv:1906.000 2019.
Anatoli Iouditski and Yuri Nesterov. Primal-dual subgradient methods for minimizing uniformly convex functions. arXiv preprint arXiv: 1401. 2014.
Prateck Jain, Sham M Kakade, Rahul Kidambi, Praneeth Netrapalli, and Aaron Sidford. Accelerating stochastic gradient descent for least squares regression. In Conference On Learning Theory, pp. 545-604, 2018.
Chi Jin, Praneeth Netrapalli, and Michael I Jordan. Accelerated gradient descent escapes saddle points faster than gradient descent. arXiv preprint arXiv: 2017
Rahul Kidambi, Praneeth Netrapalli, Prateek Jain, and Sham Kakade. On the insufficiency of existing momentum schemes for stochastic optimization. In 2018 Information Theory and Applications Workshop (ITA), pp. 1-9. IEEE, 2018.
Diederik P Kingma and Jimmy Ba. Adam: method for stochastic optimization. arXiv preprint arXiv:1412.6980, 2014.
Alex Krizhevsky, Geoffrey Hinton, et al. Learning multiple layers of features from tiny images. 2009.
Andrei Kulunchakov and Julien Mairal. A generic acceleration framework for stochastic composite optimization. In Advances Neural Information Processing Systems, pp. 22556-12567 2019.
Guanghui Lan. An optimal method for stochastic composite optimization. Mathematical Program- ming, 133(1-2):3653397 2012.
Quoc V Le, Navdeep Jaitly, and Geoffrey E Hinton. A simple way to initialize recurrent networks of rectified linear units. arXiv preprint arXiv: 1504,0094 2015.
Yann LeCun and Corinna Cortes. MNIST handwritten digit database. 2010. URL http://yann.lleuu. com/exdb/mnist/.
Qihang Lin and Lin Xiao. An adaptive accelerated proximal gradient method and its homotopy continuation for sparse optimization. In International Conference on Machine Learning, pp. 73-81, 2014.
Chaoyue Liu and Mikhail Belkin. Accelerating sgd with momentum for pvrrpaarameeerized learning. In International Conference on Learning Representations, 2020. URL https///ppenreveew.ne/ forum?id=r1 gixp4F.H..
11

---

Under review as a conference paper at ICLR 2021
Liyuan Liu, Haoming Jiang, Pengcheng He, Weizhu Chen, Xiaodong Liu, Jianfeng Gao, and Jiawei Han. On the variance of the adaptive learning rate and beyond. In International Conference on Learning Representations, 2020. URL https//pppurrooowwee//////////ap
Ilya Loshchilov and Frank Hutter. Sgdr: Stochastic gradient descent with warm restarts. arXiv preprint arXiv:1608.03390 2016.
Ilya Loshchilov and Frank Hutter. Fixing weight decay regularization in adam. 2018
Laurens van der Maaten and Geoffrey Hinton. Visualizing data using t-SNE. Journal of Machine Learning Rexearch, ((Nv))2579-2605, 2008.
Boris S Mordukhovich. Variational analysis and generalized differentiation I: Basic theory, volume 330. Springer Science Business Media, 2006.
Arkaddii S Nemirovski and Yu E Nesterov. Optimal methods of smooth convex minimization. USSR Computational Mathematics and Mathematical Physics, 25(2):21-30, 1985.
Yu Nesterov, Gradient methods for minimizing composite functions. Mathematical Programming, 140(1):125-161, 2013.
Yurii Nesterov. Introductory lectures on convex programming volume i: Basic course. 1998.
Yurii Nesterov. Lectures convex optimization, volume 137. Springer, 2018.
Yurii E Nesterov. A method for solving the convex programming problem with convergence rate (I/K 2). In Dokl. Akad. Nauk Sssr, volume 269, pp. 543-547, 1983.
Brendan O' O'donoghue and Emmanuel Candes. Adaptive restart for accelerated gradient schemes. Foundations of Computational Mathematics, (5(3):715-732,200
Adam Paszke, Sam Gross, Francisco Massa, Adam Lerer, James Bradbury, Gregory Chanan, Trevor Killeen, Zeming Lin, Natalia Gimelshein, Luca Antiga, et al. Pytorch: An imperative style, geshhperformacc deep learning library. In Advances Neural Information Processing Systems, pp. 8024-8035, 2019.
Boris T Polyak. Some methods of speeding up the convergence iteration methods. USSR Computational Mathematics and Mathematical Physics, 4(5):1-17, 1964.
Sashank Reddi, Satyen Kale, and Sanjiv Kumar. On the convergence of adam and beyond. arXiv preprint 1xXiv:1904.0023777 2019.
James Renegar. Efficient first-order methods for linear programming and semidefinite programming. arXiv preprint arXiv: 2014.
Tyrrell Rockafellar. Convex analysis. Number 28. Princeton university press, 1970.
Tyrrell Rockafellar and Roger J-B Wets. Variational analysis, volume 317. Springer Science & Business Media, 2009.
Vincent Roulet and Alexandre d' Aspremont. Sharpness, restart and acceleration. In Advances in Neural Information Processing Systems, pp. 1119-1129, 2017.
Vincent Roulet, Nicolas Boumal, and Alexandre d' Aspremont. statistical performance sparse recovery problems. arXiv preprint arXiv: 150.:::50633335 03290, 2015.
Computational complexity versus
Olga Russakovsky, Jia Deng, Hao Su, Jonathan Krause, Sanjeev Satheesh, Sean Ma, Zhiheng Huang, Andrej Karpathy, Aditya Khosla, Michael Bemstein, al. Imagenet large scale visual recognition challenge. International Journal of Computer Vision, 115(3)211-252 2015.
Weijie Su, Stephen Boyd, and Emmanuel Candes. A differential equation for modeling nesterov's accelerated gradient method: Theory and insights. In Advances in Neural Information Processing Systems, pp. 2510-2518, 2014.
12

---

Under review as a conference paper at ICLR 2021
lya Sutskever, James Martens, George Dahl, and Geoffrey Hinton. On the importance of initialization and momentum in deep learning. International Conference on Machine Learning, pp. 1139- 1147, 2013.
T. Tieleman and G. Hinton. Lecture 6.5-RmsPropp: Divide the gradient by running average of its recent magnitude. COURSERA: Neural Networks for Machine Learning, 2012.
Svante Wold, Kim Esbensen, and Paul Geladi. Principal component analysis. Chemometrics and Intelligent Laboratory Systems, 2(1-3):37-5,, 1987.
Wei Yang. Pytorch classification. https://gituu..com/ hwwp:///wwwwpppooochccsaaaiiiiie
2017.
Matthew D Zeiler. Adadelta: an adaptive learning rate method. arXiv preprint arXiv: arXiv:/212.5700 1212.5701 2012.
Sixin Zhang, Anna Choromanska, and Yann LeCun. Deep learning with elastic averaging sgd. In Advances in Neural Information Processing Systems, pp. 685-693, 2015.
Martin Zinkevich, Markus Weimer, Lihong Li, and Alex J Smola. Parallelized stochastic gradient descent. Advances in Neural Information Processing Systems, pp. 2595-2603, 2010.
13

---

Under review as a conference paper at ICLR 2021
Part
Appendices
The appendices are structured as follows. Section A, we prove Theorem 1. In Section B, we review error accumulation result of the Nesterov accelerated gradient with 8-inexact gradient. In Section C, we prove Theorem 2. In Section D, we provide some experimental details; particular, the calibration of restarting hyperparameters. In Section E, compare SRSGD with benchmark optimization algorithms on some other tasks, including training LSTM and Wasserstein GAN. In Section F, provide detailed experimental settings in studying the effects of reducing the number of epoch in training deep neural networks with SRSGD, and we provide some more experimental results. In Section and H. we further study the effects restarting frequency and training with less epochs by using SRSGD. In Section I, we visualize the optimization trajectory of SRSGD and compare with benchmark methods. A snippet of our implementation of SRSGD in PyTorch and Keras are available in Section J and K, respectively.
Table of Contents
Appendix
A Uncontrolled Bound NASGD
Preliminaries
A.2 Uncontrolled Bound of NASGD: Analysis
16
B NAG with d-Inexact Oracle & Experimental Settings in Section 3.1
19
C Convergence of SRSGD
20
C.I. Numerical Verification of the assumptions in Theorem 2
22
D Datasets and Implementation Details
23
D.1 CIFAR
23
D.2 ImageNet
23
Training ImageNet in Fewer Number Epochs:
23
D.4
Details Restarting Hyper-parameters Search
23
E
SRSGD SGD and SGD + NM ImageNet Classification and Other Tasks
24
E.1
Comparing with SGD with Nesterov Momentum on ImageNet Classification
24
E.2 Long Term Memory (LSTM) Training for Pixel-by be--eee MNIST
24
E.3
Wasserstein Generative Adversarial Networks (WGAN) Training on MNIST
25
F
Error Rate vs. Reduction Training Epochs
27
F11
Implementation Details
27
Short Training on CIFARIO/CIFAR Using SGD
28
F33 Additional Experimental Results
28
G Impact of Restarting Frequency for ImageNet and CIFAR100
29
G.1 Implementation Details
29
G.2 Impact of the Growth Rate
30
G.3 Additional Experimental Results
31
H Full Training with Less Epochs at the Intermediate Learning Rates
32
Visualization SRSGD's trajectory
33
SRSGD Implementation Pytorch
35
K SRSGD Implementation in Keras
36
14

---

Under review as a conference paper at ICLR 2021
A UNCONTROLLED BOUND OF NASGD
Consider the following optimization problem
min f(w),
(13)
where (w) is I-smooth and convex.
Start from w", GD update, with step size + can be obtained based on the minimization of the function
Qr, wh) (0 wh vf(w")) + 2 = w
(14)
With direct computation, we can get that
lgg. vf(w")) )ll
Qr Qu( k-1 w²)
min (r, ('),,,,w""
2r
where g* Σド= fi,, (w"). We assume the variance is bounded, which gives The stochastic min Qr 1x*] s 5, with ó being a constant and
gradient rule, Rg, satisfies E (1 w²) x being the sigma algebra generated by w., ......, w" iie.
x a (wr w² ,... w
NASGD can be reformulated as
++1 x
arg min Q, (v, w²) with rule R.,
k+1 + ts - (u+t1 )²),,
(15)
w k++
tx+1
where lo = 1 and 4++1 = (1 + V 412)
A.1 PRELIMINARIES
To proceed, we introduce several definitions and some useful properties in variational and convex anal- ysis. More detailed background be found Mordukhovich (2006); Nesterov (1998); Rockafellar & Wets (2009); Rockafellar (1970).
Let be convex function, say that f is T-smooth (gradient Lipschitz) if f is differentiable and [Vf(v) - f(w))l2 I - Illl-=/l2,
and we say f is v-srongyyy convex if for any w, v E dom(f)
f(w) 2 f(v) + (Vf(v). v) 2 u
Below of this subsection, we list several basic but useful lemmas, the proof can be found in Nesterov (1998). Lemma 1. If u-strongly convex, then for any v E ddomsf) we have
f(v) - f(v")( > 2 |l v²113.
(16)
where o² is the minimizer of f.
Lemma 2. If f is T-smooth, for any w, dom(s),
f(w)= s f(v) + (Vf(v), w v) + L
2 w - v/12.
15

---

Under review as a conference paper at ICLR 2021
A.2 UNCONTROLLED BOUND OF NASGD: ANALYSIS
In this part, we denote
gh+ = arg min Q- w²).
(17)
Lemma 3. If the constant > 0, then
28 E - gh+ S
(18)
r
Proof. Note that Qr w²) is strongly convex with constant r, and G++1 in (17) is the minimizer of Qv, w² With Lemma we have
Qr( ,,=,,,,"))__ Qr(0+
w0 z r 2 [|ottl -0+
(19)
Notice that
E [ w - Q,( wn"]] 1z w - min Qr -mnn
(v, w² S
The inequality (18) can be established by combining the above two inequalities. Lemma 4. If the constant satisfy
> L, then we have
E (s
2 [oatt +110
-
w0 (s( + E1lobt1 - w0013
(20)
2 -78- r
Elllw* - +.++1121
2
where T
F[r-L] +1. I.
Proof. The convexity of f gives
0 (V o oht (n-1) ((ahtz) ((ott1).
(21)
From the definition of the stochastic gradient rule R., we have
6 < E (Q+t1 w² - (r wx²)))
(22)
E (oh+1 w vf(w")))
1u+t - x001
E (0++1 w0, vl(w=))) | 10113
With (21) and (22), we have
-8 <
(
| - w0113) (s(ohtz) - Illlatt
w 13 +
(23)
(Vff(w") vf(ā+t)), gh+l x(
With the Schwarz inequality (a, b) s and = = +++1
||لاا
+ 111011 with μ
12 - Vf(uttl)- (((ttt))
24
(V - vf(ū" Jhtt1 - xttl)
(24)
(r-L) [VS(w*) v +
1
110 1 x
212
2(r - L)
(r L.)
11100= 1 -
I,2
| x 112
2(r L)
Combining (23) and (24), we have
-8
B ((
+ T [1iht1
E
(swutt) -11ottt-
w w0(133)
(25)
L
E 1 31++1
2(r
2
By rearrangement of the above inequality (25) and using Lemma 3, obtain the result.
16

---

Under review as a conference paper at ICLR 2021
Lemma 5. the constants satisfy r >> L, then we have the following bounds
E - -((
(
2 2 w0 x
+ -², g 10-+1-00))- -00)--00 - (26)
E (f((r)) - -(( 7 - rR( - 0²,
-0, gh+1 -0 - =ō,
(27)
where T = F] + and v* is the minimum.
Proof.
With Lemma 2, we have
L " 1 20.12.
f(( ff(w²) - (5++1 - -w², Vf(w"))
(28)
Using the convexity of f, we have
s(a - f(10*) 2 (v - V V[(ww)))
i.c.,
f(o²) 2 f(wx* + (0 w² vf(w))).
(29)
and the optimization condition gives According to the definition of @++1 in (14), i.e.,
gk+1 arg min Q. (u, w²) arg min(v w vf(w=*)) r - w w01
gk+1 w 1 V v((")).
(30)
Substituting (30) into (29), we obtain
f(r*) 2 f(w*) + (o" w r(w x(t1)).
(31)
Direct summation of (28) and (31) gives
L | w/ + r(w0" -0, gh+1 w²
S(Ø²) ((
r
(32)
2
Summing (32) and (20), we obtain the inequality (26)
E [f(u*) f(o*+1)] E u +12 rB(w - w jht1 w² 78.
(33)
On the other hand, with the convexity of f, we have
f(e²) f(w=*) 2 (v" wh vf(w")) (v" w r(w0 ob+11).
(34)
The summation of (28) and (34) results in
r (r- 1 2 1 8x 11-1113 r(w= 0², xktl wt
f(b²) f(++11)
(35)
Summing (35) and (20), we obtain
E (J(x") (()+
2 r El 2
- x rB - 0², oh+1 - -8,
(36)
which is the same as (27).
Theorem (Uncontrolled Bound NASGD (Theorem with detailed bounded)). Let the constant satisfy < L and the sequence {0*1 be generated by NASGD with stochastic gradient that has bounded variance. By using any constant step size Sy = S S 1/L, then we have
2r5
4k
Eif(e*) min f(v)] <
+ R
(37)
3
17

---

Under review as a conference paper at ICLR 2021
Proof. We denote
F* : B(s(o*) - f(0")).
By (26) (4g- 1) + (27), we have
2144x 1) 1)F# th Lx F
tx1BlloAt1 2²
(38)
2B( wº, 12/0 (1x 1)0* - -00) 2T
With 1/_1 = - tk. (38) x to yields
2 pk 1]
El t
(39)
2T
24 B(o wh ttw" (tx 1) 0²)
r
Substituting a - tt (la 1)0* -v" and b -1.20 -(ts -1)0* -w" into identity
l|a blÍ2 + +(aa b, b. = -Iaal1 |161|2
(40)
It follows that
t ++1 t 12 E(oht wn tw - (tx 1) v²)
(41)
14 ++ w 1/ 2t - w tx - (tx 1) v²)
+20gB(oh+1 xh t -(t+ - -1)o* -0")
(40) 11 (tx 1)v* - -011 11tx (tx- 1) v²113
+24,B(5h+L1 h+1 -4 - -(1+ 1)y* - -0")
El - (ts- 111** -
0²1 [ EE1111110 (tk-1 11---1190-11 1-0-111-0-00" -0'11
+ 2(tht - k+1
x+1 10-t1,4-10 10-10 (tx-1 1)0k v²}.
In the third identity, we used the fact tw t& + (fx-1 - 1)( wk-1). If we denote
w*
= B11141111 (44 - 1)0 - v²1 (39) can be rewritten as
F F
21 Ft Fk
+ t 27th8
+ k+1
(42)
r
+
21 R(g ktl
- Giht1 11- - (14-1 - -1 -0²
21 pk
+ + 2Tth8 1- R?
<
where we used
2v k+1 - - L 10 (1 1)0 -0")
<
1/ k k+ - 112 + B1112= 1 (12 11=-10" (12-1 100-'-0"113"
-
2t/0/r + R²
R²a
Denoting
21 k-1
pk
&
then, have
2rō
278
k3
Ex+1 S Eo +
+ R²
+
R22
(43)
r
3
With the fact, & F pk 2 222 Fk /4, then proved the result.
18

---

Under review as a conference paper at ICLR 2021
B NAG WITH Ó-INEXACT ORACLE & EXPERIMENTAL SETTINGS IN SECTION 3.1
In Devolder et al. (2014), the authors defines d-inexact gradient oracle for convex smooth optimization as follows:
Definition (ō-Inexact Oracle). Devolder et al. (2014) For a convex L-smooth function f IR_ + R. For Ye E Rd and exact first-order oracle returns a pair (f(w), Vf((w) E R R so that for ve E Rd we have
L 0 S f(v) (f(w) + (V)(2), w)) S w - w
2
A 6 --iexacct oracle returns pair (f (w) V fdh ()) E R x a so that Ve I2 we have
0 $ f(v) (f (w)
(), v w) - 2 2122 +
We have the following convergence results of GD and NAG under a d-Inext Oracle for convex smooth optimization.
Theorem 4. Devolder al. (2014)² Consider
min f(w), w Rd where (ww) is convex and L-smooth with w" being the minimum. Given access to b-inexact oracle, GD with step size 1/L returns a point w after k steps so that
L
((w))-((w' s(ww[(ww))))) O
8.
On the other hand, NAG, with step size 1/L returns
L k2
f(w*) - ff =
+ ((K)).
Theorem 4 says that NAG may not robust 8-inexact gradient. In the following, will study the numerical behavior of a variety of first-order algorithms for convex smooth optimizations with the following different inexact gradients.
Constant Variance Gaussian Noise: We consider the inexact oracle where the true gradient is contaminated with Gaussian noise NN0 0.001 We run 50K iterations of different algorithms. For SRNAG, we restart after every 200 iterations. Fig. 2 (b) shows the iteration vs. optimal gap, f(=*) (x=), with x being the minimum. NAG with the inexact gradient due constant variance noise does not converge. GD performs almost the same as ARNAG asymptotically, because ARNAG restarts too often and almost degenerates into GD. GD with constant momentum outperforms the three schemes above. and SRNAG slightly outperforms GD with constant momentum.
Decaying Variance Gaussian Noise: Again, consider minimizing (8) with the same experimen- tal setting, as before except that V fxx) is now contaminated with a decaying Gaussian noise N/ [1/100)=1)²), )2). For SRNAG, we restart every 200 iterations in the first 10k iterations, and restart every 400 iterations in the remaining 40K iterations. Fig. (c) shows the iteration vs. optimal gap by different schemes. ARNAG still performs almost the same GD. The path of NAG is oscillatory. GD with constant momentum again outperforms the previous three schemes. Here SRNAG significantly outperforms all the other schemes.
We apply the above schemes with stochastic gradient to train logistic regression model for MNIST classification LeCun & Cortes (2010). We consider five different schemes, namely, SGD, SGD + (constant) momentum, NASGD, ASGD, and SRSGD. In ARSGD, we perform restart based on the loss value of the mini-batch training data. In SRSGD, we restart the NAG momentum after every 10 iterations. We train the logistic regression model with a f weight decay of 10-4 by running size of 128. The step sizes for all the schemes are set to 0.01. Fig. 3 (a) plots the training loss vs. iteration. In this case, NASGD does not converge, and SGD with momentum does not speed up SGD, ARSGD's performance is par with SGD's. Again, SRSGD gives the best performance with the smallest training loss among these five schemes.
Logisitic Regression for MNIST Classification:
epochs using different schemes with batch
We adopt the result from Hardt (2014).
19

---

Under review as a conference paper at ICLR 2021
C CONVERGENCE OF SRSGD
We prove the convergence of Nesterov accelerated SGD with scheduled restart, i.e., the convergence of SRSGD. We denote that 0* = 1==1 in the Nesterov iteration and 0* is its use in the restart version,
i.e. SRSGD. For any restart frequency F (positive integer), we have 6 = -h [R/F] In the restart version, we can see that
< = <1 Lemma 6. Let the constant satisfies r > L and the sequence {v Ju20 be generated by the SRSGD with restart frequency F (any positive integer), have
R2
0² 11 (1-0)² 0)2²
(44)
where 0 = OF < and R = supx [
Proof. It holds that
1 - 1011
1 - x et - -w0112
(45)
1 b+1 - 08112 1| 2=11 112
b+1 - 2/112 011 - 1122
Thus,
- - 2 (1lat1 - -0012 122 - 0 01 h x² R- 112)
(46)
| k r²113 20 r kk 112112 x
02110*
-
1
(1 0+ v² 112 0(1 11 - 2x 1
Summing (46) from &- = 1 to K, we get
K 1 - Σ
(1 0) 1 k-
o k+1
w² w013 x KR²
(47)
k=1
In the following, we denote
A == [k: E 2 ( 2 Bf(o"11))
Theorem (Convergence of SRSGD). (Theorem 2 with detailed bound) Suppose f(w) is L-moooth. Consider the sequence (w* Ju20 generated by (10) with stochastic gradient that is bounded and has bound variance. Using any restart frequency and any constant step size 8y == 8 S 1/ L. Assume (T. (.((w))) R +00, then we have
that EKEA
TR²
L(1
LL
RR
min ISkSK
LE
E
112) 3 (1 8)
(48)
2
K
If ((w) is further convex and the set B = (k: Zt 2+
= ==1122 2
E El
un 12] obeys
EKER (ef(wkt))-EffH
R +0c, then
1w
w w=1 2 ft 712
min ISkSK
{E (f(w**) f(w)))) <
(49)
27
where w" is the minimum of f. To obtain c (ve > 0) error, we set s = O(c) and K = 0(1/2).
Proof. Firstly, we show the convergence of SRSGD for nonconvex optimization. L-smoothness of f.
ie., Lipschitz gradient continuity, gives
f(or+l) < f(w*) )+ + (Vf(w*), rt1 200 + 2
1100t1 =²
(50)
20

---

Under review as a conference paper at ICLR 2021
Taking expectation, get
+ ,²LRR
Ef(r - Ef((x)) rBI rEIVsS(">)
(51)
2
On the other hand, we have
f(w**) S O - + L(Okg2
11 0 11.
(52)
2
Then, we have
Bf( < Ef(v²) + OVOB(V -
(53)
I(A
2 Elle* 11- rBIIV.f((*)) RR
We also have
0 (VS(") vt - 1 0² (I(Ot) - 1(0 + L
_ 1100 ~²
(54)
2
We then get that
Ef( s Ef(v*) + 0t (1
-B V >1 + Ak
(55)
where
L(Ø
R²
A 1 0 112
Bl1
11 +
2
2
Summing the inequality gives us
Ef(ok+t) s Bf(o0)
+
0
(Ef(o*) 1Bf((*-1))
(56)
REA
K
K
r
B f
E
112 + Σ
A
1=1
k=1
It is easy to see that
Σ
[Ef(v*) - (B = 0F.
kEAA
We get the result by using Lemma 6 Secondly, prove the convergence of SRSGD for convex optimization. Let w be the minimizer of f. We have
E w0
Ekl
fWw" w" 112
(57)
Ek
w w011 2TyBE / (wo*), w -w) / 12
< 11
x x=113 - 2y ((00 w0th - w²) + -2122.
We can also derive
E ww
w²ll2 E 8¹ (0" xk w0 112
1* w" 112 + 20 E60 x xh - w²) + 2 - 11
Ell w" ll @'E (1 w w011 11 + k x² 1| 1 20 1123
+ (T) * b
= w" 1| Ô' (1 - w0113 k w 21) + 2(0 x0 -
where we used the following identity
(a b) (a- b) - ||la - dl12 - l|a
c112 + b| - c12 - 1 - d|
21

---

Under review as a conference paper at ICLR 2021
Then, have
E ++ w01l: 11 Eloe* w011 2y w0 -w0) +
0 (58)
+ R²² + @TTE(110* 10 - w0 1 -20--111 112)
We then get that
2y (f(w*) f(ww)) - Elle* w01 Ellu*t1 w 12
(59)
+ 0h (Bll w" 11 Ell w +r2
Summing the inequality gives us the desired convergence result for convex optimization.
C.I NUMERICAL VERIFICATION OF THE ASSUMPTIONS IN THEOREM 2
In this part, numerically verify the assumptions in Theorem 2. In particular, we apply SRSGD with learning rate 0.1 to train LeNet 4 for MNIST classification (we test on MNIST due to extremely large computational cost). We conduct numerical verification as follows: starting from a given point w we randomly sample 469 mini-batches (note in total we have 469 batches in the training data) with batch size 128 and compute the stochastic gradient using each mini-batch. Next, we advance the next step with each of these 469 stochastic gradients and get the approximated Ef(w"). ). We randomly choose one of these 469 positions as the updated weights of our model. By iterating the above procedure, we can get w²2, w² ..... and Ef(w"', ) (,""", .... and we use these values to verify our assumptions in Theorem 2. We set restart frequencies to be 20, 40, and 80, respectively. Figure 6 top panels plot k vs. the cardinality of the set A := (K Z [f 2 Ef(w")) and Figure 6 bottom panels plot vs. ΣREA (w - Ef("")) Figure 6 shows that ΣxEA (Bf(w*+1) Ef Ef(=")) converges to constant R < +00 We also noticed that when the training gets plateaued, B(f(w")) still oscillates, but the magnitude of the oscillation diminishes as iterations goes, which is consistent with our plots that the cardinality of A increases linearly, but R converges finite number. These numerical results show that our assumption in Theorem is reasonable.
Cardinality of set A =- (k E 2=E[ 2 Bf(w"))
(Bf(w Bf(w*))
AEA4 Restart Frequency 40
Restart Frequency 20
Restart Frequency 80
1000
43300
3005
2000
20000
10000
$1300
E0C58
20000
<0039
50000
40053
52000
3.2
20000 10000
05000
30000
62300 20000 $2000
30000
20000 42000 50000
30000
Figure 6: Cardinality of the set := e 2 [E > Ef(w")] (Top panels) and the value of R = ΣtEA (E)( - [)(())) (Bottom panels). We notice that when the training gets plateaued, E(f(w()) still oscillates, but the magnitude of the oscillation diminishes as iterations goes, which consistent with our plots that the cardinality of increases linearly, but π converges to finite number under different restart frequencies. These results confirm that our assumption in Theorem reasonable.
"We used the PyTorch implementation of LeNet at http://gihhbb.oooccciaaaggggeeee
22

---

Under review as a conference paper at ICLR 2021
D DATASETS AND IMPLEMENTATION DETAILS
D.1 CIFAR
The CIFARIO and CIFAR100 datasets Krizhevsky et al. (2009) consist of 50K training images and 10K test images from 10 and 100 classes, respectively. Both training and test data are color images of size 32 x 32. We run our CIFAR experiments on Pre-ResNet-110, 290, 470, 650, and 1001 with 5 different seeds He al. (2016b). We train each model for 200 epochs with batch size of 128 and initial learning rate of 0.1, which decayed by a factor of 10 at the 80th, 120th, and 160th epoch. The weight decay rate is 5 10- and the momentum for the SGD baseline is 0.9. Random cropping and random horizontal flipping are applied to training data. Our code is modified based on the Pytorch classification project Yang (2017),² which was also used by Liu et al. Liu et al. (2020). We provide the restarting frequencies for the exponential and linear scheme for CIFAR 10 and CIFAR 110 in Table 7 below. Using the same notation as the main text, we denote F; as the restarting frequency at the i-th learning rate.
Table 7: Restarting frequencies for CIFARIO and CIFARI00 experiments
CIFARIO
CIFARI00
Linear schedule
Fi 30, F2 60, Fa 90, F4 120 (r 2)
Fi 50, Pb 100, F3 150, F1 200 (r 2)
Exponential schodube
Fi 40, F2 = 50, Fa 63, Fa 78 (r 1:25)
F1 45, P2 68, Fg 101, F4 152 (r == 1.50)
D.2 IMAGENET
The ImageNet dataset contains roughly 1.28 million training color images and 50K validation color images from 1000 classes Russakovsky et al. (2015). We run our ImageNet experiments on ResNet- 50, 101, 152, and 200 with 5 different seeds. Following He et al. (2016a;b), we train each model for 90 epochs with a batch size of 256 and decrease the learning rate by a factor of 10 at the 30th and 60th epoch. The initial learning rate is 0.1, the momentum 0.9, and the weight decay rate is 1 10-5, Random 224 x 224 cropping and random horizontal flipping are applied to training data. We use the official Pytorch ResNet implementation Paszke al. (2019), 6 and run our experiments on 8 Nvidia V100 GPUs We report single-cre crope-croppue top-1 and top-5 errors of our models. In our experiments, we set Fi = 40 the 1st learning rate, F2 80 at the 2nd learning rate, and F3 is linearly decayed from 80 to at the 3rd learning rate (see Table 8).
Table 8: Restarting frequencies for ImageNet experiments
ImageNet
Linear schedule P
40, F2 80, Fa: linearly decayed from 80 to in the last 30 epochs
D.3 TRAINING IMAGENET FEWER NUMBER OF EPOCHS:
Table 9 contains the learning rate and restarting frequency schedule for our experiments on training ImageNet in fewer number of epochs, i.c. the reported results in Table 6 in the main text. Other settings are the same in the full-training ImageNet experiments described in Section D.2 above.
Additional Implementation Details: Implementation details for the ablation study of error rate vs. reduction in epochs and the ablation study of impact of restarting frequency are provided Section F and G below.
D.4 DETAILS ON RESTARTING HYPER-PARAMETRRS SEARCH
In our CIFARIO and CIFARI00 experiments. for both linear and exponential schedule, we conduct hyperparameter searches over the restarting frequencies using our smallest model, 110-
"Implementation available at http://gtth...oommaaa/////heesed Implementation available at httt://dchhhccoooooooosmmeeeeeee
23

---

Under review as a conference paper at ICLR 2021
Table 9: Learning rate and restarting frequency schedule for ImageNet short training, i.e. Table 6 in the main text.
ImageNet
ResNet-50
Decrease the learning rate by a factor of 10 at the 30th and 56th epoch. Train for a total of 80 epochs.
F1 60, F2 105, Fs: linearly decayed from 105 to I in the last 24 opochs
ResNet-101
Decrease the learning rate factor
and 56th epoch. Train for a total 80 epochs.
40, F2 = 80, Ps: linearly decayed from 80 the last 24 epochs
ResNet-152
Docrease the learning rate by a factor of 10 at the 30th and 51th opoch. Train for a total of 75 spochs.
F1 40, F2 80, Fs: linearly decayed from 80 in the last 24 epochs
ResNet-200 Decrease learning rale by factor
46th epoch. Train a lotal epochs.
Fi 40, F2 = S0, Fs: linearly decayed from 8U to the last 14 epochs
making choices based on final validation performance. The same chosen restarting frequencies are applied for all models including Pre-ResNet-110 10, 290, 470, 650, and 1001. In particular, we use 10,000 images from the original training set as validation set. This validation set contains 1,000 and 100 images from each class for CIFARIO and CIFAR 100, respectively. We first train Pre- Pre-ResNet-Il 110 on the remaining 40,000 training images and use the performance on the validation set averaged over 5 random seeds to select the initial restarting frequency F1 and the growth rate r. Both Fj and are selected using grid search from the sets of (20, 25, 30, 35, 40, 45, 50} and {1. 1.25, 1.5, 1.75, 2}. respectively. We then train all models including Pre- Fre-ReeNet-Il 1 110, 290, 470, 650, and 1001 on all 50,000 training images using the selected values of F and r and report the results on the test set which contains 10,000 test images. The reported test performance is averaged over 5 random seeds. We also use the same selected values of Fi and r for our short training experiments in Section 4.3.
For ImageNet experiments, Fj and the growth rate r in the set of {20, 30, 40, 50, 60) and [1, 1.25, 1.5, 1.75, 2), respectively. We select the values of Fi 40 and r = 2 which have the highest final validation accuracy averaged over 5 random seeds. Same as in CIFARIO 10 and CIFAR 100 experiments, we select F1 and r using our smallest model, ResNect-5,, and apply the same selected hyperparameter values for all models including ResNet-50, 101, 152, and 200. We also use the same selected values of F1 and r for our short training experiments in Section 4.3. However, for ResNet-50, we observe that Fi 60 and r = 1.75 yields better performance in short training. All reported results are averaged over 5 random seeds.
use linear scheduling and sweep over the initial restarting frequency
E SRSGD VS. SGD AND SGD + NM ON IMAGENET CLASSIFICATION AND OTHER TASKS
E. COMPARING WITH SGD WITH NESTEROV MOMENTUM ON IMAGENET CLASSIFICATION
In this section, we compare SRSGD with SGD with Nesterov constant momentum (SGD + NM) in training ResNets for ImageNet classification. All hyper- syper-parameters of SGD with constant Nesterov momentum used in our experiments are the same as those of SGD described in section D.2. We list the results in Table 10. Again, SRSGD remarkably outperforms SGD + NM in training ResNets for ImageNet classification, and as the network goes deeper the improvement becomes more significant.
E.2 LONG SHORT- TERM MEMORY (LSTM) TRAINING FOR PIXEL-BY-PIXEL MNIST
In this task, we examine the advantage of SRSGD over SGD and SGD with Nesterov Momentum in training recurrent neural networks. In our experiments, we use an LSTM with different numbers of hidden units (128, 256, and 512) to classify samples from the well-known MNIST dataset LeCun & Cortes (2010). We follow the implementation of Le et al. (2015) and feed each pixel of the image into the RNN sequentially. In addition, we choose a random permutation of 28 x 28- = 784 elements at the beginning of the experiment. This fixed permutation is applied to training and testing sequences. This task is known as permuted MNIST classification, which has become standard to measure the performance of RNNs and their ability capture long term dependencies.
24

---

Under review as a conference paper at ICLR 2021
Table 10: Single crop validation errors (%) on ImageNet of ResNets trained with SGD + NM and SRSGD. We report the results of SRSGD with the increasing restarting frequency in the first two learning rates. In the last learning rate, the restarting frequency is linearly decreased from 70 to 1. For baseline results, we also include the reported single-crop validation errors He et al. (2016c) (in parentheses).
Network
Params
SGD NM
SRSGD
Improvement
top-1
top-5
top
top-5
top-1 top-5
ResNet-50
25.56M
24.27
0.07
7.17
0.07
23.85 1 0.09
7.10 1 0.09
0.42 0.07
ResNet-101
14.55M
22.32 + 0.05
6,18 0.05
22.06 + 0.10
6.09 + 0.07
0.26 0.09
ResNet- 152
60.19M
21.77 1: 0.14
5.86 1: 0.09
21.46 + 0.07
5.69
+ 0.03
0.31
0.17
20sNet-200
64.67M
21.98 0.22
5.99 0.20
20.93 1 0.13
5.57 1 0.05
1.05
0.42
Implementation and Training Details: For the LSTM model, we initialize the forget bias to 1 and other biases to O. All weights matrices are initialized orthogonally except for the hidden-to-hidden weight matrices, which are initialized to be identity matrices. We train each model for 350 epochs with the imitial learning rate of 0.01. The learning rate was reduced by a factor of 10 at epoch 200 and 300. The momentum is set to 0.9 for SGD with standard and Nesterov constant momentum. The restart schedule for SRSGD is set to 90, 30, 90 The restart schedule changes at epoch 200 and 300. In all experiments, we use batch size 128 and the gradients are clipped so that their I.2 norm are at most 1. Our code is based on the code from the exponential RNN's Github.?
Our experiments corroborate the superiority of SRSGD over the two baselines. SRSGD yields much smaller test error and converges faster than SGD with standard and Nesterov constant momentum across all settings with different number of LSTM hidden units. We summarize our results in Table 1l and Figure 7.
Results:
Table 11:
Test errors (%) on Permuted MNIST of trained with SGD, SGD + NM and SRSGD, The LSTM model has 128 hidden units. In all experiments, we use the initial learning rate of 0.01, which is reduced by a factor of 10 at epoch 200 and 300. All models are trained for 350 epochs. The momentum for SGD and SGD + NM set to 0.9. The restart schedule SRSGD is set to 90, 30. and 90.
Network
No. Hidden Units
SGD
SGD + NM
SRSGD
Improvvemnnt over SGD/SGD + NM
LSTM
128
10.10 +: 0.57
9.75
8.61 + 0.30
1.49/1.14
LSTM
256
10.42 1 0.63
10.09 1 0.61
9.03 : 0.23
1.39/1.06
LSTM
512
10.04 + 0.35
9.55 1.09
8.49 +: 1.59
1.55/1.06
SGD Momentum
SGD Nesterov Momentum
SRSGD
10a
Train loss
10-1
25K
50K
75K
100K
125K
150K
Iteration
Figure 7: Training loss vs. training iterations of LSTM trained with SGD (red), SGD + NM (green), and SRSGD (blue) for PMNIST classification tasks.
E.3 WASSERSTEIN GENERATIVE ADVERSARIAL NETWORKS (WGAN) TRAINING ON MNIST
We investigate the advantage of SRSGD over SGD with standard and Nesterov momentum in training deep generative models. In our experiments, we train WGAN with gradient penalty Gulrajani
Implementation available at http:///jhuub.oo//ccccaa////////
25

---

Under review as a conference paper at ICLR 2021
al. (2017) MNIST. We evaluate models using the discriminator's loss, ie. the Earth Moving distance estimate, since in WGAN lower discriminator loss and better sample quality are correlated Arjovsky et al. (2017).
Implementation and Training Details: The detailed implementations of our generator and discrim- inator given below. For the generator, set latent dim to 100 and 32. For the discriminator, we set d to 32. We train each model for 350 epochs with the initial learning rate of 0.01. The learning rate reduced by factor of 10 at epoch 200 and 300. The momentum standard and Nesterov constant momentum. The restart schedule for SRSGD is set to 60, 120, 180. The restart schedule changes at epoch 200 and 300. In all experiments, we use batch size 64. Our code is based on the code from the Pytorch WGAN-GP Github."
to 0.9 for SGD with
import torch import torch. nn as nn
class Generator (nn nn Module):
def .-init-- -eaittt((seff (self, latent.dim. d=32): (ipprr))..init_..
self. net = mn. Sequential
ConvTransposc2d (wareeddddaeeeeeeaaa (latent_din dim d 8, 4, 1, 0),
nn (dt 8), nn (eLUU
nn. ConvTranspose2d 8, d 4, 4, 2. 1), (d dd 4), nn ReLU(Truee.
nn. ConvTransposc2u * 4, * 2, 4, 2, 1), nn. (dt 2), ReLU (True)
na. ConvTransposedddd * 2, 1, 4, 2, 1). na. nn. Tanh
def forward x): return self. (x)
class Discriminator .an.ennnnnMMM. Module)
def initt (self. d=32):
super()
self net = nn. Sequential ma (1 d. 4, 2. 1), nn InstanceNorm2d(d)) nn (0.2)
na. Conv2d d 2. 4, 2, 1), nn. InstaanceNNrm2dd (d * 2),
(0..)
nn. Conv2d x 2, 4, 4, 2, 1),
nn InstanceNorm2d (d * 4),
nn LeakyReL.U (0.2)
nn. (o * 4, 1, 4, 1, 0).
def forward x): outputs self net return outputs squeeze
Our SRSGD is still better than both the baselines. SRSGD achieves smaller discriminator loss, i.e. Earth Moving distance estimate, and converges faster than SGD with standard and Nesterov constant momentum. We summarize our results in Table 12 and Figure 8. We also demonstrate the
Results:
Implementation available at attp:///thhaccommmmmm/yyncyggggg
26

---

Under review as a conference paper at ICLR 2021
digits generated by the trained WGAN in Figure 9. By visually evaluation, observe that samples generated by the WGAN trained with SRSGD look slightly better than those generated by the WGAN trained with SGD with standard and Nesterov constant momentum.
Discriminator loss (i.e. Earth Moving distance estimate) of the WGAN with gradient penalty trained MNIST with SGD, SGD NM and SRSGD. In all experiments, learning rate 0.01, which is reduced by factor 10 at epoch 200 and 300. All models are trained for 350 epochs. The momentum for SGD and SGD NM is set to 0.9. The restart schedule in SRSGD is set to 60, 120, and 180.
Table 12:
the initial
Task
SGD
SGD NM
SRSGD
Improvemnnt SGD/SGD NM
MNIST
0.71 E 0.10
0.58 + 0.03
0.44 + 0.06
0.27/0.14
SGD Momentum
SGD Nesterov Momentum
SRSGD
10a
Moving Distance Estimate
10a
50
100
150
200
250
300
350
Epoch
Figure 8: Earth Moving distance estimate (i.e. discriminator loss) vs. training epochs of WGAN with gradient penalty trained with SGD (red), SGD NM (green), and SRSGD (blue) on MNIST.
2
3
5
[
/ 5 6 2 8
7 6 /
0
7
S
7 4
2
H 4
8
2
/
5 3
0
6
4
6
6
5
6
2
7
7
1
0
9
0
7
4
0
2
9
7
3
9
0
4 9
2 4 5 5
03
S
9
7
8 8 / 9
0 2
9
2
}
7
0
7
9
(
3
O
9
9
8
1
6
2
0 9 3 4 6 7
0
3
5
5
9
8
6
3
2
4
5
0
1
3
7
1
8
7
/
1 3
5 8
7
2
7
4
4 5
0
9
0
9
5
1
7
6
1
r
9
6
1
4
0
7
7
9
5
6
3 92
O 9
6
5
SGD
SGD + NM
SRSGD
Figure 9: MNIST digits generated by WGAN trained with gradient penalty by SGD (left), SGD + NM (middle), and SRSGD (right).
F ERROR RATE VS. REDUCTION IN TRAINING EPOCHS
F.1 IMPLEMENTATION DETAILS
CIFARIO (Figure 4, left, in the main text) and CIFAR100 (Figure in this Appendix): Except for learning rate schedule, we use the same setting described in Section D.1 above and Section 4.1 in the main text. Table 13 contains the learning rate schedule for each number of epoch reduction in Figure (left) in the main text and Figure 1I below.
ImageNet (Figure 4, right, the main text): Except for the total number of training epochs, other settings are similar experiments for training ImageNet in fewer number of epochs described in Section D.3. In particular, the learning rate and restarting frequency schedule still follow those in Table 9 above. We examine different numbers of training epochs: 90 (0 epoch reduction), 80 (10 epochs reduction), 75 (15 epochs reduction), 70 (20 epochs reduction), 65 (25 epochs reduction), and 60 (30 epochs reduction).
27

---

Under review as a conference paper at ICLR 2021
Table 13: Learning rate (LR) schedule for the ablation study of error rate vs, reduction in training epochs for CIFAR 10 experiments, i.e. Figure 4 in the main text and for CIFARIO0 experiments, i.e. Figure 11 in this Appendix.
Rof Epoch Reduction
IR Schedule
Decrease the LR by factor of 10 the 80th, 120th and 160th spoch. Train for a total of 200 opochs.
Decrease by factor 10 the 80th, 115th 150th epoch. Train for total 185 epachs.
30
Decrease the L.R by factor of 10 the 80th, 110th and 140th spoch. Train for a total of 170 epachs.
45
Decrease the LR by factor of 10 the 80th, 105th and 130th spoch. Train for total of 155 epochs.
Decrease the LR by factor 10 the 80th, 100th 120th epech. Train for total 140 epochs.
75
Decrease the LR by a factor of at the 80th, 95th and 110th epach. Train for total of 125 epuchs.
90
Decrease the LR by a factor of 10 at the 80th, 90th and 100th spach. Train for total of 110 epochs.
100
Decrease the LR factor 10 the 80th, 90th and 95th epoch. Train for total of 100 epochs.
Table 14: Classification test error (%) of SGD short training (100 epochs), SGD full training (200 epochs), SRSGD short training (100 epochs), and SRSGD full training (200 epochs) on CIFARIO 10 SGD short training yields much worse test errors than the others while SRSGD short training yields either comparable or even better results than SGD full training.
Network
SGD short training
SGD full training
SRSGD short training
SRSGD full training
Pre-RecNet-I11 110
6.36 + 0.12
5.25 + 0.14
5.43 + 0.18
4.93 + 0.13
Pre-ResNet-290
5.81 + 0.10
5.05 : 0.23
4.83 + 0.11
4.37 + 0.15
Pre-ResNet-470
5.59 + 0.19
4.92 + 0.10
4.61 0.17
1.18 0.09
Table 15: Classification test error (%) of SGD short training (100 epochs), SGD full training (200 epochs), SRSGD short training (100 epochs), and SRSGD full training (200 epochs) on CIFARI00. SGD short training yields worse test errors than the others while SRSGD short training yields either comparable or even better results than SGD full training.
Network
SGD short training
SGD full training
SRSGD short training
SRSGD full training
Pre-ResNet-110
24.34 0.21
23.75 + 0.20
23.85 + 0.19
23.49 + 0.23
2re-ResNat-290
22.70 0.25
21.78 0.21
21.77 + 0.43
21.49 1: 0.27
Pre: 4770
22.43 1. 0.18
21.43 0.30
21.42 1: 0.19
20.71 1: 0.32
F.2
SHORT TRAINING ON CIFARIO/CIFARION USING SGD
For better comparison between SRSGD training using fewer epochs and SGD full training, we also conduct experiments with SGD training using fewer epochs on CIFARIO and CIFAR100. Table 14 and 15 compares SRSGD short training using 100 epoch, SGD short training using 100 epochs, SRSGD full training using 200 epochs, and SGD full training using 200 epochs for Pre-ResNet- 100 290, and 470 on CIFARIO and CIFAR100, respectively. The learning rate schedule for SGD short training using 100 epochs is the same as the learning rate schedule for SRSGD short training using 100 epoch given in Section 4 and in Table 13 above. In particular, for both SGD and SRSGD training using 100 epochs, we decrease the learning rate by a factor of 10 at the 80th, 90th, and 95th epoch. We observe that SGD short training has the worst performance compared to the others while SRSGD short training yields either comparable or even better results than SGD full training.
F.3 ADDITIONAL EXPERIMENTAL RESULTS
Figure 10 shows error rate vs. reduction in epochs for all models trained on CIFARIO and ImageNet.
It is a more complete version of Figure 4 in the main text. Table 16 and Table 17 provide detailed test errors vs. number of training epoch reduction reported in Figure 4 and Figure 10. We also conduct an additional ablation study of error rate vs. reduction in epochs for CIFAR 100 and include the results in Figure 11 and Table 18 below.
28

---

Under review as a conference paper at ICLR 2021
Pre- Pre-ReeNNtt-11 - Pre-ResNet-290
ResNet-50
ResNet-101
Pre-ResNet-470 Pre-ResNet-650
-
ResNet-152
ResNet-200
Pre-ResNet-1001
CIFAR10
ImageNet
5.5
26.0
Validation Error
25.0
Test Error
Single Crop
24.0
23.0
22.0
21.0
15
30
45
60
75
10
15
20
25
Number of Epoch Reduction
Figure 10: Test error vs. number of training epochs. Dashed lines are test emrors SGD trained in 200 epochs for CIFARIO and 90 epochs for ImageNet. For CIFAR, SRSGD with fewer epochs achieves comparable results to SRSGD with 200 epochs. For ImageNet, training with less epochs slightly decreases the performance of SRSGD but still achieves comparable results 200-epoch SGD.
Table 16: Test error vs. number of training epochs for CIFARIO
Network
110 (90 less)
125 (75 less)
140 (60 less)
155 (45 less)
170 (30 less)
185 (15 less)
200 (full trainings)
Pre-ResNet-110
Pre-ResNet-290
4.80 0.14
4.71 = 0.13
4.58 + 0.11
4.45 + 0.09
4.43 1 0.09
4.44 +: 0.11
4.37 0.15
Pre-ResNet-470
1.52 = 0.16
4.13 = 0.12
4.29 = 0.11
4.33 = 0.07
4.23 - 0.12
4.18 + 0.09
4.18 + 0.09
Pre-ResNer-650
4.35 = 0.10
4.24 = 0.05
4.22 = 0.15
4.10 = 0.15
4.12 0.14
4.02 + 0.05
4.00 +: 0.07
Pre Cee-ReNNet-IO0 1001
4.23 0.19
4.13 1: 0.12
4.08 0.15
4.10 0.09
3.93 1: 0.11
4.06 1: 0.14
3.87 0.07
Table 17: Top single crop validation error vs. number of training epochs for ImageNet
Network
60 (30 loss)
65 (25 loss)
(20 less)
75 (15 less)
(10 less)
90 (full trainings)
ResNet-50
25. + 0.42
25.02 = 0.15
21.77 0.14
21.38 0.01
24.30 + 0.21
23.85 + 0.09
ResNet-101
23.11 + 0.10
22.79 0.01
22.71 0.21
22.56 0.10
22.44
0.03
22.06 + 0.10
152
+:
22.12 0.04
21.97
0.07
ResNet-200
21.92 1: 0.17 21.69 + 0.20
21.64 0.03
21.45 0.06
21.30 1: 0.03
20.93 0.13
Table 18: Test error number of training epochs for CIFAR100
Network
110
125 (75 less)
140 less)
155 less)
170 less)
185 (15 less)
200 (full trainings)
Re0
24.06
1
23.49
Pre-ResNet-290
21.96 0.45
21.77 0.21
21.67 + 0.37
21.56 0.33
21.38 0.44
21.47 0.32
21.49 0.27
Pro-RosNet-470
21.35 + 0.17
21.25 0.17
21.21 + 0.18
21.09 = 0.28
20.87 0.28
20.81 + 0.32
20.71 4: 0.32
Pre-ResNet-650
21.18 4: 0.27
20.95 +: 0.13
20.77 + 0.31
20.61
0.19
20.57 0.13
20.47 4 0.07
20.36 d: 0.25
Pre ResNet-100 1001
20.27 1. 0.17
20.03 0.13
20.05 1: 0.22
19.74 0.18
19.71 0.22
19.67 0.22
19.75 0.11
G IMPACT OF RESTARTING FREQUENCY FOR IMAGENET AND CIFAR 100
G.1 IMPLEMENTATION DETAILS
For the CIFAR10 experiments Pre-ResNet-200 in Figure 5 in the main text, well as the CIFAR100 100 and ImageNet experiments Figure 14 and 15 in this Appendix, we vary the initial restarting frequency F,. Other settings are the same described in Section D above.
29

---

Under review as a conference paper at ICLR 2021
Pre-ResNet-101
Pre-ResNet-290
Pre-ResNet-440 Pre-ResNet-650
24.0
Test Error
23.0
22.0
21.0
20.0
0
15
30
45
60
75
90
Number of Epoch Reduction
Figure 11: Test error number of epoch reduction in CIFAR100 training. The dashed lines test errors of the SGD baseline. For CIFARI00, SRSGD training with fewer epochs can achieve comparable results SRSGD training with full 200 epochs. In some cases, such with Pre-ResNet- 290 and 1001, SRSGD training with fewer epochs achieves even better results than SRSGD training with full 200 epochs.
r=
r=1.0
r=2.0
r=10.0
100
5.3
Test Error
Train Loss
10-1
10-2
4.9
0
100 Epoch
200
0.7
1
2
10
Growth Rate (r)
Figure 12: Training loss (left) and test eπror (right) of Pre-ResNet-I 10 trained on CIFAR1O with different growth rate (linear schedule). Here, we fix the initial restarting frequency trainings. Increasing the restarting frequency during training yields better results than decreasing the restarting frequency. but increasing the restarting frequency too fast and too much also diminishes the performance of SRSGD.
30 for all
G.2 IMPACT OF THE GROWTH RATE r
We do ablation study for the growth to understand its impact the behavior of SRSGD, We choose a case study of training Pre-ResNet-I1 10 on CIFAR10 using SRSGD with linear schedule scheme for the restarting frequency. We fix the initial restarting frequency Fi 30 and vary the growth rate We choose r from the set of (0.7. 1.0, 2.0, 10.0). These values of r represent four different scenarios. When r = 0.7, the restarting frequency decreases every time the learning rate reduced by a factor of 10. When
1.0, the restarting frequency stays constant during the training. When r 2.0, the restarting frequency increases every time the learning rate is reduced by factor of 10. Finally, when much faster and to larger values. Figure 12 summarizes the results of our ablation study. We observe that for CIFAR1O, decreasing the restarting frequency or keeping it constant during training yields worse results than increasing the restarting frequency. However, increasing the restarting frequency much also diminishes the performance of SRSGD.
10.0, it is similar to when 2.0, but the restarting frequency increases
30

---

Under review as a conference paper at ICLR 2021
G.3 ADDITIONAL EXPERIMENTAL RESULTS
To complete our study on the impact of restarting frequency in Section 5.2 in the main text, we examine the case of CIFARI00 and ImageNet in this section. We summarize our results in Figure 14 and 15 below. Also, Figure 13 is more detailed version of Figure 5 in the main text.
10a
NASGD
11-4
71-30
Approuimate
withott
Test Error of NASGD
32.44 0.84
Train Loss
Approsimate NASGD
11-10
Test Error
momentum
10-1
71-46
Approumate NA3GO
71-60
Approximate
10"7
SGD without
16000
150
200
250
30
40
50
Epoch
Initial Restarting Frequency (F,)
Figure 13: Training loss (left) and test error (right) of Pre-ResNet-290 trained on CIFARIO with different initial restarting frequencies F1 (linear schedule). SRSGD with small Fi approximates SGD without momentum, while SRSGD with large Fi approximates NASGD.Th training loss curve and test accuracy of NASGD are shown in red and confirm the result of Theorem that NASGD accumulates error due to the stochastic gradients.
NASGO
Fi-3
27.0
Appreximatt
Error
26.0
SGD without momentum
66.44 0.90
Train Loss
10f
Approvimete
NASGD
P1-25
Test Error
Appros mate
Approximate SGD without momentum
F2-E0
22.0
10-2
21.0
50
100
150
200
250
10
30
40
50
60 70 80
90
Epoch
Initial Restarting Frequency (F,)
Figure 14: Training loss and test error of Pre-ResNet-290 trained on CIFARIO0 with different initial restarting frequencies Fi (linear schedule). SRSGD with small Fi approximates SGD without momentum, while SRSGD with large F1 approximates NASGD. The training loss curve and test accuracy of NASGD shown in red and confirm the result of Theorem I that NASGD accumulates error due to the stochastic gradients.
10"
Approkimate
1105
SGD without momentum
Approximate NASGD
10
F1-20
25.0
Train Loss
Approximate NASGD
F1-40
Test T Error
10
11-40
F1-100
F1-80
24.0
2 10
F1-200
F1-300
Approximate
23.0
10"
SGD without
momentum
20
40
80
1
5
20
40
60
80
100
200
300
Epoch
Initial Restarting Frequency (F,)
Figure 15: Training loss and test error of ResNet-101 trained on ImageNet with different initial restarting frequencies F, We use linear schedule and linearly decrease the restarting frequency to I at the last learning rate. SRSGD with small F, approximates SGD without momentum, while SRSGD with large F1 approximates NASGD,
31

---

Under review as a conference paper at ICLR 2021
H FULL TRAINING WITH LESS EPOCHS AT THE INTERMEDIATE LEARNING RATES
We explore SRSGD full training (200 epochs CIFAR and 90 epochs ImageNet) with less number of epochs at the intermediate learning rates and report the results in Table 19, 20, 21 and Figure 16, 17. 18 below. The settings and implementation details here are similar those in Section F, but using all 200 epochs for CIFAR experiments and 90 epochs for ImageNet experiments.
Tre-ResNet-290
Tre-ResNet-470
Pre-ResNett650
Pre-ResNet-
5.5
5.0
Test Error
4.5
4.0
10 15
20
25
30
Number of Epoch Reduction at the 2nd and 3rd learning rate
Figure 16: Test error when using new learning rate schedules with less training epochs the 2nd and 3rd learning rate for CIFAR10. We still train in full 200 epochs in this experiment. On the x-axis, 10, for example, means we reduce the number of training epochs by 10 at each intermediate learning rate, i.e the 2nd and 3rd learning rate. The dashed lines are test errors of the SGD baseline.
Table 19: Test error when using new learning rate schedules with less training epochs at the 2nd and 3rd learning rate for CIFARIO. We still train in full 200 epochs this experiment, In the table, 80-90- 100, for example, means reduce the learning rate by factor of 10 at the 80th, 90th, and 100th epoch.
Network
80-90 90- 100
-0-95-11 110
80
1100001110 120
80 105 - 130
80
110- 140
80-
905115- 150
80 120 160
Pre-ResNet-110
5.32 0.14
5.24 0.17
5.11 + 0.13
5.04 + 0.15
4.92 2
4.95 + 0.12
4.93 4: 0.13
Pro-ResNet-290
4.73
1.67 0.12
1.53 0.10
1.40 0.11
1.42 0.09
1.42
4.37 = 0.15
Pre-ResNet-470
4.48 0.16
4.34 0.10
4.25 + 0.12
4.28 - 0.10
4.19 0.10
1.14::.00
4.18 + 0.09
Pre 650
4.25 1: 0.13
4.12 1: 0.06
4.13 1: 0.09
4.03 1: 0.11
4.04 0.11
4.04 1: 0.04
4.00 + 0.07
Pre- Pre-ResNet-100 1001
4.14
0.18
4.06
1:
0.12
4.04 1: 0.15
4.08 +: 0.09
3.92 0.13
4.05 1: 0.14
3.87 + 0.07
Table 20: Test error when using new learning rate schedules with less training epochs at the 2nd and 3rd learning rate for CIFAR100. We still train in full 200 epochs in this experiment. In the table, 80-90-100, for example, means we reduce the learning rate by factor of 10 at the 80th, 90th, and 100th epoch.
150
120
10
23.65 4: 0.14
23.96 1: 0.26
23.97 + 0.31
23.53 = 0.13
23.57 = 0.36
23.68 4 0.24
23.49 + 0.23
Pre 2900
21.94 1: 0.44
21.71 1: 0.27
21.55 1 0.40
21.44 : 0.31
21.37 + 0.45
21.47 1: 0.32
21.49 1 0.27
Pro-ResNet-470
21.29 +: 0.11
21.21
0.14
21.17 + 0.18
20.99
0.28
20.81 0.22
20.80 - 0.31
20.71 - 0.32
Pro-ReaNet-650
21.11
0.24
20.91 0.17
20.00 + 0.33
20.52
0.18
20.51 0.16
20.43 0.10
20.36 + 0.25
Ro--ReNNer-O0 1001
20.21
20.00 0.11
19.86 +: 0.19
19.55 4 0.19
19.09
19.60 0.17
19.75 4 0.11
32

---

Under review as a conference paper at ICLR 2021
Pre-ResNet-101
Pre- Nre-Re0
Pre-ResNet-470
Pre-ResNet-650
Pre-ResNet-1001
24.0
Test Error
23.0
21.0
20.0
Number of Epoch Reduction at the 2nd and 3rd learning rate
Figure 17: Test error when using new learning rate schedules with less training epochs the 2nd and 3rd learning rate for CIFAR100 We still train in full 200 epochs in this experiment. On the x-axis, 10, for example, means we reduce the number of training epochs by 10 at each intermediate learning rate, i.e. the 2nd and 3rd learning rate. The dashed lines are test errors of the SGD baseline.
ResNet-50
ResNet-101
ResNet-152
- ResNet-200
ImageNet
Validation Error
24.0
Single Crop
23.0
22.0
21.0
10
15 20
Number of Epoch Reduction at the 2nd learning rate
Figure 18: Test eтror when using new learning rate schedules with less training epochs at the 2nd learning rate for ImageNet. We still train in full 90 epochs in this experiment. On the x-axis, 10, for example, means we reduce the number of training epochs by 10 at the 2nd learning rate. The dashed lines are errors of the SGD baseline.
Table 21: Top single crop validation error when using new learning rate schedules with less training epochs the 2nd learning rate for ImageNet. We still train in full 90 epochs in this experiment. In the table, 30-40, for example, means reduce the learning rate by factor of 10 at the 30th and 40th epoch.
Network
30
30-45
30
30
30-60 60
ResNet-50
24.44 + 0.16
24.06 + 0.15
24.05 0.09
23.89 = 0.14
23.85 + 0.09
ResNet- 101
22.49 1 0.09
22.51 0.05
22.24
0.01
22.20 = 0.01
22.06 1: 0.10
ResNei-152
0.01
21.84
21.65
21.46 - 0.07
ResNet-200
21.65 + 0.02
21.27 0.14
21.12 0.02
21.07 = 0.01
20.93 + 0.18
I VISUALIZATION OF SRSGD'S TRAJECTORY
Here we visualize the training trajectory through bad minima of SRSGD, SGD with constant momen- tum, and SGD. In particular, we train neural net classifier (2019) and find bad minima along its training. Each red dot in Figure 19 represents the trained model after each 10 epochs in the training. From each red dot, we search for nearby bad local minima,
swiss roll data in Huang et al.
33

---

Under review as a conference paper at ICLR 2021
which are the blue dots. Those bad local minima achieve good training but bad test error. We plots the trained models and bad local minima using PCA Wold et al. (1987) and t-SNE Maaten Hinton (2008) embedding. The blue color bar is for the test accuracy of bad local minima; the red color bar is for the number of training epochs.
PCA Embedding of the Trajectory
4000
SGD
SGD + Momentum
SRSGD
t-SNE Embedding of the Trajectory
SGD
SGD + Momentum
SRSGD
Figure 19: Trajectory through bad minima of SGD, SGD with constant momentum, and SRSGD during the training: we train neural net classifier and plot the iterates of SGD after each ten epoch (red dots). We also plot locations of nearby "bad" minima with poor generalization (blue dots). We visualize these using PCA and t-SNE embedding. The blue color bar is for the test accuracy of bad local minima while the red color bar is for the number of training epochs. All blue dots for SGD with constant momentum and SRSGD achieve near perfect train accuracy, but with test accuracy below 59%. All blue dots for SGD achieves average train accuracy of 73.1 1% and with test accuracy also below 59%. The final iterate (yellow star) of SGD, SGD with constant momentum, and SRSGD) achieve 73.13%, 99.25%, and 100.0% test accuracy, respectively.
(CONTINUED NEXT PAGE)
34

---

Under review as a conference paper at ICLR 2021
J SRSGD IMPLEMENTATION IN PYTORCH
import torch
from
optimizer import Optimizer, required
class SRSGD( Optimizer):
Scheduled Restart SGD.
Args:
params (iterable): iterable of parameters optimize
or dicts defining parameter groups
Ir (float): learning rate.
weight.decay (float, optional): weight decay (L2 penalty) (
default: 0)
iter.count (integer); count the iterations mod 200
Example:
optimizer torch optim RISGD(mode)) w parameters Ir=0.1, weight,deeay=Se iter,count=!) >>> optimizer. zero-grad
>>>
>>> loss-fn (iodel))n target). (rrget).bcckwarr backward
>>> optimizer. ()
>>> iter-count optimizer. .tt
Formula:
v-(1+13 p-t Iræg.t
[1+1] = v [t+1} (iter count)/(iter count43)*(V (t+1) - v t)
...
def
- params, Ir=required weight decay=0.,
iter_count=l. restaring-iter:00::
if not required and < 0.0:
raise ValueError (" "'haalid_leaminn---nee..f format(Ir))
if weight.decay < 0.0:
raise ValueError htw.aaaa....iihhh.......eeeeeee formatt (eight_decay))
if itert < 1:
raise VarueError if restarting iter < 1:
format (iter. (iter_count))
raise ValueError (" I formatt restarting.iter)
defaults = diet(r woight.ecayswwiihh.dee iter_count=
itun_
restarting ita.ttiingiterrrestaatteee iter)
super (SRSGD, self)...init... Sraitt..pprram, defaults)
def s.ststtate... (self, state):
super settt (state)
def ipdate_iter
idx =
for group in self param groups: if idx 1:
group iter count'] #=
if group iiter.cuutt' >= group "' restartinngiiter ']: group iter_count")
idx
return group 'iter_ group restarting-iter')
def step (self, closure=None): ann
Perform single optimization step
Arguments: closure (callable. optional): closure that reevaluates the model and returns the loss.
loss None
if closure is None:
35

---

Under review as a conference paper at ICLR 2021
loss closure
for group self para.param.......m...aa.a.aaaa pat.paaaaaaappps... weight_decay = group laappp'weiege weighttdecayy)
momentum = (groupl iter_count'] 1.) /( group [iter__ount']
2.)
for p group[ ppraams
if p.grad is None: continue
d.p p. p...rdd.co data if weight_decay !=0:
d.p. (weight decay, p. data)
param state = state
if "momentum not param
buf0 = param_state coamentum.buffer " torch. clone (p .data). detach
else:
buf0 param_state imomentum_buffcc
bufl = data group 'r
data bufl mooentum=(bbufl buf0)
param-state momentum.buffer bufl
iter_count, iter_total self. update_iter()
return loss
K SRSGD IMPLEMENTATION KERAS
import numpy np
import tensorflow as from keras import backend as K
from keras. optimizers import Optimizer from keras legacy import interfaces if K. backend () 'tensorflow': import tensorflow as
class SRSGD Optimizer):
Scheduled Restart Stochastic gradient descent optimizer. Includes support for Nesterov momentum and learning rate decay.
# Arguments
learning-rate: float >= 0. Learning rate.
def ..init__ learning.ratc=00001 iter,countzl, restarting.iter iter
=40, ** =*wargg)):
learning rate kwargs. ( 'Ir', (''r' learning rate)
self. initial decay kwargs
0.0)
(SRSGD, self)...init... (**kwargs) .la......mm.............
with K. namecsccope
self iteratioos = variable (0, 'type='int64", iterations')
int64', name=
self ler.ingarnng. K. variable (learning-rate. name=
"earning_rate"))
self. decay K. variable Preiable(self.... wet.leeeiei.illldeeee.........
name= name='decay ')
# for srsgd
self, iter_count K. variable (iter_count. dtype= int64', name=
'iter_count')
self, restartiinggg..... -tter iter = K. variable www.aaaleeeeeeeaaaaaeaaaar (restarting-iter, dtype= int64 name= restarting.iter
self, nesterov nesterov
36

---

Under review as a conference paper at ICLR 2021
@interfaces legaecyger.upplacss.spppo @K. symbolic
def get get.updates (self, loss params):
grads self. get.gradients (loss. params) self updates [K. update.. add add self. iterations, 1)]
momentum = (K. cast iter count dtype=K. dtype (self. ( ) 1.)/(K. cast iter.count, dtype=K. dtype (self. decay)) + 2.)
Ir self, rea if self. initial decay > 0:
Ir lr * (1. (1. + self decay K. cast (self. iterations,
K. dtype (self.decay decay)
))
momentum shapes [K. int.int.sappp (p) for in params]
moments [K. variable (value=K, vet_value (p), dtype= dtype decay). , name= moment_" str(i)) for (i, p) in enumerate (actatteeppran (params)]
self. weights = [self iterations] moments + [self iter count]
for p. g. in (params, grads moments):
= Ir new_p = momentum * (v (v- m) self. apdates.append (K. update (m, v))
# Apply constraints.
if getattr 'constraint', None) is not None:
new.p constraint (new.p)
self. updates append (K. update new.p))
condition all less self, iter_count, self restarting.iter) new new_iter_count K. switch condition, self itt. 1, self. iter count self restarting iter 1)
self updates. append (K. update self, count, new iter count))
return self self. updates
def get_config config ('learning-rate" float get (self. learning.rate)
'deayy: float (K. get value (self (self.decca))))
'iter_count': int vel (self. itter
Destarting-iter int(K. get value restarin iter ))}
base_config = (SRSOD, (ett)).et.coofig..
return dict (list items ()) listfc items ))))
37


Reviews:
[{"review_id": "xdUsxnVs_Sd", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "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": "UPDATE:\n\nI find the main contribution of the work to be the empirical analysis. I personally liked this paper, but I must agree with the other reviewers that improving the theoretical results will strengthen the paper's impact. This would require a major revision not suited for a conference rebuttal, and so, for now, I have downgraded my score to a borderline accept, but I look forward to seeing a future revision of this paper.\n\n#### Summary\nThis work proposes to combine Nesterov momentum (with the Nesterov (1983) $\\frac{t_{k}-1}{t_{k+1}}$ momentum schedule for convex functions) and the scheduled restart method (of Roulet and d’Aspremont (2017)) for minimizing finite-sums with stochastic mini-batch gradients. This work theoretically argues that adaptive restarts can prevent the error accumulation identified by Devolder et al. (2017) for $\\delta$-inexact gradients.  The stabilizing property is empirically explored (to a small degree) on a Laplacian cycle graph quadratic function with additive Gaussian noise. The most extensive results, which are conducted with mini-batch gradients on CIFAR10 and ImageNet, indicate that adaptive restarts accelerate convergence of deep neural networks.\n\nAdaptive restarts with Nesterov momentum is shown to be very effective for deep learning, hence my strong accept score, though I think there is room for improvement.\n\n---\n\n#### Originality\n\nWhile adaptive restarts have previously been used to improve the convergence of Nesterov's method, this work focuses on using these adaptive restarts to prevent error accumulation with stochastic gradients. The motivation is sufficiently original in my opinion, and very interesting!\n\n---\n\n#### Quality and Significance\n\nI think this work does not reach its full potential. Acceleration of adaptive restarts has been demonstrated in previous work with deterministic gradients (e.g., Roulet and d’Aspremont (2017)). This work provides empirical evidence of similar behaviour for deep learning with mini-batch gradients, but the purpose (and novelty) in this work is the argument that adaptive restarts stabilize convergence.\n\n*On the results:*\nThe deep learning experiments are very thorough. One minor observation is that the accuracies in Table 5 are slightly lower than established benchmarks, and fall within the margin of improvement (at least on ResNet-50). It is common to include an additional decay at the 80th epoch (not just 30 and 60) on ImageNet; so I suspect this may be the reason for the slightly weaker baselines.\n\n*Room for improvement*:\nThe theorem of error accumulation is conducted in the Appendix under a $\\delta$-bounded variance assumption. This is an interesting result, but unfortunately wouldn't even hold for least-squares problems when using mini-batch gradients, and so seems disconnected from practical machine learning problems. The assumption of Theorem 2 that the cardinality of $\\text{set}( k | E[f(w_{k+1})] \\geq E[f(w_{k}] )$ is finite also seems strong. Moreover, the stabilizing hypothesis is only weakly evaluated on a single run of a quadratic and logistic MNIST problem. Extending results to finite-sum settings (i.e., without the bounded variance assumption) would be a great improvement. A reference is missed to [1], where instability of Nesterov's method is demonstrated for smooth strongly-convex finite-sums under interpolation. In Section 5 in that work (Conclusion), they posit that adaptive restarts can be used to stabilize the method to the destabilizing behaviour they identify, but do not explore this direction. There may be possible avenues for extending the stabilizing results in this section to finite-sums\n\n[1] M. Assran and M. Rabbat, \"On the Convergence of Nesterov's Accelerated Gradient Method in Stochastic Settings,\" ICML 2020\n\n---\n\n#### Clarity\n\nClarity leaves room for improvement. Firstly, it should be clearly stated in the introduction and the abstract that theoretical results in this work considers Nesterov momentum with time-varying momentum (i.e., following Nesterov (1983)). Assumptions for the theorems should also be stated in the main text (not buried in the appendix), e.g., the $\\delta$-bounded variance assumption, and the update rule for the momentum parameter.\n\nNote, that NAG can be run with time-varying momentum, which as indicated achieves the optimal rate on convex functions, or it can be run with constant momentum (Nesterov, 2004), which achieves the optimal rate for strongly-convex functions. Therefore, the subtle point that NAG is given by equation (3), but with time-varying momentum, is not good practice in my opinion.\n\nThe following claim is not true in general \"Since NAG momentum achieves a much better convergence rate than constant momentum with exact gradient, we consider the following question:”  this holds to the best of my knowledge for convex functions, but NAG achieves the optimal convergence rate with constant momentum for strongly-convex function (Nesterov, 2004).\n\nPlease consider rewording \"SGD\" to \"HB-SGD\" since you use it to refer to SGD with heavy-ball momentum. Also consider renaming the proposed momentum restarted method since it does not indicate that momentum is used.", "extra_scores": {}, "extra_text": {}}, {"review_id": "qVW5tR_lv3P", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "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 to restart the momentum parameter in SGD (with Nesterov's momentum) according to some carefully chosen schedules in training deep neural network, which is named as SRSGD. Two different restarting schedules are proposed: linear schedule and exponential schedule. The strong point of this paper is its extensive experimental evaluations, which justify that SRSGD significantly improves the convergence speed and generalization over standard momentum SGD. The empirical analysis also sheds some light on the parameter tuning and interpretation of SRSGD.\n\nThis paper is well-written and easy to follow. Overall, I like this work and see the following strengths of this paper:\n- The proposed approach significantly outperforms standard momentum SGD in several DNN tasks and the advantage grows with the depth of DNN, which is appealing to practitioners.\n- The experiments are comprehensive and constructive. Various image classification benchmarks were tested and the confidence intervals are also provided. I appreciate the effort the authors put into that.\n- Although the proposed restarting schedules seem to be hard to tune in practice, the authors provide empirical analysis on the impacts of different parameters, which gives some guidance.\n\nOn the other side, I have some concerns on the theoretical aspects: \n\n- Theorem 1 (and 2) assumes a bounded variance of the stochastic gradient, which may not be true for ERM (e.g., for least squares \"Jain, P., et al. (2018). Accelerating Stochastic Gradient Descent for Least Squares Regression. In COLT, pages 545–604.\"). Thus, the \"mini-batch stochastic gradient\" is not precise in Theorem 1 (and 2) and should be replaced with certain assumptions.\n- Under the classic bounded variance assumption, there exists a nice workaround of the non-convergence issue of NASGD in Theorem 1: the AC-SA approach proposed in \"Lan, G. (2012). An optimal method for stochastic composite optimization. Math. Program., 133(1-2):365–397.\". AC-SA is basically NASGD with some parameter constraints. It can be shown that AC-SA maps to scheme (5) with $\\frac{t_k - 1}{t_{k+1}} = \\frac{\\beta_k - 1}{\\beta_{k+1}}$ and $s_k=\\frac{\\gamma_k}{\\beta_k}$. Corollary 1 in (Lan, G., 2012) states that if $\\frac{t_k - 1}{t_{k+1}} = \\frac{k-1}{k+2}$ and $s_k= \\min\\{\\frac{1}{2L}, \\frac{C}{N^{1.5}}\\}$, where $N$ is the total number of iterations, NASGD converges at the optimal $O(\\frac{L}{N^2} + \\frac{\\sigma}{\\sqrt{N}})$ rate. Thus, the non-convergence issue can be solved by simply fixing $N$ in advance and setting $s_k$ accordingly. \n\nDue to these points, the discussion in Section 3.1 is not very insightful to me. There are some recent works studying the non-acceleration issues of SGD with HB and NAG momentum for least squares:\n- Kidambi, R., et al. (2018).On the insufficiency of existing momentum schemes for Stochastic Optimization. In ICLR.\n- Liu, C. and Belkin, M. (2020). Accelerating SGD with momentum for over-parameterized learning. In ICLR.\n\nTheir setting (stochastic unbounded variance) is somewhat closer to ERM. Since this line of work is quite relevant, a proper literature review and adding relevant bibliographical entries might be necessary.\n\nOther comments:\n- In fact, both the constant scheme (3) and the variable-pararmeter one are referred to as NAG in optimization community. In the strongly convex case, NAG uses a constant $\\mu$ to achieve acceleration and is a non-monotone method (this relates to the claim under ARNAG in Section 2). See his book \"Nesterov, Y. (2018). Lectures on convex optimization, volume 137. Springer\". \n- \"Constant momentum achieves state-of-the-art result in DL (Sutskever et al., 2013)\". Actually, Sutskever et al. (2013) tried a variable momentum similar to the one in the paper.\n- The second sentence in Related Work. \"SGD with scheduled momentum\" -> \"These works all use constant momentum\"?\n- The discussion about NAG with $\\delta$-inexact oracle does not seem to be quite connected with other parts of the paper since this inexactness is deterministic. \n- \"dom(J)\" is not defined in Appendix A.", "extra_scores": {}, "extra_text": {}}, {"review_id": "gfgwxTXfn2t", "reviewer": "AnonReviewer5", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "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 focuses on Nesterov's Accelerated Gradient (NAG) method with a scheduled restart for stochastic optimization. The authors particularly provide a particular momentum restart scheme and characterize its convergence for both nonconvex and convex objective functions. Furthermore, various experiments have been conducted to highlight the strength of their algorithm.\n\nOverall, the paper is well-written and provides new insights into the benefits of using momentum restart in accelerated methods. That said, I believe the authors could improve the related work section to add further discussions on previous works on this topic, especially in the context of stochastic optimization. For instance, [1] has also developed a multistage variant of NAG with momentum restart between stages. The idea of applying restart techniques to stochastic methods is studied in [2] as well.\n\nMy major concern is regarding the theoretical contribution on this paper. \n\nFirst, I encourage the authors to clearly state the assumptions that they are making to obtain their results such as Theorem 2. For instance, looking into the details of their analysis (Lemma 6 and Theorem 5 in Section C of the appendix), it seems that the authors are assuming the gradients are bounded (by $R$). In addition, I am suspicious the authors are somehow assuming the function $f$ is bounded when they bound \n$\\sum_{k \\in \\mathcal{A}}\\left(\\mathbb{E} f\\left({v}^{k}\\right)-\\mathbb{E} f\\left({v}^{k-1}\\right)\\right)=\\bar{R}<+\\infty$\nin the proof of Theorem 5. Anyhow, these assumptions should be stated upfront so that the readers could compare these results with other works. \n\nSecond, I am not sure how much assumptions such as \n$\\mathcal{A}:=$ { $k \\in \\mathbb{Z}^{+} \\mid \\mathbb{E} f\\left({w}^{k+1}\\right) \\geq \\mathbb{E} f\\left({w}^{k}\\right)$}\nbeing finite are realistic. Of course for finite number of iterations $\\mathcal{A}$ is finite, but as the proof shows, its growth should be constant relative to $K$. However, Nesterov's method is known to be non-monotone, and hence, this is not a straightforward assumption to make (see Figure 1 in [3] for instance). A discussion regarding this assumption (and the other similar assumption for the convex case) is appreciated. \n\nReferences \n\n[1] Necdet Serhat Aybat, Alireza Fallah, Mert Gurbuzbalaban, and Asuman Ozdaglar. A universally optimal multistage accelerated sto chastic gradient metho d. In Advances in Neural Information Processing Systems, pages 8525\u0015 8536, 2019.\n\n[2] Andrei Kulunchakov and Julien Mairal. A generic acceleration framework for sto chastic comp osite optimization. In Advances in Neural Information Process- ing Systems, pages 12556\u001512567, 2019. \n\n[3] Weijie Su, Stephen Boyd, and Emmanuel J Candes. A di\u001berential equation for mo deling nesterov's accelerated gradient metho d: theory and insights. The Journal of Machine Learning Research, 17(1):5312\u00155354, 2016.", "extra_scores": {}, "extra_text": {}}, {"review_id": "XV_Gu23gjjc", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "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 author propose a scheduled restart scheme for SGD with Nesterov momentum named SRSGD, convergence result and various experiments are provided. However, the idea is the combination of restart schedule and NGD, and the convergence result is not that hard to go through with the existence of current proof of SGD.  In specific,\n\n1. the convergence result of SRSGD is O(1/epsilon^2), which is exactly the same with the convergence result of vanilla SGD, this implies that the the NAG momentum does not contribute to the theoretical part. Therefore, it will be easier  to prove the convergence of SRSGD following the the typical proof structure of SGD with some additional error term, e.g.,  \n\n\"Stochastic First- and Zeroth-order Methods for Nonconvex Stochastic Programming\", \n\n\"Accelerated gradient methods for nonconvex nonlinear and stochastic programming\". \n\n2. I understand the acceleration of convergence may happens in experiments but not in theory, and the main focus of this paper lies on the experiments. However,   although success in experiments,  the intuition why restart scheme can improve generalization error is not convinced to me.  At least, the authors should provide more explanation on this.\n\nOverall, I think the contribution here are not enough to be published in ICLR. \n\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "XCvo5cMaQVx", "reviewer": "AnonReviewer4", "summary": "", "questions": "", "limitations": "", "rating": 4, "confidence": 4, "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": "To summary, the authors proposed an algorithm named Scheduled Restart SGD (SRSGD) to solve the empirical risk minimization problem. They provided a theoretical analysis along with experiments to support the benefits of their new algorithm.\n\nThe good points are:\n\n- The authors proposed a fairly new algorithm that integrates scheduled restart Nesterov accelerated gradient (NAG) momentum with SGD.\n- They conducted experiments to show the benefit of SRSGD: reduce overfitting and the training time, generalize better as the neural network grows deeper,..\n- They discussed the theoretical aspects and provided a convergence analysis.\n\nThe weak points are: \n\n- The idea of using Nesterov momentum for SGD is not new. (To be more clear, the algorithm SGD with Nesterov momentum is already in PyTorch’s library [[1]]). As the authors said, the restart momentum schedule is also in literature as well. The novelty (as far as I understand), is only combining these things to SGD, which is a well-known algorithm. \n- There are some specific reasons that make the theoretical analysis of the paper not convincing (please see details below). Moreover, the convergence rate doesn’t reflect any novelty. Therefore, their analysis can not persuade the readers. \n- There are clearly some benefits of SRSGD, however, it requires two additional hyper-parameters compared to other adaptive methods and SGD with momentum (as in Section 4.1). This could increase the tuning time and could be a disadvantage of SRSGD. \n\nBecause of the weak points stated above, I cannot accept this paper at the moment. The detail concern and comments are below: \n\n- About Theorem 1: The authors claimed that they 'proved the error accumulation of Nesterov accelerated SGD’, as a reason to use the restart momentum schedule. However, Theorem 1 states that $\\mathbb{E} (f(w^k) - f(w^*)) = O (k)$, which means that $\\mathbb{E} (f(w^k) - f(w^*)) \\leq C \\cdot k$ for a positive constant $C$ (by their definition in Notation, page 3). This gives no information on the non-convergence of NASGD. I checked the appendix to look closer, however the proof is not rigorous enough to see what the authors want to prove.\n\n- About Theorem 2: The authors imposed a new assumption: the set $ \\mathcal{A} := $ { $ \\{ k \\in \\mathbb{Z}^+ | \\mathbb{E} f(w^{k+1}) \\geq \\mathbb{E} f(w^{k})  \\}$ } is finite. The concerns are as follows: Firstly, it is really hard and maybe impossible to check this condition. Secondly, in the appendix, the set $\\mathcal{A}$ directly involves a term $\\bar{R}$, which is finite thanks to the assumption. But $\\bar{R}$ can be arbitrarily large and make the right-hand side unbounded. Furthermore, the analysis also relies on another term $R$, which is $\\sup_x || \\nabla f(x) ||_2 $. This term could also be unbounded if the authors don’t assume the bounded gradient for the problem. \n\n- For the above reasons, there seems to be no theoretical guarantee for the new algorithm. About the empirical aspects, it is nice that the authors provided numerous experiments using different data sets and network architectures. The improvement is understandable because SRSGD needs 2 additional hyper-parameters ($F_1$ and $r$) and requires more tuning effort. The comparison with Adam and RMSProp are limited, while they are the popular algorithms for deep learning models. The authors also claimed that the training time and overfitting can be reduced by half. I think it could be better to see this aspect compared not only to plain SGD but also to Adam and other adaptive algorithms. \n\nMinor comments:\n\n- It is much better if the authors state the theorem results more clearly before using the asymptotic notation. The current bound is not rigorous, and people cannot see how the final bound looks like.\n- I think the 'Case study - Quadratic function’ in (8) should be written before Figure 2, so that the readers can see the problem you are optimizing easily.\n\n[1]:  https://pytorch.org/docs/stable/optim.html\n\n\n", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: The reviewers acknowledge that the paper has some promising experiments. However, they think that the theoretical contributions are not rigorous, specifically the assumption in Theorem 2. It is true that the main part of the proof relies on this assumption. The main question is whether this assumption holds or not. The way that the authors provide some numerical verification is not convincing and does not necessarily help in this situation: 

1) MNIST data set with LeNet is definitely not enough to represent all situations. 
2) This assumption depends on the algorithm so the parameter choices are also very important. 

Some reviewers and I agree that this assumption may hold in some scenarios, but assuming it (without proving it) would significantly reduce the contribution of the paper. 

The following is the suggestion to improve the paper. Since this assumption is not standard and hard to verify, the authors should verify more experiments with various data sets and network architectures with difference choices of the algorithm parameters to have some sense whether this assumption may be true or not. Next, please try to show that this assumption holds or come up with different analysis with more reasonable assumptions. 

The authors should consider to improve the theory to strengthen the paper and resubmit this paper in the future venues. 

Decision: Reject