Gradient descent with generalized Newton’s method

We thank the reviewer for the comments! We address them below and welcome more feedbacks. We would appreciate it if the reviewer could raise the score if satisfied.

No GitHub repository: At this day, there is no open-source implementation provided.

We will open-source the code as soon as this work is accepted!

Plots: Several plots (such as Figures 1 and 8) could be improved. For example, in Figure 8, placing the legend below the figures would enhance clarity, especially since they share the same optimizer legend.

We will place the legend as suggested in the next version.

Computational overhead: While the paper claims minimal overhead, the two extra forward passes in the training loop may introduce non-trivial complexities in practical implementations, especially on large distributed systems. A more detailed discussion or experiments about this could strengthen the paper. For example, replace the number of iterations by the training time.

We kindly refer to Figure 5 for the training time plots and the theoretical discussion in Sec 4.1. We have derived and observed that for $\Phi\geq 4$, the overhead is indeed minimal even for large models. We expect the same for distributed systems as we briefly discussed in Sec 4.2. In all our experiments, the overhead is less than 10% in practice.

Tuning hyperparameter: It is unclear how authors chose hyperparameters for AdamW, SGD, etc… A grid search experiment or reference to the literature could strengthen the paper. Providing more details on the tuning process would enhance the reproducibility of the results.

We did not tune the hyperparameters for AdamW except for the learning rate. We use 0.9 momentum for SGD, which is an arguably common choice. We declare the choice of hyperparameters in Appendix B.2/B.3, e.g. "All transformers (RoBERTa, GPT2) are trained with AdamW using default hyperparameters in Pytorch." We also specified whether the model is pretrained or not, batch size, context length, training epochs, and evaluation performances throughout Appendix B. Please kindly let us know whether this is sufficient.

Figure 2: The concept of $g^{optim}$ in the illustration is unclear. It would be helpful to clarify which optimizer (SGD?) is used in this figure. Can you add a brief explanation of in the figure caption or main text, specifying which optimizer it refers to ?

Here $g^{optim}$ is the pre-conditioned gradient that was specified in Appendix B.2.1 in the original submission. In this figure, ResNet is using SGD and GPT is using AdamW. We have modified the caption to ease the reading.

Figure 4: ...Surprisingly (for me), ResNet-152 has a worse train accuracy than ResNet18 for GeN-SGD but not for GeN-AdamW. It would be better to run the same experiments with basic SGD and AdamW for comparison. The test loss for ResNet-152 appears quite unstable at the beginning of the training process.

We agree ResNet-152 has worse train performance, but this can be explained by overfitting: while ResNet18 clearly overfits (reaching 0.1 training loss around 500 iterations; but the test loss is above 0.6), ResNet152 does not overfit as much (reaching 0.3 training loss at the end and 0.4 test loss). For now, we may refer to Figure 8 for GeN-AdamW v.s. basic AdamW comparison.

Figure 8: The number of iterations is unclear—10,000 iterations correspond to 5 epochs? From my experience, practitioners use 200 epochs to achieve over 95% test accuracy for Adam (or AdamW) with ResNet on CIFAR10. Did you use pre-trained models? In addition, was a learning rate of 1e-4 used for AdamW on ResNet-CIFAR10? If so, I recommend a grid search for the learning rate, as the literature (e.g., Prodigy or D-Adaptation) often uses 1e-3. It is also unclear whether Figure 8 shows training from scratch or fine-tuning. Finally, including results for ImageNet trained from scratch would be interesting.

Yes, 10000 iterations correspond to 5 epochs. You are right that hundreds of epochs are needed for training from scratch. We have declared our settings in Appendix B during the original submission. Here is a summary: we are using pre-trained models (ResNet and ViT) from torchvision and timm libraries. We use SGD for ResNet and only AdamW for ViT. We did a grid search for the learning rate that optimizes the performance of constant learning rate, and then fixes it to other schemes. As for Prodigy and D-Adapation, the default initial learning rate is 1e-6 according to Line 50, which is the setting we used. Unfortunately we don't have the compute to pretrain ImageNet from scratch, but we intend to do this in future work!

Thank you for your response and for taking the time to address my concerns.

While 15 epochs are limited, and 200 epochs would provide a more thorough comparison with other optimizers, I understand the time constraints. Could you plot the training log on a logarithmic scale to better highlight the differences?

Thank you for the detailed response.

While my concerns have been partly addressed, I still believe that GeN should be compared with networks trained from scratch rather than fine-tuned. This would simplify comparisons with other optimizers whose performance is well-documented in the literature.

Dear reviewer,

We hope you are satisfied with our point-to-point response. Please kindly let us know whether we can improve in the last day of rebuttal. It would be greatly appreciated if you could consider raising the score.

Our settings/hyperparameters have been declared in Appendix B, Figure 8's legend has been adjusted and $g^{optim}$ in Figure 2's caption has been highlighted. We particular enjoy the discussion of overfitting in Figure 4 (that ResNet152 has higher training loss than ResNet18 but this is not to worry about because the test loss is better) and the complexity analysis (that with $B=cF$ for $2\leq c\leq 5$, GeN is reasonably fast at a relative speed 60 to 75% of basic AdamW, this speed could improve to close to 100% with lazy frequency). We will add other experiments in the camera-ready.

I appreciate the authors’ clarifications, especially regarding the empirical results, and I have decided to increase my score.

Several claims made in the paper, e.g., "To our best knowledge, GeN is the first automatic optimizer that is applicable to the general optimizers" are overly strong even without the related work that I have introduced here --- adaptive learning rate methods are a well-studied area.

We have changed to a more appropriate statement "Overall, GeN is an automatic optimizer that is applicable to the general optimizers and works successfully in deep learning without adding much computations...". We kindly bring up the second half of the sentence "To our best knowledge, GeN is the first automatic optimizer that is applicable to the general optimizers and works successfully in deep learning without adding much computations." Most methods are either not automatic/adaptive (like heuristic schedulers), or not generally applicable (like LDA, QLAB, DoG, as I quote from QLAB "... while QLABGrad required approximately 1.4 times more time. Notably, LQA showed the most significant increase in training duration, taking about 1.6 times longer than SGD."), or requires much extra computation (like Hessian-vector product).

I found it highly confusing to refer to this method as "Generalized Newton's Method" when there is no second-order computation. The proposed method applies a local quadratic approximation to choose a learning rate adaptively. It can be combined with a second-order preconditioner, but as it stands this technique is not related to Newton's method.

We refer to Proposition 3.2 where the connection is built: from equation (3.2), we can transform SGD to GeN-SGD and Adam to GeN-Adam, but we prove that GeN-Newton is equivalent to the original Newton's method. Here we use the term "generalized" to mean two things (1) the GeN optimizers can be derived by applying the generalized inverse as in (3.3); (2) Newton's method is a special case of GeN optimizers, so we generalize Newton's update $H^{-1}G$ by allowing the update direction to be any $g^{optim}$.

The derivation of the optimal learning rate should be laid out more clearly (as it is in the original works). For example, you could write down how the quadratic equations are combined to compute the coefficients. And then the form of the optimal learning rate in terms of these coefficients, before the final derivation shown in Eq. 3.3.

This is great reminder! We add Appendix A.5 to demonstrate how to fit the quadratic equations and how to use the coefficients to derive optimal learning rate.

We thank the reviewer for all the constructive feedback and the well-grounded questions. We will address your comments one by one. We would sincerely appreciate it if the reviewer could provide more feedback or questions!

The major weakness of this paper is that the proposed method is not novel. This technique has been used before within the optimization literature and has even been applied to deep-learning optimization problems.

We would like to set the stage by clarifying that our GeN in equation (3.2) is a method, and Algorithm 1 is an algorithm that approximately implements this method. We agree that there are some similarities between our method/algorithm and [1,2,3,4], but we believe the difference is significant enough to claim some novelty.

1. At the algorithm level, LDA [1] is indeed similar to our Algorithm 1 but it is only a sub-case (only works on SGD, as I quote from the paper “This results in a new variant of the SGD method.”). In their Figure 1-4, the red curves in each figure are exactly the same, i.e. LDA-SGD is compared to SGD, SGD-M, Adam, but there is no LDA-Adam. This limitation is also reflected in their Algorithm 1 where g is the gradient, not a pre-conditioned gradient like our $g^{optim}$.

2. At the method level, LDA [1] didn't shed light on the methodology that connects to Newton's method. The method was not explicitly written out and no theorem was provided. In contrast, we introduce GeN as an extension of Newton's method through the generalized inverse (see equation (3.3)): $\text{GeN}: w_{t+1}=w_{t}-(g_\text{optim}^{\top} H)^{-1} g_\text{optim}^{\top} G$ The connection is made rigorous in Proposition 3.2 that Newton's method is a sub-case, and the convergence is analyzed in Appendix E.

3. Similar differences go to QLAB [3], the method only works for SGD (their equation 7 indicates $V=\nabla L$, not the pre-conditioned gradient), and the algorithm is very different from ours: QLAB requires 1 extra forward pass and the gradient norms, whereas our GeN requires 2 extra forward passes but not gradient norms.

4. [4] also only works for SGD (see their $\eta$ in Sec 2.3, where the numerator is $g_t^\top g_t$ instead of our $G_t^\top g_t^{optim}$). This method uses the Hessian-vector product, similar to AdaHessian and Sophia as we have discussed in the second paragraph of Sec 3.2. We note that Hessian-vector product is not only slow, but also not supported yet in distributed learning systems. For completeness, we add Algorithm 2 in Appendix C to implement GeN with Hessian-vector product.

We will surely add these papers to related work with a detailed comparison. However, given that the methods are limited to SGD without direct connection to the pre-conditioning (which reflects the importance of Hessian information that GeN leverages), we hope the reviewer would agree that GeN is novel in the methodology (connecting to Newton's method and working on general optimizers), the theoretical analysis (e.g. the error analysis and convergence), and the algorithmic design (see Remark 3.4, especially the efficiency trick with lazy frequency.)

We thank the reviewer for liking our paper and all the feedbacks! We will address the notation issue (say using <u,v> to denote inner product instead of u^T v) in the camera-ready. We fixed the typos in line 208 and line 842.

Below are our point-to-point response.

My concern regarding the algorithm itself is that I do not see a step to actually verify that the learning rate chosen in combination with the diretion ends up with a descent direction. This would be a simple thing to fix, but would require some (small) extra computation.

When you find the step size by minimizing the quadratic, do you ensure that the step is actually a good one? Given the highly nonconvex and nonsmooth nature deep learning loss surfaces I would be concerned that you could get unlucky and the minimizing step size would actually significantly increase the loss (i.e. the interpolating points happen to have low loss values but any point on a convex combination between them has a high loss).

We agree and assure the reviewer that we do verify the learning rate chosen in practice. Our approach is to fit the quadratic function in equation (2.3), then look at the coefficients. The coefficient for the quadratic term is supposed to be gHg and positive, and the coefficient for the linear term is supposed to be Gg and also positive. If this is the case, we have a convex function (where a minimum is well-defined) and a positive learning rate, only then we update the algorithm. This in practice has ensured a decrease in loss, which we will make clear in Algorithm 1. In addition, our smoothing has helped stabilize the training in case we got unlucky.

Given that the solution to the quadratic should be optimal, what is the motivation for instead taking an exponential moving average of learning rates? While it is mentioned that it helps in C.3, is the instability prohibitive if you just use ? If so is there a reason why?

The main purpose of using smoothing is to stabilize the training, as $\eta^*$ is an approximation of the minimizing learning rate, because our quadratic function is fitted on a mini-batch that contains noise (see Proposition 3.5). As our proposition implies, for large batch size (say B>1000), it is empirically safe to use $\eta^*$ without the smoothing; since we don't want to limit ourselves, we would recommend using the smoothing for general batch size.

Could the authors be more clear on the connections between minimizing a quadratic defined by 3 points and the finite differencing schemes discussed in appendix A.1 and A.3?

$\eta^*$ can be approximated by minimizing a quadratic or computing finite difference, however, using different sets of learning rates (e.g. $\{-\eta,0,\eta\}$ or $\{0,\eta,2\eta\}$) can give different precision of approximation. Our recommendation in (3.3) can be equivalently understood from minimization or finite difference. The main reason we mentioned finite difference is related to the zero-th order optimization (like MeZO) which uses finite difference.

Is there any way to measure the estimation of error that the proof in A.4 addresses? Central limit theorem arguments can be very loose at times especially in situations without a large batch size (perhaps this is why some experiments required a larger than usual batch). Is it possible to show the error on models that are small enough to actually compute ?

We have some measures like Figure 3, by trial-and-error. We agree the central limit theorem can be loose without large batch size. One alternative is to use 5 points instead of 3 to estimate $\eta^*$, and measure how well the quadratic is fitted. We leave this as future work since this approach adds some overhead.

Could the authors clarify how many points they sample to form the quadratic? In Algorithm 1, three points are used, in appendix C.2 5 is reccomended, and in Figure 2 there appear to be 11 and 10 for the ResNet and GPT2 respectivly. Given this is one of the more important and expensive hyperparaemters, I would be interested to know the sensitivity and if results would differ significantly for fewer/more points.

We used 3 points in all experiments. We tested 5 points and the training is slightly more stable, but the final accuracy is indistinguishable. In Figure 2, the goal is to observe whether the actual $L(w-\eta g)$ follows a quadratic function or not, so we must use more than 3 points; otherwise, any 3 points will uniquely define a quadratic and the fitting is 100% accurate but not informative. Please let me know if this is not clear.

When comparing to other algorithms, such as in Figure 8, are the hyperparemters for those algorithms/schedules tuned or taken from other works using these configurations?

We tuned the learning rate for constant learning rate schedule and then applied it to cosine/linear decay schedules. We use the default learning rate for Prodigy/D-adaptation. We use the default momentum, weight decay, etc. for AdamW in Pytorch.

We thank the reviewer for the comments! We address them below and welcome more feedbacks. We would appreciate it if the reviewer could raise the score if satisfied.

Why are the vision models on image classification tasks only trained for 5 or 10 epochs? It is common to use much longer training schedules for CIFAR10/100/iNat/ etc.

We kindly remind the reviewer that these are fine-tuning tasks so it is common to use 5 to 10 epochs, as the models have empirically reached their capacity. Please kindly let us know if some references are desired to support our claims.

The loss in Figure for the RN18 trained with GeN-SGD exhibits a step-wise learning rate decay, which is strange since the proposed method cannot produce step-wise decay due to the strong EMA smoothing of the learning-rate in Alg.1. Please fix this or clarify.

We didn't see a step-wise learning rate decay with ResNet18 in Figure 14. Are you referring to the epoch-wise loss decay in Figure 4 or 5? This pattern is normal and commonly observed in deep learning, even if the learning rate is smoothly scheduled, because the model overfits the first batch of the next epoch. Some references could be found by googling "loss drop every epoch", see also here and here.

The segmentation/detection experiments are not clear. Are you training on Penn-Fudan or COCO? What are you evaluating on? Are there pretrained components to your model or the neck/head? What are the 5 losses you're using?

We kindly refer to Sec 6.3, which states our experiment details that are exactly following the official pytorch tutorial (https://pytorch.org/tutorials/intermediate/torchvision_tutorial.html). In short, we train on Penn-Fudan with a model that has been pretrained on COCO. We evaluate on Penn-Fudan. The losses are classifier loss, bounding box regression loss in object detection, mask loss, objectness loss, Region Proposal Network (RPN) bounding box regression loss, as given in the tutorial.

Related work is relegated to a small discussion in the appendix and is lacking much many obvious references, including stochastic newton and other stochastic second-order or sketching methods. The comparison with D-Adaptation is also lacking in the main text and the experiments (except Figure 8, but here all models are only trained for 5 or 10 epochs as well).

We are happy to include more references (especially the ones mentioned by the reviewer) and extend the discussion in Appendix D.3. We haven't compared with D-Adaptation in all experiments, because we also need to compare with heuristic learning rates, to different base optimizers, and to PEFT methods. We are happy to add the experiments if the reviewer would like to pick some interesting ones.

Dear reviewer,

We hope you are satisfied with our point-to-point response. Please kindly let us know whether we can improve in the last day of rebuttal. It would be greatly appreciated if you could consider raising the score.

Our settings/hyperparameters have been declared, e.g. whether a model is pretrained in Appendix B and which losses are used in segmentation in Sec 6.3 (highlighted in yellow). We add Appendix D.3 for more discussion of second-order method. We are happy to address if you have any remaining concerns!

Dear reviewer, may we check with you whether our responses are sufficient? We would sincerely appreciate it if you can support this work by raising the score, given that the rebuttal period ends today and your feedback is well-received.

We sincerely thank the AC for handling our paper and the reviewers for the constructive feedback! For the final version, we will polish our current theoretical analysis of convergence, make clear comparison with prior work, and release the code so follow-up can extend the scale and generalizability of tasks and optimizers. Thank you for appreciating the merit and insight of our work!