Venue: ICLR 2020 Conference

Reviews:

final_score: rating: 8: Accept
review_content: This paper applies new assumption on smoothness that assume the norm of Hessian is bounded by a scalar plus norm of gradient. The traditional smoothness is only bounded with a scalar, the proposed assumption is more relaxed because now the norm of Hessian can grow with the norm of gradient. Under this assumption, the authors show clipped gradient converges faster than gradient for general nonconvex problems. The authors provide insights on why the proposed assumption is good for describing neural networks, and empirically verify the assumption with ResNet on CIFAR and LSTM on PTB. 

I like the paper in general. It is well written and easy to follow. The contributions are clearly described and the techniques seem to be solid. 

I want a little bit more discussion to help me better understand the paper. 

1) Intuitively, try best in plain English, why does clipped gradient convergence does not have dependency on L_1 M? Could the authors provide more discussion on the learning rate (hyperparameters) used for clipped gradient and gradient?

2) The convergence rates under the proposed assumption are slower than traditional smoothness assumption. Could you verify the slow convergence rate under proposed assumption aligns better with practical training? Could you provide a toy example, for example x^3, to show the advantage of the proposed assumption and the convergence under the assumption? What is the gap between clipped gradient and gradient, for experiments in figure 4, and possible toy problem? Could the authors elaborate the difference of clipped gradient and gradient with the details of theory, instead of simply claiming clipped gradient is faster?

Typo, page 5, (0, L) -> (L, 0)


============ after rebuttal ===================
I am happy to see the paper in the conference. The paper is intuitive and well written. My remaining comments are still on the slower convergence rate comparing to previous assumption. Even before, researchers suggest overparameterized network can converge faster than expected. This paper suggests a generally slower convergence rate if the proposed assumption does fit practice better.   

review_title: Official Blind Review #1

final_score: rating: 8: Accept
review_content: In this paper, the authors relax the generally used Lipschitz smoothness condition in optimization, to a more general smoothness condition that may depend on norm of the gradient. The authors proved that, with this relaxed condition, under such cases, both GD and clipped GD can converge within O(1/\epsilon^2) time, but when their exists x where the gradient norm can be very large, the clipped GD will converge provably faster than GD with a proved GD convergence rate lower bound. The authors also generalize their results to SGD. Experiments show that in deep neural network local gradient Lipschitz constant is scale with gradient norm, and use clipped gradient can accelerate convergence while keep good generalization performance as expected, which is well observed by other researchers.

Detailed comments:
1. The f^* In theorem 3 is not defined. I think it’s not the f^* in Assumption 1? Should be more clear. Also, in non-convex optimization, can the deterministic GD find the global optimum? If f^* is the stationary point the algorithm find, then the Assumption 1 is a little weird. The authors should better clarify this.
2. Feel the claim of the Assumption can be relaxed to only hold on \mathcal{S} is a little confusing. Which Assumption can be relaxed? It seems that in the proof of Lemma 9, we need the Assumption 3 holds for the set \|x^+-x\| \leq min{1/L_1, 1}. I think maybe the other Assumption will also be needed globally, unless the authors can prove that the optimization is only on a compact set in S.
3. Maybe a discussion connected the existing Lipschitz constant based results to the new results in this paper can make the readers more aware of the contribution in this paper. For example, the Lipschitz constant of neural network can be of order O(L_1 M) due to the definition, so if L_1 M is large, for clipped GD we can still have expected decreasing of O(1/L_0) each turn while vanilla GD with the best O(1/L) step size can still only have O(1/L) where L = L_0 + L_1 M due to the traditional results based on Lipschitz smoothness.

I don’t totally go through the whole proof, but I think the results are reasonable and the most of the techniques are standard to the whole community. So there may be no fatal error that violates the conclusion. I find the whole paper interesting and match the intuition from the practice. However, I think it can be polished to make the whole idea more clear and more easy to accept by the potential theorists and practitioner audience.
review_title: Official Blind Review #2

final_score: rating: 8: Accept
review_content: The authors provide the definition of a (L_0, L_1)-smooth function.
They motivate this class of function based on theoretical arguments and
empirical observations in the context of neural network training loss.
The authors go on to show that for (L_0, L_1)-smooth loss constant
step-size gradient descent can perform arbitrarily bad with poor initialization.
Specifically, the largest constant step size that can be used without divergence
depends on the upper bound of the gradient norm.
If the function is steep (high gradient norm) at some point during the
optimization process the steps need to become arbitrarily small
(especially relevant in nonconvex loss, where gradient norm does not always decrease).
The small constant step size slows down convergence everywhere else.
The described phenomenon is an argument for step sizes adaptivity in general
Clipping the gradient based on the known (L_0, L_1)-smoothness is a form of
adaptivity that makes steps small enough to avoid divergence only where the
function is steep and can thus be more efficient.

Overall, the authors give a theoretical justification for the use of clipped
gradient descent in the context of training neural networks.
The analysis of clipped gradient descent is performed rigorously (proofs are
provided in the appendix) and extended to the stochastic gradient descent setting.
The motivation for using (L_0, L_1)-smoothness and gradient clipping is also
shown to be relevant in practical experiments with language and image
classification models.

I recommend to accept the paper.

The paper is a clearly stated contribution to optimization theory as motivated
by machine learning applications.
The authors give a clean theoretical analysis of a previously empirically
observed phenomenon and an algorithm that is already used in practice.

Notes:
- Page 1, first paragraph:
If f(x) = E_xi [f(x, xi)] then f(x) the expectation is generally not stochastic,
like you write before. It is clear what you mean but Maybe use a different symbol.

- Page 2, ...we observe the function smoothness has a strong correlation with gradient norm 2:
Perhaps write something like "(see Figure 2)" instead of just "2" here.

- Page 2, after definition of Lipschitz continuous:
Nitpick: Formal definition based on Hessian norm upper bound should also have, for all x \in \mathbb R^d

- General: Some equations that are not referenced seem to be numbered, some are not.

review_title: Official Blind Review #3

Meta-review: Gradient clipping is increasingly popular and it's nice to see a paper theoretically exploring its nice performance. All reviewers appreciated the work and the results.

Please make sure to incorporate all of their comments for the final version.
Decision: Accept (Talk)