A Coefficient Makes SVRG Effective

## Abstract

Abstract Stochastic Variance Reduced Gradient (SVRG), introduced by Johnson & Zhang ( 2013 ) , is a theoretically compelling optimization method. However, as Defazio & Bottou ( 2019 ) highlights, its effectiveness in deep learning is yet to be proven. In this work, we demonstrate the potential of SVRG in optimizing real-world neural networks. Our analysis finds that, for deeper networks, the strength of the variance reduction term in SVRG should be smaller and decrease as training progresses. Inspired by this, we introduce a multiplicative coefficient α 𝛼 \alpha to control the strength and adjust it through a linear decay schedule. We name our method α 𝛼 \alpha -SVRG. Our results show α 𝛼 \alpha -SVRG better optimizes neural networks, consistently reducing training loss compared to both baseline and the standard SVRG across various architectures and image classification datasets. We hope our findings encourage further exploration into variance reduction techniques in deep learning. Code is available at https://github.com/davidyyd/alpha-SVRG .

## 1 Introduction

A decade ago, Johnson & Zhang () proposed a simple approach to reducing gradient variance in SGD – Stochastic Variance Reduced Gradient (SVRG). SVRG maintains a snapshot model, forming a variance reduction term with the difference between the snapshot’s stochastic gradient and its full gradient over the entire dataset. By adjusting the gradient for the current model with the variance reduction term, SVRG is able to reduce SGD’s gradient variance and accelerate SGD to be almost as fast as the full-batch gradient descent in strongly convex settings.

Over the years, a variety of SVRG variants have emerged. Some focus on further accelerating convergence in convex settings (Xiao & Zhang, ; Lin et al., ; Defazio, ), while others are tailored for non-convex scenarios (Allen-Zhu & Hazan, ; Reddi et al., ; Lei et al., ; Nguyen et al., ; Fang et al., ; Elibol et al., ). Both SVRG and its variants have shown effective in optimizing simpler machine learning models like logistic and ridge regression.

Despite the theoretical value of SVRG and its subsequent works, they have seen limited practical success in neural network training. Most SVRG research in non-convex settings is limited to modest experiments: training basic models like Multi-Layer Perceptrons (MLP) or simple CNNs on small datasets like MNIST and CIFAR-10. These studies usually exclude evaluations on more capable and deeper networks. More recently, Defazio & Bottou () have exploited several variance reduction methods, including SVRG, to deep vision models. They have founded that SVRG fails to reduce gradient variance for deep neural networks because the model parameters update so quickly on the loss surface that the snapshot model becomes outdated.

In this work, we show that adding a multiplicative coefficient to SVRG’s variance reduction term can make it effective for deep models. Our exploration is motivated by an intriguing observation: SVRG can only reduce gradient variance in the initial training stages, but actually *increase* it later. To tackle this problem, we mathematically derive the optimal coefficient for the variance reduction term to minimize the gradient variance. Our empirical analysis then leads to two key observations about this optimal coefficient: (1) as depth of the model increases, the optimal coefficient becomes smaller; (2) as training advances, the optimal coefficient decreases, consistently dropping well below the standard SVRG’s default coefficient of 1. These findings explain why a constant coefficient of 1 in standard SVRG, while initially effective, eventually fails to reduce gradient variance.

Based on these observations, we introduce a linearly decaying coefficient $\alpha$ to control the strength of the variance reduction term in SVRG. We call our method $\alpha$-SVRG and illustrate it in Figure [1](#S1.F1). $\alpha$-SVRG stably reduces gradient variance and optimizes models better. We evaluate $\alpha$-SVRG on a range of architectures and multiple image classification datasets. $\alpha$-SVRG consistently achieves a lower training loss than baseline and the standard SVRG. Our results highlight the value of SVRG in deep learning. We hope our work can offer insights about SVRG and stimulate more research in variance reduction approaches for optimization in neural networks.

Figure: Figure 1: SVRG vs. $\bm{\alpha}$-SVRG. Both SVRG (left) and $\alpha$-SVRG (right) use the difference between snapshot stochastic gradient (gray) and snapshot full gradient (blue) to form variance reduction term (orange), which modifies model stochastic gradient (black) into variance reduced gradient (red). But $\alpha$-SVRG employs an coefficient $\alpha$ to modulate the strength of the variance reduction term. With the coefficient, $\alpha$-SVRG reduces the variance of each update and results in faster convergence.
Refer to caption: /html/2311.05589/assets/x1.png

## 2 Motivation: SVRG may not always reduce variance

SVRG formulation. We first introduce the basic formulation of SVRG. We adopt the following notation: $t$ is the iteration index, ${\bm{\theta}}^{t}$ represents the current model parameters, and $\nabla f_{i}(\cdot)$ denotes the gradient of loss function $f$ for the $i$-th mini-batch(^1^11In SVRG’s original work (Johnson & Zhang, ), this corresponds to the $i$-th data point.). When the subscript $i$ is omitted, $\nabla f(\cdot)$ represents the full gradient across the entire dataset. A key concept in SVRG is the snapshot model, represented as ${\bm{\theta}}^{\text{past}}$. It is a snapshot of the model at a previous iteration before $t$, acting as an approximation of ${\bm{\theta}}^{t}$. We store its full gradient $\nabla f({\bm{\theta}}^{\text{past}})$. This snapshot is taken periodically. SVRG defines the variance reduced gradient ${\bm{g}}_{i}^{t}$, as follows:

$$ $\displaystyle{\bm{g}}_{i}^{t}=\nabla f_{i}({\bm{\theta}}^{t})-\underbrace{(\nabla f_{i}({\bm{\theta}}^{\text{past}})-\nabla f({\bm{\theta}}^{\text{past}}))}_{\text{variance reduction term}}.$ (1) $$

Intuitively, SVRG uses the difference between the mini-batch gradient and the full gradient of a past model to modify the current mini-batch gradient. This could make ${\bm{g}}^{t}$ better aligned with the full gradient and therefore stabilize each update on the current model.

Initially, SVRG was introduced in the context of vanilla SGD. Subsequent studies (Dubois-Taine et al., ; Wang & Klabjan, ) have incorporated it into alternative optimization algorithms. In this work, we focus on the variance reduction term in SVRG. Since this term only modifies the original gradient, it is applicable to various optimizers beyond vanilla SGD. Additionally, we follow the practice in Defazio & Bottou () to take the snapshot once per training epoch.

**Table 1: Gradient variance metrics. ${\bm{g}}$ is the mean of the mini-batch gradients. The index $k$ refers to the $k$-th component of gradient $g_{i,k}$. References: $*$ Liu et al. (), $\dagger$ Defazio & Bottou (), $\ddagger$ Jastrzebski et al. ().**
| name | formula | description |
| --- | --- | --- |
| metric 1^∗ | $\frac{2}{N(N-1)}\sum_{i\neq j}\frac{1}{2}\left(1-\frac{\langle{\bm{g}}_{i},{\bm{g}}_{j}\rangle}{\|{\bm{g}}_{i}\|^{2}\|{\bm{g}}_{j}\|^{2}}\right)$ | cosine distance between pair-wise gradients |
| metric 2^† | $\sum_{k=1}^{d}\mathrm{Var}(g_{i,k})$ | sum of variances for component-wise gradients |
| metric 3^‡ | $\lambda_{max}(\frac{1}{N}\sum_{i=1}^{N}({\bm{g}}_{i}-{\bm{g}})({\bm{g}}_{i}-{\bm{g}})^{T})$ | the largest eigenvalue of sample covariance matrix |

Gradient variance. Our goal is to assess SVRG’s effectiveness in reducing gradient variance. To this end, we gather $N$ mini-batch gradients, denoted as $\{{\bm{g}}_{i}|i\in\{1,\cdots,N\}\}$, by performing back-propagation on checkpoints of the model with randomly selected $N$ mini-batches. For SVRG, each of these gradients is modified based on Equation [1](#S2.E1). To present a comprehensive view, we employ three existing metrics from prior studies to quantify gradient variance in Table [1](#S2.T1).

SVRG’s effect on gradient variance. To understand how SVRG affects training, we examine two simple models: a single linear layer (Logistic Regression) and a 4-layer Multi-Layer Perceptron (MLP-4). We train them over 30 epochs on CIFAR-10 (Krizhevsky, ). We compare SVRG with SGD against the baseline using only vanilla SGD.

Figure: Figure 2: SVRG on Logistic Regression. SVRG effectively reduces the gradient variance for Logistic Regression, leading to a lower training loss than the baseline.
Refer to caption: /html/2311.05589/assets/x2.png

We plot Logistic Regression’s gradient variance (top two and bottom left) and the training loss (bottom right) in Figure [2](#S2.F2). For the Logistic Regression, SVRG consistently reduces both the gradient variance and training loss throughout the entire training process.

Figure: Figure 3: SVRG on MLP-4. In the first few epochs, SVRG substantially reduces the gradient variance for MLP-4, but afterwards, SVRG increases it, well above the baseline. As a result, SVRG exhibits a higher training loss than the baseline at the end of training.
Refer to caption: /html/2311.05589/assets/x6.png

In contrast, for MLP-4, SVRG may not always reduce gradient variance. As shown in Figure [3](#S2.F3), SVRG only manages to decrease the gradient variance in the first five epochs. However, SVRG can greatly increase gradient variance thereafter. Consequently, SVRG has a larger final training loss than the baseline, suggesting that the increase in gradient variance hinders MLP-4’s convergence.

This surprising empirical observation in a slightly deeper model leads us to question whether SVRG may alter the gradient too excessively at certain phases of training. Can we mitigate this adverse effect? We explore these questions starting from a theoretical framework in the following section.

## 3 A closer look at control variates in SVRG

Control variates (Lavenberg et al., ) is a technique initially developed in Monte Carlo methods to reduce variance. We aim to estimate the expected value of a random variable X. The variance of this estimate usually depends on $\mathrm{Var}({\textnormal{X}})$. To form a less variate estimate ${\textnormal{X}}^{*}$, we can use a control variate Y that correlates with X and a coefficient $\alpha$ to regulate the influence of Y and $\mathbb{E}[{\textnormal{Y}}]$ :

$$ $\displaystyle{\textnormal{X}}^{*}={\textnormal{X}}-\alpha({\textnormal{Y}}-\mathbb{E}[{\textnormal{Y}}]).$ (2) $$

This estimate remains unbiased for any value of $\alpha$. The coefficient that minimizes the variance of the estimate can be derived as:

$$ $\displaystyle\alpha^{*}=\frac{\mathrm{Cov}({\textnormal{X}},{\textnormal{Y}})}{\mathrm{Var}({\textnormal{Y}})}=\rho({\textnormal{X}},{\textnormal{Y}})\frac{\sigma({\textnormal{X}})}{\sigma({\textnormal{Y}})},$ (3) $$

where $\rho({\textnormal{X}},{\textnormal{Y}})$ represents the correlation coefficient between X and Y; $\sigma(\cdot)$ denotes the standard deviation. The derivation is detailed in Appendix [A](#A1).
The minimized variance becomes $\mathrm{Var}({\textnormal{X}}^{*})=(1-\rho({\textnormal{X}},{\textnormal{Y}})^{2})\mathrm{Var}({\textnormal{X}})$. The higher the correlation is, the lower the variance of the estimate is.

Note that SVRG uses control variates to reduce variance in each component of the gradient. This variance reduction occurs at each iteration $t$. Take a closer look at Equation [1](#S2.E1) and [2](#S3.E2): the model stochastic gradient $f_{i}({\bm{\theta}}^{t})$ is the random variable X; the snapshot stochastic gradient $f_{i}({\bm{\theta}}^{\text{past}})$ is the control variate Y; and the snapshot full gradient $f({\bm{\theta}}^{\text{past}})$ is the expectation $\mathbb{E}[{\textnormal{Y}}]$.

A key difference between SVRG and control variates is that SVRG omits the coefficient $\alpha$, defaulting it to 1. This is possibly because the gradient distribution does not change drastically in strongly convex settings. Yet, SVRG’s subsequent studies, even those addressing non-convex cases, have neglected the coefficient and formulated their theories based on Equation [1](#S2.E1).

Motivated by this, we introduce a time-dependent coefficient vector $\bm{\alpha}_{t}\in\mathbb{R}^{d}$ in SVRG:

$$ $\displaystyle{\bm{g}}_{i}^{t}=\nabla f_{i}({\bm{\theta}}^{t})-\bm{\alpha}_{t}\odot(\nabla f_{i}({\bm{\theta}}^{\text{past}})-\nabla f({\bm{\theta}}^{\text{past}})),$ (4) $$

where $\odot$ represents the element-wise multiplication.

Optimal coefficient.
We adopt the same gradient variance definition as Defazio & Bottou () (metric 2 above) and aim to determine the optimal $\bm{\alpha}_{t}^{*}$ that minimizes it at each iteration. Specifically, our objective is to minimize the sum of variances across each component of ${\bm{g}}^{t}$. Let $k$ index the $k$-th component $\alpha^{*}_{t,k}$ and the $k$-th component of the gradient $\nabla f_{\cdot,k}(\cdot)$. For clarity, we omit the mini-batch index $i$. This can be formally expressed as the following optimization problem:

$$ $\displaystyle\min_{\bm{\alpha}_{t}}\sum_{k=1}^{d}\mathrm{Var}(g^{t}_{\cdot,k})=\sum_{k=1}^{d}\min_{\alpha_{t,k}}\mathrm{Var}(g^{t}_{\cdot,k}).$ (5) $$

The order of minimization and summation in Equation [5](#S3.E5) can be switched because the variance of the $k$-th component of the gradient only depends on the $k$-th component of the coefficient by our formulation. Applying Equation [3](#S3.E3) yields the optimal coefficient $\alpha^{*}_{t,k}$:

$$ $\displaystyle\alpha^{*}_{t,k}=\frac{\mathrm{Cov}(\nabla f_{\cdot,k}({\bm{\theta}}^{\text{past}}),\nabla f_{\cdot,k}({\bm{\theta}}^{t}))}{\mathrm{Var}(\nabla f_{\cdot,k}({\bm{\theta}}^{\text{past}}))}=\rho(\nabla f_{\cdot,k}({\bm{\theta}}^{\text{past}}),\nabla f_{\cdot,k}({\bm{\theta}}^{t}))\frac{\sigma(\nabla f_{\cdot,k}({\bm{\theta}}^{t}))}{\sigma(\nabla f_{\cdot,k}({\bm{\theta}}^{\text{past}}))},$ (6) $$

A stronger correlation between the snapshot and model gradients leads to a larger optimal coefficient.

For small networks like MLP-4, calculating the optimal coefficient at each iteration is feasible by gathering all mini-batch gradients for both the current and snapshot models. For larger networks, however, this method becomes impractical; we will address this challenge later in the paper.

Observations on optimal coefficient.
To explore how the optimal coefficient evolves in a normal training setting, we train 1, 2, and 4-layer MLPs (Logistic Regression, MLP-2, and MLP-4) using SGD and AdamW (Loshchilov & Hutter, ) on CIFAR-10 without using SVRG. Given the small size of these models, we can analytically compute the optimal coefficient at each iteration. We plot its mean value over all indices $k$ in Figure [4](#S3.F4).
We can make two notable observations as below.

Figure: (a) SGD
Refer to caption: /html/2311.05589/assets/x10.png

*Observation 1: deeper models have smaller optimal coefficients.* For Logistic Regression, the optimal coefficient remains relatively stable, hovering near 1. For MLP-2, the coefficient deviates from 1, dropping to about 0.6. For MLP-4, it decreases more sharply, reaching approximately 0.4.

*Observation 2: the optimal coefficients of deeper models generally decrease as training goes.* This suggests that as training advances, the correlation between snapshot gradients and model gradients, as described in Equation [6](#S3.E6), decreases. This is possibly because the gradient direction varies more and becomes less predictable as the models become better trained.

These observations shed light on why the standard SVRG struggles to reduce gradient variance or training loss in later training stages (Figure [3](#S2.F3)). A default coefficient of 1 proves to be too high and the weakening correlation between snapshot and model gradients necessitates a smaller coefficient. Without a suitable coefficient, gradient variance may increase, leading to oscillations in SGD.

Optimal coefficient’s effect on gradient variance. We evaluate whether optimal coefficient makes SVRG more effective in reducing gradient variance. Specifically, we use SVRG with optimal coefficient to train a MLP-4 by computing the optimal coefficient (Equation [6](#S3.E6)) and adjust the gradient (Equation [4](#S3.E4)) at each iteration. We compare SVRG with optimal coefficient to the standard SVRG and the baseline. The results are presented in Figure [5](#S3.F5). Using the optimal coefficient enables SVRG to reduce gradient variance in the early stages of training without increasing it later. The consistent gradient variance reduction yields a lower training loss than the baseline and the standard SVRG.

Figure: Figure 5: SVRG with optimal coefficient on MLP-4. SVRG with the optimal coefficient reduces gradient variance stably and achieves a substantially lower training loss than the baseline.
Refer to caption: /html/2311.05589/assets/x12.png

## 4 α 𝛼 \alpha -SVRG

From our analysis above, it becomes clear that the best coefficient for SVRG is not necessarily 1 for multi-layer networks. However, computing the optimal coefficient at each iteration would result in a complexity similar to full batch gradient descent. This approach quickly becomes impractical for larger networks like ResNet (He et al., ). In this section, we demonstrate how using a preset schedule of $\alpha$ values can achieve a similar effect of using the computed optimal coefficients.

$\alpha$-SVRG. Given the decreasing trend (Figure [4](#S3.F4)) and the computational challenge, we propose to apply a linearly decreasing scalar coefficient for SVRG, starting from an initial value $\alpha_{0}$ and decreasing to 0. This is our main method in this paper, and we name it $\alpha$-SVRG.

$\bm{\alpha}$-SVRG vs. optimal coefficient.
To evaluate how well $\alpha$-SVRG matches SVRG with optimal coefficient, we train a MLP-4 using $\alpha$-SVRG and compare it to SVRG with optimal coefficient and the baseline. For all experiments in this section, we set $\alpha_{0}=0.5$. The results are presented in Figure [6](#S4.F6). Interestingly, $\alpha$-SVRG exhibits a gradient variance trend that is not much different from SVRG with optimal coefficient. A similar pattern is observed in training loss. $\alpha$-SVRG only has a slightly higher training loss than SVRG with optimal coefficient but still lower than the baseline.

Figure: Figure 6: $\bm{\alpha}$-SVRG on MLP-4. $\alpha$-SVRG behaves similarly to SVRG with optimal coefficient.
Refer to caption: /html/2311.05589/assets/x16.png

$\bm{\alpha}$-SVRG with AdamW. Since AdamW (Loshchilov & Hutter, ) is a widely used optimizer in modern neural network training, we assess the performance of $\alpha$-SVRG with AdamW. We replace

Figure: Figure 7: $\bm{\alpha}$-SVRG with AdamW on MLP-4. $\alpha$-SVRG lowers the gradient variance throughout the entire training process, leading to a decrease in the training loss.
Refer to caption: /html/2311.05589/assets/x20.png

the baseline optimizer SGD with AdamW to train a MLP-4 on CIFAR-10. We compare $\alpha$-SVRG with the standard SVRG and the baseline. The results are shown in Figure [7](#S4.F7). $\alpha$-SVRG exhibits a pronounced gradient variance reduction and a smaller training loss for MLP-4 than the baseline.

$\bm{\alpha}$-SVRG on deeper networks.
We further study the effectiveness of $\alpha$-SVRG with AdamW on real-world neural architectures, moving beyond simple MLPs. To this end, we train a modern ConvNet architecture, ConvNeXt-Femto (ConvNeXt-F) (Liu et al., ; Wightman, ), on CIFAR-10 using the default AdamW optimizer. We compare $\alpha$-SVRG with the standard SVRG and the baseline. We show the results in Figure [8](#S4.F8). $\alpha$-SVRG reduces gradient variance, in contrast to the standard SVRG increasing it. Furthermore, while the training loss of the standard SVRG stagnates after around 100 epochs, the training loss of $\alpha$-SVRG continues to decrease, outperforming that of the baseline. This demonstrates the potential of $\alpha$-SVRG in handling more complex models. We further delve into this exploration with additional experiments next.

Figure: Figure 8: $\bm{\alpha}$-SVRG on ConvNeXt-F. $\alpha$-SVRG effectively reduces the gradient variance for ConvNeXt-F, leading to faster convergence compared to the baseline.
Refer to caption: /html/2311.05589/assets/x24.png

## 5 Experiments

### 5.1 Settings

Datasets. We evaluate $\alpha$-SVRG using ImageNet-1K classification (Deng et al., ) as well as smaller image classification datasets: CIFAR-100 (Krizhevsky, ), Flowers (Nilsback & Zisserman, ), Pets (Parkhi et al., ), STL-10 (Coates et al., ), Food-101 (Bossard et al., ), DTD (Cimpoi et al., ), SVHN (Netzer et al., ), and EuroSAT (Helber et al., ; ).

Models.
We use recently proposed vision models on ImageNet-1K, categorized into two groups: (1) smaller models with 5-19M parameters, including ConvNeXt-F (Wightman, ; Liu et al., ), ViT-T/16 (Dosovitskiy et al., ), Swin-F (Liu et al., ), and Mixer-S/32 (Tolstikhin et al., ); (2) larger models featuring 86M and 89M parameters: ViT-B/16 and ConvNeXt-B. ConvNeXt-F is also evaluated on all smaller image classification datasets.

Training.
We report both the training loss and the validation accuracy. Our basic training setting follows ConvNeXt (Liu et al., ), which uses AdamW (our baseline optimizer). On small datasets, we choose the best $\alpha_{0}$ from {0.5, 0.75, 1}. We find the coefficient is robust and does not require extensive tuning. Therefore, for ImageNet-1K, we set $\alpha_{0}$ to 0.75 for smaller models and 0.5 for larger ones. Other training settings for $\alpha$-SVRG remain the same with the baseline. Further experimental settings can be founded in Appendix [B](#A2).

### 5.2 Results

Table [2](#S5.T2) presents the results of training various models on ImageNet-1K. The standard SVRG often increases the training loss, especially in larger models. In contrast, $\alpha$-SVRG decreases the training loss, confirming the effectiveness of the added coefficient to optimize real-world neural networks. This also supports our earlier finding that deeper models benefit from lower coefficient values.

**Table 2: Results on ImageNet-1K. The standard SVRG increases the train loss for most models, whereas $\alpha$-SVRG consistently decreases it for all models.**
|  | ConvNeXt-F | ViT-T | Swin-F | Mixer-S | ViT-B | ConvNeXt-B |  |  |  |  |  |  |
| --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- |
| train loss |  |  |  |  |  |  |  |  |  |  |  |  |
| baseline | 3.487 | - | 3.443 | - | 3.427 | - | 3.635 | - | 2.817 | - | 2.644 | - |
| +SVRG | 3.505 | $\uparrow\,$.018 | 3.431 | $\downarrow\,$.012 | 3.389 | $\downarrow\,$.038 | 3.776 | $\uparrow\,$.141 | 3.309 | $\uparrow\,$.492 | 3.113 | $\uparrow\,$.469 |
| +$\alpha$-SVRG | 3.467 | $\downarrow\,$.020 | 3.415 | $\downarrow\,$.028 | 3.392 | $\downarrow\,$.035 | 3.609 | $\downarrow\,$.026 | 2.806 | $\downarrow\,$.011 | 2.642 | $\downarrow\,$.002 |
| validation accuracy |  |  |  |  |  |  |  |  |  |  |  |  |
| baseline | 76.0 | - | 73.9 | - | 74.3 | - | 71.0 | - | 81.6 | - | 83.7 | - |
| +SVRG | 75.7 | $\downarrow\,$0.3 | 74.3 | $\uparrow\,$0.4 | 74.3 | $\uparrow\,$0.0 | 68.8 | $\downarrow\,$2.2 | 78.0 | $\downarrow\,$3.6 | 80.8 | $\downarrow\,$2.9 |
| +$\alpha$-SVRG | 76.3 | $\uparrow\,$0.3 | 74.2 | $\uparrow\,$0.3 | 74.8 | $\uparrow\,$0.5 | 70.5 | $\downarrow\,$0.5 | 81.6 | $\uparrow\,$0.0 | 83.1 | $\downarrow\,$0.6 |

**Table 3: Results on smaller classification datasets. While the standard SVRG mostly hurts the performance, $\alpha$-SVRG decreases the train loss and increases the validation accuracy.**
|  | CIFAR-100 | Pets | Flowers | STL-10 | Food-101 | DTD | SVHN | EuroSAT |  |  |  |  |  |  |  |  |
| --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- |
| train loss |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |
| baseline | 2.66 | - | 2.20 | - | 2.40 | - | 1.64 | - | 2.45 | - | 1.98 | - | 1.59 | - | 1.25 | - |
| +SVRG | 2.94 | $\uparrow\,$0.28 | 3.42 | $\uparrow\,$1.22 | 2.26 | $\downarrow\,$0.14 | 1.90 | $\uparrow\,$0.26 | 3.03 | $\uparrow\,$0.58 | 2.01 | $\uparrow\,$0.03 | 1.64 | $\uparrow\,$0.05 | 1.25 | 0.00 |
| +$\alpha$-SVRG | 2.62 | $\downarrow\,$0.04 | 1.96 | $\downarrow\,$0.24 | 2.16 | $\downarrow\,$0.24 | 1.57 | $\downarrow\,$0.07 | 2.42 | $\downarrow\,$0.03 | 1.83 | $\downarrow\,$0.15 | 1.57 | $\downarrow\,$0.02 | 1.23 | $\downarrow\,$0.02 |
| validation accuracy |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |
| baseline | 81.0 | - | 72.8 | - | 80.8 | - | 82.3 | - | 85.9 | - | 57.9 | - | 94.9 | - | 98.1 | - |
| +SVRG | 78.2 | $\downarrow\,$2.8 | 17.6 | $\downarrow\,$55.2 | 82.6 | $\uparrow\,$1.8 | 65.1 | $\downarrow\,$17.2 | 79.6 | $\downarrow\,$6.3 | 57.8 | $\downarrow\,$0.1 | 95.7 | $\uparrow\,$0.8 | 97.9 | $\downarrow\,$0.2 |
| +$\alpha$-SVRG | 81.4 | $\uparrow\,$0.4 | 77.8 | $\uparrow\,$5.0 | 83.3 | $\uparrow\,$2.5 | 84.0 | $\uparrow\,$1.7 | 85.9 | $\uparrow\,$0.0 | 61.8 | $\uparrow\,$3.9 | 95.8 | $\uparrow\,$0.9 | 98.2 | $\uparrow\,$0.1 |

Table [3](#S5.T3) displays the results of training ConvNeXt-F on smaller image classification datasets. The standard SVRG generally elevates the training loss and impairs the generalization. On the contrary, $\alpha$-SVRG lowers the training loss and improves the validation accuracy across all small datasets.

Note that a lower training loss in $\alpha$-SVRG does not always lead to better generalization on the validation set. For smaller models, a lower training loss usually directly translates to a higher validation accuracy. In larger models (Mixer-S, ViT-B, and ConvNeXt-B), additional adjustments to regularization strength may be needed for better generalization. This is out of scope for $\alpha$-SVRG as an optimization method, but warrant future research on co-adapting optimization and regularization.

### 5.3 Analysis

We analyze various components from $\alpha$-SVRG. In the following experiments, we use an initial value $\alpha_{0}=0.5$ and ConvNeXt-F on STL-10 as the default setting. Because the standard SVRG is ineffective here as discussed above, we omit it and only compare $\alpha$-SVRG with an AdamW baseline.

Coefficient value. We investigate the impact of the initial value of the coefficient $\alpha_{0}$ for $\alpha$-SVRG. We vary it between 0 and 1 and observe its effect on the training loss. The results are presented in Figure [10](#S5.F10). The favorable range for initial values in $\alpha$-SVRG is quite broad, ranging from 0.2 to 0.9. This robustness indicates $\alpha$-SVRG requires minimal tuning in the practical setting.

Figure: Figure 9: Coefficient value. $\alpha$-SVRG is effective with a wide range of coefficient values.
Refer to caption: /html/2311.05589/assets/x28.png

Batch size. Since the batch size controls the variance among mini-batch data, we change the batch size to understand how it affects $\alpha$-SVRG. We also scale the learning rate linearly (Goyal et al., ). The default batch size is 128. In Figure [10](#S5.F10), we can see that $\alpha$-SVRG leads to a lower training loss when the batch size is larger, but it is worse than the baseline when the batch size is smaller. This may stem from the weakening correlation between snapshot gradients and model gradients as the batch size decreases. Therefore, a sufficiently large batch size is essential for $\alpha$-SVRG.

Snapshot interval. The snapshot interval specifies the number of iterations between two consecutive snapshot takens. We vary it from 1 to 312 iterations to understand its effect on $\alpha$-SVRG. The default value is 39 iterations (one epoch). Figure [11](#S5.F11) illustrates $\alpha$-SVRG has a lower training loss than the baseline even with a larger snapshot interval, where snapshot is relatively distant from the current model. On the other hand, a shorter snapshot interval results in a lower training loss but requires additional training time, as a full gradient must be calculated each time a snapshot is taken.

Figure: Figure 11: Snapshot interval. Although higher snapshot intervals lead to weakening correlations between the model gradients and the snapshot gradients, $\alpha$-SVRG still lowers the training loss.
Refer to caption: /html/2311.05589/assets/x30.png

## 6 Related Work

Variance reduction in optimization. There are a range of methods aiming at reducing gradient variance by directly modifying stochastic gradient. Initial works (Johnson & Zhang, ; Shalev-Shwartz & Zhang, ; Schmidt et al., ) focus on simple convex settings. Subsequent research further enhances these methods (Defazio et al., ; ; Mairal, ; Lin et al., ; Defazio, ; Allen-Zhu, ; Lin et al., ) or handles finite sums in non-convex landscapes (Allen-Zhu & Hazan, ; Reddi et al., ; Nguyen et al., ; Lei et al., ; Fang et al., ; Li & Li, ; Wang et al., ; Elibol et al., ; Kavis et al., ). While these studies concentrate more on theoretical aspects of SVRG and do not show its effectiveness in optimizing real-world neural networks, we primarily explore the practical utility of SVRG.

Implicit variance reduction. Apart from methods that explicitly adjust the gradient, there are variance reduction techniques that implicitly reduce gradient variance through other means. A variety of optimizers (Zeiler, ; Kingma & Ba, ; Dozat, ; Lydia & Francis, ; Loshchilov & Hutter, ; Liu et al., ; ; Chen et al., ) utilize momentum to mitigate gradient variance. They achieve this by averaging past gradients exponentially, thus stabilizing subsequent updates. Lookahead optimizer (Zhang et al., ) reduces gradient variance by only updating model once every $k$ iterations. Dropout (Hinton et al., ) is also found to reduce gradient variance and better optimize models when used at early training (Liu et al., ).

## 7 Conclusion

Over the past decade, SVRG has been a method with significant impact in the theory of optimization. In this work, we explore the practical effectiveness of SVRG in real-world neural network training. Our key insight is the optimal strength for the variance reduction term in SVRG is not necessarily 1. It should be lower for deeper networks and decrease as training advances. This motivates us to introduce $\alpha$-SVRG: applying a linearly decreasing coefficient $\alpha$ to SVRG. $\alpha$-SVRG leads to a steady reduction in gradient variance and optimizes models better. Our experiments show that $\alpha$-SVRG consistently achieves a lower training loss compared to both the baseline and the standard SVRG. Our results motivate further research in variance reduction methods in neural network training.

Acknowledgement. We would like to thank Kaiming He, Aaron Defazio, Zeyuan Allen-Zhu, Kirill Vishniakov, Huijin Ou, and Jiayi Xu for valuable discussions and feedback.

## Appendix

## Appendix A Derivation of the Optimal Coefficient

We present the full derivation of the optimal coefficient for control variates:

$$ $\displaystyle\min_{\alpha}\mathrm{Var}({\textnormal{X}}^{*})=\min_{\alpha}\mathrm{Var}({\textnormal{X}}-\alpha{\textnormal{Y}})$ (7) $\displaystyle=\min_{\alpha}\mathrm{Var}({\textnormal{X}})-2\alpha\mathrm{Cov}({\textnormal{X}},{\textnormal{Y}})+\alpha^{2}\mathrm{Var}({\textnormal{Y}}).$ (8) $$

Differentiating the objective with respect to $\alpha$, we can determine the optimal coefficient $\alpha^{*}$:

$$ $\displaystyle 2\alpha\mathrm{Var}({\textnormal{Y}})-2\mathrm{Cov}({\textnormal{X}},{\textnormal{Y}})=0,$ (9) $\displaystyle\implies\alpha^{*}=\frac{\mathrm{Cov}({\textnormal{X}},{\textnormal{Y}})}{\mathrm{Var}({\textnormal{Y}})}.$ (10) $$

Lastly, we can plug the definition of correlation coefficient:

$$ $\displaystyle\rho({\textnormal{X}},{\textnormal{Y}})=\frac{\mathrm{Cov}({\textnormal{X}},{\textnormal{Y}})}{\sigma({\textnormal{X}})\sigma({\textnormal{Y}})}$ (11) $$

into the optimal coefficient and rewrite Equation [10](#A1.E10) as:

$$ $\displaystyle\alpha^{*}=\rho({\textnormal{X}},{\textnormal{Y}})\frac{\sigma({\textnormal{X}})}{\sigma({\textnormal{Y}})}.$ (12) $$

## Appendix B Experimental Settings

Training recipe.
Table [4](#A2.T4) outlines our training recipe. It is based on the setting in ConvNeXt (Liu et al., ). For all experiments, the base learning rate is set at 4e-3, except for training ConvNeXt-F on ImageNet-1K using $\alpha$-SVRG, where increasing it to 8e-3 reduces the training loss very much.

**Table 4: Our basic training recipe, adapted from ConvNeXt (Liu et al., ).**
| Training Setting | Configuration |
| --- | --- |
| weight init | trunc. normal (0.2) |
| optimizer | AdamW |
| base learning rate | 4e-3 |
| weight decay | 0.05 |
| optimizer momentum | $\beta_{1},\beta_{2}=0.9,0.999$ |
| learning rate schedule | cosine decay |
| warmup schedule | linear |
| randaugment (Cubuk et al., ) | (9, 0.5) |
| mixup (Zhang et al., ) | 0.8 |
| cutmix (Yun et al., ) | 1.0 |
| random erasing (Zhong et al., ) | 0.25 |
| label smoothing (Szegedy et al., ) | 0.1 |
| layer scale (Touvron et al., ) | 1e-6 |

Hyper-parameters.
Table [4](#A2.T4) details the batch size, warmup epochs, and training epochs for each dataset. All the hyper-parameters selections are done on the baseline. We set the batch size in proportion to the total size of each dataset. We tune the total number of training epochs

**Table 5: Hyper-parameter setting.**
|  | C-100 | Pets | Flowers | STL-10 | Food | DTD | SVHN | EuroSAT | IN1K |
| --- | --- | --- | --- | --- | --- | --- | --- | --- | --- |
| batch size | 1024 | 128 | 128 | 128 | 1024 | 128 | 1024 | 512 | 4096 |
| warmup epochs | 50 | 100 | 100 | 50 | 50 | 100 | 20 | 40 | 50 |
| training epochs | 300 | 600 | 600 | 300 | 300 | 600 | 100 | 200 | 300 |

for each dataset to achieve reasonable performance with the AdamW baseline. The warmup epochs are set to one-fifth or one-sixth of the total training epochs.

We do not use stochastic depth (Huang et al., ) on small models. For larger models, we adhere to the original work (Dosovitskiy et al., ; Liu et al., ), using a stochastic depth rate of 0.4 for ViT-B and 0.5 for ConvNeXt-B. In these models, we maintain a consistent stochastic pattern between the current model and the snapshot at each iteration (Defazio & Bottou, ).

## Appendix C Detailed Results

Table [6](#A3.T6) shows the performance of ConvNeXt-F trained with $\alpha$-SVRG using different initial coefficients $\alpha_{0}$ on multiple small datasets. $\alpha$-SVRG reduces the training loss of ConvNeXt-F and enhances the validation accuracy on most datasets, regardless of the choice of initial coefficient $\alpha_{0}$. This demonstrates the robustness of $\alpha$-SVRG to the initial coefficient.

**(a) train loss**
|  | CIFAR-100 | Pets | Flowers | STL-10 |  |  |  |  |
| --- | --- | --- | --- | --- | --- | --- | --- | --- |
| baseline | 2.659 | - | 2.203 | - | 2.400 | - | 1.641 | - |
| +SVRG | 2.937 | $\uparrow\,$0.278 | 3.424 | $\uparrow\,$1.221 | 2.256 | $\downarrow\,$0.144 | 1.899 | $\uparrow\,$0.258 |
| +$\alpha$-SVRG $(\alpha_{0}=0.5)$ | 2.622 | $\downarrow\,$0.037 | 1.960 | $\downarrow\,$0.243 | 2.265 | $\downarrow\,$0.135 | 1.583 | $\downarrow\,$0.058 |
| +$\alpha$-SVRG $(\alpha_{0}=0.75)$ | 2.646 | $\downarrow\,$0.013 | 2.004 | $\downarrow\,$0.199 | 2.162 | $\downarrow\,$0.238 | 1.568 | $\downarrow\,$0.073 |
| +$\alpha$-SVRG $(\alpha_{0}=1)$ | 2.712 | $\uparrow\,$0.053 | 1.994 | $\downarrow\,$0.209 | 2.259 | $\downarrow\,$0.141 | 1.573 | $\downarrow\,$0.068 |

## Peer Reviews

confidence: 5
contribution: 3
initial_rating: 6
presentation: 4
questions: See above
soundness: 4
strengths: I like the paper, it is a simple idea yet presented very clearly:

1) The graphics and plots help the reader get the idea behind the paper. The many presented variance metrics also are very helpful in convincing the reader of the approach.

2) The authors go step by step, showing improved performance with "optimal variance reduction" and later showing why a simple coefficient can close most of the gap. This is very important, makes the investigation very scientific.

3) There are many experiments presented in the corresponding section.
summary: This paper revisit SVRG in deep learning, showing how reasoning more carefully about control variates. The paper starts by a nice recap of what is believed to be variance reduction and SVRG performance in deep learning, and then guides the reader to the "additional parameter" solution. The authors complement their finding (i.e. a simple modification of SVRG can help training) experimentally on a diverse range of datasets in vision, using many architecture.
weaknesses: I think this could be a very interesting easy reference for modern SVRG. I believe though some additional points can help delivering the idea in a more solid way:

1) 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 rare - 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.

2) 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 withouth 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.

If the authors can show some improvements around these points, I am happy to raise my score!

-------

Authors addressed part of my concerns, and will likely improve experiments further, increased to accept.

---

confidence: 4
contribution: 2
initial_rating: 6
presentation: 3
questions: In the schedule of Eq. (9), why do we use a constant of $10^{-2}$ instead of other constants? Can this constant also be tuned?
soundness: 3
strengths: 1. The flow of the paper is easy to follow.
2. There is adequate discussion about the experiment results.
3. The perspective of the gradient preconditioning is interesting.
summary: This paper observes the ineffectiveness of SVRG due to the decay of the relevance between the batch gradient and the snapshot. The paper then proposes $\alpha$-SVRG, with $\alpha$ as a conditioning multiplicator to account for the decaying relevance. The approach is shown to be effective in multiple experiments.
weaknesses: 1. The design of the scheduling of $\alpha$ may require more discussions and refinements. Specifically,
- 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\approx0.75$ may be a better choice that $\alpha_0=0.5$ (at least for the small model that is used). (c) In the experiment that yields Table 3, however, $\alpha-0.5$ for small models and $\alpha_0=0.75$ for larger ones.
- 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.
2. 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$.

---

confidence: 4
contribution: 2
initial_rating: 5
presentation: 4
questions: In Figure 5, the gradient variance of $\alpha$-SVRG is not lower than SGD in the late phase in terms of any metric. Does the improvement of $\alpha$-SVRG in training loss, if any, come from the reduced variance in the early phase? If this is the case, would it be more effective to employ $\alpha$-SVRG only during the initial phase and switch to standard AdamW or SGD for the later stages?

To further elaborate my question, the role of gradient noise in helping generalization is widely discussed in the literature (e.g., [1]-[5]). In the late phase of training, we even need to encourage more helpful, benign noise that drives the model parameter to better generalizing minima. From this perspective, why not altogether remove the correction term in SVRG in the late phase?

[1] Samuel Smith, Erich Elsen, and Soham De. On the generalization benefit of noise in stochastic gradient descent. ICML'2020.

[2] Alex Damian, Tengyu Ma, and Jason D. Lee. Label noise SGD provably prefers flat global minimizers. NeurIPS'2021.

[3] Zhiyuan Li, Tianhao Wang, and Sanjeev Arora. What happens after SGD reaches zero loss?–a mathematical framework. ICLR'2021.

[4] Guy Blanc, Neha Gupta, Gregory Valiant, and Paul Valiant. Implicit regularization for deep neural networks driven by an ornstein-uhlenbeck like process. COLT'2020.

[5] Xinran Gu, Kaifeng Lyu, Longbo Huang, Sanjeev Arora. Why (and When) does Local SGD Generalize Better than SGD? ICLR'2023.
soundness: 3
strengths: 1. This paper is well-written with clear logic. It first identifies the problem with the original SVRG by monitoring the gradient variance during training. Then, it addresses the identified issue by introducing an extra coefficient that adjusts the scale of the SVRG correction.

2. The evaluation is comprehensive. The authors not only conducted extensive experiments across various datasets and model architectures but also explored other possible schedules for the introduced hyperparameter $\alpha$. However, I still have some concerns about the effectiveness and extra cost of $\alpha$-SVRG (see weaknesses).
summary: This paper proposed the $\alpha$-SVGR algorithm, which introduces a linearly decaying coefficient to adjust the scale of the correction term in SVRG. The proposed algorithm is inspired by the observation that the original SVRG does not effectively reduce the variance in the late training phase. To show the effectiveness of $\alpha$-SVRG, the authors conducted extensive experiments across various datasets and model architectures.
weaknesses: **Major**
1. The effectiveness of $\alpha$-SVRG: In Table 2, compared with the baseline $\alpha$-SVRG's improvement in training loss and validation accuracy is marginal. 

2. 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 $\theta^{\text{past}}$ and $\nabla f(\theta^{\text{past}})$ in memory. The paper fails to address or discuss these significant costs.


In summary, while the paper offers a good starting point for investigating why SVRG underperforms in deep learning, the enhancements to the original SVRG model, represented by $\alpha$-SVRG, do not sufficiently justify the substantial additional costs and provide only limited benefits compared to standard SGD or AdamW.


**Minor**:
1. 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.

2. Typos in eqs (7)-(9).

---

confidence: 4
contribution: 2
initial_rating: 5
presentation: 3
questions: - 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.

- 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 SVRG update cannot be presented as a linear mapping and therefore this connection seems to be misleading.
soundness: 3
strengths: - The paper is well-written and easy to follow. 

- There is a clear intuition as to why there should be a scaler smaller than 1 in the update of SVRG from the example in (2). The authors support this change by computing theoretical values of the scaler $\alpha$ for logistic regression and MLPs. It turns out that the values of  $\alpha$ drop to the end of the training for MLP and stay stable around $1$ for logistic regression. This empirical evaluation separates convex logistic regression (where SVRG is known to perform well) and non-convex MLP (where SVRG doesn't perform well).

- The proposed $\alpha$-SVRG method was tested on several DL workloads demonstrating its potential improvement over other baselines like SGD, SGD+SVRG, and AdamW.

- The authors provide potentially useful $\alpha$-schedulers that gradually decrease the values of $\alpha$. This is explained by the fact that vanilla SVRG can reduce the variance at the beginning of the training (where the stochastic gradients are more aligned) and fails in the end.
summary: The paper studies a modification of the variance-reduced method SVRG. The authors attempted to fix the issue of the applicability of variance-reduced methods in deep learning which was noticed by Defazio & Bottou, 2019. The modification consists of adding a scaler to the variance term in the update of SVRG. The authors explain this change by considering an example of the reconstruction of one random variable X from another variable Y correlated to X. The authors provide the convergence guarantees for the proposed modification of SVRG and demonstrate its effectiveness for several DL benchmarks.
weaknesses: - 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. 

- The convergence of $\alpha$-SVRG is presented under the assumption of bounded gradients $\|\nabla f_i(x)\|\le \sigma$. In my opinion, this assumption is strong and doesn't allow to show the theoretical benefit of using $\alpha$-SVRG instead of vanilla SVRG. 

- The authors claim that $\alpha$-SVRG decreases the variance. I don't understand why this is the case. For example, based on Figure 5 $\alpha$-SVRG can reduce the variance only in the beginning (where vanilla SVRG can do that as well) but afterward, the variance of $\alpha$-SVRG is similar to SGD which doesn't have any variance reduction mechanism inside. Moreover, the fluctuations of empirical variance of $\alpha$-SVRG are higher than that of SGD. Therefore, I believe it would make sense to average the variance across several random seeds to see the statistical error (it might happen that in the beginning $\alpha$-SVRG was a bit lucky). This would be also beneficial for the train loss dynamics to understand how significant the improvement. For example, for some workloads, the improvement in Table 3 is in the second digit after the dot which most likely is within the standard deviation which I believe cannot be used as significant (the results in table 8 seem to support my comment).

- The comment above also relates to the claims of the form "...can reduce gradient variance significantly..." (see line 353 and other lines like this). First, since the results of one run are presented it is not possible to measure the significance (it might be that the differences in training dynamics of the algorithm and its $\alpha$-SVRG version are within standard deviation). Second, how is "significance" measured for the proposed 3 variance metrics? Can the change 0.1 be considered large? What is the threshold for being "significant"?

- 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.

- 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.

To summarize, in my view, the authors didn't provide enough empirical evidence to showcase the usefulness of $\alpha$-SVRG even though the idea of adding a scaler is intuitively logical.  The improvement is typically marginal (within standard deviation) and comes with a significant increase in memory usage and full gradient computation.

Meta-review: The paper introduces α-SVRG, a variant of SVRG that integrates a coefficient to dynamically control the strength of variance reduction, decaying it over time. The reviewers appreciated the novelty of this approach and its demonstrated empirical effectiveness on various deep-learning tasks. The rebuttal and clarifications satisfied the reviewers. The consensus after discussion is that the empirical contributions and practical improvements are significant and novel enough to warrant acceptance.

Decision: Accept (Poster)