Venue: NeurIPS 2022 Conference

Reviews:

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: summary: This work extends adaptive (L0, L1)-smooth [1] from gradient clip that clips large gradients to signSGD that shrinks the learning rate when the gradient norm is large. The author proves the convergence and shows the experiments.

The core idea is that the gradient smoothness is small (it changes quickly) when the gradient norm is large. Both gradient clip and signSGD reduces the learning rate when the curvature changes too fast. 

[1] Zhang, Jingzhao, Tianxing He, Suvrit Sra, and Ali Jadbabaie. "Why gradient clipping accelerates training: A theoretical justification for adaptivity." arXiv preprint arXiv:1905.11881 (2019).
strengths_and_weaknesses: Strengths: 
1） Based on the (L0, L1)-smooth observation, the extension from gradient clip to signSGD follows the intuition. 
2） both theoretical proofs and experimental results are shown. 


Weaknesses:
1) The (L0, L1)-smooth observation is well demonstrated by [1]. 
2) [1] already prove the fast convergence rate of normalized gradient methods with the (L0, L2)-smooth. 
The signSGD is close related to the normalized gradient method. (comparing equation (6) in [1] with algorithm 1 line 5-7). 
It reduces the novelty is this work. 

[1] Zhang, Jingzhao, Tianxing He, Suvrit Sra, and Ali Jadbabaie. "Why gradient clipping accelerates training: A theoretical justification for adaptivity." arXiv preprint arXiv:1905.11881 (2019).
questions: no
limitations: see strengths and weaknesses.
review_title: null

final_score: rating: 5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.
review_content: summary: In this paper, the authors firstly studied the applicability and generalization of the relaxed smoothness assumption. Empirically, the authors showed that Transformer, one of the most widely used practical models, also satisfied the relaxed smoothness assumption for some $L_0, L_1$, which showed the assumption is meaningful and not too strong.  Secondly, given the relaxed smoothness assumption, the authors proposed and analyzed a generalized SignSGD algorithm. From theoretical perspective, the authors not only proved the convergence rates, but also located the critical role of the momentum players: it reduces the noise effect and gives an exponential decaying effect on the unbounded gradient norms and smoothness. 
strengths_and_weaknesses: This paper has high writing quality, complete literature review. The topic is OK in terms of originality and significance. However, according to the authors' experimental results, the generalized SignSGD seems to be a little worse than the best existing algorithm, which may make it difficult to be widely used in practice. On the other hand, in the main theorem, the left hand side is the minimum of norm over T, which I feel quite strange, since the most metric I saw is the last-iterate norm and the average norm. It would be better if the authors can make a clear explanation on this. 
questions: Is it possible to propose a last-iterate norm upper bound or average-iterate norm upper bound? 
By the way, the numbering of the lemmas is quite strange. Lemma 11 is in front of Lemma 9. Could you explain that?
limitations: I don't think this paper has any potential negative societal impact since it is completely a theory-based work. All the experiments are used to verify their theory and compare with other optimizers.
review_title: null

final_score: rating: 7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
review_content: summary: This paper tackles the problem of optimizing non-convex stochastic functions with relaxed smoothness assumptions, e.g. the $(L_0,L_1)$-smoothness, where the smoothness parameter (i.e. upper bound on the second-order derivative) can be unbounded and locally proportional to the gradient magnitude. Building on prior works [1,2], this paper studies a more fine-grained smoothness, namely the coordinate-wise $(L_0,L_1)$-smoothness. Under this assumption, the authors propose an algorithm based on normalized gradient with momentum and analyze its convergence guarantee. The resulting complexity bound has a similar form to [2], showing that the efficacy of the algorithm does not depend on $L_1$ or the gradient upper bound when $\epsilon$ is small enough. The authors also give experiments to show that coordinate-wise $(L_0,L_1)$-smoothness is reasonable and the proposed algorithm is practically efficient.

[1] Why gradient clipping accelerates training: A theoretical justification for adaptivity. ICLR 2020.

[2] Improved Analysis of Clipping Algorithms for Non-convex Optimization. NeurIPS 2020.
strengths_and_weaknesses: **Strengths**:
1. (**Relevance and significance**) Non-convex optimization plays a central role in modern deep learning. Traditionally, the analysis of non-convex optimization algorithms relies heavily on the smoothness of objective functions, in which case vanilla SGD is provably optimal. However, such an assumption is quite unrealistic in practice, especially in training deep neural networks such as LSTMs, for which SGD is much worse than adaptive gradient methods empirically (e.g., Adam). Recently, such an inconsistency between theory and practice has been partially addressed by introducing a relaxed smoothness assumption [1,2]. However, their assumption is still not satisfactory, as the linear dependency between smoothness and gradient norm is very coarse and quite artificial. Investigating better smoothness conditions that align well with practice is clearly of significant value. This paper takes a step towards such a research problem, which in my opinion is important and relevant to the optimization community.

2. (**Writing**). This paper is well-written, clear, and easy to read. The related work section is comprehensive, despite there is an important work missing (see the Weakness part). The comparison between this paper and prior works is well-explained. 

3. (**Technical novelty**). I believe studying coordinate-wise smoothness is novel and the proposed algorithm is clean. The similarity of the proposed algorithm with Adam is quite interesting.

**Weaknesses**:

However, I have to say currently this paper have several major weaknesses. I hope they can be addressed before acceptance.

1. (**Missing related work**). A recent work [3] tackled almost the same problem with a similar algorithm as proposed in this paper, and thus should be discussed in detail. In particular, the work of [3] studied the algorithm called normalized SGD with momentum under the $(L_0,L_1)$-smoothness assumption (Algorithm 1 and Theorem 3.5 in their paper). They already pointed out how gradient normalization and momentum can be combined together when dealing with $(L_0,L_1)$-smooth functions with noisy gradients, and how a carefully chosen momentum factor reduces the noise and the required mini-batch size. They also pointed out the relationship with Adam. The only difference is that this paper studies coordinate-wise smoothness and thus uses coordinate-wise gradient normalization. Therefore, I suggest the authors to revise some statements in this paper to avoid overclaim, for example, the abstract/conclusion sections, as well as the following lines:
- Line 74-76: "To the best of our knowledge, this work is the first one establishing guarantees for generalized SignSGD as well as Adam-type updates under a relaxed smoothness condition."
- Line 8: "we show that clipping is not indispensable in tackling such scenarios...... Our analysis underlines the critical role that momentum plays: ...... but it also substantially reduces the effects of unbounded smoothness and gradient norms."

  Moreover, [3] also relaxed the bounded noise assumption to a much weaker assumption, which is better than this paper. They also found a concrete problem called the distributionally robust optimization, which is provably $(L_0,L_1)$-smooth. On the other hand, compared with [3], the strength of this paper lies in the coordinate-wise smoothness / coordinate-wise normalization which are different and novel. 

2. (**Regarding the Assumption**) The proposed smoothness assumption seems unreasonable if I understand correctly. For example, consider the quadratic function $F(x)=\frac 1 2 (x_1+x_2)^2$. It does not satisfy the inequality:
\begin{equation}
\left|\frac{\partial F}{\partial x_{j}}(\boldsymbol{y})-\frac{\partial F}{\partial x_{j}}(\boldsymbol{x})\right| \leq\left(L_{0, j}+L_{1, j}\left|\frac{\partial F}{\partial x_{j}}(\boldsymbol{x})\right|\right)\left|y_{j}-x_{j}\right|
\end{equation}
because $\left|\frac{\partial F}{\partial x_{j}}(\boldsymbol{y})-\frac{\partial F}{\partial x_{j}}(\boldsymbol{x})\right|$ can be arbitrarily large as $y_i,i\neq j$ can be chosen arbitrarily which however does not change the right hand side. This seems problematic as even the simple quadratic functions (which are smooth and convex) do not satisfy the condition. The authors should illustrate what functions satisfy this assumption and why it is acceptable.

3. (**Regarding the main results**)
- The main result only provides a complexity upper bound in terms of $\min_t ||\nabla F(x_t)||_1$. This seems a bit weak since $\min_t ||\nabla F(x_t)||_1\le \epsilon$ does not even indicate convergence of the algorithm. It is likely that the gradients near the end of training (say, the last $0.1T$ iterations) are all large. Can you use better metrics to derive the complexity bounds, such as $\frac 1 T \sum_t ||\nabla F(x_t)||_1$ as in [2], or other better forms?
- It seems that $\beta_2=0$ gives the best bound: $\rho$ reaches the maximal value and the algorithm does not require the extra assumption of the gradient upper bound $M_j$. So what is the advantages of increasing $\beta_2$? Why do the authors consider the general case when $\beta_2>0$?
- This paper makes the assumption that the gradient noise is bounded, which is somewhat restrictive (while it is indeed used in prior works [1,2] for analyzing gradient clipping). However, since [3] successfully derived complexity guarantees of the normalized SGD+momentum algorithm under the weaker and more common noise assumption, I think it is likely that this paper can follow the same techniques to relax the noise assumption. Actually, after coarsely reading the proof I found that part of the analysis (e.g., Lemma 11) is similar to the noise reduction analysis in [3]. This weakness is not a major one, but it would be nice to address it.

Nevertheless, I appreciate the motivation of this paper. The current rating is *not final* and I am willing to increase the score if the major concerns (including concerns 1, 2, and the first of 3) are addressed after the author response.

**Miscellaneous minor issues**: In line 194, it should be $\beta_1<1$.

[3] Non-convex Distributionally Robust Optimization: Non-asymptotic Analysis. NeurIPS 2021.
questions: See the above section.
limitations: No negative societal impact
review_title: null

Meta-review: metareview: During the discussion it became clear that this work naturally extends previous works
on signSGD to encompass generalised methods. Several clarifications were made by the authors throughout the rebuttal process, and this has mostly satisfied the reviewers. Moreover, I think that all in all this work may be interesting to the neurips community, and I recommend to accept it.
confidence: Certain
Decision: Accept