Variance Reduction for Stochastic Gradient Optimization

Chong Wang, Xi Chen, Alexander J. Smola, Eric P. XingNeurIPS 2013 · OpenReview

Stochastic Gradient Descent (SGD) is the workhorse of modern machine learning, especially for massive datasets. Instead of calculating a gradient over the entire dataset—which is computationally expensive—SGD estimates the gradient using a small "mini-batch."

However, these estimates are inherently "noisy." If the variance of this noise is high, the optimization algorithm spends a lot of time bouncing around instead of heading straight for the optimum. While increasing the mini-batch size reduces noise, it also increases the computational cost per step, defeating the purpose of using stochastic methods. This paper introduces a general framework to speed up Stochastic Gradient (SG) optimization by reducing this gradient variance, allowing for faster convergence and the use of larger learning rates without sacrificing stability.

The Control Variate Framework

The authors propose a general remedy using a classical statistical technique called control variates. The core idea is to augment the noisy gradient $g_d(w)$ with a second term $h_d(w)$ that is highly correlated with it. The new, "improved" gradient is formulated as:

$$\tilde{g}_d(w) = g_d(w) - A^T(h_d(w) - \mathbb{E}[h_d(w)])$$

For this approach to be effective, two conditions must be met:

  1. High Correlation: The proxy $h_d(w)$ must closely track the noise in the original gradient.
  2. Easy Expectation: The average value $\mathbb{E}[h_d(w)]$ must be inexpensive to compute, often pre-computed or derived from simple data moments.
Visualizing how data statistics correct the noisy gradient direction.

The intuition is simple: you don't need to know the true gradient to reduce noise. You just need a proxy that moves in the same direction as the noise. Low-order moments (like mean and variance) act as a rough sketch of the data distribution. Because these don't change during training, they provide a stable "anchor" to correct the fluctuating stochastic gradients.

The paper demonstrates how to construct these control variates for two distinct problems:

  • Logistic Regression (Convex): Using a first-order Taylor expansion of the sigmoid function. The resulting control variate's expectation depends only on the mean and variance of the input features, which can be calculated once prior to training.
  • Latent Dirichlet Allocation (Non-convex): In the context of Stochastic Variational Inference (SVI), the authors approximate iterative local updates with a fixed-step version, forming a control variate based on second-order moments of word frequencies in the corpus.

Key Results

The authors evaluated their approach on several well-known benchmarks, including the covtype dataset for Logistic Regression and massive text corpora (Nature, New York Times, Wikipedia) for LDA.

High variance usually forces practitioners to use tiny learning rates to prevent the model from diverging. By significantly reducing variance, this method allows for much larger learning rates (e.g., $\rho_t = 1.0$), leading to a much faster "take-off" during training.

Performance comparison showing faster convergence and higher test accuracy for the variance-reduced method.
  • Faster Convergence: In Logistic Regression, the variance-reduced version reached the optimum much faster than standard SGD. With a learning rate of 1.0, the variance-reduced method converged rapidly, whereas standard SGD was too unstable to perform well at that same rate.
  • Higher Accuracy: For LDA, the proposed method consistently achieved better held-out log-likelihood (a measure of generalization) across all three massive datasets compared to standard SVI.
  • High Correlation: Empirical tests showed the Pearson correlation between the control variates and the noisy gradients was consistently high (above 0.96), proving the Taylor-expansion-based proxies effectively captured the noise.

Limitations and Future Directions

While the framework is general, a primary limitation is that the specific control variate ($h_d$) must be manually derived for each new type of model. Additionally, there is a slight computational overhead per iteration to calculate the control variate, though this is generally outweighed by the massive gains in convergence speed.

Future work may explore integrating this variance reduction technique with second-order methods (like Newton's method). Because variance reduction provides a "cleaner" look at the local geometry of the loss function, it could make complex optimization techniques much more viable in a stochastic setting.

Summary updated

Abstract

Stochastic gradient optimization is a class of widely used algorithms for training machine learning models. To optimize an objective, it uses the noisy gradient computed from the random data samples instead of the true gradient computed from the entire dataset. However, when the variance of the noisy gradient is large, the algorithm might spend much time bouncing around, leading to slower convergence and worse performance. In this paper, we develop a general approach of using control variate for variance reduction in stochastic gradient. Data statistics such as low-order moments (pre-computed or estimated online) is used to form the control variate. We demonstrate how to construct the control variate for two practical problems using stochastic gradient optimization. One is convex---the MAP estimation for logistic regression, and the other is non-convex---stochastic variational inference for latent Dirichlet allocation. On both problems, our approach shows faster convergence and better performance than the classical approach.
BibTeX
@inproceedings{wang2013variance,
  author = {Chong Wang and Xi Chen and Alexander J. Smola and Eric P. Xing},
  title = {{Variance Reduction for Stochastic Gradient Optimization}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2013},
  url = {https://openreview.net/forum?id=HJEAcOZ_Wr},
}
Figure