Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 4: Ok but not good enough - rejection
review_content: summary: This paper proposes a universal framework for adaptive gradients methods by introducing a universal adaptive matrix. It also offers the theoretical convergence analysis for this optimizing method, and proves that this method can achieve the complexity of $O(\epsilon^{-3})$ for finding an $\epsilon$-stationary point. 
main_review: The main concern is about the practicability of SUPER-Adam in the Case 2 in Algorithm 1. It is known that the number of parameters of modern DNNs is typically more than 10 million, such as the number of parameters of VGG16 is ~134 million and that of ResNet18 is 33 million. Therefore, $H_t$ in SUPER-Adam in Case 2 will be at least 8 order of magnitude larger than that in $H_t$ in SUPER-Adam in Case 1 that is commonly used, so we need to scale the learning rate $\eta_t$ by a factor of $>10$ million to maintain the comparable convergence rate with Adam. This overlarge factor may be impractical. Actually, from Section 6.1, we know the authors also did not set $\eta$ so large.

When $M_t \rightarrow 0$ , SUPER-Adam in the Case 1 cannot ensure $\rho H_t^{-1} \rightarrow I_d$ in Eq. (17), and then $\Vert\nabla f(x_t) \Vert \rightarrow 0$ will not hold. In this case, Theorem 1 and Theorem 2 might be somewhat meaningless. 


Theorem 1 and Theorem 2 and their proofs are obviously followed the paper that proposed STORM with a little change, but the authors did not report this close relation. Therefore, the bright spot of the convergence analysis is discounted

From the 1st and 5th subfigure of figure 2, we know the learning rate for SUPER-Adam decays by a factor (maybe 10) at the 70th and 100th epoch, respectively, which is not described in experimental settings. Moreover, this learning rate decay strategy seems to be not used for other optimizing methods except AdaBlief. Hence, the comparison may be unfair. Additionally, it is known that SGD-type methods commonly perform better for image classification than adaptive gradient methods, so I would like to see SGD will be also compared to SUPER-Adam.


limitations_and_societal_impact: The author need to  address the problesm above.
review_title: null

final_score: rating: 4: Ok but not good enough - rejection
review_content: summary: This manuscript introduces a unified framework (i.e., SUPER-ADAM) of adaptive gradient methods for nonconvex optimization. It is proved that a universal convergence measure converges with a fast rate, which recovers the $O(\epsilon^{-3})$ complexity by STORM. Another result is that it also recovers $O(\epsilon^{-4})$ result by SGD, when individual function does not have a Lipschitz-continuous gradient. Numerical experiments on image classification and language modeling shows that SUPER-ADAM has faster convergence rate when training deep neural networks.
main_review: The unified framework is new to me, but the only algorithmic innovation is line 12 in Algorithm 1. The choices of $\tau=0$ or $\tau=1$ are nothing but hyper-parameters which make the algorithm use the standard gradient estimator or the STORM estimator. I have the following concerns.

1. Convergence Measure. The authors claim that the proposed measure in (15) is tighter than existing measures. I agree that it is the case when we are facing unconstrained nonconvex optimization with non-coordinate-wise adaptive learning rate. What about constrained case and adaptive case in which the preconditioning matrix is not identity? I do not think it is still tighter. For example, the gradient mapping may not be a lower bound for the measure in (15). In unconstrained adaptive learning rate case, $\rho H_t^{-1}$ should be very small when $t$ gets large, so it is also not an upper bound of the gradient norm. For fair comparison, is it possible to prove the convergence measure in the usual sense (i.e., gradient mapping in constrained case and gradient norm in unconstrained adaptive case)? 

2. As I mentioned, line 12 is the only difference compared with existing methods. Why line 12 is important to recover the convergence rate of STORM? There is no doubt that in unconstrained case, without line 12 and with $\tau=1$, the algorithm is the same as STORM and hence can recover $O(\epsilon^{-3})$ rate. Also I would like to ask the same question in terms of SGD.

3. After inspecting Lemma 2 and Lemma 3 and Theorem 3 in this manuscript, I think the proofs are almost adapted from STORM paper, except for plugging in the Lemma 1 in [10] and the line 11 of Algorithm 1. Please clarify what are the technical innovations when compared with Lemma 1, Lemma 2 and Theorem 1 in the STORM paper. 

Experiments:
For SUPER-ADAM with $\tau=1$, since the algorithm need to calculate two stochastic gradients at one iteration, so the running time might be slow. Is it possible to report the running time results?

From my point of view, the theoretical contribution is minimal for unconstrained problems, since SGD and STORM are already optimal with different assumptions, and SUPER-ADAM's algorithm design is very similar to them except for the line 12. The convergence measure when using coordinate-wise adaptive learning rate for unconstrained problems is not comparable with the usual gradient norm. 

SUPER-ADAM might be interesting in constrained case. However, the convergence measure is not comparable with gradient mapping, and there are no empirical studies for constrained problems in this submission. 

Due to these reasons, it is hard to say that the algorithm is universal.
limitations_and_societal_impact: Yes.
review_title: null

final_score: rating: 8: Top 50% of accepted NeurIPS papers, clear accept
review_content: summary: This paper proposes a faster and universal framework of adaptive gradients (super-adam) for nonconvex stochastic optimization. Specifically, super-adam introduces a universal adaptive matrix that includes most existing adaptive gradient forms and many new adaptive learning rates. In particular, it can flexibly integrate the momentum and variance reduced techniques. Moreover, this paper provides an effective and interesting theoretical analysis framework based on a new convergence metric. Meanwhile, it provides the extensive experimental results to demonstrate the efficiency of the super-adam algorithm. Overall, it is an interesting and innovative paper. It will have a wide range of applications in machine learning. 
main_review: Some comments:
 
1.  I recommend the authors to proofread the paper again. 
Some typos: 
1) In the line 9: “our framework can flexibly integrates …” should be “our framework can flexibly integrate…”
2) In the line 115: “proposed to adapt the stepsize” should be “proposed to adopt the stepsize”
3) At the step 13 of super-adam algorithm, there is a symbol error: “[g_t - ” should be “[ g_t + ”.
In the line 436, the gradient estimator g_{t+1} is right. So I think that this symbol error at the step 13 of algorithm is a typo. 
4) In the line 145, “g_t - \nabla f(x_{t+1};\xi_{t+1})” should be “g_t - \nabla f(x_t;\xi_{t+1})”.
 
2.  I also recommend the authors to detail the adaptive learning rates used in the super-adam algorithm in the experiment. 

----After Rebuttal----
As the author's rebuttal well addressed my main concerns, I increased my score to 8 to support this paper. Thanks.
limitations_and_societal_impact: See above
review_title: null

final_score: rating: 8: Top 50% of accepted NeurIPS papers, clear accept
review_content: summary: This paper presents a universal adaptive gradient framework (i.e., super-adam), which can flexibly incorporate the momentum and variance reduced techniques to effectively accelerate the convergence of the algorithm. Moreover, it provides a sound convergence analysis framework for the super-adam under the nonconvex setting. Experimental results on some deep learning tasks demonstrate the efficiency of the proposed super-adam algorithm. Super-adam may have broad applications in training deep learning models. Overall, I recommend accepting this paper. 
 

main_review: I have the following major comments/questions:

1) In the theoretical analysis, the parameter $\rho$ is very important. Could you summarize the impact of this parameter on the convergence analysis? E.g., how it affects the convergence properties of the proposed algorithm?

2) In the super-adam algorithm, we can choose flexible adaptive learning rates. Could you give us a guide on how to choose a good adaptive learning rate in the experiment? 
 
Minor comments:

1) In Abstract, the line 9: “…can flexibly integrates…”  should  be  “… can flexibly integrate…”;
 
2) In the convergence analysis, the gradient estimator $g_{t+1}$ is right (in the line 436).  At step 13 of the super-adam algorithm,  there exists a symbol error:  $g_t -$ should be  $g_t +$.
 
3) In the experiment, do you use the same adaptive learning rates in super-adam ($\tau=1$) and super-adam ($\tau=0$) ? 
limitations_and_societal_impact: yes
review_title: null

Meta-review: During the discussion phase, the paper has received intensive discussion between the authors and the reviewers about the merits and the concerns. Two reviewers have a strong favor of accepting this paper given that the paper presents a new analysis of Adam method for constrained non-convex optimization and also an improved variant of Adam by using recursive variance reduction methods with an optimal complexity. The major concerns are from the used convergence measure that is different from the standard convergence measure, and the authors' argument about its implication for the convergence of the standard  measure in terms of (proximal) gradient norm. The AC agrees that the presented results are interesting and the analysis of the Adam-style methods for constrained non-convex optimization is novel. The concern about the inconsistency between the presented convergence measure and the standard convergence measure is understandable given that the paper considers the constrained non-convex optimization. However, the authors should weaken their argument about its implication for the convergence of the gradient  norm or add more evidence such as empirical results presented in the rebuttal for further supporting their claim. The AC believes the concern should be addressable, and hence recommends an acceptance.  


Decision: Accept (Poster)