Venue: ICLR 2018 conference

Reviews:

final_score: rating: 2: Strong rejection
review_content: This paper proposes a variation to the familiar AdaGrad/Adam/etc family of optimization algorithms based a gradient magnitude normalization. More precisely, the components of the gradient are split into blocks (one block per layer), and each block is normalized by its L2 norm. The concatenation of these normalized gradients are used in place of the standard gradient in AdaGrad/Adam/SGD. The authors find the resulting optimizer performs slightly better than its competitors on four tasks.

I feel this paper would be much stronger focusing extensively on one or two small problems and models, providing insight into how normalization affects optimization, rather than chasing state-of-the-art numbers on a variety of datasets and models. I believe the significance and originality of this work to be lacking.

## Pros ##

The paper is easy to follow. The algorithm and experiment setups are clearly explained, and the plots are easy to understand. I appreciate the variety in experimental setups. The authors provide a proof of convergence for the AdaGrad variant on convex functions.

## Cons ##

The paper fails to provide new insights to the reader. It succeeds in asking a question (how do normalized gradients impact training of neural networks?), but fails to add theoretical or empirical knowledge that furthers the field. While effectively changing the geometry of the problem, no motivation (theoretical or intuitive) is given as to why this normalization scheme should be effective.

From the empirical side, the authors compare the proposed optimizers on many datasets and models, but concerningly only using the baselines' default hyperparameters. Even ADAM, a supposedly "hands-free" optimizer, has been shown to vary greatly in performance when its hyperparameters are well chosen (https://arxiv.org/abs/1705.08292). This is simply unfair to the baselines, and conclusions cannot meaningfully be drawn from this alone. In addition, different tasks use different optimizers, which strikes me as odd, and no error bars are added to any plots.

From the theoretical side, the authors show a convergence bound that is minimized when the number of blocks is one. This, however, is not what the authors use in experiments, and no reasoning about the choice of blocks == network layers is given.

## Specific comments ##

p1: "Gradient computation is expensive" is not a good justification. All empirical risk minimization, convex or not, requires a full pass over the dataset. Many convex problems outside of ERM involve very expensive gradient computations.

p1: "These two challenges indicate that for each iteration, stochastic gradient might be the best practical first order information we can get". See loads of work in approximate second-order methods that show otherwise! Hessian-free Optimization, K-FAC, Learning to Learn Gradient Descent, ACKTR's use of Kronecker-factored Trust Region.

p2: You may want to reference Layer-Specific Adaptive Learning Rates for Deep Networks (https://arxiv.org/pdf/1510.04609.pdf), as it appears relevant to the layer-wise nature of your paper.

p2: "Recently, provably correct algorithms..." I'm fairly confident that Adam and RMSProp lack provable correctness. You may want to soften this statement.

p3: The expression being minimized is the sample risk, rather than the expected risk.

p5: The relationship between NG and NG_{UNIT} is confusing. I suggest keeping only the vanilla method analyzed in this paper, or that the second method be better motivated.
review_title: Paper is good start for a research question, but is insufficient for a research publication.

final_score: rating: 4: Ok but not good enough - rejection
review_content: This paper proposes a family of first-order stochastic optimization schemes based on (1)  normalizing (batches of) stochastic gradient descents and (2) choosing from a step size updating scheme. The authors argue that iterative first-order optimization algorithms can be interpreted as a choice of an update direction and a step size, so they suggest that one should always normalize the gradient when computing the direction and then choose a step size using the normalized gradient. 

The presentation in the paper is clear, and the exposition is easy to follow. The authors also do a good job of presenting related work and putting their ideas in the proper context. The authors also test their proposed method on many datasets, which is appreciated.

However, I didn't find the main idea of the paper to be particularly compelling. The proposed technique is reasonable on its own, but the empirical results do not come with any measure of statistical significance. The authors also do not analyze the sensitivity of the different optimization algorithms to hyperparameter choice, opting to only use the default. Moreover, some algorithms were used as benchmarks on some datasets but not others. For a primarily empirical paper, every state-of-the-art algorithm should be used as a point of comparison on every dataset considered. These factors altogether render the experiments uninformative in comparing the proposed suite of algorithms to state-of-the-art methods. The theoretical result in the convex setting is also not data-dependent, despite the fact that it is the normalized gradient version of AdaGrad, which does come with a data-dependent convergence guarantee.

Given the suite of optimization algorithms in the literature and in use today, any new optimization framework should either demonstrate improved (or at least matching) guarantees in some common (e.g. convex) settings or definitively outperform state-of-the-art methods on problems that are of widespread interest. Unfortunately, this paper does neither. 

Because of these points, I do not feel the quality, originality, and significance of the work to be high enough to merit acceptance. 

Some specific comments:
p. 2: "adaptive feature-dependent step size has attracted lots of attention". When you apply feature-dependent step sizes, you are effectively changing the direction of the gradient, so your meta learning formulation, as posed, doesn't make as much sense.
p. 2: "we hope the resulting methods can benefit from both techniques". What reason do you have to hope for this? Why should they be complimentary? Existing optimization techniques are based on careful design and coupling of gradients or surrogate gradients, with specific learning rate schedules. Arbitrarily mixing the two doesn't seem to be theoretically well-motivated.
p. 2: "numerical results shows that normalized gradient always helps to improve the performance of the original methods when the network structure is deep". It would be great to provide some intuition for this.  
p. 2: "we also provide a convergence proof under this framework when the problem is convex and the stepsize is adaptive". The result that you prove guarantees a \theta(\sqrt{T}) convergence rate. On the other hand, the AdaGrad algorithm guarantees a data-dependent bound that is O(\sqrt{T}) but can also be much smaller. This suggests that there is no theoretical motivation to use NGD with an adaptive step size over AdaGrad.
p. 2-3: "NGD can find a \eps-optimal solution....when the objective function is quasi-convex. ....extended NGD for upper semi-continuous quasi-convex objective functions...". This seems like a typo. How are results that go from quasi-convex to upper semi-continuous quasi-convex an extension?
p. 3: There should be a reference for RMSProp.
p. 3: "where each block of parameters x^i can be viewed as parameters associated to the ith layer in the network". Why is layer parametrization (and later on normalization) a good way idea? There should be either a reference or an explanation.
p. 4: "x=(x_1, x_2, \ldots, x_B)". Should these subscripts be superscripts?
p. 4: "For all the algorithms, we use their default settings." This seems insufficient for an empirical paper, since most problems often involve some amount of hyperparameter tuning. How sensitive is each method to the choice of hyperparameters? What about the impact of initialization?
p. 4-8: None of the experimental results have error bars or any measure of statistical significance.
p. 5: "NG... is a variant of the NG_{UNIT} method". This method is never motivated.
p. 5-6: Why are SGD and Adam used for MNIST but not on CIFAR? 
p. 5: "we chose the best heyper-paerameter from the 56 layer residual network." Apart from the typos, are these parameters chosen from the training set or the test set? 
p. 6: Why isn't Adam tested on ImageNet?

  
POST AUTHOR RESPONSE: After reading the author response and taking into account the fact that the authors have spent the time to add more experiments and clarify their theoretical result, I have decided to upgrade my score from a 3 to a 4. However, I still do not feel that the paper is up to the standards of the conference. 





 
review_title: Clearly written paper, but experiments are not compelling and theoretical result is suboptimal

final_score: rating: 9: Top 15% of accepted papers, strong accept
review_content: This paper illustrates the benefits of using normalized gradients when training deep models.
Beyond exploring the "vanilla" normalized gradient algorithm they also consider adaptive versions, i.e., methods that employ per block (adaptive) learning rates using ideas from AdaGrad and Adam.
Finally, the authors provide a theoretical analysis of NG with adaptive step-size, showing convergence guarantees in the stochastic convex optimization setting.

I find this paper both very interesting and important. 
The normalized gradient method was previously shown to overcome some non-convex phenomena which are hurdles to SGD, yet there was still the gap of  combining NG with methods which automatically tune the learning rate.

The current paper addresses this gap by a very simple (yet clever) combination of NG with AdaGrad and Adam, and the authors do a great job by illustrating the benefits of their scheme by testing it over a very wide span of deep learning 
models. In light of their experiments it seems like AdamNG and NG should be adopted as the new state-of-the-art methods in deep-learning applications.

Additional comments:
-In the experiments the authors use the same parameters as is used by Adam/AdaGrad, etc..
Did the authors also try to fine tune the parameters of their NG versions? If so what is the benefit that they get by doing so?
-It will be useful if the authors can provide some intuition about why is the learning rate  chosen per block for NG?
Did the authors also try to choose a learning rate per weight vector rather than per block? If so, what is the behaviour that they see.
-I find the theoretical analysis a bit incomplete. The authors should spell out the choice of the learning rate in Thm. 1 and compare to AdaGrad.

review_title: A very interesting and important paper

Meta-review: The paper proposes to study the impact of normalizing the gradient for each layer before applying existing techniques such as SG + momentum, Adam or AdaGrad. The study is done on a reasonable number of datasets and, after the reviewers' comments, confidence intervals have been added,  although Table 1 puts results in bold but many of these results are not statistically significant.

The paper, however, lacks a proper analysis of the results. Two main things could be improved:
- Normalization does not always have the same effect but the reasons for it are not discussed. This needs not be done theoretically but a more thorough analysis would have been appreciated.
- There is no hyperparameter tuning, which means that the results are heavily dependent on which hyperparameters were chosen. Thus, it is hard to draw any conclusion.

Regarding the seemingly conflicting remarks of the two reviewers, it all depends on what the paper is trying to achieve. If it tries to show that is it state-of-the-art, then comparing to state-of-the-art algorithms on every dataset is crucial. If it tries to study the impact of one specific change, in this case layer normalization, on the optimization, then comparing to the vanilla version is fine. The paper seems to try to address the latter so it is OK if it is not compared to all the state-of-the-art algorithms. However, proper tuning of existing methods is still required.

Ultimately, a better understanding of layer normalization could be useful but the paper is not convincing enough to provide that understanding. There is no need to increase the number of datasets but it should rather focus on designing setups to test and validate hypotheses.
Decision: Reject