Venue: ICLR 2021 Conference

Reviews:

final_score: rating: 6: Marginally above acceptance threshold
review_content: This paper studies the deterministic Heavy Ball (HB) method compared with vanilla gradient descent (GD) in nonconvex optimization.
In particular, they consider two optimization problems, i.e., phase retrieval and cubic-regularized problem, and try to show HB is better than GD, and the larger momentum parameter $\beta$, the better benefit of HB.

They consider two stages for these two problems. The first stage is to find/fall into a benign region (strongly-convex region) and then the second stage can directly use previous HB results for strongly convex functions (i.e., linear convergence).
Thus the main part/contribution is to show how HB could perform better than GD in the first stage. In this paper, they show this by providing Theorem 1 and 2 for these two problems respectively.
However, I have some questions/concerns regarding Theorem 1 and 2.

For Theorem 1 (phase retrieval):
1a. They first analyze the HB using the population update (i.e., Eq (5)), then they consider Eq (11) for dealing with finite samples case. The author should show/prove that Eq (11) is the update form for finite case and also satisfies the corresponding assumption in Theorem 1.
1b. Why the initial point $\||w_0\||$ is not equal to 1 in Theorem 1, i.e., sampling from the unit sphere? Since they assume that $\||w_*\||=1$.
1c. They claim that HB is better than GD by a factor of $1+c_\eta \beta$ according to Theorem 1. But what’s the result for GD, is it $T_\zeta \lesssim\log d$? It looks a bit strange as it does not depend on the step-size $\eta$.

For Theorem 2 (cubic regularized)
2a. In general, the value of step-size $\eta$ varies for different algorithms. So only according to their Theorem 2, I am not convinced that HB is better than GD as the authors claimed since GD may choose different step-size due to nonexistence of momentum.
2b. Beyond Theorem 2, I have a question regarding Figure 2b. Why there are oscillations for the last two curves in Figure 2b? 

review_title: Interesting work but the results are not very clear

final_score: rating: 4: Ok but not good enough - rejection
review_content: #########################
Summary: 
This paper studies heavy ball momentum in non-convex optimization. It has provided some theory to explain the good performance of heavy ball method in some type of nonconvex problems, i.e., the phase retrieval problem and cubic-regularized problem.

#########################
Reasons for score: 
Overall, I vote for rejecting. Although this paper has some contribution to explain the superiority of heavy ball method over vanilla SGD, the problem has very special structure, which makes its not very much likely to be generalized to general problems and applications.  

##########################
Pros: 
1. This paper has proven the superiority of heavy ball method in some cases by showing that heavy ball momentum helps the iterate to enter a benign region that contains a global optimal point faster. 


##########################
Cons: 
1. The considered problems have very special structures, i.e., the phase retrieval problem and cubic-regularized problem, which would prevent the generalization to a broad family of problems. Even though that the authors have tried to generalize it to solve the problem of top eigenvector computation and saddle point escape problem, they still focus on special subproblems of these two. 

2. In terms of writing, the authors did not give enough background of the considered phase retrieval problem and cubic-regularized problem. I do not feel that the ICLR community would be familiar with these two problems.

##########################
Questions:
1. Why are considered problem important on their own? And how can they be connected to problems that the ICLR community would be interested in?

review_title: Summary 

final_score: rating: 7: Good paper, accept
review_content: This paper analyzes Polyak momentum in the deterministic case for two simple but important non-convex problems: phase retrieval and finding the cubic-regularized newton step. It is shown that in both cases the problems posses a “benign region” in which the objective “looks” a bit convex. In the phase retrieval case, assuming that the data is generated from a normal distribution, it is shown that having a non-zero momentum parameter in fact allows the momentum method to find the benign region faster, after which standard convex analysis can take over to find the optimal point.

For the cubic regularization problem, a similar result showing faster convergence to the benign region is shown. The key steps appear to be observing that in both instances, the benign region is essentially just asking for the norm of the iterate to reach sufficient magnitude. Then, a technical lemma (Lemma 1) and careful analysis of the gradients of the individual losses shows that the iterates increase in magnitude very quickly, with the momentum parameter accelerating the increase.

Overall I think these are interesting results. I think the major weakness (as admitted by the authors) is that for the cubic-regularization problem, there is no guarantee that the iterates will in fact stay in the benign region once they have entered it. Although it seems plausible that such behavior is in fact guaranteed, this does somewhat weaken the theoretical impact. The other issue is that as far as I can see, these results improve by at most a constant factor of about 2 over the number of iterations required by ordinary gradient descent, which is not a huge amount. However, constants are important in practice, and many analyses of Polyak momentum in the non-convex setting actually get worse when there is momentum, so at least this is going in the right direction :)

I think the cubic-regularization result seems the most promising for future development as it may have some application to generally showing faster a convergence on second-order-smooth non-convex problems.

Minor nit:
In Lemma 1, what does “the effective dynamics satisfies...” mean? It sounds cool, but I don’t actually know what effective dynamics are. Maybe you could just say “a_t satisfies...”. Similarly for the other few places that effective dynamics shows up.

review_title: Interesting analysis showing constant-factor improvements with momentum.

final_score: rating: 6: Marginally above acceptance threshold
review_content: The authors analysed the dynamics heavy ball momentum in non-convex optimization settings (namely the phase retrieval and the cubic-regularized problems). The results show that the algorithm leads to a faster convergence rate in comparison with gradient descent without inertial contributions. Although there are results in the context of convex optimization, the result in non-convex setting is novel and very interesting. 

In the phase retrieval case, following an approach analogous to [Chen et al. (2018)] the authors show that the dynamics can be reduced to the study of the parallel and perpendicular components of the weights with respect to the ground truth. 
However in that case, the landscape is non-convex anymore since the number of samples is infinity and the spurious minima disappear (as the authors reported in the introduction [Davis et al., 2018; Soltanolkotabi, 2014; Sun et al., 2016; White et al., 2016]).
In order to analysed the case with a finite number of datapoints, the authors introduced perturbation terms in the dynamical equations and hypothesized that the perturbation is bounded by a constant c_n that the they ask to be smaller than zeta. 
My main concerns on this part are the following : 
* is the landscape still convex under this constraint?
* is there the possibility that for some regimes for which the hypothesis break and heavy ball momentum will behave poorly compared to gradient descent? In the paper it seems that it always speed up the performances, but this is not clear from the theorem. 

The authors in thm.1 and 2, give a characterization of the speed up given by the momentum parameter beta. The authors should check whether the bound is strict in simulations, and verify numerically that in fact the speed is correctly captured by the theory. 

**Other comments :** 

* There is a change of notation between the one used for Fig.1 and the one reported in the appendix (d<-m, n<-m). Furthermore those details are important and should put forward in the caption. 
* The figures need larger fonts. It is almost impossible read them in the printed paper.

review_title: relavant contribution but clarifications are needed

Meta-review: This paper considers the analysis of momentum for nonconvex problems. While this is a worthy direction, as some reviewers pointed out, the examples considered are rather specialized and one can argue they are mostly "convex-like". Therefore it is not clear that these results are generalizable and whether the analysis offers insights about how momentum helps (including faster escape of saddle in nonconvex regime, and faster convergence in the convex regime). In the current form, these results have limited scopes.

Decision: Reject