Venue: ICLR 2021 Conference

Reviews:

final_score: rating: 5: Marginally below acceptance threshold
review_content: 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.

Overall, 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.

My major concern is regarding the theoretical contribution on this paper. 

First, 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 
$\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$
in the proof of Theorem 5. Anyhow, these assumptions should be stated upfront so that the readers could compare these results with other works. 

Second, I am not sure how much assumptions such as 
$\mathcal{A}:=$ { $k \in \mathbb{Z}^{+} \mid \mathbb{E} f\left({w}^{k+1}\right) \geq \mathbb{E} f\left({w}^{k}\right)$}
being 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. 

References 

[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 8536, 2019.

[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12567, 2019. 

[3] Weijie Su, Stephen Boyd, and Emmanuel J Candes. A dierential equation for mo deling nesterov's accelerated gradient metho d: theory and insights. The Journal of Machine Learning Research, 17(1):53125354, 2016.
review_title: New insight into applying momentum restart in stochastic optimization; concerns regarding theoretical contribution

final_score: rating: 6: Marginally above acceptance threshold
review_content: UPDATE:

I 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.

#### Summary
This 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.

Adaptive 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.

---

#### Originality

While 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!

---

#### Quality and Significance

I 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.

*On the results:*
The 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.

*Room for improvement*:
The 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

[1] M. Assran and M. Rabbat, "On the Convergence of Nesterov's Accelerated Gradient Method in Stochastic Settings," ICML 2020

---

#### Clarity

Clarity 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.

Note, 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.

The 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).

Please 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.
review_title: Nice idea and many experiments, but stability is under-explored

final_score: rating: 5: Marginally below acceptance threshold
review_content: 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,

1. 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.,  

"Stochastic First- and Zeroth-order Methods for Nonconvex Stochastic Programming", 

"Accelerated gradient methods for nonconvex nonlinear and stochastic programming". 

2. 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.

Overall, I think the contribution here are not enough to be published in ICLR. 


review_title: Review

final_score: rating: 4: Ok but not good enough - rejection
review_content: 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.

The good points are:

- The authors proposed a fairly new algorithm that integrates scheduled restart Nesterov accelerated gradient (NAG) momentum with SGD.
- They conducted experiments to show the benefit of SRSGD: reduce overfitting and the training time, generalize better as the neural network grows deeper,..
- They discussed the theoretical aspects and provided a convergence analysis.

The weak points are: 

- 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. 
- 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. 
- 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. 

Because of the weak points stated above, I cannot accept this paper at the moment. The detail concern and comments are below: 

- 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.

- 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. 

- 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. 

Minor comments:

- 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.
- 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.

[1]:  https://pytorch.org/docs/stable/optim.html



review_title: The theoretical analysis is not convincing.

final_score: rating: 6: Marginally above acceptance threshold
review_content: 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.

This paper is well-written and easy to follow. Overall, I like this work and see the following strengths of this paper:
- 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.
- 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.
- 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.

On the other side, I have some concerns on the theoretical aspects: 

- 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.
- 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. 

Due 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:
- Kidambi, R., et al. (2018).On the insufficiency of existing momentum schemes for Stochastic Optimization. In ICLR.
- Liu, C. and Belkin, M. (2020). Accelerating SGD with momentum for over-parameterized learning. In ICLR.

Their 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.

Other comments:
- 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". 
- "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.
- The second sentence in Related Work. "SGD with scheduled momentum" -> "These works all use constant momentum"?
- 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. 
- "dom(J)" is not defined in Appendix A.
review_title: I tend to accept this paper due to its impressive experimental results. However, there are some theoretical issues need to be addressed.

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