Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: The authors study a variant of the heavy ball method, where the stepsizes are chosen in a cyclical order. The paper considers the problem of minimising quadratic functions (there is a paragraph on local analysis for more general functions, but this is reduced to  the quadratic case  by linearisation). In the case where the cycle is 2 and the intervals of the eigenvalues of the quadratic functions are known, the authors show how this cyclic stepsize choice can lead to acceleration. In the more general setting of cycle $K$, their analysis is subject to some polynomial.



main_review: 
Overall, I found this paper interesting, and the theoretical study of good stepsize choices is important for stochastic algorithms.
However, in general, I'm not sure how practical/useful the results here actually are, Algorithm 3 requires finding a polynomial which may not exist and involves solving a difficult system of $K$ nonlinear equations. The $K=2$ scheme also requires not just estimating the largest and smallest eigenvalue, but also the eigenvalue gap. This is in contrast to  existing analysis into cyclical stepsizes in descent methods, see last paragraph. 

I'm also a  confused about the statement in Theorem 3.1, it refers to Algorithm 1 where $h_0$ and $h_1$ are given explicitly in terms of the eigenvalue bounds and $m$, but you mention immediately after this theorem about optimising $h_0$ and $h_1$, so are these values fixed as in the Algorithm or are they arbitrary? If they are arbitrary, what the corresponding optimal $h_0$ and $h_1$ are which give the optimal rate in  corollary 3.2 (otherwise, after estimating the eigenvalue bounds, would one need to apply something like Newton's method to optimise for these step sizes? This could be potentially more costly than the acceleration obtained?) ?
Finally,  another question I have is: the motivation given in the introduction is from the use of restarts in stochastic algorithms, while the analysis here is in the deterministic setting, do the authors expect the results here to apply also in the stochastic? Perhaps some numerical illustrations on this would be helpful? 

There is  a related strand of work on the use of cyclical stepsize for descent methods (with  many results appearing in the later 1990's and early 2000's)  -- the analysis into acceleration in  convergence rates  has also been studied in many works. These works make connections to the relationship between eigenvalues of the Hessian (similar to the analysis in this work), and also provide guidance on practical choices of stepsizes based on past iterates. Some examples: Friedlander et al, SIAM Journal on Numerical Analysis, Vol. 36, No. 1 (1999), pp. 275-289; Dai and Fletcher, Math. Program., Ser. A 103, 541–559 (2005); Dai et al, IMA Journal of Numerical Analysis (2006) doi:10.1093/imanum/drl006. See also the more recent work by Kalousek, Found Comput Math (2017) 17:359–42, DOI 10.1007/s10208-015-9290-8. Since this body of work very close to the results presented, the authors should  reference appropriately  and provide some discussions on the relation to their work.
limitations_and_societal_impact: Yes
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: This paper studies the cyclicial step-sizes to improve the worst-case convergence of the heavy ball method (deterministic version). More precisely, the authors 1) achieve a faster asymptotic worst-case convergence  rate compared to the polayk heavy ball method for the strongly convex and L-smooth quadratic objectives,  2) show how to select the optimal momentum and step-size cycles, and 3) extend the local convergence to the non-quadratic case. Furthemore, numerical experiments on quadratics and logistic regressions have been conducted to demonstrate the main strength of the cyclicial heavy ball method.
main_review: Overall, the paper is well-written and the proof is solid. The novelty of  this paper is that the authors take advantage of the cyclical step-size strategies which recently have been widely used in the stochastic optimization setting, to improve the worst-case convergence of the traditional heavy ball method. The strong points of this paper are its theoretical parts: 1) the cyclicial heavy ball  for example with 2 cycles has a faster worst-case convergence over the traditional polyak heavy ball method (see Table 1); 2) provide a systematic approach to select the optimal parameters for momentum and step-size cycles if given the spectrum interval of Hessian $\Lambda$ and cycle length $K$.  I like the results, however 1) their analysis heavily relies on the distribution of the Hessian's eigenvalues which makes it uneasy to be extended to other general settings; 2) the algorithm needs to estimate some extra eigenvalues which may be expensive for large scale problems. I have the following detailed concerns or comments on this paper:

1) From Figure 2, we can see that when the eigenvalue gap $R \neq 0$, you have two choice for the optimal step-sizes $(h_0, h_1)$: 1) $h_0 > h_1$ and 2) $h_0 < h_1$. In Algorithm 2, the authors use the first choice that $h_0 > h_1$. If you choose another one i.e., $h_0 < h_1$,  could you get similar results? How will it affect your numerical results?
2) The cyclicial step-sizes indeed have been widely used in deep learning. However, it is not very clear why the cyclicial step-size strategy proposed in this paper helps to improve the traditional heavy ball method. Could you try to explain it a little bit?
3) The theoretical results for the cyclicial heavy ball method heavily rely on the location of the Hessian’s eigenvalues and also the quadratic assumption. Is it possible or easy to extend this idea to e.g., the general convex problems and nonconvex problems, especially in deep learning, or stochastic heavy ball method?
4) In Figure 4, from the first and the last pictures of the bottom row, we can see that the cyclicial heavy ball with optimal parameters performs worse than the polyak heavy ball method at the beginning. Could you clarify why this happens?
5) The computational cost: except the smallest ($\mu$) and largest ($L$) eigenvalues as polyak heavy ball, the proposed algorithm also needs to know the distribution of the eigenvalues, 1) if the eigenvalues of Hessian are clustered (the best situation) around the smallest or largest eigenvalues for example MNIST dataset (see the first picture of Figure 4), we still need to estimate other two top eigenvalues except the extremal eigenvalues (i.e., $\mu$ and $L$). So it will be costly and impractical for the large scale optimization problems. Especially, for the datasets in which the distribution of the Hessian’s eigenvalues is dense (not clustered), the computational cost will be highly increased but the improvements seem to be less because in this case the eigenvalue gap $R$ is smaller.  Could you summary in what kinds of situations the increasing of the computational cost can be ignored compared to its improvements. 

Other Comments:
1) There are some mistakes in Table 1: 1) in the first line ($R \in [0,1)$), the value  of "Set $\Lambda$ " is wrong, it should be $[\mu, \mu + (L-\mu)(1-R)/2] \cup [L-(L-\mu)(1-R)/2, L]$;  2) in the third line and the fourth column($R=1-2\gamma \kappa$), the speedup should be “ $O(\kappa^{-1/2})$ ” instead of “$O(\kappa^{1/2})$”. 
2) In the theoretical part, the authors use $m$ and $\lambda$, which appear frequently, to denote the momentum parameter and the eigenvalue of Hessian, respectively. But in the numerical part, $m$ is also used to denote the dimension of the data matrix and $\lambda$ is used to denote the regularization parameter. This easily leads to misunderstandings to the readers. 
3) There is an additional "with" in the name of Algorithm 2. 


limitations_and_societal_impact: In general, the authors have adequately addressed the limitations and potential negative societal impact of their work.
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: This paper studies cyclical step sizes for heavy ball momentum. It is shown that under some conditions, it is possible to improve the convergence rate of heavy ball by relying on cyclical step sizes with K = 2. The result is obtained by a careful examine of the spectrum of the Hessian. The cases for larger K are also discussed. In general, the results are nice but also has its own limitation.
main_review: Strength:

(+) This work demonstrates that cyclic step sizes are useful and theoretically improves over HB under certain conditions. I believe the results are of interests in the community.

(+) The paper is well written and easy to follow.


Weakness

(-) Though theoretically appealing, it is unclear that the improvement comes from. In particular, is it possible to tighten the HB convergence as well assuming (3) is true? This is a critical question since without demonstrating it, it is not possible to conclude cyclic step sizes are helpful. 

(-) For quadratic problems, it is relative easy to find L2 and mu2, but is it common in e.g., logistic regression or other loss functions to find these parameters? 
limitations_and_societal_impact: This is mainly a theoretical work. The Societal impact depends on how it is applied to solve real problems.
review_title: null

final_score: rating: 5: Marginally below the acceptance threshold
review_content: summary: This paper studies using cyclical step-sizes of Heavy Ball for solving strongly convex quadratic problems. The authors first study setting the step size to two specific values periodically (period=2), where the values are related to the spectrum (i.e. the eigenvalues) of the underlying quadratic matrix. Assuming the spectrum can be divided into two groups. The authors prove that the resulting asymptotic rate of using the cyclical step size can be faster than that of the standard step size of Heavy Ball. Then, the authors discuss the extension to the case that the step size can have K values and the step size is set to the possible step sizes in a cyclical fashion.

main_review: I have some challenges for the authors.

 


=== 1. The paper missed a highly relevant reference: Samet Oymak. "Super-Convergence with an Unstable Learning Rate" arXiv:2102.10734 February. 2021. 

The result of showing that if the spectrum of the Hessian can be grouped into two clusters, then using a cyclical Learning Rate can lead to a faster convergence compared to using the standard step size has been shown in [Oymak 2021]. Though I understand [Oymak 2021] is for gradient descent while this paper is for Heavy Ball, the novelty of this paper is not very high from this perspective.


=== 2. The intuition behind the acceleration result due to the cyclical step sizes seems not be explicitly described in the paper.


After reading the paper, I'm still not sure where exactly did the authors provide an explanation why the cyclical step sizes help faster convergence. It will be more helpful for the readers if the authors can be more transparent about their acceleration result.

On the other hand, [Oymak 2021] conveys a very clear message that periodically setting a large step size can help the progress on directions that correspond to small eigenvalues, while a small step size help to prevent divergence, and hence shows the benefit of using cyclical step sizes.


=== 3. The theoretical results are hard to interpret. 



(3.a) The work makes an assumption that the eigenvalues are located in a way so that there are two intervals of the same size (line 61). It appears to be a strong assumption so the authors might want to discuss if it is an artifact of analysis.

(3.b) (Theorem 3.1) It is not easy to tell what would be the optimal momentum parameter $m$ and what would be the optimal step sizes of $h_1$ and $h_2$ from Theorem 3.1. Also, the choice of the momentum parameter $m$ and the step sizes $h_1$ and $h_2$ determines $\sigma_{\sup}$ in a seemingly complicated way. The authors might want to explain the interaction between these parameters. It would be better to present Theorem 3.1 in a more user-friendly fashion.

(3.c) (Section 4.2 and 4.3) The authors consider using cyclical step sizes with a longer cycle than 2 in the later parts of this paper. Does the result there show any benefit of using a longer cyclical step size? If so, can the authors provide a discussion here? If not, what would be the point of showing the result?




=== 4. Significance


The result in this paper seems to be very specific to the strongly convex quadratic problems, where the Hessian is a fixed matrix. If the Hessian changes a lot, then the analysis/techniques in this paper would likely be useless. So it is unclear if this work really makes an important step towards theoretically understanding the success of cyclical step sizes in practice.   

A relevant question: Does the insight from the theoretical results in this paper leads to any new heuristic in optimization? 


************* after rebuttal **************

I decided to leave the score as it is, because I think the idea has a great similarity to [Oymak 2021], and the proof techniques are not particularly novel and/or are standard for Heavy Ball (e.g. [Pedregosa 2021]). It is unclear to me if this paper makes another important step towards understanding cyclical step sizes in practice, compared with [Oymak 2021]. I don't think if the insights of this paper lead to any practical heuristics, and the practical contributions seem not central to the paper.

Also, the concern about the interaction of the parameters which was also raised by Reviewer 9ZCq is lingering. 

Ref:
[Pedregosa 2021]
http://fa.bianp.net/blog/2021/hitchhiker/
limitations_and_societal_impact: The authors adequately addressed the limitations and potential negative societal impact of their work.
review_title: null

Meta-review: Given the reviewers comments and after thorough discussion, it has been decided that this paper will not be accepted at NeurIPS 2021. The relationship to previous work and comments about parameter selection should be taken into consideration by authors when considering revisions of this manuscript.
Decision: Reject