Venue: ICLR 2022 Conference

Reviews:

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: The paper proposes a memory-augmented optimizer to make use of the history information of the gradients. The motivation is that the aggregation of past gradients nudges parameter updates in a better direction. However, it remains to answer how much historical information of the gradients is sufficient. The authors study and analyze the memory requirement of several common optimization algorithms. Based on that, the authors propose a new optimizer that retains a limited gradient history and those gradients are selected by their importance. This method could be built upon existing popular optimizers like Adam and SGD and enjoys accelerated convergence and improved performance.
main_review: Pros
* The selection of the critical gradients directly depends on the $l_2$ norm of the gradients and the aggregation function is simple enough, so the idea itself looks reasonable and the implementation of the algorithm is straightforward. Furthermore, the optimizer could be combined with other popular first-order optimizers which can make it more useful.
* The related work section is well-written and the number of citations is adequate. I feel comfortable reading through the paper and the points are obvious to me. The comparison between the proposed method and other algorithms on memory requirements and performance improvement is clear.
* The experiment results are strong. Figure 2 gives a nice summary about how the proposed memory-augmented optimizer influences performance of the original optimizer.

Cons
* Although it seems natural to choose gradients of large norm as the critical ones. I did not find any motivation or explanation for that. There are several related works trying to utilize the information of historical gradients, but it is not clear how saving the critical gradients by looking at their norm helps improve the performance. More specifically, In Figure 5 (a) and (b), it seems the choices of selection techniques and replacement methods do not influence the results a lot. I would be rather interested if the author could give some insights about the reason why such selection mechanisms work well.

* The theoretical proof looks merely fine to me. It is not clear how the choice of $K$ will influence the bound. It would be more obvious and convincing if the authors could give some examples rather than simply claim it may be possible to accelerate convergence rates when $K > 1$. I guess such acceleration might depend on specific conditions and these conditions could show some improvements and limitations of the proposed algorithm. 

Comments
* Maybe there is a limitation for the number of pages, but I personally feel it will make the paper look more complete if Algorithm 1 goes to the main body.
* The description of $A_t$ at the bottom of page 13 seems to be wrong. Shouldn't the blocks of identity matrices be moved one block to their left?
summary_of_the_review: In general, the paper is well-written and the experimental results look strong. However, the lack of clear motivation and explanation of the proposed method downgrades my rating to the paper. Furthermore, the theoretical part could be more detailed as the current one does not provide a convincing improvement over vanilla SGD method. I hope the authors will answer these questions in the future.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: The paper proposes a framework for memory-augmented gradient descent optimizers which only keep a limited a limited buffer of gradient history and can be integrated with existing optimizers. The method proposed in the paper is centered around "critical gradients" with large l2 norm and only retaining them in the limited buffer. Experimental results show the faster convergence in terms of iterations compared to standard SGD algorithms without critical gradient buffers. 

main_review: The critical gradient strategy seems fairly interesting and a promising way to accelerate training. The paper was fun to read and well written. The experimental evaluation is fairly comprehensive and has interesting analysis. The main concerns I have are:
* Although the convergence speed in terms of iterations is faster, the wall clock time relative to baselines especially with large buffer sizes seems much higher Appendix D2 Table 4. The overhead seems to stem from the book keeping, replacement and aggregation strategy. Is there a convergence speed comparison Figure 2 with wall clock times as opposed to number of gradient updates?  
* In Analysis there is nice study on the staleness of the gradients in the buffer. Can the staleness bound just be enforced instead of relying on it being empirically the case?  
* If the critical gradients are finally aggregated either via sum or averaging there can be easier strategies for doing the same aggregation in a more online fashion without additional memory. Especially given that there is a decay term when doing gradient selection for replacement. Was there an attempt to try more online approaches?

summary_of_the_review: The proposed method of only storing critical gradients in a limited size memory buffer seems interesting. The experimental evaluation is comprehensive. However, the method only seems to improve in terms of gradient steps but not wall clock time to converge due to bookkeeping overheads.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: Bridging the advances from theoretical and empirical side, this paper proposes a framework for memory augmented optimizers, a strategy which can improve any off-the-shelf first order optimizers trading off increased memory with faster convergence. 
main_review: Strengths:
- A general framework which can accommodate existing first order optimizers to trade off memory with faster convergence.
- Convergence proof for smooth strongly convex functions 
- Solid set of experiments
  - Sensitivity to hparams
  - Alternatives to l_2 norm for deeming gradients critical


Areas of improvements and questions:
- Either make figure 1 vertical or at least make the text vertical so that its easier to read.
- In Figure 2, I see that several tasks degrade convergence. Is there a way to make sure this method does no worse than before? I will increase my score if this is done.
summary_of_the_review: Overall good paper, some areas of improvements
review_title: null

final_score: rating: 8: accept, good paper
review_content: summary_of_the_paper: The paper proposes an optimisation framework that uses K previous gradients stored in a buffer to compute an aggregated proxy-gradient for the  use in other gradient frameworks (studied are SGD, SGDM, RMSProp, Adam) and evaluates it on CIFAR 10/100 as well as NLP tasks. The paper also presents a convergence proof on strongly convex smooth objectives. In almost all empirical evaluations the method shows an improvement in terms of iteration and performance and ablations are performed to show strong robustness to hyperparameters introduced.
main_review: Strengths:

- analysis on strongly convex smooth objectives
- good empirical evaluation
- strong results on evaluated datasets

Weaknesses

- nowhere near SotA validation on CIFAR 10/100? Validation should be around 75% looking at wideresnets, results, while this is an optimisation paper, I feel like this makes it hard to compare/more vulnerable to accidental cherry picking
- architectures only visible in supplimentary, and appendix listing them for analysis would help the reader to have all information in one place
- strongly convex smooth is a strong assumption to place on convergence, although the empirical performance alleviates this to some degree
- I'm missing some comparison to other discussions of gradient staleness e.g. from the Asychronous Distributed SGD community http://proceedings.mlr.press/v80/damaskinos18a/damaskinos18a.pdf 

Questions:

- do you have any explanations of the cases where you regress in performance/speed? violation of the assumptions, high gradient variance or anything else?
summary_of_the_review: Overall, I like this paper as a simple to implement empirical improvement to other algorithm that just "makes sense": very large gradients should probably have an impact for a longer time BUT not all at once so as to not dominate fully.  It gives good but not overwhelming empirical evidence (difficult to compare to SotA due to architecture choice and different tuning) and some theoretical justification (albeit not applicable to the settings evaluated).
review_title: null

Meta-review: The paper proposes a general method to enhance the performance of first-order optimizers. The main idea is to use a memory buffer to maintain a limited set of critical gradients from recent history. Namely, gradients with large l2 norm. The paper includes a convergence proof on strongly convex smooth objectives. Experimental results are reported for several architectures in vision and language tasks. When integrated with several commonly used optimizers (SGD, SGDM, RMSProp, Adam), the method shows an improvement in terms of learning speed as well as improved performance (in almost all cases). Several ablations are performed to show strong robustness to hyperparameters introduced.

The paper is very well written and easy to follow. The proposed method is simple and effective. The empirical evaluation is strong and the ablation studies exhaustive and convincing, as pointed out by all four reviewers.

The authors provided a solid rebuttal addressing many questions raised by the reviewers.

Reviewer KE2X is the only reviewer recommending to reject the paper, pointing out that the paper lacks a clear motivation on why the critical gradients are selected based on the l2 norm. In their response the authors provided a connection with recent methods designed to find important examples when training neural networks. In the discussion (not visible to the authors). Reviewer v5GJ stated that this criterion is intuitive and acceptable given the strong empirical performance reported. The AC agrees with this view.

Reviewer KE2X also points out that the theoretical results do not provide a convincing improvement over vanilla SGD. The authors acknowledge this point, adding that the convergence results apply to a wide variety of critical gradient methods and aggregation strategies, so it is natural to expect that improvements will depend on the specific conditions. While the AC agrees that having stronger theoretical results would improve the paper, as it stands it is certainly above acceptance threshold.

Overall the paper makes a solid contribution with a method that is simple and effective. It will likely inspire other alternative methods in the future. The AC recommends accepting the work.
Decision: Accept (Poster)