AGD: an Auto-switchable Optimizer using Stepwise Gradient Difference for Preconditioning Matrix

Summary

The paper proposes a new gradient based optimization called AGD. The idea is to utilize gradient difference between the current and previous steps in the preconditioning matrix which is related to Hessian. Also, an autoswitching function is proposed to switch between SGD and the adaptive optimizer. As mentioned in the paper, both ideas were previously brought up but the attempt to make an explicit optimizer is first done in the paper.

Strengths

- Well written and motivated - Conducting number of downstream experiments - Presenting extra studies to examine the method

Weaknesses

-The idea is not fully new - The details of experiments could be more explained

Questions

- Figure 3 suggests AGD is faster to converge, and Table 3 suggests AGD results in better performance. Could we make such a conclusion that it should be always used instead of SOTA optimization methods? - What is the stop criteria of different optimization techniques in Table 3? I am wondering if the improvement obtained by AGD is accurately examined or for example all methods go for the same number of iterations and AGD converges faster? You argued this issue in section 4.3 for CV task. - The performance of AGD in CV task is quite marginal. How about the convergence time? does AGD maybe converges faster? - I would have also liked to see more about autoswitching and why and how it happens in a simple toy example.

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.

Confidence

2: You are willing to defend your assessment, but it is quite likely that you did not understand the central parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.

Soundness

3 good

Presentation

3 good

Contribution

2 fair

Limitations

-

Summary

This paper introduces a novel optimizer, namely, Auto-switchable optimizer with Gradient Difference of adjacent steps. The authors propose a different way of approximating information from the Hessian for faster and better convergence in a way that a preconditioning matrix is computed using successive optimization steps in the parameter steps. The authors evaluate their optimization algorithm across different tasks and including some widely used architectures such as Transformers and RNNs. Moreover, the authors provide a theoretical analysis of the convergence of their algorithm and some bounds.

Strengths

- The paper is well written in terms of giving the appropriate context of the most commonly used optimization algorithms, nice figures for toy experiments to understand how the algorithm works. - The experimental framework idea is well designed in the sense that a good range of optimization tasks is considered to show the importance of the algorithm. - The idea of using the successive steps seems novel to me to approximate Hessian information for faster convergence.

Weaknesses

- In my humble opinion, the issue with the current idea lies in terms of the number/width of the optimization steps and how far the solution lies compared to the initialization point in the parameter space. The information that one can obtain by gradient differentials in the optimization space is only getting less and less useful while we increase the dimensionality of the optimization space. That means that for smaller optimization problems where the optimal solution would lie close to the initialization point, then I can really see the benefit of AGD compared to less Hessian well-informed optimizers like Adam. One can also see this emergent problem even from the theoretical analysis of the authors. For instance, in Theorem 2, the authors bound the approximation of the function using $D_\infty$ which effectively is the upper bound in terms of successive optimization steps in the parameter space and also an upper bound of each weight vector compared to its distance from the optimal solution. That means that for real-world multi-dimensional optimization problems (e.g. billions of parameters) those bounds and probably the algorithm itself could be called into question. Having said that, there are other works like NTK that have shown that neural networks stay pretty close in general near the initialization regime, so, I would not consider it appropriate to ask the authors to prove these things but they could put more effort into making their experiments more convincing to ameliorate this huge concern. - Building upon my previous argument, my belief about the problem of scaling of the algorithm to bigger optimization problems is also displayed in the experiments where AGD scores significantly higher than all the other optimizers in smaller parameter spaces (e.g. 1-2 layers of LSTM) but becomes almost negligible with slightly bigger networks (e.g. compare Adam vs Proposed in Table 4, ResNEt 20, 32, Table 5 MLP, DCN, compare AdamW vs AGD in Table 1 Transformer). Having said that, the authors can include experiments with larger and state-of-the-art networks (e.g. ResNet 100+ layers on ImageNet, include some experiments with some networks with 500+ million parameters transformers) to prove me wrong and compare against state-of-the-art performance reported numbers with SGD and/or Adam. I am willing to increase my score if most of the most important above concerns are addressed by the authors since I truly believe that the paper has a great potential to offer a more robust general optimization strategy to replace Adam.

Questions

Would you consider including experiments with some harder tasks such as estimation tasks, e.g. audio source separation instead of detection and retrieval tasks?

Rating

3: Reject: For instance, a paper with technical flaws, weak evaluation, inadequate reproducibility and incompletely addressed ethical considerations.

Confidence

4: You are confident in your assessment, but not absolutely certain. It is unlikely, but not impossible, that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work.

Soundness

2 fair

Presentation

3 good

Contribution

2 fair

Limitations

The authors should include my first point under the weaknesses of the paper and include a small paragraph to address this potential limitation of their algorithm.

Summary

The paper proposes a new optimizer based on finite difference approximation to obtain the inner product between the Hessian row vector and the parameter vector difference from gradients of succeeding steps and an auto-switching function to switch between SGD and the adaptive optimizer. It uses an exponential moving average of gradient instead of gradient for lower variance. Experimental results show that the proposed method performs better than existing methods in most cases.

Strengths

The proposed algorithm can efficiently acquire the information of the Hessian. Experimental results show performance improvements.

Weaknesses

The explanation of related works is minimum. It needs to be more concretely clarified what problem of existing second-order methods it addresses. The experiments in section 4 only report model performance and do not report computational costs. I need help finding Figures 5 and 6 in the paper. Are they missing?

Questions

What is the reason for the performance improvement? Is it due to its ability to find better local optima or the faster convergence in a limited computation budget?

Rating

5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.

Confidence

3: You are fairly confident in your assessment. It is possible that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.

Soundness

2 fair

Presentation

2 fair

Contribution

3 good

Limitations

There is no numerical explanation for the computational cost.

Summary

The paper proposes a new optimizer called AGD that integrates the information of the Hessian into the preconditioning matrix and switches dynamically between SGD and the adaptive optimizer. The authors establish theoretically proven convergence guarantees in both non-convex and convex stochastic settings. The authors validate AGD on a total of six public datasets: two from NLP (IWSLT14 and PTB), two from CV (Cifar10 and ImageNet), and the rest from RecSys (Criteo and Avazu). The experimental results reveal that AGD can outperform or be on a par with the SOTA optimizers. Overall, the paper makes a significant contribution to the field of deep learning optimization. AGD is a promising new optimizer that has the potential to improve the performance of deep learning models on a variety of tasks.

Strengths

• AGD can achieve a faster convergence rate over SGD • AGD can automatically switch between stochastic and adaptive optimization, depending on the progress of the optimization. This allows AGD to achieve the best of both worlds, i.e., the fast convergence of adaptive optimizers and the robustness of SGD. • AGD has a few flexible hyperparameters, making tuning for different tasks and datasets easy. • AGD was evaluated on various datasets across different domains, and it outperformed other optimizers in most cases.

Weaknesses

• The convergence rate of AGD depends on the hyperparameters δ and β1. If these hyperparameters are not chosen carefully, AGD may not converge to the optimal solution. Looking forward to seeing more comprehensive robustness evaluation using different network structures and larger datasets. • AGD requires more computation than SGD. How is its efficiency for large-scale problems, e.g., large language models? I think performance on large-scale generative model optimization is a very interesting direction. Does the author have plans to try on such a task?

Questions

• Please see weaknesses.

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.

Confidence

3: You are fairly confident in your assessment. It is possible that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.

Soundness

3 good

Presentation

3 good

Contribution

3 good

Limitations

There is no limitation discussed in the paper.

Summary

This paper proposed AGD, a novel optimiser that can dynamically switch between an adaptive optimiser and SGD. To achieve this, an auto-switching function is introduced to change the diagonal elements of the preconditioning matrix based on the gradients of adjacent steps. Both theoretical analysis on the convergence of the optimiser, and experimental results on six public CV, NLP and RecSys setups are provided, demonstrating AGD is a promising method both in theory and practice.

Strengths

It is often noticed in practice that SGD with proper hyperparameters (learning rate, momentum, and weight decay) can outperform the adaptive optimisers with better local optimum found, while the adaptive optimisers require less effort in hyperparameter tuning and sometimes faster convergence. The auto-switching strategy may help combine the advantages of them, and experimental results and analysis demonstrate the soundness and robustness of the chosen auto-switching function.

Weaknesses

1. Optimisers can perform differently on large-scale and small-scale experiments. Although good PTB results are given in the paper, a larger-scale language modelling experiment may still be useful. 2. Some hyperparameter settings, such as those for PTB, are missing in the paper and the supplementary materials. The effect of regularisation methods, in particular L2 and dropout, are not given. This often makes a key difference to the generalisation ability of the test set and the performance of SGD and could be at least considered in the numerical analysis session. 3. The proof of the faster convergence speed of AGD using the case studies in Sec. 3.2 may have resulted in some questions, as the comparisons of optimisers with different learning rates and other hyperparameters may not be fair enough. 4. Extra memory cost, computational cost and possible limitations of the method are not discussed.

Questions

What's the trajectory of Adam at the minimum point B in Figure 1?

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.

Confidence

4: You are confident in your assessment, but not absolutely certain. It is unlikely, but not impossible, that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work.

Soundness

3 good

Presentation

3 good

Contribution

3 good

Limitations

Discussions of regularisation methods (at least with SGD) and large-scale experiments with complex model structures (e.g. a Transformer with both encoder and decoder) are missing. The analysis of the convergence speed in the numerical analysis session may not be completely fair. Would be useful to include the analysis of computation and storage costs.

after rebuttal

Thanks for the response!

Response to the authors.

Thanks for your response and for trying to address my concerns. Here is my response: > To our knowledge, the issue exists for all optimizers. The generalization bound of Adam-like optimizers also includes , as shown in Theorem 5 of [1]. The generalization bound of SGD includes , where is the starting point and is the optimal point, as shown in Theorem 2.1.14 of [2]. Therefore, the statement the issue with the current idea lies in ... how far the solution lies compared to the initialization point in the parameter space is inappropriate. The statement is perfectly valid since the truth is that Adam and other optimizers are prefered over other optimizers only for their experimental results and not for their theoretical properties. Although Adam like optimizers might have the same issue in proving useful bounds, that fact alone does not mean that all other theoretical bounds for Adam-like optimizers should also prove bounds which are not informative. All in all though, the authors' answer is not correlated with my criticism which was: _"In my humble opinion, the issue with the current idea lies in terms of the number/width of the optimization steps and how far the solution lies compared to the initialization point in the parameter space. The information that one can obtain by gradient differentials in the optimization space is only getting less and less useful while we increase the dimensionality of the optimization space. That means that for smaller optimization problems where the optimal solution would lie close to the initialization point, then I can really see the benefit of AGD compared to less Hessian well-informed optimizers like Adam."_. In my initial review I also said: _"I would not consider it appropriate to ask the authors to prove these things but they could put more effort into making their experiments more convincing to ameliorate this huge concern."_, thus, I think the authors have misinterpreted my critisism and considered that I am attacking their proof whereas I was simply talking about the fact that their algorithm might provide boosts over vanilla Adam for smaller optimization spaces. Having said that, I acknoledge and welcome that the authors have tried to run the appropriate large scale experiments to show that my concern is not valid and empriically show that their algorithm outperforms AdamW. > In addition, we have experimentally demonstrated the effectiveness of AGD for models with a large number of parameters, as shown in the Figure 1 of the PDF provided in the Global Response. We conducted optimizer experiments on the GPT2 (124 M) and GPT2-Large (774 M) models using the OpenWebText dataset. The results indicate that AGD outperformed the AdamW optimizer in terms of convergence. We hope our results address your concern. Thanks for running this experiment. However, the validation losses reported on https://github.com/karpathy/nanoGPT when training these larger models on OpenWebText are 3.12 and 2.67 for GPT-2 and GPT-2-LARGE, respectively. In the authors' rebuttal, the reported baseline numbers are approximately 3.08 and 2.72 for GPT-2 and GPT-2-LARGE, correspondingly. That fact makes me skeptical about the validity of these experiments and how can a discrepancy like this be caused (I would expect both losses to be higher than the reported ones in https://github.com/karpathy/nanoGPT in the case of less training time or at least have a similar pattern). It could be the case that the weight decay could play a role here and Adam would also behave very similarly to AGD. > Firstly, LSTMs tend to have far more parameters than ResNets, as convolutional kernels typically have fewer parameters. This difference can be observed in Table 2 of the paper. Firstly, the above statement is absolutely incorrect, the number of parameters in convolutional and recurrent neural networks depends on the task and the context that one wants to model. It might be true that for some easy problems like image classification for 28x28 pixels, one only needs a few small convolutional kernels in order to obtain the appropriate receptive field. On the contrary, if you had an audio waveform sampled at 16kHz and you wanted to model time-dependencies over 5 second clips, one would need a much larger amount of trainable parameters for a CNN model compared to an LSTM that can implicitly carry the state for each time-step. In Table 2, the authors compare LSTM models for NLP tasks and compare them with CNNs for computer vision tasks with input-sizes of at most (224x224), thus, no generalization can be made from this Table. All in all, the authors' experiments with GPT make me skeptical and my main criticism (AGD behaves similarily to Adam except of smaller optimization spaces) remains. Thus, I cannot increase my score until I see a clear performance improvement of AGD vs Adam for a large-scale model and task.