On the Ineffectiveness of Variance Reduced Optimization for Deep Learning

1 Introduction

• SVR methods, including SVRG and SAGA [Defazio et al., 2014a], use control variates to reduce stochastic-gradient variance in finite-sum problems.Each component loss corresponds to one training data point; control variates aim to reduce variance without bias.Source: §1 · p. 1
• SVR methods achieve linear convergence for smooth strongly-convex problems, improving on SGD’s sub-linear rate; related approaches exploit finite-sum structure through primal or dual methods.The literature also extended variance reduction to general non-convex and saddle-point problems.Source: §1 · p. 1
• The paper studies variance reduction on image-classification CNNs, examining practical complications and variance behavior, and finds streaming SVRG variants do not improve over regular SVRG.The authors also quantify network properties affecting variance reduction.Source: §1 · p. 1

Standard SVR approach

• SVRG alternates training epochs with snapshot points, where it evaluates and stores the full gradient at the snapshot iterate.A snapshot is commonly taken once per epoch, though the interval can vary.Source: Standard SVR approach · p. 2
• The SVRG step augments the sampled-data SGD gradient with a control variate formed from the sampled-data snapshot gradient and the full snapshot gradient.The per-example snapshot gradient can be stored during the snapshot pass or recomputed when needed; recomputation is typically most practical.Source: Standard SVR approach · p. 2
• Conditioned on the current iterate, the expected SVRG step is an unbiased gradient step, while successive directions remain correlated through the shared snapshot-gradient term.The paper notes that this kind of step correlation is also seen in momentum methods and is considered a contributing factor to their effectiveness.Source: Standard SVR approach · p. 2

Data augmentation

• With transform locking, step variance starts at zero and rises through the epoch; without locking, it starts nonzero and remains uniformly worse.The proposed fix caches each datapoint’s snapshot transform and reuses it during the following epoch.Source: Data augmentation · pp. 2–3

Batch normalization

• Naive gradient recomputation with batch normalization can catastrophically diverge, while a BN reset temporarily saves and restores normalization statistics around the snapshot-gradient evaluation.Batch normalization also breaks the finite-sum structure because each datapoint’s loss depends on its minibatch statistics; the snapshot pass should use train mode so the two evaluations match.Source: Batch normalization · p. 3

Dropout

• Dropout masks reduce snapshot-to-epoch gradient correlation; reusing per-datapoint seeds is proposed, but dropout is absent from the reported experiments.The authors omit it because residual architectures benefit little from dropout when batch normalization is used.Source: Dropout · p. 3

Iterate averaging

• Although theory calls for averaged or random snapshots, a 10% tail average sped early CIFAR10 convergence but worsened final test error, so it was omitted.The initial speedup did not persist after the first step-size reduction.Source: Iterate averaging · p. 4

Measurement approach

• The study compared SVRG-estimate variance with SGD stochastic-gradient variance, estimating variance over a full-dataset pass and using transform locking and batch-norm reset for favorable SVRG performance.Ratios below one indicate variance reduction; the authors state that a ratio below 1/3 is needed to offset SVRG’s added computational cost.Source: §3 · p. 4

Models

• The comparison covered LeNet-5, size-matched ResNet-18, ResNet-110, and DenseNet-40-36 models.The two smaller models had approximately 62 thousand and 69 thousand parameters, respectively; ResNet-110 and DenseNet had approximately 1.7 million and 1.5 million.Source: §3 · p. 4

Results

• LeNet showed 4x-to-2x lower SVRG-step variance, while DenseNet-40-36 and ResNet-110 showed increased variance for most of each epoch before epoch 150.At only 2% of an epoch, the reported variance reduction for the latter models was a factor of 2, so more frequent snapshot passes could not help during early optimization.Source: §3 · p. 4
• The small ResNet showed some mid-epoch variance reduction early in optimization, but benefited less from SVRG than the similarly sized LeNet.The authors associate the contrast with the modern architecture’s greater ability to fit the data.Source: §3 · p. 4

4 Snapshot intervals

• Classical convex theory sets snapshot intervals proportional to the condition number, while practice commonly uses one epoch between snapshots.Source: §4 · p. 4
• At 11% into an epoch, ResNet-110 and DenseNet SVRG variance already exceeds SGD during epochs 10–150; snapshots this frequent cost an order of magnitude more wall-clock time and still underperform per epoch.Source: Figure 2 · p. 5, §4 · p. 5
• With less frequent snapshots, SVRG variance is approximately 2x SGD on the two harder problems during epochs 10–150, as the stale correction becomes effectively uncorrelated with the stochastic gradient.Source: §4 · p. 5

4.1 Variance reduction and optimization speed

• Variance reduction can speed optimization only when the variance ceiling arrives before the curvature limit; deep residual networks shift from curvature-limited early epochs to variance-limited later ones.Increasing batch size lowered variance enough to increase the learning rate proportionally for reduction factors up to 30-fold in the cited work.Source: §4.1 · pp. 5–6

5 Why variance reduction fails

• For DenseNet, SVRG gives no actual variance reduction for most of the run, and the same holds for larger ResNets; LeNet instead shows consistently lower variance during initial convergence.Source: §5 · p. 6
• DenseNet moves significantly farther from the snapshot within an epoch than LeNet, while measured curvature is very similar between the models, supporting iterate distance as the dominant factor in the variance-reduction gap.Source: §5 · p. 6
• The authors caution that their failure to improve on larger problems does not refute SVRG results on small MNIST networks, which they consider unrepresentative of harder deep-learning training.Source: §5 · p. 6

5.1 Smoothness

• Using smooth ELU yields a small improvement in variance reduction, but DenseNet still shows no significant reduction.Source: §5.1 · p. 6

6 Streaming SVRG Variants

• Streaming SVRG alternates a mega-batch snapshot-gradient computation with inner steps on sampled mini-batches; mega-batches are typically 10–32 times larger than regular mini-batches.Source: §6 · p. 7
• The implementation uses a fixed number of inner steps, although theory suggests a random number; mega-batch and inner-step data points are independent, while sampling inner batches from the mega-batch would introduce bias as in SCSG.Source: §6 · p. 7
• The experiments used mega-batches 10 times the size of 128-instance CIFAR10 mini-batches, took 10 inner steps per snapshot, and estimated variance using the full dataset at each point.Source: §6 · p. 7
• At epoch 50, both tested models show 10x lower variance on the first streaming-SVRG step, but variance quickly rises; LeNet permits much greater reduction than DenseNet, where the benefit is not compelling at three times SGD’s amortized step cost.Source: Figure 4 · p. 7, §6 · p. 7

7 Other methods for non-convex variance-reduced optimization

• SAGA-like methods have lower computational costs than SVRG but similar per-epoch convergence rates; the authors do not expect them to improve on SGD for large models and note their gradient-storage burden, while dual methods have similar storage costs and are not generally applicable to non-convex settings.Source: §7 · p. 7
• Catalyst uses a secondary variance-reduction method to solve subproblems, but does not match the best general non-convex theoretical rates and is not well-suited to nonsmooth ReLU models.Source: §7 · pp. 7–8
• SARAH shares SVRG’s high per-epoch computational cost; despite SARAH++ having the best theoretical non-convex rate among the methods considered, the tested SARAH-style methods did not converge reliably, which the authors attribute to accumulated inner-loop error.Source: §7 · p. 8

• CIFAR10 comparisons averaged 10 runs with shared momentum and learning-rate settings, while ImageNet comparisons used one run per method and had lower run-to-run variability.Source: §8 · p. 8
• Heavy correlation between consecutive SVRG steps means variance reduction does not directly translate into faster convergence.Source: §8 · p. 8
• SVRG is slightly faster than SGD on LeNet but a little slower on larger ResNet/ImageNet and DenseNet/CIFAR10 problems; SCSG performs worst in each comparison.Source: §8 · pp. 8–9

• On ResNet-50/ImageNet, starting SVRG at epoch 0, 20, 40, 60, or 80 did not improve test accuracy over the SGD-only baseline.Source: §9 · p. 9
• DenseNet-169/ImageNet fine-tuning from epochs 60 or 80 through epoch 90 also showed no improvement.Source: §9 · p. 9
• The experiments tested late SVRG use because prior results suggested SVRG might provide a benefit late in training.Source: §9 · p. 9

• The reported negative results do not rule out using stochastic variance reduction on deep-learning problems.Source: Conclusion · p. 9
• The authors identify adaptive application of variance reduction as a possible direction for future work.Source: Conclusion · p. 9
• They also suggest applying variance reduction to learning rates or scaling matrices, or combining it with Adagrad or ADAM.Source: Conclusion · p. 9