Venue: ICLR 2020 Conference

Reviews:

final_score: rating: 3: Weak Reject
review_content: In this paper, the authors present a new adaptive gradient method AvaGrad. The authors claim the proposed method is less sensitive to its hyperparameters, compared to previous algorithms, and this is due to decoupling the learning rate and the damping parameter.

Overall, the paper is well written, and is on an important topic. However, I have a few concerns about the paper, which I will list below.

1. The fact that adaptive gradient methods converge with a fast rate when the sum in the denominator is taken till the t-1th iterate has appeared in previous papers before [1]. The convergence rate analysis for this case is fairly simple, and I am not sure if analyzing RMSProp/Adam in this setting should be considered a significant contributions of the paper.

2. The proposed algorithm AvaGrad is a simple but interesting idea. I have a number questions about the experimental evaluation though, which makes it hard for me to evaluate the significance of the results presented:

a) Was momentum used with SGD?

b) How is the optimal hyperparameters (learning rate and damping, i..e, epsilon, parameters) selected?

c) Do any of these conclusions change when trying out a very small or very large batch size?

d) I am not convinced that using the same optimal hyperparams as the WRN-28-4 task on the WRN-28-10 and ResNet50 models is a reasonable experiment. Why is this a good idea? While this does support the claim that adaptive gradient methods are less sensitive to hyperparameter settings, but makes the other claim about AvaGrad generalizing just as well as SGD weaker?

e) One of the key claims that adaptive gradient methods generalize better when using a large damping (epsilon) parameter has appeared in previous papers as well [2, 3].


Overall, in my view, this is a borderline paper mostly because I think a number of the results presented have been shown in other recent papers. My score reflects this. However, I think decoupling the learning rate and the damping parameter by normalizing the preconditioner is a simple but interesting idea, and I am willing to increase my score based on the discussion with the authors and other reviewers.


[1] X. Li and F. Orabona. On the Convergence of Stochastic Gradient Descent with Adaptive Stepsizes. In AISTATS 2019
[2] M. Zaheer, S. Reddi, D. Sachan, S. Kale, and S. Kumar. Adaptive methods for nonconvex optimization. in NeurIPS 2018.
[3] S. De, A. Mukherjee, and E. Ullah. Convergence guarantees for rmsprop and adam in non-convex optimization and an empirical comparison to nesterov acceleration. arXiv:1807.06766, 2018.

A few more minor comments:

1. The authors say that methods like AMSGrad fail to match the convergence rate of SGD. But this statement seems misleading since it is not clear whether the worse rate is due to the analysis (which gives an upper bound) or the algorithm?

2. In the related work section, the authors discuss convergence rates of algorithms with constant and decreasing step sizes together. This can be confusing to the reader, and it is best to explicitly mention the setting under which the different results were derived.

=======================================

Edit after rebuttal:
I thank the authors for the detailed response and for the updated version of the paper. After discussion with other reviewers, we are still not convinced that the hyperparameter tuning in the experiments (especially the baselines) is rigorous enough. This is especially important given that this paper proposes a new optimizer. We are also concerned about the novelty of the results, and believe most of these results have appeared in previous work. So I am not increasing my score. I would encourage the authors to do a more rigorous experimental evaluation of the proposed algorithm.
review_title: Official Blind Review #4

final_score: rating: 6: Weak Accept
review_content: In this paper the authors develop variants of Adam which corrects for the relationship of the gradient and adaptive terms that causes convergence issues, naming them Delayed Adam and AvaGrad. They also provide proofs demonstrating they solve the convergence issues of Adam in O(1/sqrt(T)) time. They also introduce a convex problem where Adam fails to converge to a stationary point.

This paper is clearly written and has reasonable experimental support of its claims. However in terms of novelty, AdaShift was published at ICLR last year (https://openreview.net/forum?id=HkgTkhRcKQ) and seems to include a closely related analysis and update rule of your proposed optimizers. In AdaShift instead of correcting for the correlation between the gradient and eta_t, they correct for the relationship between the gradient and the second moment term v_t. Could you further clarify the differences between the two, both in your approach to deriving the new update rule and the algorithms themselves? Additionally, their Theorem 1 could be compared to yours, but noting the differences for these seems less important. If the optimizers are unique enough, including AdaShift in your experiments would be very useful for demonstrating their differences.

Regarding experiments, while it is true that adaptive methods are supposed to be less “sensitive” to hyperparameter choices, the limits of the feasible ranges for each hyperparameter could vary drastically across problems (especially, as previously demonstrated, across different batch sizes.) Thus, not retuning across experiments seems like it could negatively affect performance for any of the transferred hyperparameter settings. Instead of demonstrating hyperparameter insensitivity by carrying over hyperparameter settings, one could instead retune for each problem and show that a higher percent of hyperparameter combinations result in the same/similar best performance (similar to what is done in Fig. 2, but also showing a (1-dimensional) SGD version which would presumably contain fewer high performing settings.)

Some additional comments:
-The contribution of Theorem 1 is a nice addition to the literature.
-Your tuning of epsilon is great! I believe more papers should include epsilon in their hyperparameter sweeps.
-Scaling epsilon with step size makes sense when considering that Adam is similar to a trust region method, where epsilon is inversely proportional to the trust region radius. However, in section 5 implying that epsilon should be as large as possible in the worst case seems like an odd result given that this would always diminish your second moment term as much as possible, defeating the point of the additional Adam-like adaptivity. Can you comment on why this diminished adaptivity would be desirable in the worst case scenario analyzed?
-The synthetic toy problem is much appreciated, more papers should start with a small, interpretable experiment.
-Was SGD with momentum used? If not, this may not be a fair comparison, as I believe it is much more common to use momentum with SGD. If momentum was used, was the momentum hyperparameter tuned? If not, this may be advantageous to the Adam based methods, as they have more versatile adaptability and thus may not need as much care with their selection of momentum values.
-Was a validation set used for CIFAR? You note in appendix C that there are 50k train and 10k test. You mention validation performance in the main text, so this is just double checking.
-The demonstration in figures 2, 3 of decoupling the step size and epsilon in interesting! Given that the best performing values seem to be on the edges of the ranges tested, I would be curious if the trend continues for more extreme values of alpha and epsilon (one could sparsely search along the predicted trendlines.)

Nits:
-“Vanilla SGD is still prevalent, in spite of the development of seemingly more sophisticated adaptive alternatives...” This could use some citations to back up the claim, because as far as I know it is much more common to use SGD with momentum and is actually rare to use vanilla SGD (the DenseNets and Resnets citations use momentum=0.9.)
-It would be nice to highlight in color the diff from vanilla Adam in the Algorithm sections.
-It is not super clear from the text how in eq 26 you get \sum{E[f(w_t)|Z]} = f(w_1)
-I may be misreading something, but I believe the H in the leftmost term in the last line of eq 33 should be an L.
-In section 5, “for a fixed learning rate (as is typically done in practice, except for discrete decays during training)” seems like an overly broad claim, given that authors commonly use polynomial, linear, exponential, cosine, or other learning rate decay/warmups. Granted for some CIFAR and ImageNet benchmarks there are more common discrete learning rate schedules, but that does not seem to be the overwhelmingly prevalent technique.

Overall, while this area of analyzing Adam and proposing modifications is a popular and crowded subject, I believe this paper may contribute to it if my concerns are addressed. While I currently do not recommend acceptance, I am open to changing my score after considering the author comments!

review_title: Official Blind Review #3

final_score: rating: 3: Weak Reject
review_content: Summary:
This paper proposes a new adaptive method, which is called AvaGrad. The authors first show that Adam may not converge to a stationary point for a stochastic convex optimization in Theorem1, which is closely related to [1]. They then show that by simply making $eta_t$ to be independent of the sample $s_t$, Adam is able to converge just like SGD in Theorem2. Theorem2 follows the standard SGD techniques. Next, they propose AVAGRAD, which is based on the idea of getting rid of the effect of $\epsilon$. 

Strength:
The experiment results are impressive. They show that Adam can outperform SGD on vision tasks.
Recently, people have found out that $\epsilon$ is a very sensitive hyper-parameter. It is good to see some research directly addresses this problem. 

Weakness:
The word "domain" is confusing. 
If the Adam-type algorithms are the delayed version in Table 1?
It is not compatible with AdamW. 
The results on the image datasets seem too good to be true.

Implementation Issue:
***Many implementation details in the below discussion are different from the paper (e.g. hyperparameters and network architecture). So the following experiment results may not be used for assessment of the quality of the proposed method.***
I tried the proposed Delayed Adam on CIFAR-10 using the codebase in (https://github.com/LiyuanLucasLiu/RAdam/tree/master/cifar_imagenet). The performance seems the same as Adam. Delayed Adam even leads to a *divergence* problem, especially with a large learning rate (0.03). The divergence problem never happens when using Adam and AdamW with the same hyperparameters.
Implementation details: 
1. Replace the optimizer with the original PyTorch Adam implementation. (https://github.com/pytorch/pytorch/blob/master/torch/optim/adam.py) 
2. Swap line 96 and 108 as suggested in the paper. 
3. Modified line 89 (bias_correction2=1 - beta2 ** (state['step']-1)) 
4. Do not run line 97-107 when state['step']==1. 
5. Run the following code: python cifar.py -a resnet --depth 20 --epochs 164 --schedule 81 122 --gamma 0.1 --wd 1e-4 --optimizer adam  --beta1 0.9 --beta2 0.999  --checkpoint ./logdir --gpu-id 0 --model_name adam_003 --lr 0.03

If the authors can provide more implementation details, I would promote my rating. 
e.g., 
1. Are you still using bias correction in the proposed method? If so how do you use them?
2. Do you update the model for the first step?

Reference:
[1] On the convergence of adam and beyond

review_title: Official Blind Review #2

Meta-review: This paper proposes an adaptive gradient method for optimization in deep learning called AvaGrad.  The authors argue that AvaGrad greatly simplifies hyperparameter search (over e.g. ADAM) and demonstrate competitive performance on benchmark image and text problems.  In thorough reviews, thorough author response and discussion by the reviewers (which are are all appreciated) a few concerns about the work came to light and were debated.  One reviewer was compelled by the author response to raise their recommendation to weak accept.  However, none of the reviewers felt strongly enough to champion the paper for acceptance and even the reviewer assigning the highest score had reservations.  A major issue of debate was the treatment of hyperparameters, i.e. that the authors tuned hyperparameters on a smaller problem and then assumed these would extrapolate to larger problems. In a largely empirical paper this does seem to be a significant concern.  The space of adaptive optimizers for deep learning is a crowded one and thus the empirical (or theoretical) burden of proof of superiority is high.  The authors state regarding a concurrent submission: "when hyperparameters are properly tuned, echoing our results on this matter", however, it seems that the reviewers disagree that the hyperparameters are indeed properly tuned in this paper.  It's due to these remaining reservations that the recommendation is to reject.  
Decision: Reject