A Coefficient Makes SVRG Effective

We are encouraged that you find our work tries to fix the failure of variance reduction methods in deep learning. We address your concerns and questions below:

W1: SVRG-type methods do not suit the DL framework well not only because of the failure to effectively reduce the variance but also because of the necessity of full gradient computation from time to time. From this perspective, methods Zero-SARAH are more interesting to explore.

We agree SVRG-type methods require periodic full gradient computation. Nevertheless, it is possible to compute the full gradient by first dividing the data into mini-batches and then accumulating the gradients through the mini-batches. It does increase the computation cost. Our implementation has reduced this to 1$\times$ by storing the individual snapshot mini-batch gradient $\nabla f_i(\theta^\text{past})$ in the memory when calculating the snapshot full batch gradient $\nabla f(\theta^\text{past})$ at the beginning of each epoch.

Below we demonstrate we can reduce the additional computation cost of $\alpha$-SVRG compared with AdamW by applying $\alpha$-SVRG only in the early phase. Specifically, we only apply $\alpha$-SVRG ($\alpha_0=0.75$) during the initial 10% of the training and add transition epoch for the coefficient schedule, where the coefficient decreases from its original value to 0. Empirically, we find this transition epoch crucial for maintaining the stability of momentum in the base optimizer. The results are shown below.

Train loss

Validation accuracy

We can see that early $\alpha$-SVRG can achieve lower training losses than AdamW across all datasets. It also improves validation accuracy in most cases. In this sense, applying $\alpha$-SVRG only in the early phase not only introduces little computational cost but also can reduce training loss and improve validation accuracy. We have added this experiment in Appendix J.2 of the current draft.

As you pointed out, Zero-SARAH [1] indeed eliminates the full gradient computation. Nevertheless, it requires the storage of all gradients w.r.t each data point and this could be a very large memory cost for most deep learning problems. For example, ResNet-18 has 11M parameters and if we store its gradients w.r.t each of 50K training data points in CIFAR-10, the memory cost is about 50K $\times$ 44.7MB $\approx$ 2181GB.

In general, there is a trade-off between the memory cost and the additional computation cost for variance reduction methods. It is up to practitioners to choose the method that is most suitable for their specific task and hardware. We have added a discussion of this trade-off in our related work section (line 514) and cited relevant works including Zero-SARAH.

[1] Li et al. ZeroSARAH: Efficient nonconvex finite-sum optimization with zero full gradient computation. arXiv'21.

W2: The convergence of $\alpha$-SVRG is presented under the assumption of bounded gradients . In my opinion, this assumption is strong and doesn't allow to show the theoretical benefit of using alpha-SVRG instead of vanilla SVRG.

Our work starts from a more empirical perspective and the convergence analysis of $\alpha$-SVRG in Appendix G is present for completeness. We do believe there is room to further improve the convergence analysis of $\alpha$-SVRG. For example, maybe we can dynamically adjust the coefficient $\alpha$ based on the past optimization trajectory. This might require a new theoretical tool to better analyze $\alpha$-SVRG and it would be an interesting direction for future work to explore.

W5: The results in Figure 10 are controversial to the claims of the paper. For small batch sizes you expect alpha-SVRG to perform better since the variance should be larger. However, AdamW without any variance reduction mechanism handles the variance better than.

We wish to clarify that smaller batch sizes do lead to larger gradient variance. However, under larger gradient variance, $\alpha$-SVRG is not assumed to perform better. Note that in Figure 10, we use the same coefficient of 0.5 (line 464) when changing batch size. As batch size decreases, the correlation among mini-batch gradients decreases. Using the same coefficient 0.5 might not be the best choice and we should instead decrease the coefficient to account for the weakening correlation. If we decrease the coefficient to 0.25 or 0.125, $\alpha$-SVRG can still decrease the training loss. We show the results below.

W6: The authors use various deep learning techniques like warmup in the training and the improvement might come from a weird combination of all of those techniques with $\alpha$-SVRG update. In my view, it is important to understand if $\alpha$-SVRG procedure alone indeed helps to reduce variance.

Note that our experiments in Section 5 are strictly controlled. We use the same training recipe for both baseline, standard SVRG, and $\alpha$-SVRG (line 371). Therefore, any improvement over the baseline should come from $\alpha$-SVRG only. This is also applied to all initial experiments in Sections 2, 3, and 4. Moreover, for our experiments using SGD, we did not use any warmup but a constant learning rate.

To see whether $\alpha$-SVRG alone can reduce gradient variance, we remove various deep learning techniques that might potentially alter loss landscape (e.g., learning rate warmup, learning rate cosine decay, mixup-cutmix, label smoothing) in our training recipe one by one. The experiments are conducted on CIFAR-100 and STL-10 and the results are reported below. We can see that even without any of these techniques, $\alpha$-SVRG can still reduce training loss. This confirms that the improvement comes from $\alpha$-SVRG alone.

STL-10

CIFAR-100

Q1: Could you please elaborate how $\alpha$-SVRG update is plugged in AdamW? Do you perform $\alpha$-SVRG update on the stochastic gradient which is then used in AdamW? Or do you perform $\alpha$-SVRG trick for the updates of AdamW? In general, this would be beneficial to add a pseudocode at least in the appendix how to combine the proposed $\alpha$-SVRG update with any optimizer.

We indeed did not make it clear in the original draft. When combining $\alpha$-SVRG with AdamW, we input the variance reduced gradient $g^t_i$ (the output of $\alpha$-SVRG) into the update rule of AdamW. This practice follows other work integrating SVRG into alternative optimizer algorithms [1, 2]. We have also added the pseudo-code for $\alpha$-SVRG with AdamW in Algorithm 2 of Appendix G.

[1] Dubois-Taine et al. SVRG meets adagrad: Painless variance reduction. Machine Learning'22.
[2] Wang et al. Divergence results and convergence of a variance reduced version of adam. arXiv'22.

Q2: I don't understand the connection of $\alpha$-SVRG and preconditioning. In (38) the authors define a matrix A. Could you provide the exact form for A? I believe the $\alpha$-SVRG update cannot be presented as a linear mapping and therefore this connection seems to be misleading.

After careful review, we find it is not possible to derive $A$ in a closed form. We have removed the paragraph discussing this connection from Appendix G.

We thank you for your valuable feedback and see resolving your questions and concerns as a great improvement to our paper. If you have any further questions or concerns, we are very happy to answer.

Thank you for your quick response to our rebuttal! We address your further concerns below:

Q1: I appreciate the authors idea to use $\alpha$-SVRG in the early stages only and gradually decrease $\alpha$ to 0. However, this means that there is additional tuning: $(i)$ how long should we use $\alpha$-SVRG, how to detect that $\alpha$-SVRG stops reducing the variance? $(ii)$ How to decrease $\alpha$, is the linear decrease good enough or should we use cosine/exponential decrease/something else?

We are currently preparing an updated response for Q1, and please refer to the newer version once it is posted. Thank you and sorry for the confusion.

Q2: In several applications like training large language models (typically performed by doing only a few passes over the data) or training RL models (here we don't have access to the full gradient at all), computing the full gradient is a significant limitation of $\alpha$-SVRG. In my opinion, the authors should have proposed a more practical algorithm where the full gradient can be somehow approximated.

We agree with you that computing the full gradient is indeed not possible in some deep learning problems. Below we discuss three potential ways to address this limitation.

1. We can use the idea of mega-batch [1, 2, 3] in SVRG-type methods. They typically use 10-32 $\times$ mini-batch samples to estimate the full gradient. In this way, we can still form the variance reduced gradient $g^t_i$ by replacing the full gradient with its mega-batch approximation and then updating the model with the variance reduced gradient.

2. There is also recent work from last week (https://arxiv.org/abs/2411.10438) that adapts the variance reduction method to train Large Language Models. They eliminate the need to compute the full gradient by only using mini-batch gradient $\nabla f_i(\theta^t)$ and snapshot gradient $\nabla f_i(\theta^{\text{past},t})$ to form the variance reduction term. Moreover, similar to us, they also employ a coefficient to control the variance reduction strength.

3. We can also use the EMA of the past snapshot gradients to approximate the full gradient. Specifically, we first form the snapshot model as the EMA of the past model parameters $\theta^{\text{past},t+1} = \beta_1 \theta^{\text{past},t} + (1 - \beta_1) \theta^{t}$, and the full batch gradient can then be approximated by the EMA of the past snapshot mini-batch gradients: $m^{t+1} = \beta_2 m^t + (1 - \beta_2) \nabla f_i(\theta^{\text{past},t})$. The variance reduced gradient is still constructed as before: $g^t_i = \nabla f_i(\theta^t) - \alpha^t (f_i(\theta^{\text{past},t}) - m^t)$. We show the results using $\alpha$-SVRG with EMA ($\beta_1=0.9999$, $\beta_2=0.9$) on various datasets. We can see that $\alpha$-SVRG (EMA) can achieve competitive results, compared with standard $\alpha$-SVRG. More importantly, $\alpha$-SVRG (EMA) consistently outperforms AdamW across different datasets.

Train loss

Validation accuracy

Overall, we agree that our current setup for $\alpha$-SVRG might not be well-suited for all deep learning problems, such as training Large Language Models. Nevertheless, our work has demonstrated the potential of SVRG-type methods in training real-world neural networks. It would be of great value for future work to improve our method further and make it widely applicable in deep learning.

[1] Frostig et al. Competing with the empirical risk minimizer in a single pass. COLT'15.
[2] Lei et al. Non-convex finite-sum optimization via scsg methods. NeurIPS'17.
[3] Papini et al. Stochastic variance-reduced policy gradient. ICML'18.

Again, we thank you for your constructive comments and they are always improving our paper! If you have any further questions or concerns, we are very happy to answer.

I would like to thank the authors for such a significant effort in addressing the concerns. The provided empirical results do help to understand the performance of $\alpha$-SVRG better. I still believe this method is far from being practical for the following reasons:

• I appreciate the authors idea to use $\alpha$-SVRG in the early stages only and gradually decrease $\alpha$ to 0. However, this means that there is additional tuning: $(i)$ how long should we use $\alpha$-SVRG, how to detect that $\alpha$-SVRG stops reducing the variance? $(ii)$ How to decrease $\alpha$, is the linear decrease good enough or should we use cosine/exponential decrease/something else?
• In several applications like training large language models (typically pertaining is performed by doing only a few passes over the data) or training RL models (here we don't have access to the full gradient at all). In my opinion, computing the full gradient is a significant limitation of $\alpha$-SVRG in modern applications where both model and data sizes are huge. Therefore, the authors should have proposed a more practical algorithm where the full gradient can be somehow approximated.

Nonetheless, based o the provided set of experiments I increase my score.

Please note that we have updated our previous response for Q2 above and posted a new response for Q1 here.

Q1 (1): I appreciate the authors idea to use $\alpha$-SVRG in the early stages only and gradually decrease $\alpha$ to 0. However, this means that there is additional tuning: $(i)$ how long should we use $\alpha$-SVRG, how to detect that $\alpha$-SVRG stops reducing the variance?

We agree that how long to apply early $\alpha$-SVRG is another hyperparameter for our method. To understand this better, we vary the length of applying early $\alpha$-SVRG (using a linear schedule with $\alpha_0=0.75$ and a transition epoch) from 2.5% to 20% of the training and the results are reported below. $\alpha$-SVRG can achieve a lower training loss compared to the baseline AdamW with as little as 5% of the total training time. The reduction in training loss becomes much more pronounced as we extend the time to apply early $\alpha$-SVRG.

For your concern about how to detect that $\alpha$-SVRG stops reducing the gradient variance, we can leverage all the mini-batch gradients $\nabla f_i(\theta^t)$ and variance reduced gradients $g^t_i$ in each epoch to determine the stopping point. If the gradient variance estimated by variance reduced gradients $Var(g^t_i)$ is larger than that by mini-batch gradients $Var(\nabla f_i(\theta^t))$, we should disable $\alpha$-SVRG thereafter.

Q1 (2): How to decrease $\alpha$, is the linear decrease good enough or should we use cosine/exponential decrease/something else?

There are indeed different ways to decrease $\alpha$ to 0 for early $\alpha$-SVRG. Our previous experiments only use a single epoch to decrease $\alpha$ to 0. Below we extend the length of this transition period to multiple epochs ($\{1,2,4\}$) and compare different schedules (linear, cosine, exponential, quadratic).

CIFAR-100 (baseline: 2.659)

Flowers (baseline: 2.400)

Pets (baseline: 2.203)

STL-10 (baseline: 1.641)

The results show that early $\alpha$-SVRG can achieve a lower training loss than the baseline AdamW regardless of the schedule. Among all the schedules, the linear schedule decreases the training loss the most and the optimal length of the transition epoch is usually 1 or 2. Therefore, we recommend using the linear schedule and transition epoch length 1 in practice.

We hope our above responses can address your questions. Please let us know if you have any further questions or concerns!

Thank you for your further reply!

Regarding the intuition behind our setup, we acknowledge that gradient correlations in non-convex models may not strictly follow the linear relationships in Equation (2). Nevertheless, the original SVRG has already assumed a linear structure: using $\nabla f_i(\theta^{\text{past}}) - \nabla f(\theta^{\text{past}})$ to reduce variance in $f_i(\theta^t)$. Our proposed $\alpha$-SVRG only adds a coefficient $\alpha$ to this linear structure and aims to address other shortcomings of SVRG.

We also acknowledge that our $\alpha$-SVRG introduces one more hyperparameter $\alpha_0$. However, we view it more as a missing hyperparameter that should have been there for the original SVRG, for effective variance reduction. We also showed that setting $\alpha_0$ at different values between 0 and 1 can generally improve or at least not hurt the performance (Table 7 in Appendix B), although the best value may vary.

Regarding your comment “the authors have to use different schedulers to set the parameter $\alpha$ in the experiments”, we wish to clarify that our main results (Table 2 and Table 3) always use a linear scheduler, and the search of the initial coefficients $\alpha_0$ is only done under the linear scheduler. Our experiments (Table 4) also show that $\alpha$-SVRG with a linear schedule (our default recommendation) can already achieve lower training loss than baseline AdamW.

Thank you again for reviewing our paper and engaging in discussions. We are encouraged that our rebuttal addressed most of your concerns, and we appreciate the rating increase from 3 to 5. We hope these final clarifications can help address your remaining concerns.

We sincerely thank you for your comment. We appreciate you find that our work has a clear logic and our experiments are very comprehensive. We address your concerns and questions below:

W1: The effectiveness of $\alpha$-SVRG: In Table 2, compared with the baseline alpha-SVRG's improvement in training loss and validation accuracy is marginal.

Our results in Table 2 are on the ImageNet-1K dataset. Improving performance on this complex dataset by a large margin can be challenging. Recent model architecture papers [1]-[4] consider accuracy improvement similar to our scale on ImageNet-1k (<1.0%) to be significant enough. Therefore, the improvements we achieve using a single coefficient in our work are quite significant.

Additionally, our method demonstrates a greater advantage over AdamW on other image classification datasets, as shown in Table 3. For instance, on the Pets dataset, our approach achieves approximately an 11.0% relative reduction in training loss and a 5.0% absolute improvement in validation accuracy compared to the baseline AdamW optimizer.

[1] Tu et al. MaxViT: Multi-Axis Vision Transformer. ECCV'22.
[2] Yu et al. MetaFormer Baselines for Vision. TPAMI'22.
[3] Woo et al. ConvNeXt V2: Co-designing and Scaling ConvNets with Masked Autoencoders. CVPR'23.
[4] Liu et al. A ConvNet for the 2020s. CVPR'22.

W2: The computation and memory cost of $\alpha$-SVRG: $\alpha$-SVRG requires additional computations for the full gradient $\nabla f(\theta^\text{past})$ and the mini-batch gradient at $\theta^\text{past}$, $\nabla f_i(\theta^\text{past})$. Additionally, it necessitates maintaining $\nabla f(\theta^\text{past})$ and $\nabla f(\theta)$ in memory. The paper fails to address or discuss these significant costs.

Our original intention is to primarily compare $\boldsymbol{\alpha}$-SVRG to standard SVRG. Both of them require computing the full gradient $\nabla f(\theta^\text{past})$ and the mini-batch gradient $\nabla f_i(\theta^\text{past})$ for snapshot model. Therefore, the computation cost and memory cost of $\alpha$-SVRG is the same as standard SVRG.

We agree with you that computing the full gradient $\nabla f(\theta^\text{past})$ and the mini-batch gradient $\nabla f_i(\theta^\text{past})$ for the snapshot model is not negligible. This is indeed one fundamental problem for most variance reduction methods [1]-[7]. In particular, the way that the variance reduction works requires computing another term that is correlated with the original mini-batch gradient $\nabla f_i(\theta)$. This additional term is where the computation cost comes from. We have included a discussion of this limitation in Appendix I.

To address your concern about the memory cost, we would like to clarify that storing the full gradient $\nabla f(\theta^\text{past})$ and the mini-batch gradient $\nabla f_i(\theta^\text{past})$ for the snapshot model does not require much memory. Specifically, we need to store two gradients, each of which is the same size as the original model. For a small model like "ResNet18" with 11M parameters studied in our paper, this memory cost is about 2 $\times$ 44.7MB; for a large model like "ConvNeXt-Base" with 88.6M parameters, the memory cost is about 2 $\times$ 337.9MB. Both of them are less than 1GB, which should not be a big issue for modern GPUs.

We will further address your concern about the additional computation cost of $\alpha$-SVRG compared with AdamW in Q1.

[1] Nguyen et al. SARAH: A novel method for machine learning problems using stochastic recursive gradient. ICLR'17.
[2] Lei et al. Non-convex finite-sum optimization via scsg methods. NeurIPS'17.
[3] Fang et al. Spider: Near-optimal non-convex optimization via stochastic path-integrated differential estimator. NeurIPS'18.
[4] Wang et al. Spiderboost and momentum: Faster variance reduction algorithms. NeurIPS'19.
[5] Cutkosky et al. Momentum-Based Variance Reduction in Non-Convex SGD. NeurIPS'19.
[6] Li et al. ZeroSARAH: Efficient nonconvex finite-sum optimization with zero full gradient computation. arXiv'21.
[7] Kavis et al. Adaptive stochastic variance reduction for non-convex finite-sum minimization. NeurIPS'22.

W3: The authors are advised to include the pseudo-code for AdamW + alpha-SVRG rather than merely describing its use of AdamW as the base optimizer.

Thank you for the suggestion. We have added the pseudo-code for $\alpha$-SVRG with AdamW in Algorithm 2 of Appendix G.

W4: Typos in eqs (7)-(9).

Thank you for pointing this out. In our original draft, Equations 7 - 9 are indeed not very clear. We wish to clarify that $t$ is the global iteration index, which can be decomposed into the epoch index $s$ and the iteration index $i$ within the epoch. In other words, $\boldsymbol{s}$ is a function of $\boldsymbol{t}$. So for clarity, we should use $s(t)$ instead of $s$ in Equations 7 - 9. We have revised these equations in the current draft.

Thank you for the detailed response and for the additional experiments on early $\alpha$-SVRG. I believe the key reason why both $\alpha$-SVRG and early $\alpha$-SVRG perform well lies in the complex role of noise in modern deep learning. On the one hand, noise can hinder optimization and lead to slower convergence; on the other hand, it also induces implicit regularization, helping to find better generalizing minima. As such, there is an inherent tradeoff in controlling the noise scale, and $\alpha$-SVRG strikes an effective balance by dynamically adjusting the noise. One advantage of $\alpha$-SVRG over early $\alpha$-SVRG is that the latter introduces an additional hyperparameter — the time to switch — which adds complexity to the tuning process.

Overall, I appreciate the authors' efforts in rethinking classical algorithms like SVRG, which perform well theoretically in convex settings, and adapting them to work effectively in modern deep learning. I also suggest that the authors consider including a discussion on the implicit bias induced by gradient noise in the next version of the paper.

We sincerely thank you for your comment. We appreciate you find our method $\alpha$-SVRG effective under multiple settings. We address your concerns and questions below:

W1.1: The effect of $\alpha_0$. The following three points are a bit inconsistent as a whole: (a). From Figure 4, the optimal $\alpha_0$ seems to be almost the same for different models. (b) From Table 4 and Figure 9, it seems that $\alpha_0=0.75$ may be a better choice than $\alpha_0=0.5$ (at least for the small model that is used). (c) In the experiment that yields Table 3, however, $\alpha_0=0.5$ for small models and $\alpha_0=0.75$ for larger ones.

We clarify the inconsistency you mentioned before:

1. In Figure 4, we did not schedule the coefficient $\boldsymbol{\alpha}$ (and $\boldsymbol{\alpha}_0$). Instead, the coefficient is computed based on Equation 6 and should be the same (with a value of 1) at the beginning of each epoch. This is because at that time the snapshot model is exactly the same as the current model and they have a perfect correlation of 1 (Equation 6).
2. In contrast, in our proposed method $\alpha$-SVRG, we schedule $\alpha$ during the training. Note that $\boldsymbol{\alpha}_0$ in the schedule does not represent the coefficient at the first iteration but the average of all the coefficients during the first epoch (Equation 7 and Figure 12). Therefore, we set it to $\alpha_0=0.75$ to account for the average value for the coefficient during the first epoch.
3. For Table 3, we use $\boldsymbol{\alpha}_0=0.75$ for smaller models and $\boldsymbol{\alpha}_0=0.5$ for larger ones (see line 370). This choice of initial coefficient $\alpha_0$ is based on the observation that a deeper model generally has a lower coefficient in Figure 4.

W1.2: The schedule of $\alpha$. It may be interesting to analyze different types of scheduling of $\alpha$ based on the perspective of preconditioning in Appendix G.

We agree with you that it may be interesting to analyze different types of scheduling of $\alpha_0$ based on the perspective of preconditioning. For example, we can utilize the information (e.g., gradient norm, variance, momentum) in the past optimization trajectory to adjust $\alpha$ dynamically and possibly eliminate the need of scheduling $\alpha$ at all. Nevertheless, our work has empirically found that simple linear decay (Equation 7) is very effective. We believe it might be interesting for future works to understand how to further improve the schedule of $\alpha$.

W2: For the experiment that yields Figure 4, it would be better if the authors could conduct experiments on different datasets and try to analyze the effect of data on the optimal alpha $\alpha^*$.

Thank you for the suggestion. We have added experiments to analyze the optimal coefficient on datasets with different numbers of object classes, in particular CIFAR-10 and CIFAR-100 below. We train three models (Logistic Regression, MLP-2, and MLP-4) on each dataset and compute the optimal coefficient during the training. The results are available here. We observe that the optimal coefficient is smaller for CIFAR-100 than CIFAR-10. This is possibly because CIFAR-100 has 10x object classes than CIFAR-10, making the correlation between the snapshot model gradient $\nabla f_i(\theta^\text{past})$ and the current model gradient $\nabla f_i(\theta^t)$ lower. We have incorporated this experiment in Appendix K.1 of the current draft.

Q1: In the schedule of Eq. (9), why do we use a constant of 0.01 instead of other constants? Can this constant also be tuned?

Thank you for pointing this out. The value 0.01 determines the final coefficient $\alpha$ at the last epoch and we expect the final value should be very close to 0. If we use 0 instead, then the coefficient for the first epoch is not well defined since setting $s=0$ turns Equation 9 into $\alpha^t_\text{geometric}=\alpha_0(\frac{0}{\alpha_0})^0$.

As you point out, we can indeed tune this value. Below we search this constant over the range $\{0.1, 0.05, 0.01, 0.005, 0.001\}$ with the experiment of Table 4 training ConvNeXt-Femto on STL-10. We can see that the best constant is 0.01 for all three initial coefficients. Therefore, we use 0.01 as a default choice. To improve the presentation for Equation 9, we will replace the constant 0.01 with the symbol $\alpha_\text{final}$ in the revision.

We thank you for your valuable feedback and see resolving your questions and concerns as a great improvement to our paper. If you have any further questions or concerns, we are very happy to answer.

Dear Reviewer Nknp,

We hope this message finds you well. We kindly request your review of our rebuttal and would greatly appreciate your feedback. If you have any further questions or require additional clarification, please do not hesitate to let us know.

Thank you for your time and consideration!

Best regards,
Authors

We sincerely thank you for your comment. We appreciate you find our work very scientific and can be a very interesting and easy reference for modern SVRG. We address your concerns and questions below:

W1: As far as I understand, you are always using Adam with lr 3e-4 in your experiments. This is a quite nice lr - but it is well-known that Adam might profit from additional tuning. I do not believe your point here should be "you are better than Adam" - many papers overclaim performance as their main point, but you show much more. I think here what could be helpful is a plot of final accuracy or training loss over learning rate - comparing both with SGD and Adam. Showing this for 1 learning rate is not enough. Note that you do not have to show you are better than Adam, but just that you are better than SVRG and close most of the gap.

We wish to clarify that the base learning rate for both the baseline (SGD/AdamW) and $\boldsymbol{\alpha}$-SVRG for all experiments in Section 5 is 4e-3. This control setting ensures that any performance gain comes from $\alpha$-SVRG itself rather than any other factors (e.g., learning rate).

Here we present results of $\alpha$-SVRG at different learning rates. Specifically, we sweep the learning rate for AdamW and $\alpha$-SVRG ($\alpha_0=0.5$) over the range of $\\{\text{1e-2}, \text{5e-3}, \text{1e-3}, \text{5e-4}, \text{1e-4}\\}$ and compare their final training loss here (click the link). The results show $\alpha$-SVRG can decrease training loss better than vanilla AdamW in most cases. We have incorporated this experiment in Appendix J.1 of the current draft.

Note that in our experiments in Section 5, when comparing to the baseline (SGD / AdamW), $\alpha$-SVRG and standard SVRG use SGD / AdamW as the base optimizer. In other words, the variance reduced gradient from $\alpha$-SVRG is input into the update rule of the base optimizer (SGD / AdamW). Therefore, it is possible for $\alpha$-SVRG to perform better than AdamW since the variance reduction mechanism in $\alpha$-SVRG can help the base optimizer (AdamW) converge faster. Nevertheless, we agree with you that the comparison to SVRG should be the main focus of the paper. In the revision, we will focus on the comparison to SVRG.

W2: Figure 5 (SVRG with optimal alpha) is a bit weak: not much improvement over SGD id shown. Do you have an explanation for this? In a way this is the "best we can get" - yet in this specific example Adam, SGD and SVRG (with or without alpha) perform quite similar! the variance metrics also confirm that not much variance reduction is happening. I would personally try to find another example or compare this performance on multiple examples.

We agree with you that the gap between SVRG with optimal coefficient and SGD baseline in original Figure 5 does not seem very large. This is because the scale of the training loss is very small when it has converged close to 0. Here we provide better visualization of vanilla SGD, standard SVRG, SVRG with optimal coefficient, $\boldsymbol{\alpha}$-SVRG for Figure 5 in log scale here. We can see the gap is much larger than the original one. Qualitatively, SVRG with optimal coefficient achieves 17.7% lower final training loss (0.154) than SGD baseline (0.187). If we compare the final training loss of SVRG with optimal coefficient to standard SVRG (0.262), their gap is even larger with a 41.3% difference.

In terms of variance reduction, we would like to clarify that the variance reduction of SVRG with optimal coefficient (and $\boldsymbol{\alpha}$-SVRG) happens mostly during the early training (the first 5 epochs in Figure 5). Quantitatively (see below), in Figure 5, the gradient variance of SVRG with optimal coefficient is about 40% lower than baseline at the beginning of the training.

We show our above finding about the variance reduction of SVRG with optimal coefficient also applies to other datasets (e.g., Flowers and EuroSAT). Here are the results. You can see on these datasets, the effects of gradient variance reduction and training loss decrease from $\alpha$-SVRG are more pronounced.

We thank you for your valuable feedback and see resolving your questions and concerns as a great improvement to our paper. If you have any further questions or concerns, we are very happy to answer.

Thank you for your quick response to our rebuttal! We address your further concerns below:

Q1: There is a bit of an improvement between alpha-SVRG and SVRG (the second plot you attached, which would greatly profit from multiple seeds): this "tiny bit" is enough to be better than Adam. I think placing a comparison with SGD and SVRG in the plots you attached (first link) would be of great interest!

We have just launched the experiments to compare SGD with $\alpha$-SVRG at different learning rates. We will update the results here once it is done. If it does not come out before the discussion deadline, we will still add them into our revision.

Q2: "the base learning rate for both the baseline (SGD/AdamW) and alpha-SVRG for all experiments in Section 5 is 4e-3. This control setting ensures that any performance gain comes from alpha-SVRG" -- is very wrong. it is well known that optimal learning rate is hyperparameter-dependent: especially when comparing with Adam.

We agree with your point that learning rate is a very important hyper-parameter when comparing different optimizers. The optimal learning rate can be drastically different for $\alpha$-SVRG and SGD / AdamW. In response, we have included AdamW results in the Appendix J.1 and will incorporate the SGD results once the ongoing experiments are complete.

We again thank you for your time and feedback on the paper! Your review has been very helpful in enhancing our paper.