Venue: ICLR 2021 Conference

Reviews:

final_score: rating: 5: Marginally below acceptance threshold
review_content: This paper's major contribution is analyzing the HB method for non-smooth objectives functions and showing the last iterate convergence for it. Comparing to existing results, they show a tighter upper bound by dropping a log(t) term from the
suboptimality's upper bound. It also analysis an adaptive variant of the HB and show similar results. All the proofs are clear and straightforward.

Comments: 

1- This paper needs major rewriting and restructuring and in its current format is not ready to be published. 
The abstract talks about a specific parameter and its value, which the reader has no idea about it. 

 a)- When an acronym is used, its full name should appear once before.

 b)- Typos exist in their proof. For example, in the proof of Lemma 1, and in the last equation, there is no u, but the line above reads for all u in Q. Also, in the paragraph for the paper's 3rd contribution, it says decaying \beta_1,t goes to 1. It is not a decaying but increasing parameter. 

c)- There are two appendices, one at the end of the main part, and the other part is in a separate file. 

d)- Two related works which haven’t been considered in related work 
      Sebbouh O., et.al. On the convergence of the Stochastic Heavy Ball Method
      Sun, T. et. la., Non-Ergodic Convergence Analysis of Heavy-Ball Algorithms

2- In terms of contributions: 

a)- I don’t think dropping a log(t) terms in an analysis of a method means acceleration. Usually, Log(t) term appears due to some technical difficulties in the analysis and also in practice when training a model is not a large value. 

b)- Since you compare the HB method with SGD, I suggest putting the proof for stochastic HB instead of the deterministic case. 

c)- In the experimental section, it would be nice to see the results on bigger datasets like Imagenet and also different tasks such as NLP models. Moreover, for SGD you set the step size \alpha_t to be fixed, which theoretically SGD won’t converge in this situation. To be fair, similar to your sep-size, which is decreasing \alpha_t for SGD should be decreasing with an appropriate rate. Finally, since you run the experiments for 5 runs, it would be useful to add the error bar to your graphs. 
review_title: The paper needs major rewriting. 

final_score: rating: 6: Marginally above acceptance threshold
review_content: The authors investigate the convergence of the projected Heavy-ball method (and an adaptive variant) for convex problems with convex constraints. The authors prove 4 results: 2 individual (last iterate) convergence rates and 2 rates using averaging. Notably, in their proofs they require an increasing (from 1/2 to 1) momentum parameter and a decreasing stepsize. Finally, the authors present some experimental results.

The paper is overall a nice and pleasant read, with no major typos and a nice introduction. Also, to the best of my knowledge, the individual convergence rates proved by the authors are novel.
However, I do not think the paper is ready for publication, for the following reasons (in order of importance, the last points are easy-to-fix)

1) The paper is short – the main section is only 2 pages and the proof (in the appendix) does not exceed one page. I am not particularly blown away by the results or the proof technique – I think the authors should try to extend their study. For instance, an easy way to make the result more general is to extend it to momentum parameters of the form t/(t+r) for r>2 (it should work the same).

2) Reading the paper, it seems the authors are the first to provide an individual convergence rate for HB. This is not true, indeed Ghadimi 2015 also has a rate of O(1/t) for the last iterate of HB under momentum t/(t+2)  and stepsize 1/t. Here, the authors add a projection, hence have to also reduce the stepsize to 1/t^3/2.. @authors is this the only novelty? Also, an increasing momentum is considered in Orvieto et al. 2019 (Role of memory in stochastic optimization).

3) Even though the authors claim to have convex empirical results in the abstract, the experiments are for non convex problems (a CNN model). This in my view does not make much sense since (a) the authors only study convex problems with convex constraints (where are the constraints here?), (b) no experiment has a decreasing stepsize (c) a momentum of k/(k+2) was shown already in Sutskever et al. 2013 not to be optimal in the non convex case. In essence, I think the experiments do not back up the theory: the authors should at least compare with a fixed-momentum method.

4) I am seriously not convinced that O(1/t) compared to O(log(t)/t ) motivates the so-called “acceleration” of Heavy ball. I think the authors should rephrase that. Btw @authors can you actually see this log difference in experiments on convex objectives? Also, it would be great to cite and compare your result/proof technique with Defossez et al. 2019 (On the convergence of Adam and Adagrad).

5) Many results are presented without proof, such as the ones for the stochastic case.

I think the authors should take some time to work on their interesting direction and resubmit to ICML. I think the results are interesting, just they need to be discussed/complemented/verified a bit better.

------------------------------------------

Score updated after rebuttal, please see comment below
review_title: An interesting read that still requires a bit of work

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

The convergence of Momentum methods has been widely studied but most of existing works consider the average convergence. In this work the author considers the individual convergence of the last iteration. The accelerated convergence rate O(1/sqrt(t)) is established.

Pros:
1. The individual convergence of momentum methods is pretty interesting. It is very valuable to established the accelerated convergence rate, which is missing in the existing litterature.

2. The paper overall is well written but need to reword some statement for rigorousness.

Cons:
1. This paper only consider convex optimization. This limits its effectiveness to explain the good performance of momentum method in training deep neural networks.

2. I suggest the authors to reword their statement of the third contribution on page 3 "However, in order to get the optimal individual convergence, β1t has to be time-varying". Theorem 4 only shows that adaptive momentum can achieve individual convergence. Theorem 5 shows that constant momentum can achieve average convergence. These two results cannot lead to the conclusion that constant moment does not have individual convergence. In fact, we have observed it in practice. Moreover, the author should add more discussion on the difficulty of establish constant convergence for constant momentum

3. There is a large gap between the numerical and theoretical results. In the theoretical result, the authors consider convex optimization which is quite different from training deep neural networks. Moreover, when training DNN, the algorithm used is SGD with momentum but not GD with momentum. Note that M-SGD and M-GD has significantly difference, I am not sure how the theoretical results can provide useful hints to practice.

Minor Comments:
1. The abstract mentions that the numerical result on convex optimization is included. However, I don't find this result. Please add it.
2. I hope the authors can provide more proof sketch to help the reader understand the proof.
review_title: This work study the the individual convergence of Polyak momentum method in solving non-convex problems.

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

This paper provides the convergence analysis of the Heavy-ball method with the individual convergence and provides the convergence of its adaptive version. 

Pros: 

1. The motivation is interesting, most of time we use the last iteration while most of theorem can only provide convergence result for the average output. I am glad to see that the theoretical proof of the individual convergence for stochastic Heavy-ball method is studied in this paper,  

2. The convergence result of HB methods achieved in this paper is 1/\sqrt(t) which is better the optimal result of SGD. This demonstrate the advantage of momentum-based methods.

3. Their proof is different form all the existing analysis of averaging convergence.

Cons:

1. It will be much better if the author can explain more on the difference between the current proof and the existing proof. 


Overall, I tend to accept this paper. However I am not an expert on this area and I will not be sad if this paper is rejected by others.
review_title: Review

Meta-review: This paper studies the *last iterate* convergence of the projected Heavy-ball method (and an adaptive variant) for convex problems, and propose a specific coefficient schedule. All reviewers thought that looking at the last-iterate convergence of the HB method was interesting and that the proofs, while simple, were interestingly novel. Several concerns were raised by the quality of the writing. Several were addressed in a revision and the rebuttal. While R1 did not update their score, the AC thinks that the rebuttal has addressed appropriately their initial concerns. The AC recommends the paper for acceptance, *but* it is important that the authors make an appropriate careful pass over their paper for the camera ready version.

### comments about the write-up

- The paper still contains many typos (e.g. missing $1/t$ term in the average after equation (2); many misspelled words, etc.), please carefully proofread your paper again.
- The AC agrees with R1 that the quality of presentation still needs improvement. $\beta_{1t}$ is still used in the introduction without being defined -- please define it properly first e.g. 
- The word "optimal" and "optimality" is usually misused in the manuscript. To refer to the convergence rate of an optimization algorithm, the standard terminology is to talk about the "suboptimality" or the "error" (e.g. see the terminology used by the cited [Harvey et al. 2019, Jain et al. 2019] papers). For example, one would say that the error or suboptimality of SGD has a $O(1/\sqrt{t})$ convergence rate. Saying "optimality of" or "optimal individual convergence rate" is quite confusing, and should be corrected. The adjective "optimal" (when talking about a convergence rate) should be restricted to when a matching lower bound exists.
- Finally, the text introducing the experimental section should be fixed to clarify the actual results and motivation. Specifically, the "validate the correctness of our convergence analysis" only applies in the convex setting. I recommend that a high level description of the convex experiment and the main message of the results is moved from the appendix to the main paper there (there is space). And then, the deep learning experiments can be introduced as just investigating the practical performance of the suggested coefficient schedule for HB.
Decision: Accept (Poster)